2
$\begingroup$

I'm trying to understand a statement from the book "Perturbation Analysis of Optimization Problems", by Bonnans and Shapiro. Let me start by providing some context. In page 148, the authors write down the optimality conditions for the problem

$$\min_{x\in Q} f(x) \text{ subject to } G(x)\in K,$$

where $Q$ and $K$ are convex subsets of Banach spaces $X$ and $Y$, respectively, and $f\colon X\to \mathbb{R}$, and $G\colon X\to Y$.

In equation 3.8, the authors say that for some feasible point $x_0$, the optimality conditions are

$$x\in\text{argmin}_{x\in Q} L(x,\lambda) \text{ and } \lambda\in N_K(G(x_0)),$$

Where $L(x,\lambda)\colon= f(x) + \langle \lambda, G(X)\rangle$ is the lagrangian associated with the problem, and $N_K(G(x_0))$ is the normal cone of $K$ at the point $x_0$.

After that, in equation 3.9, they say that when $K$ is a cone, the condition $\lambda\in N_K(G(x_0))$ is equivalent to

$$ G(x_0)\in K,\, \lambda \in K^\circ, \text{ and } \langle \lambda, G(x_0)\rangle =0,$$

and that's where I'm struggling. I see that these conditions resemble the classic KKT conditions and they correspond to primal feasibility, dual feasibility, and complementarity, respectively. But I want to figure this out formally and hopefully be able to have some geometric interpretation of it.

Can someone help me out with this?

Thanks in advance

$\endgroup$

1 Answer 1

2
$\begingroup$

The answer to my question became clear when I stumbled upon Example 2.62 and Equation 2.110 from the book, which are located in pages 50/51. Let me state that as a lemma for completeness:

Lemma: Let $X$ be a banach space, let $K\subseteq X$ be a closed convex cone, and let $x\in K$, then

$$N_K(x)= K^\circ \cap \text{span}(\{x\})^\bot.$$

Using this result, let's prove the desired equivalence:

First of all, note that the existence of $\lambda\in N_K(G(x_0))$ implies that $N_K(G(x_0))\not = \varnothing $ and therefore we have that $G(x_0)\in K$. Moreover, since $\lambda\in N_K(G(x_0))$ and by our lemma we have that $N_K(G(x_0))\subseteq K^\circ$ and hence $\lambda\in K^\circ$. Finally, let's use the definition of $N_K(G(x_0))$ as $$N_K(G(x_0))\colon = \{x\in X\,\colon \langle x, z - G(x_0)\rangle \leq 0\text{ for each } z\in K\}.$$ Recall that $\lambda\in N_K(G(x_0))$ by hypothesis. Taking $z=0$, we readily obtain that $\langle \lambda, G(x_0)\rangle \geq 0$. On the other hand, setting $z=2G(x_0)$ gives us that $\langle \lambda, G(x_0)\rangle \leq 0$. Thus, we conclude that $\langle \lambda , G(x_0)\rangle =0$.

For the reverse implication, we have by hypothesis that $\langle\lambda,G(x_0)\rangle =0$, which implies that $\lambda \in \text{span}(\{G(x\})^\bot$. We are also given that $\lambda\in K^\circ$, which allows us to conclude that $\lambda\in$$K^\circ \cap \text{span}(\{G(x_0)\})^\bot.$ By our lemma, that's exactly $N_K(G(x_0))$.

I know it was not that hard but finding that lemma was essential. Hope it helps someone someday.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.