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?


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.