1
$\begingroup$

In convex analysis optimization, I would like to show that the necessary conditions of the multiplier rule correspond to the nonexistence of a decrease direction. I would like to prove the following theorem:

Theorem: Let $\{\zeta_i : i = 1,2,...,k \}$ finite subset in $X^{*}$ - dual space of the normed space $X$. The following are equivalent:

$(a)$ There is no $v \in X$ such that $\langle \zeta_i , v \rangle < 0 , \forall i = 1,...,k$;

$(b)$ The set $\{\zeta_i : i = 1,2,...,k \}$ is positively linearly dependent : there exists a nonzero nonnegative vector $\gamma \in \mathbb{R}^k$ such that $\sum_{1}^{k} \gamma_i \zeta_i = 0$.

$\quad$ To prove $(a) \implies (b)$, I will construct two subsets and I try to use the separation theorem. Before, I enunciate such theorem:

(Hahn-Banach separation theorem)

Let $K_1$ and $K_2$ be nonempty, disjoint convex subsets of the normed space $X$. If $K_1$ is open, then the sets can be separated. That is, there exist $\gamma$$X^{*}$ and $\eta$ ∈ R such that $$\langle \gamma , x \rangle < \eta \leq \langle \gamma , y \rangle, \quad \forall x \in K_1 , y \in K_2.$$

To apply the separation theorem, let

$$K_1 = \{y \in \mathbb{R}^k : y_i < 0, \forall i\}, \quad K_2 = \{ (\langle \zeta_1 , v \rangle , ..., \zeta_k , v \rangle) : v \in X \}$$

The sets $K_1 , K_2$ are both convex and nonempty. By $(a)$ the sets are disjoint. Then, by the separation theorem, exist $\eta \in \mathbb{R}$ and $\gamma \in \mathbb{R}^k$. It is straightforward show that $\eta = 0$ and

$$ 0 \leq \sum \gamma_i \langle \zeta_i , v \rangle, \quad \forall v \in X.$$

I can't show the nonnegative of $\gamma$ and the other inequality

$$ 0 \geq \sum \gamma_i \langle \zeta_i , v \rangle, \quad \forall v \in X.$$

Some help?

$\endgroup$
1
$\begingroup$

Hints:

  1. Assume $\gamma_m<0$ for some $m$. Then fix $x_0\in K_1$ and note that $x_t=x_0-t e_m\in K_1$, $\forall t\ge 0$ ($e_m$ is the $m$th vector of the canonical basis of $\Bbb R^k$). What $\langle\gamma, x_t\rangle<0$ would mean for $t\to+\infty$?
  2. Other inequality: $-v\in X$.
$\endgroup$
  • $\begingroup$ Yes, this is true. I think I focused a lot on the $K_2$ set and not on the $K_1$ set. Thank you! $\endgroup$ – orrillo Nov 20 '18 at 2:21
  • $\begingroup$ Only one doubt. I tried to imagine the set $K_2 $ in small dimensions. For example. I think that in the case $k = 2$ we have lines $x = 0$ or $y = 0$ and in the case $k = 3$, maybe planes of the form $x = 0$, $y = 0$ or $z = 0$. Or maybe lines in the tridemsional space. $\endgroup$ – orrillo Nov 20 '18 at 2:26
  • 1
    $\begingroup$ @orrillo For $k=2$: if $\zeta_1$, $\zeta_2$ are linearly independent then $K_2={\Bbb R}^2$. If they are linearly dependent then $K_2$ is a line through the origin. It can be any line, not just the axes $x=0$ or $y=0$. If we denote $x=\langle\zeta_1,v\rangle$ and $y=\langle\zeta_2,v\rangle$, for dependent $\zeta_i$ we can find $\gamma_1$, $\gamma_2$ such that $\gamma_1x+\gamma_2y=\langle\gamma_1\zeta_1+\gamma_2\zeta_2,v\rangle=0$. However, if (a) is true, the line cannot go in the third quadrant, which is $K_1$. $\endgroup$ – A.Γ. Nov 20 '18 at 7:14

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.