2
$\begingroup$

I am reading through Chapter 12 of "Numerical Optimization" by Nocedal and Wright, in which Sufficient Second-Order conditions for local optima in constrained optimisation are discussed. They describe the Sufficient Second-Order Condition as follows

Theorem 12.6 - Suppose that for some feasible point $x^{*} \in \mathbb{R}$ there is a Lagrange multiplier vector $\lambda^{*}$ such that the KKT conditions are satisfied. Suppose also that

$$w^{T}\nabla^{2}_{xx}\mathcal{L}(x^{*}, \lambda^{*})w > 0, \quad \forall w \in \mathcal{C}(x^{*}, \lambda^{*}), \: w \neq 0 $$

Then $x^{*}$ is a strict local solution of the corresponding optimisation problem.

Where $\mathcal{C}(x^{*}, \lambda^{*})$ is defined as follows

We define the Critical Cone as follows:

$w \in C(x^{*}, \lambda^{*})$ if and only if

  1. $\nabla c_{i}(x^{*})^{T}w = 0 \quad \forall i \in \mathcal{E}$
  2. $\nabla c_{i}(x^{*})^{T}w = 0 \quad \forall i \in \mathcal{A}(x^{*})\cap\mathcal{I} \text{ with }\lambda_{i}^{*} > 0$
  3. $\nabla c_{i}(x^{*})^{T}w \geq 0 \quad \forall i \in \mathcal{A}(x^{*})\cap\mathcal{I} \text{ with } \lambda_{i}^{*} = 0 $

where $\mathcal{E}$ is the index set of equality constraints, $\mathcal{I}$ is the index set of inequality constraints, $\mathcal{A}(x^{*})$ is the index set of active constraints, and $c_{i}$ is the constraint function corresponding to index $i$.

The authors discuss weaker versions of the second-order sufficient condition which rely on additional assumptions and correspond to a two-sided projection of the Hessian of the Lagrangian.

The simplest case is obtained when the multiplier $\lambda^{*}$ that satisfies the KKT conditions is unique and strict complementarity holds. In this case, the definition of $\mathcal{C}(x^{*}, \lambda^{*})$ reduces to

$$\mathcal{C}(x^{*}, \lambda^{*}) = \text{Null }[\nabla c_{i}(x^{*})^{T}]_{i \in \mathcal{A}(x^{*})}$$

Why is the uniqueness of the lagrange multiplier vector required here? Doesn't the equivalence of the critical cone to the null space of the matrix of active constraint gradients follow from strict complementarity alone? If so, what is the benefit to having a unique vector of Lagrange multipliers?

Perhaps the benefit of uniqueness comes later? The authors use the above equivalence to show that the sufficient second-order condition can be restated as

$$u^{T}Z^{T}\nabla_{xx}^{2}\mathcal{L}(x^{*}, \lambda^{*})Zu \quad\text{is positive definite}$$

where $\mathcal{C}(x^{*}, \lambda^{*}) = \{ Zu \: | \: u \in \mathbb{R}^{|\mathcal{A}(x^{*})|}\}$. The authors claim that $Z$ can be found via QR decomposition of the matrix of active constraint gradients. Does the uniqueness of the lagrange multiplier vector make this any easier?

$\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.