4
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .