4
$\begingroup$

Suppose we are minimizing $f(x)$. The first order necessary condition of $x^*$ being local minmum is: $$\nabla f(x^*)= \mathbf{0}.$$ For sufficiency, we check if also $\nabla^2f(x^*) \succ 0$, i.e., the Hessian is positive definite at $x^*$. I know that if $\nabla^2f(x^*) \prec 0$ then this is a local maximizer. Moreover, if it is indefinite, $x^*$ is a saddle point. Finally, the sufficiency condition fails to classify if $\nabla^2 f(x^*) \succeq 0$ or $\nabla^2f(x^*)\preceq 0$ but not strictly positive/negative definite. So semi- definiteness makes it not possible to conclude.

Now, I want to see such a situation in constrained optimization. Assume we are minimizing $f(x)$ over some $h(x) \leq 0, \ g(x) =0$. The necessary condition of $x^*$ being a local minimum is (given that this point is a regular point) satisfying the KKT conditions. It is known that a regular point $x^*$ satisfying KKT conditions is local minimizer if it also satisfies: $$s^\top \nabla_{xx}^2 L(x^*, \lambda^*, \rho^*)s >0 $$ for all $s \neq 0$ such that: $$ \begin{bmatrix} \frac{\partial g(x^*)}{\partial x} \\ \frac{\partial h_a(x^*)}{\partial x} \end{bmatrix} s = \mathbf{0}.$$ Here, $h_a$ denotes the set of active inequality constraints at $x^*$. Also $\lambda^*, \rho^*$ are the optimal Lagrange multipliers corresponding to the inequality and equality constraints (but unnecessary detail here).

Similarly, for all $s$ satisfying the second condition if we have $s^\top \nabla_{xx}^2 L(x^*, \lambda^*, \rho^*)s <0 $ then we have a local maximizer. My question is, is there any way to conclude 'saddle point' or 'not enough evidence to classify' as in the unconstrained case?

Can I say if for some of the $s$ values we have $s^\top \nabla_{xx}^2 L(x^*, \lambda^*, \rho^*)s >0$ and for some others we have $s^\top \nabla_{xx}^2 L(x^*, \lambda^*, \rho^*)s = 0 $ is this non-concludable? And similarly, if we have some $s^\top \nabla_{xx}^2 L(x^*, \lambda^*, \rho^*)s > 0 $ and some $s^\top \nabla_{xx}^2 L(x^*, \lambda^*, \rho^*)s < 0 $, is this definitely something like a constrained saddle point?

$\endgroup$

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.