Numerical methods and KKT in NLP I am studying numerical methods and NLP. I started with gradient based methods, newton methods and KKT conditions. I found the following sentence:


*

*A local minimum is found by solving KKT conditions, using iterative
techniques based on Newton’s method.


In basic courses we used KKT conditions to calculate the minimum.
Does the sentence above mean, that you calculate the "candidate - point" through numerical methods (gradient, Newton, quasi netwon..) and then you check if this particular point satisfy KKT?
Example:
$min:  f(a,b) = 3a + 4b$
subject to
$k_1 (a,b) = -a^2 -b^2+2b \le 0 $
$k_2 (a,b) = a^2+b^2-4 \le 0 $
The KKT conditions are:
$3-2\lambda_1a+2\lambda_2 a = 0 $
$4+2\lambda_1(2-2b)+2\lambda_2b = 0 $
$\lambda_1(-a^2 -b^2+2b) = 0 $
$\lambda_1(a^2+b^2-4) = 0 $
$\lambda_1, \lambda_2  \ge 0 $
In basic courses we learned how to calculate based on this KKT conditions the KKT-points. But I am not sure, how to use numerical methods (Newton, steepest descent,...) to solve this KKT conditions (this are equations, there is no longer a $min ...$)?
 A: You're missing two additional pieces of the KKT conditions
\begin{align*}
k_1 (a,b) =& -a^2 -b^2+2b \le 0\\
k_2 (a,b) =& a^2+b^2-4 \le 0 
\end{align*}
In answer to your question, it depends on whether or not you have inequality constraints or not.  If we only have equality constraints, the KKT conditions for the problem
$$
\min\limits_{x\in \mathbb{R}^m} \{f(x) : g(x) = 0\}
$$
are
\begin{align*}
\nabla f(x) + g^\prime(x)^T y =& 0\\
g(x) =& 0
\end{align*}
In this case, we have a nonlinear system of equations for $x$ and $y$ that we can attack with Newton's method for nonlinear equations.  Note, Newton's method is not guaranteed to converge from an arbitrary starting guess, so we typically need a globalization method like a line-search or trust-region method to guarantee convergence.  However, for these problems, your assertion is basically correct: we can write down the KKT conditions and then use an iterative method like Newton's method to solve them.  This gives rise to things like SQP methods.
With inequality constraints, the KKT conditions for the problem
$$
\min\limits_{x\in \mathbb{R}^m} \{f(x) : h(x) \geq 0\}
$$
are
\begin{align*}
\nabla f(x) - h^\prime(x)^T z =& 0\\
h(x) \geq& 0\\
z\geq& 0\\
h(x)\circ z =& 0
\end{align*}
where $\circ$ denotes the pointwise product.  This is not a nonlinear system of equations.  It is a nonlinear system of equations and inequalities.  Therefore, we need more sophisticated tools to deal with this case.  Really, we don't have that many tools at our disposal, so the game here is to use a trick to deal with the inequality pieces, which then forces the rest of the problem to look like a nonlinear system of equations, which we then go back to Newton's method.  These tricks are things like projection, active set, or interior point methods.
Anyway, after that, yes, we basically just keep iterating on these algorithms and then check the KKT conditions at the end of each step.  As soon as we satisfy them, we quit.  Technically, there's some nuance since the KKT conditions only tell us when we're stationary (min, max, or saddle).  However, the globalization method (line-search or trust-region), typically makes sure that we're heading toward our desired min or max.
