2
$\begingroup$

If we have a constrained optimization problem $$\max_xf(x_1,...,x_n), \text {s.t.} g(x_1, ...,x_n)=0$$ Then we can use Lagrange's theorem and use these as first order conditions, to find the critical points of the lagrangian.

But I am now reading that as Second order conditions for a maximum we need: $$v^TD^2L(x^*, \lambda ^*)v<0, \forall (v\neq 0)\in \mathbb R^n \text {for which } Dg(x^*)v=0$$

My lecture notes then go on to say that to find points that satisfy this condition, we need to construct the "bordered Hessian", and check the sign of the "last n-m" leading principal minors.

I have two questions:

  1. Is there an intuitive explanation for why this condition on the bordered hessian implies that the S.O.C. for a maximum is met? How does it relate to positive definiteness of the bordered hessian for example?

  2. Are there other ways to check whether these conditions are met? e.g. can we also check the eigenvalues of the bordered hessian ?

$\endgroup$
  • $\begingroup$ Is $g : R^n \to R^m$ ? $\endgroup$ – Red shoes Oct 16 '17 at 6:15
  • $\begingroup$ Yes, but I usually assume $m=1$ for simplicity. $\endgroup$ – user56834 Oct 16 '17 at 6:28
  • $\begingroup$ The subspace $v \in \mathbb{R}^n$ for which $Dg(x^*)v = 0$, is the kernel of $D(g^*)$. It corresponds to the tangent space to the constraint set. The inequality $v^T D^2 L(x^*,\lambda^*)v < 0$ says that the quadratic form given by $D^2L(...)$ is negative definite on that tangent space, which informally corresponds to being "concave down" ($y=-x^2$ has negative derivative; in unconstrained optimization, the [ordinary] Hessian being negative definite corresponds to maximum). ... To pass to eigenvalues, might need to decompose matrix first, into blocks for the tangent space and normal? $\endgroup$ – Zach Teitler Oct 16 '17 at 7:15
  • $\begingroup$ @zach-Teiler, so that is why the matrix needs to be positive definite on the tangent space. That I find intuitive. But why is that positive definiteness implied by the conditions on the "bordered hessian". How do we even interpret this "bordered" hessian $\endgroup$ – user56834 Oct 16 '17 at 9:19
  • $\begingroup$ @zach-teitler, sorry miss spelled your name $\endgroup$ – user56834 Oct 16 '17 at 9:25

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.