3
$\begingroup$

Given a typical optimization problem for a scalar function of a vector $x$ with a set of equality constraints $$ \min_x f(x)\\ \text{s.t.}\quad g(x)=\mathbf{0} $$ To solve the above, one would define a Lagrangian function with a vector of multipliers for each of the constraints as follows $$ \mathcal{L}(x,\lambda) = f(x)+g(x)^T\lambda $$ Using subscripts to denote differentiation, the solution $(x^*,\lambda^*)$ is found when $$ \mathcal{L}_x(x^*,\lambda^*)=0 $$ When solving using numerical method, one would use the Hessian to solve the following systems of equations to calculate a step $$ \left(\begin{matrix}\mathcal{L}_{xx} & g_x^T \\ g_x & 0\end{matrix}\right) \left(\begin{matrix}s_x \\ s_\lambda \end{matrix}\right) = \left(\begin{matrix}-\mathcal{L}_x \\ -g \end{matrix}\right) $$ such that the system will proceed to a new point $(x+s_x,\lambda+s_\lambda)$. In my experience with solving this linear system, setting the initial $\lambda$ to be large is usually enough to make it the solver run smoothly.

Now, since the solution requires $\mathcal{L}_x=0$, in order to accelerate the process I am tempted to try solve the following problem $$ \min_\lambda \frac{1}{2}|\mathcal{L}_x|^2 $$ for which the minimizing $\lambda$ is found at $$ \lambda = -(g_xg_x^T)^{-1}g_xf_x $$ So this $\lambda$ would be calculated first, and after that, $\mathcal{L}_{x}$ and $\mathcal{L}_{xx}$. But when I tried this trick, the solver failed miserably. Why is that so?

$\endgroup$
4
  • $\begingroup$ If there are fewer constraints than variables, then $g: \mathbb{R}^K \rightarrow \mathbb{R}^J$ with $J<K$, in which case the matrix $g_x g_x^T$ has dimension $K\times K$ and is singular (there is also a minus sign missing in your last equation). $\endgroup$ – Bertrand Jan 31 at 20:31
  • 1
    $\begingroup$ @Bertrand Thank you for pointing out the missing sign. As for $g_x g_x^T$, the transpose notation is quite confusing even to myself, but $\lambda\in\mathbb{R}^J$ and $g_x^T\in\mathbb{R}^{K\times J}$ thus $g_x g_x^T\in\mathbb{R}^{J\times J}$. $\endgroup$ – syockit Feb 1 at 3:00
  • $\begingroup$ I don't understand why one would expect this to work; could you explain the reasoning behind this approach a bit more? $\endgroup$ – Nick Alger Feb 1 at 3:48
  • $\begingroup$ @NickAlger The idea is that by starting with the smallest $\mathcal{L}_x$ possible at the beginning of each step I had hoped that the points move closer to the solution. I noticed that for an initial position where $g\neq 0$ but $f_x=0$ (minimal point of unconstrained problem), then $\lambda$ becomes 0. This may give a hint that this trick is not working. $\endgroup$ – syockit Feb 1 at 9:51
1
$\begingroup$

If there are fewer constraints than variables, then $g: \mathbb{R}^K \rightarrow \mathbb{R}^J$ with $J<K$. If the constraints are not redundant then $rk(g_x(x))=J$.

The optimal values satisfy the first order conditions $$ f_x(x)+g_x(x)^T\lambda=0,$$ a system of $K$ equations with $K+J$ unknown $(x,\lambda)$.

After inserting your expression for $\lambda$ into the first order conditions, you obtain the reduced system of $K$ equations and $K$ unknown: \begin{equation} \tag{1} (I_K-g_x^T(g_xg_x^T)^{-1}g_x)f_x(x)=0. \end{equation}

This system has an infinite number of solutions. Indeed, the matrix $P:=g_x^T(g_xg_x^T)^{-1}g_x$ is an orthogonal projector onto $col(g^T_x)$, and $rk(P)=J<K$. The matrix $I_K-g_x^T(g_xg_x^T)^{-1}g_x$ is an orthogonal projector onto $col^\perp (g^T_x)$ and the rank of this matrix is $K-J$.
If you consider only the system (1), your solution is undetermined, but if you exploit the information comprised in the $J$ constraints $g(x)=0$ and include them to the system (1) of $K-J$ independent equations, this would be helpful to reduce the indeterminatness of the solution, and to find possibly a finite number of solutions.

$\endgroup$
1
  • $\begingroup$ Sorry for being late in replying. Your answer points the usage of reduced system approach. In a typical reduced system approach though, one would decompose $s_x$ into two components, on of them being the null space of $g_x$ and another one perpendicular to the null space. That indeed yields a $K-J$ system. I'm more interested in a way to accelerate the original $K+J$ system. $\endgroup$ – syockit Feb 5 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.