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, 2021 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, 2021 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, 2021 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, 2021 at 9:51

1 Answer 1

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, 2021 at 13:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .