# An aplication of the Hahn-Banach separation theorem: multiplier rule

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?

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$$.
• Yes, this is true. I think I focused a lot on the $K_2$ set and not on the $K_1$ set. Thank you! – orrillo Nov 20 '18 at 2:21
• 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. – orrillo Nov 20 '18 at 2:26
• @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$. – A.Γ. Nov 20 '18 at 7:14