# Skin weight optimization (lagrange) (4)

## 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}$$