4
$\begingroup$

I was reading Boyd & Vandenberghe's "Convex Optimization" (Ch10), where the following equality constrained convex program is considered (p526):

\begin{equation} \begin{array}{rl} \textrm{minimize} & f(x)\\ \textrm{subject to} & Ax=b, \end{array} \end{equation}

and Newton's method is employed to solve the optimality conditions, $$Ax=b, \qquad \nabla f(x)+A^Tw=0.$$

More specifically, given a feasible point $x$ (which satisfies $Ax=b$), we find the next feasible point, $x+\Delta x_{nt}$, by solving

$$\left[\begin{array}{cc}\nabla^2 f(x) & A^T\\A & 0\end{array}\right] \left[\begin{array}{c}\Delta x_{nt} \\ w\end{array}\right] = \left[\begin{array}{c}-\nabla f(x) \\ 0\end{array}\right].$$

This is straightforward, if the so-called KKT matrix,$\left[\begin{array}{cc}\nabla^2 f(x) & A^T\\A & 0\end{array}\right]$, is nonsingular (invertible). And it is stated in the book that the Newton step, $\Delta x_{nt}$, is defined only at points for which the KKT matrix is non-singular.

So what do we do when the KKT matrix happen to be singular during the iterations? Conceivably, if the above system of equations is consistent, we can just pick one solution as $\Delta x_{nt}$ and continue with the iterations, right?

However, if the above system of equations is not even consistent, it's not clear to me what a good strategy would be? Are there better ways than just picking another feasible initial point and restarting the Newton's method all over again, wishing that we may end up with a sequence of non-singular KKT matrices that lead to an optimal (acceptable) solution?

Does it make sense to use the projection of the negative gradient $-\nabla f(x)$ on the null space of matrix $A$ as $\Delta x_{nt}$? (This ensures that $x+\Delta x_{nt}$ remains feasible, but it's not clear if it's still a descent direction?)

I'd appreciate any pointers or comments. Thanks a lot!

$\endgroup$
  • 1
    $\begingroup$ I would use least squares solution and hope for the best. $\endgroup$ – user357151 Jan 11 '17 at 22:13
  • 1
    $\begingroup$ You can force feasibility and do LS on the linearized optimality equations. In other words you can minimize $\| Bx-c \|$ subject to $Ax=b$. $\endgroup$ – Ian Jan 12 '17 at 3:24
  • 1
    $\begingroup$ That said, if I found a point where the KKT matrix was singular, I would probably just take a small random perturbation of the point I'm already at. (It should not be extremely small; you want the KKT matrix to have a good condition number, not just be nonsingular.) Unless the underlying problem is quite weird, this should fix the issue. $\endgroup$ – Ian Jan 12 '17 at 3:36
  • 1
    $\begingroup$ off the top of my head, I would definitely go with the minimum-norm solution to the system, which would involve computing the Moore-Penrose pseudoinverse of the coefficent matrix. $\endgroup$ – Michael Grant Jan 12 '17 at 3:44
  • 3
    $\begingroup$ I'd say you're giving up too much by doing that. A better bet is to add a small multiple of the identity matrix to $\nabla^2 f(x)$ to make it positive definite. If $A$ has full row rank this will give you a nonsingular system, and only a small degradation from the Newton system. In fact, this approach will have the nice result of preferring solutions with small norm $\|\Delta x_{nt}\|$. $\endgroup$ – Michael Grant Jan 12 '17 at 5:45

Your Answer

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

Browse other questions tagged or ask your own question.