Solving an Energy Minimization Problem, as Outlined in a PaperThe paper fairly succinctly boils the problem down to the following equation: 1 2 x T ( M + h 2 L ) x − h 2 x T J d + x T bWhere:- the system consists of m nodes and s springs- h is the timestep(constant)- x is a column vector of length 3m (or 3m∗1 matrix) representing the node positions,- ( M + h 2 L ) is a matrix of size 3m∗3m (which, in this case, is symmetric, positive semi-definite, and does not change after being initialized.),- J is a matrix of size 3m∗3s, and- d is a column vector of size 3s representing the spring directions. (this particular equation is equation 14 in section 4 of the paper)- b is a column vector of length 3m, which represents the xyz components of the external forces acting on each nodeI am at a stage where I can generate all of vectors and matrices in code based on some arbitrary mesh consisting of nodes and links, but I am having trouble figuring out how I would go about solving for d and x. I have an initial guess for x (as outlined towards the ends of both section 3 and 4), but I don't have much experience solving entire systems like this.My main question has two parts:is there some generic procedure one would use to go about solving such a system?if not, could some resources on the topic be suggested? Even some search terms more specific than "energy minimisation" would be of great use!Ultimately I just don't know where to start, and the paper seems to simply say "starting with an initial guess for x, first we compute the optimal d", but I don't know what "compute the optimal d" entails.Similarly, I wouldn't know where to start with computing the optimal values for x. I assume this would involve differentiating w.r.t. x and finding the values when the derivative equals zero but again, I have no idea how to apply this to entire matrices of values, as opposed to single values.I am aware that each term in the above equation should evaluate to a scalar value, but I don't know how I would be able to obtain a value for each row/cell in the column vectors x and d.NOTE: I believe there are one or two minor errors in the paper, such as d ∈ R 2 s which, I believe, should be d ∈ R 3 s , since we are dealing with springs in 3 dimensions.

Question

Solving an Energy Minimization Problem, as Outlined in a PaperThe paper fairly succinctly boils the problem down to the following equation:      1    2        x    T    (  M  +      h    2    L  )  x  −      h    2        x    T    J  d  +      x    T    bWhere:- the system consists of m nodes and s springs- h is the timestep(constant)- x is a column vector of length 3m (or 3m∗1 matrix) representing the node positions,-   (  M  +      h    2    L  ) is a matrix of size 3m∗3m (which, in this case, is symmetric, positive semi-definite, and does not change after being initialized.),- J is a matrix of size 3m∗3s, and- d is a column vector of size 3s representing the spring directions. (this particular equation is equation 14 in section 4 of the paper)- b is a column vector of length 3m, which represents the xyz components of the external forces acting on each nodeI am at a stage where I can generate all of vectors and matrices in code based on some arbitrary mesh consisting of nodes and links, but I am having trouble figuring out how I would go about solving for d and x. I have an initial guess for x (as outlined towards the ends of both section 3 and 4), but I don&#039;t have much experience solving entire systems like this.My main question has two parts:is there some generic procedure one would use to go about solving such a system?if not, could some resources on the topic be suggested? Even some search terms more specific than &quot;energy minimisation&quot; would be of great use!Ultimately I just don&#039;t know where to start, and the paper seems to simply say &quot;starting with an initial guess for x, first we compute the optimal d&quot;, but I don&#039;t know what &quot;compute the optimal d&quot; entails.Similarly, I wouldn&#039;t know where to start with computing the optimal values for x. I assume this would involve differentiating w.r.t. x and finding the values when the derivative equals zero but again, I have no idea how to apply this to entire matrices of values, as opposed to single values.I am aware that each term in the above equation should evaluate to a scalar value, but I don&#039;t know how I would be able to obtain a value for each row/cell in the column vectors x and d.NOTE: I believe there are one or two minor errors in the paper, such as   d  ∈      R          2      s       which, I believe, should be   d  ∈      R          3      s      , since we are dealing with springs in 3 dimensions.

Maeve Saunders · Accepted Answer

According to your comment above you&#039;re looking for the following:                    arg        ⁡                  min                      x                                    {                      1            2                                              x                                      T                                            (            M            +                                          h                                            2                                      L            )                    x          −                                    h                                      2                                                          x                                      T                                J          d          +                                    x                                      T                                b          }                    Rewriting the above yields:                    arg        ⁡                  min                      x                                    {                      1            2                                              x                                      T                                            (            M            +                                          h                                            2                                      L            )                    x          −                                                    (                                                      h                                                        2                                                  J                d                +                b                )                                                    T                                x          }                    Now, according to your description   M  +            h              2        L is PSD Matrix hence the above is a simple quadratic form of a convex problem:                    arg        ⁡                  min                      x                                    {                      1            2                                              x                                      T                                            (            M            +                                          h                                            2                                      L            )                    x          −                                                    (                                                      h                                                        2                                                  J                d                +                b                )                                                    T                                x          }                                    =        arg        ⁡                  min                      x                                    {                      1            2                                              x                                      T                                A          x          −                                    c                                      T                                x          }                                                  =                              A                                −            1                          c                                          =                                            (              M              +                                                h                                                  2                                            L              )                                            −            1                                    (                                    h                                      2                                J          d          +          b          )

Open question

Answer & Explanation

New Questions in Linear algebra