Constraint optimization (Lagrange multiplier)

We introduce the Lagrange energy function as:

$$ \mathcal L(\vec w, \vec \lambda) = E(\vec w) - \sum_{i=1}^v { \lambda_i g_i( \vec w) } $$

with $\vec \lambda = [ \lambda_0, \lambda_1, \lambda_2, \cdots, \lambda_v ] $ and $ g_i $ a constraint at each vertex to preserve skin weight normalization. Finding the minimum $ \vec w_{min} $ of $ E $ under the constraints $ g_i $ is equivalent to solve the system:

$$ \nabla \mathcal L(\vec w, \vec \lambda) = 0 \iff \left \{ \begin{array}{lll} \nabla E(\vec w) - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} & = & 0\\ g_1(\vec w) & = & 0 \\ \vdots & & \\ g_v(\vec w) & = & 0\\ \end{array} \right . $$

A single constraint is defined as:
$$ \begin{array}{lll} g_i( \vec w_i) & = & 0 \\ 1 - \sum_{j=1}^{|\vec w_i|} w_{ij} & = & 0 \\ \left [ \begin{matrix} 1 & \dots & 1 \end{matrix} \right ] \vec w_i & = & 1 \\ \mathbf g_i^T \vec w_i & = & 1 \\ \end{array} $$

We can represent the system of constraints for every vertices:
$$ \begin{bmatrix} 1 & \cdots & 1 & 0 & 0 & 0 & \cdots & 0 \\ 0 & \cdots & 0 & 1 & 1 & 0 & \cdots & 0 \\ 0 & \cdots & 0 & 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & 0 & \ddots & 0 \\ 0 & \cdots & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} . \begin{bmatrix} \vec w_0 \\ \vec w_1 \\ \vec w_2 \\ \vdots \\ \vec w_v \\ \end{bmatrix} = \vec 1 \\ \mathbf C \vec w = \vec m $$

As for the system $ \nabla E(\vec w) - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} = 0 $ we already know $ \nabla E(\vec w) = (\mathbf A \vec w - \vec b) $ so lets focus on $ g(\vec w) = - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} $ of our system:
$$ \begin{array}{lll} \nabla g_i (\vec w) & = & 1 - \sum_{j=1}^{|\vec w_i|} w_{ij} \\ & = & \nabla[1] - \nabla \left [ \sum_{j=1}^{|\vec w_i|} w_{ij} \right ] \\ & = & 0 - \begin{bmatrix} 0 & \dots & 0 & 1_{i0} & \dots & 1_{ij} & \dots & 1_{i|\vec w_i|} & 0 & \dots & 0 \end{bmatrix}^T \\ & = & - \vec 1_i \text{ vector of ones for the entries } |\vec w_i| \text{ of vertex i and zero otherwise} \end{array} $$

$$ \begin{array}{lll} \nabla g(\vec w) & = & - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} \\ & = & - \sum_{i=1}^v {\lambda_i . (- \vec 1_i)} \\ & = & \sum_{i=1}^v { \vec \lambda_i }\\ & = & \begin{bmatrix} \vec 1_0 & \vec 1_1 & \dots & \vec 1_i & \dots & \vec 1_{v} \end{bmatrix} \vec \lambda\\ & = & \begin{array}{c|cccccc|} \nabla \mathbf G & 0 & 1 & \dots & i & \dots & v \\ \hline w_{00} & 1 & 0 & \dots & 0 & \dots & 0 \\ w_{10} & 0 & 1 & 0 & 0 & 0 & 0 \\ w_{11} & 0 & 1 & 0 & 0 & 0 & 0 \\ & 0 & 0 & \ddots & 0 & 0 & 0 \\ w_{i0} & 0 & 0 & 0 & 1 & 0 & 0 \\ w_{ij} & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ w_{in_i}& 0 & 0 & 0 & 1 & 0 & 0 \\ & 0 & 0 & 0 & 0 & \ddots & 0 \\ w_{vn_v} & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \phantom{.} . \begin{bmatrix} \lambda_0 \\ \lambda_1 \\ \vdots \\ \lambda_i \\ \vdots \\ \lambda_v \\ \end{bmatrix} \\ & = & \nabla \mathbf G \vec \lambda\\ \end{array} $$

Which translates to:

$$ \begin{array}{lll} \nabla E(\vec w) - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} & = & 0\\ (\mathbf A \vec w - \vec b) + \nabla \mathbf G \vec \lambda & = & 0\\ \mathbf A \vec w + \nabla \mathbf G \vec \lambda & = & \vec b \\ \end{array} $$

Let's seek the matrix representation $ \mathbf M \mathbf x = \mathbf m$ of $ \nabla \mathcal L(\vec w, \vec \lambda) = 0 $:

• $ \vec m \in \mathbb R^v \text{ and } \vec m = \vec 1 $
• $ \mathbf M : (|\vec w| + |\vec \lambda|) \times (|\vec w| + |\vec \lambda|) $
• $ \mathbf A : |\vec w| \times |\vec w| $
• $ \mathbf C : |\vec w| \times |\vec w| $
• $ \nabla \mathbf G \in \mathbb R^{ v \times |\vec w| } $

$$ \begin{bmatrix} \mathbf A & \nabla \mathbf G \\ \mathbf C & 0 \\ \end{bmatrix} \begin{bmatrix} \vec w_0 \\ \vdots \\ \vec w_i \\ \vdots \\ \vec w_j \\ \vdots \\ \vec w_v \\ \lambda_0 \\ \vdots \\ \lambda_i \\ \vdots \\ \lambda_v \\ \end{bmatrix} = \begin{bmatrix} \vec b_0 \\ \vdots \\ \vec b_i \\ \vdots \\ \vec b_j \\ \vdots \\ \vec b_v \\ m_0 \\ \vdots \\ m_i \\ \vdots \\ m_v \\ \end{bmatrix} $$