# Regularity Conditions for Constrained Optimization

Question:

Let $G$ be a convex mapping from $\Omega \subseteq X$ into a normed space $Z$, and assume that $P \subseteq Z$ be a positive cone with nonempty interior. Show that the following two regularity conditions are equivalent:

(i) there exists $x_{1} \in \Omega$ such that $G(x_{1}) < \theta$,

(ii) for every nonnull $z^{\ast} \geq \theta$, there exists $x \in \Omega$ such that $\langle G(x) , z^{\ast} \rangle < 0$.

(The notation follows Optimization by Vector-Space Methods by Luenberger.)

(Attempted) Solution:

I can prove (i) implies (ii).

Suppose there exists $x_{1} \in \Omega$ such that $G(x_{1}) < 0$. Then, we have that $$\begin{array}{rcrl} G(x_{1}) < 0 & \Rightarrow & -G(x_{1}) \geq 0 \\ & \Rightarrow & \langle -G(x_{1}) , z^{\ast} \rangle \geq 0 & \forall \, z^{\ast} \geq 0 \\ & \Rightarrow & \langle G(x_{1}) , z^{\ast} \rangle \leq 0 & \forall \, z^{\ast} \geq 0. \end{array}$$ Suppose $\langle G(x_{1}) , z_{0}^{\ast} \rangle = 0$ for some $z_{0}^{\ast} \geq 0$. Since $-G(x_{1})$ is contained in the interior of $P$, there exists an $\varepsilon > 0$ such that $||z + G(x_{1})|| < \varepsilon$ implies $z \in P$. Choose any $z \in Z$, and define $$\alpha = \frac{\varepsilon}{||z|| + 1}.$$ Our choice of $\alpha$ ensures that $-G(x_{1}) + \alpha z$ and $-G(x_{1}) - \alpha z$ are both contained in the interior of $P$. Observe that $$-G(x_{1}) \pm \alpha z \in P \qquad \Rightarrow \qquad \langle -G(x_{1}) \pm \alpha z , z_{0}^{\ast} \rangle \geq 0.$$ But we also have that $$\tfrac{1}{2} \cdot \langle -G(x_{1}) + \alpha z , z_{0}^{\ast} \rangle + \tfrac{1}{2} \cdot \langle -G(x_{1}) - \alpha z , z_{0}^{\ast} \rangle = \langle -G(x_{1}) , z_{0}^{\ast} \rangle = 0.$$ Combining these results, we can conclude that $$\langle -G(x_{1}) \pm \alpha z , z_{0}^{\ast} \rangle = 0.$$ In particular, we have that $$\langle -G(x_{1}) + \alpha z , z_{0}^{\ast} \rangle = \langle -G(x_{1}) , z_{0}^{\ast} \rangle + \alpha \cdot \langle z , z_{0}^{\ast} \rangle = \alpha \cdot \langle z , z_{0}^{\ast} \rangle = 0.$$ Because $\alpha$ is nonzero, this implies that $\langle z , z_{0}^{\ast} \rangle = 0$. Since $z \in Z$ was arbitrary, this implies that $z_{0}^{\ast} = \theta$. Thus, we have shown that for all $z^{\ast} \geq \theta$, we have that $\langle G(x_{1}) , z^{\ast} \rangle \leq 0$ with equality if and only if $z^{\ast} = \theta$. In other words, for every $z^{\ast} \geq \theta$ such that $z \neq \theta$, we have that $\langle G(x_{1}) , z^{\ast}) < 0$. Thus, $x_{1} \in \Omega$ satisfies the desired condition uniformly for all nonnull $z^{\ast} \geq 0$.

Then, I am completely at a loss as to how I should prove (ii) implies (i). I was also wondering if there is a name for the second regularity condition (I think the second condition is called Slater's condition).

-

Commentary: The key thing to note here is that the cone $P$ has a non-empty interior. Another point to note is that proofs of this sort almost invariably involve some form of Hahn Banach, so when you are stuck, think separation! As an aside, I find proofs involving generalized inequalities to be very, very slick, but sometimes the level of abstraction obfuscates certain detail which can be, ironically, simplifying. So I use the abstraction as an aide-mémoire, but when it comes to proofs, I revert to the underlying sets (as in $z^* \in P^+$ instead of $z^* \geq \theta$). Of course, this is a very personal perspective.
($\Rightarrow$): $G(x_1) < \theta$ means that $-G(x_1) \in P^\circ$. Let $B$ be the open unit ball, then for some $\delta>0$ we have $\delta B+\{-G(x_1)\} \subset P$. Now let $z^* \geq 0$ be non-zero. In particular, this means that $z^* \in P^+$, and $I=(-\epsilon, \epsilon) \subset z^*(\delta B)$, for some $\epsilon>0$ (since it is an open map). Since $\delta B+\{-G(x_1)\} \subset P$, we have $I + \{z^*(-G(x_1))\} \subset [0,\infty)$ which implies $-\epsilon -z^*(-G(x_1)) \geq 0$, or equivalently, $z^*(G(x_1)) < -\epsilon <0$, as required.
($\Leftarrow$): The set $C=-G(\Omega)$ is convex, and $P$ is a convex cone with interior. I want to show that $C\cap P^\circ$ is non-empty. Proceeding by contradiction, suppose $C \cap P^\circ = \emptyset$. Apply the Eidelheit separation theorem (Theorem 5.12.3 in Luenberger) to obtain a $\zeta^* \in Z^*$ such that $\sup_{x\in P^\circ} \zeta^*(x) \leq \inf_{x \in C} \zeta^*(x)$. It will suit us better to let $z^* = -\zeta^*$, then we have $\inf_{x\in P^\circ} z^*(x) \geq \sup_{x \in C} z^*(x)$. Since $P^\circ$ is a cone, the left hand side can only take the values $0$ or $-\infty$, and since $C$ is non-empty, this gives the two equalities $\inf_{x\in P^\circ} z^*(x) \geq 0$ and $0 \geq \sup_{x \in C} z^*(x)$. The first equality shows that $z^* \in P^+$ (ie, $z^* \geq \theta$), and the second gives $\inf_{x \in G(\Omega)} z^*(x) \geq 0$. Hence we must have $C \cap P^\circ \neq \emptyset$, hence there exists $x_1\in \Omega$ such that $-G(x_1) \in P^\circ$, or in other words, $G(x_1) < \theta$.