1
$\begingroup$

Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint.

The problem only has equality constraint. Why does the solution requires using the KKT condition, which is for inequality constraint?

This lecture note mention using KKT condition and quadratic approximation gives the following:

Newton's method with line search:

$$ \begin{bmatrix} \nabla^{2} f & A^{T} \\ A & 0 \\ \end{bmatrix} \begin{bmatrix} u \\ w \\ \end{bmatrix} = \begin{bmatrix} - \nabla f \\ 0 \\ \end{bmatrix} $$

$\vec{x}^{(n+1)} = \vec{x}^{(n)} + t\vec{u}$ where $t$ is the step size found by backtracking.

Improve this question
$\endgroup$
6
  • $\begingroup$ Why do you think the KKT conditions are only for inequality constrained problems? $\endgroup$ – Wolfgang Bangerth Oct 19 '18 at 20:37
  • 2
    $\begingroup$ I would suggest taking a look at a book like the one by Nocedal & Wright. It will have an extensive discussion of the optimality conditions and Newton steps. $\endgroup$ – Wolfgang Bangerth Oct 19 '18 at 20:37
  • $\begingroup$ Hmm. Why Lagrange multiplier is not enough? I will study block triangular approximation instead of KKT because I am on a deadline to calculate this fast. But I want to learn the reason when I get a chance. I haven't taken any class about optimization and fall back to the method I learn in high school. $\endgroup$ – R zu Oct 19 '18 at 21:10
  • $\begingroup$ That book has so many diagrams. Reading it is pure joy. Thanks. $\endgroup$ – R zu Oct 19 '18 at 21:13
  • $\begingroup$ KKT conditions = optimality conditions involving Lagrange multipliers. The only difference for inequality constraints is that there are additional sign conditions on the multipliers (including complementarity conditions). So there's no contradiction between your approach and the lecture notes'. (There's a reason this approach is also known as Lagrange-Newton method.) $\endgroup$ – Christian Clason Oct 19 '18 at 22:32
2
$\begingroup$

You know that you have to use the Lagrange multiplier, $$ L(x,\mu)=f(x)+\mu^T(Ax-b). $$ The derivatives of that function that have to be zero at a possible minimum are $$ 0=\frac{\partial L}{\partial x}=f'(x)+\mu^TA\\ 0=\frac{\partial L}{\partial \mu}=(Ax-b)^T $$ To compute a Newton step $(u,w)$ for the pair $x,\mu$ you have to solve $$ f'(x)+f''(x)u+(\mu+w)^TA=0\\ A(x+u)-b=0 $$ Converting first and second derivative to gradient and Hessean results in $$ \begin{bmatrix} \nabla^2f(x)&A^T\\ A&0 \end{bmatrix} \begin{bmatrix} u\\w \end{bmatrix} = \begin{bmatrix} -\nabla f-A^T\mu\\-(Ax-b) \end{bmatrix} $$ By the first assumption one can assume that in every step $Ax=b$ exactly so that the right side in the second block reduces to zero. I'm not sure why you assume that $A^T\mu=0$.

It would of course now be useful to parametrize the kernel of $A$ to remove the second block of equations so that only the (potentially) non-linear equations of the first block remain.

If $U=Cz$ parametrizes the kernel, $AC=0$, then the reduced system has to minimize $f(x_0+Cz)$, thus $f'(x_0+Cz)C=0$, so that the Newton update $Δz$ is obtained from $$C^T\nabla^2f(x_0+Cz)C\,\Delta z=-C^T\nabla f(x_0+Cz)$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ Several lecture notes say $A^{T}\mu = 0$ including stat.cmu.edu/~ryantibs/convexopt-S15/lectures/14-newton.pdf and members.cbio.mines-paristech.fr/~jvert/teaching/2006insead/… $\endgroup$ – R zu Oct 21 '18 at 14:45
  • $\begingroup$ $Ax - b = 0$ in the last system of equations and $A(x + u) -b = 0$ in the 2nd last system. Still don't get whye $A^{T}\mu = 0$. That seems to be not from KKT. $\endgroup$ – R zu Oct 21 '18 at 15:55
  • $\begingroup$ Because $Ax - b = 0$, $A(x+u) - b = 0$ implies $Au = 0$. $\endgroup$ – R zu Oct 21 '18 at 16:00
  • $\begingroup$ Found math.stackexchange.com/questions/221544/… Same derivation as you did here except they use the Jacobian of the constraint instead of $A$ here. $\endgroup$ – R zu Oct 21 '18 at 17:15
  • 1
    $\begingroup$ If the constraint is linear (as in this case), you a) have that $A$ is the Jacobian of the constraint and b) you can reformulate to solve in each step for $(u,\mu^{k+1})$ (with $x^{k+1} = x^k+u$) rather than $(u,w)$ (with $\mu^{k+1} = \mu^k+w$). This accounts for the difference between the two formulations (note that only $x$ is updated in the OP). $\endgroup$ – Christian Clason Oct 23 '18 at 9:23

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.