Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

Proof:

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

The first condition is similar to that required by Slater's condition, but the latter is typically applied to a convex optimization problem with equality and inequality constraints. In this case, the problem satisfies a Slater condition if there is a point in the domain that satisfies all constraints and also that all inequality constraints are strictly satisfied.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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