Recover Lagrange multiplier values for known values in quadratic energy minimization

Alec Jacobson

March 05, 2012

weblog/

Often I'm minimizing energies of the form:

E = ½ x^T y^T Q x + x^Ty^T b
              y

where Q is a quadratic coefficient matrix, b is a vector of linear coefficients, x are unknown, and y are known. Now normally if I just want to minimize this energy I treat the known values (y) as constants and take the derivative with respect to the unknowns (x) and set it to zero. Then I just move all the terms involving y to the right hand side. However if I'd like to know how setting these known values affected the energy minimization then its useful to treat the known values not as constant but as constraints. So I have the same energy as above, where now both x and y are variables, but subject to the constraints that

y = y*

where y* are the known values of y. I can enforce these via Lagrange multipliers. Then once I've found my solution the values of the Lagrange multipliers corresponding to each y will tell me the effect of that y's constraint on the energy minimization. The problem now becomes finding the saddle point (equilibrium) of the following Lagrangian:

Λ = ½ x^T y^T Q x + x^Ty^T b + λ^T y - λ^T y*
              y

Or equivalently by repeating the λ^Ty terms:

Λ = ½ x^T y^T λ^T Q_xx Q_xy 0 x + x^Ty^T λ^T b_x
              Q_yx Q_yy I y           b_y
              0   I   0 λ          -y*

Now, let's start to take derivatives with respect to each of the sets of variables. We begin with λ. Setting ∂Λ/∂λ^T = 0 gives us:

∂Λ    0 I 0 x + -y*
--- =       y       = 0
∂λ^T         λ

which reduces simply to revealing our known values:

y = y*

Now look at setting ∂Λ/∂x^T = 0 which gives us:

∂Λ    Q_xx Q_xy 0 x + b_x
--- =           y       = 0
∂x^T             λ

which after substituting our result y=y* reduces to the system of equations we are used to seeing when minimizing quadratic energies with fixed values:

Q_xx x = -b_x - Q_xy y*

So we can invert Q_xx and solve for x:

x* = Q_xx^-1 ( -b_x - Q_xy y* )

Now x and y are known, all that's left is to solve for λ by taking the last set of derivatives. So we set ∂Λ/∂y^T = 0 which gives us:

∂Λ    Q_yx Q_yy I x + b_y
--- =           y       = 0
∂y^T             λ

Plugging in our known values and moving them to the right-hand side reveals the values of λ:

λ* = - Q_yx x* - Q_yy y* - b_y

The great thing about all of this is that you don't have to do anything extra. If you're already set up to immediately solve for x treating y as constant you've got everything you need to determine the values of λ without every actually implementing the equivalent Lagrangian.