本文共 3777 字，大约阅读时间需要 12 分钟。

There are a many different ways to minimize a quadratic energy with constant constraints. I wrote out the exact steps for three such ways:

1. Separate the energy into knowns and unknowns, then solve for the
   unknowns by setting gradient with respect to those unknowns to zero.
2. Add additional term to energy that punishes not satisfying the known
   values of your constant constraints in the least squares sense, the
   solve for all variables by setting gradient with respect to all
   variables to zero.
3. Add additional variables called lagrange multipliers to energy so
   that the problem is no longer to find a minimum but a stationary
   point in the new energy. Such a stationary point guarantees that our
   constraints are met. Find the stationary point by the usual method
   of setting the gradient to zero, this time the gradient is with
   respect to all original variables and these new variables.

The pretty print type-up with MATLAB pseudocode.

A plain text, unicode version:

Quadratic energy

$E = Z^T * Q * Z + Z^T * L + C$

We want to fix some of the values of Z, we can rearrange the Z’s that are still

free and the ones we want to fix so that$Z = \begin{bmatrix}X\\Y\end{bmatrix}$, where X are the free values and Y are the fixed values;

Split energy into knowns and unknowns

$Z = \begin{bmatrix}X\\Y\end{bmatrix}$ or Z(unknown) = X and Z(known) = Y

$$\begin{align}E =& [X^T \ Y^T] * Q * \begin{bmatrix}X\\Y\end{bmatrix} + [X^T \ Y^T] * L + C\\=& [X^T \ 0] * Q * \begin{bmatrix}X\\Y\end{bmatrix} + [0 \ Y^T] * Q * \begin{bmatrix}X\\Y\end{bmatrix}+ [X^T \ 0] * L + [0 \ Y^T] * L + C\\=&[X^T \ 0] * Q * \begin{bmatrix}X\\0\end{bmatrix}+ [X^T \ 0] * Q * \begin{bmatrix}0\\Y\end{bmatrix} + [0 \ Y^T] * Q * \begin{bmatrix}X\\0\end{bmatrix} + [0 \ Y^T] * Q * \begin{bmatrix}0\\Y\end{bmatrix} + [X^T \ 0] * L + [0 \ Y^T] * L + C\end{align}$$

$$\begin{align}E =& [X^T \ 0] * \begin{bmatrix}Q(unknown, unknown)&0\\0&0\end{bmatrix} * \begin{bmatrix}X\\0\end{bmatrix}+ [X^T \ 0] * \begin{bmatrix}0&Q(unknown, known)\\0&0\end{bmatrix} * \begin{bmatrix}0\\Y\end{bmatrix} + [0 \ Y^T] * \begin{bmatrix}0&0\\Q(known, unknown)&0\end{bmatrix} * \begin{bmatrix}X\\0\end{bmatrix} + [0 \ Y^T] * \begin{bmatrix}0&0\\0&Q(known, known)\end{bmatrix} * \begin{bmatrix}0\\Y\end{bmatrix} + [X^T \ 0] * L + [0 \ Y^T] * L + C\end{align}$$

$$\begin{align}E =& X^T * Q(unknown, unknown) * X+ X^T * Q(unknown, known) * Y + Y^T * Q(known, unknown) * X + Y^T * Q(known, known) * Y + X^T * L(unknown) + Y^T * L(known) + C\\=& X^T * Q(unknown, unknown) * X+ X^T * Q(unknown, known) * Y + (Y^T * Q(known, unknown) * X)^T + Y^T * Q(known, known) * Y + X^T * L(unknown) + Y^T * L(known) + C\dots \text{the transpose of a scaler is the scaler itself}\\=&X^T * Q(unknown, unknown) * X+ X^T * Q(unknown, known) * Y + X^T * Q(known, unknown)^T * Y + Y^T * Q(known, known) * Y + X^T * L(unknown) + Y^T * L(known) + C\end{align}$$

$E = X^T * NQ * X + X^T * NL + NC$

where $NQ = Q(unknown,unknown)$ $NL = Q(unknown,known) * Y + Q(known,unknown)^T * Y + L(unknown)$ $NC = Y^T * Q(known,known) * Y + Y^T * L(known) + C$

$\frac{\partial E}{\partial X} = 2*NQ*X + NL$

Solve for X with:

$X=(-2*NQ)^{-1}*NL$

Enforce fixed values via soft contraints with high weights

$E = Z^T * Q * Z + Z^T * L + C$

Add new energy term punishing being far from fixed variables $NE = Z^T * Q * Z + Z^T * L + C + w * (Z(known) - Y)^T * I * (Z(known) - Y)$ where w is a large number, e.g. 10000 $NE = Z^T * Q * Z + Z^T * L + C + w * (Z^T -[0 \ Y^T])* \begin{bmatrix}0&0\\0&I(known,known)\end{bmatrix} * (Z - \begin{bmatrix}0\\Y\end{bmatrix})$ where W is a diagonal matrix with $W_{ii} = 0$ if $i∈unknown$ and $W_{ii} = w$ if $i∈known$ $NE = Z^T * Q * Z + Z^T * L + C + (Z^T - [0 \ Y^T]) * W * (Z - \begin{bmatrix}0\\Y\end{bmatrix})$ $NE = Z^T * Q * Z + Z^T * L + C + Z^T * W * Z - 2 * Z^T * W * \begin{bmatrix}0\\Y\end{bmatrix} + [0 \ Y^T] * W * \begin{bmatrix}0\\Y\end{bmatrix}$ $NE = Z^T * NQ * Z + Z^T * NL + NC$ $NQ = Q + W$ $NL = L - 2W * \begin{bmatrix}0\\Y\end{bmatrix}$ $NC = C + [0 \ Y^T] * W * \begin{bmatrix}0\\Y\end{bmatrix}$

Differentiate with respect to $Z$

$\frac{∂E}{∂Z} = 2 * NQ * Z + NL$

Solve for Z with:

$Z = -0.5 * {NQ}^{-1} * NL$ or re-expanded $Z = -0.5 * {(Q + W)}^{-1} * (L - 2 * W * \begin{bmatrix}0\\Y\end{bmatrix})$

Discard known parts of Z to find X

$X = Z(unknown)$ But be careful to look at Z(known) - Y to be sure your fixed values are being met, if not then w is too low. If the X values look like garbage then perhaps you’re getting numerical error because w is too high.

Lagrange multipliers

We want to minimize

$E = Z^T * Q * Z + Z^T * L + C$ subject to the constant constraints: $Z(known) = Y$ Find stationary point of new energy: $NE = E + ∑λ_i *(Z_i - Y_i)$,i∈known $NE = E + [Z^T \ λ^T] * QC * \begin{bmatrix}Z\\λ\end{bmatrix} - [Z^T \ λ^T] * \begin{bmatrix}0\\2Y\end{bmatrix}$ (notice the 2 because $\lambda Z$ shows up twice in the quadratic part) where $QC = \begin{bmatrix}0&0&0\\0&0&I(known,known)\\0&I(known,known)&0\end{bmatrix}$ $NE = [Z^T \ λ^T] * NQ * \begin{bmatrix}Z\\λ\end{bmatrix}+ [Z^T \ λ^T] * NL + C$ $NQ = \begin{bmatrix}Q&0\\0&0\end{bmatrix}+ QC = \begin{bmatrix} Q&\begin{matrix}0\\\frac{1}{2}I(known,known)\end{matrix}\\\begin{matrix}0&\frac{1}{2}I(known,known)\end{matrix}&0\end{bmatrix}$ $NL = \begin{bmatrix}L\\0\end{bmatrix} + \begin{bmatrix}0\\Y\end{bmatrix}$ Differentiate with respect to all variables, including lagrange multipliers $\frac{∂E}{∂\begin{bmatrix}Z\\λ\end{bmatrix}} = 2 * NQ * \begin{bmatrix}Z\\λ\end{bmatrix} + NL$ Solve with $\begin{bmatrix}Z\\λ\end{bmatrix} = -0.5 * {NQ}^{-1} * NL$

Discard fixed values and langrange multipliers.

X = Z(known) The value of λi is the “force” of the constraint or how hard we had to pull the energery minimum to meet the constraints. See

转载地址：http://zpxdi.baihongyu.com/