Mixing
An aplication of the Hahn-Banach separation theorem: multiplier rule
up vote
1
down vote
favorite
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?
convex-analysis separation-axioms
asked 2 days ago
orrillo
291110
add a comment |
up vote
1
down vote
favorite
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?
convex-analysis separation-axioms
asked 2 days ago
orrillo
291110
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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?
convex-analysis separation-axioms
asked 2 days ago
orrillo
291110
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?
convex-analysis separation-axioms
convex-analysis separation-axioms
asked 2 days ago
orrillo
291110
asked 2 days ago
orrillo
291110
asked 2 days ago
orrillo
291110
asked 2 days ago
orrillo
291110
asked 2 days ago
orrillo
291110
291110
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Hints:
- Assume $gamma_m<0$ for some $m$. Then fix $x_0in K_1$ and note that $x_t=x_0-t e_min K_1$, $forall tge 0$ ($e_m$ is the $m$th vector of the canonical basis of $Bbb R^k$). What $langlegamma, x_trangle<0$ would mean for $tto+infty$?
- Other inequality: $-vin X$.
answered 2 days ago
A.Γ.
21.1k22355
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
2 days ago
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
2 days ago
1
@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=langlezeta_1,vrangle$ and $y=langlezeta_2,vrangle$, for dependent $zeta_i$ we can find $gamma_1$, $gamma_2$ such that $gamma_1x+gamma_2y=langlegamma_1zeta_1+gamma_2zeta_2,vrangle=0$. However, if (a) is true, the line cannot go in the third quadrant, which is $K_1$.
– A.Γ.
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Hints:
- Assume $gamma_m<0$ for some $m$. Then fix $x_0in K_1$ and note that $x_t=x_0-t e_min K_1$, $forall tge 0$ ($e_m$ is the $m$th vector of the canonical basis of $Bbb R^k$). What $langlegamma, x_trangle<0$ would mean for $tto+infty$?
- Other inequality: $-vin X$.
answered 2 days ago
A.Γ.
21.1k22355
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
2 days ago
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
2 days ago
1
@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=langlezeta_1,vrangle$ and $y=langlezeta_2,vrangle$, for dependent $zeta_i$ we can find $gamma_1$, $gamma_2$ such that $gamma_1x+gamma_2y=langlegamma_1zeta_1+gamma_2zeta_2,vrangle=0$. However, if (a) is true, the line cannot go in the third quadrant, which is $K_1$.
– A.Γ.
2 days ago
add a comment |
up vote
1
down vote
accepted
Hints:
- Assume $gamma_m<0$ for some $m$. Then fix $x_0in K_1$ and note that $x_t=x_0-t e_min K_1$, $forall tge 0$ ($e_m$ is the $m$th vector of the canonical basis of $Bbb R^k$). What $langlegamma, x_trangle<0$ would mean for $tto+infty$?
- Other inequality: $-vin X$.
answered 2 days ago
A.Γ.
21.1k22355
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
2 days ago
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
2 days ago
1
@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=langlezeta_1,vrangle$ and $y=langlezeta_2,vrangle$, for dependent $zeta_i$ we can find $gamma_1$, $gamma_2$ such that $gamma_1x+gamma_2y=langlegamma_1zeta_1+gamma_2zeta_2,vrangle=0$. However, if (a) is true, the line cannot go in the third quadrant, which is $K_1$.
– A.Γ.
2 days ago
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Hints:
- Assume $gamma_m<0$ for some $m$. Then fix $x_0in K_1$ and note that $x_t=x_0-t e_min K_1$, $forall tge 0$ ($e_m$ is the $m$th vector of the canonical basis of $Bbb R^k$). What $langlegamma, x_trangle<0$ would mean for $tto+infty$?
- Other inequality: $-vin X$.
answered 2 days ago
A.Γ.
21.1k22355
Hints:
- Assume $gamma_m<0$ for some $m$. Then fix $x_0in K_1$ and note that $x_t=x_0-t e_min K_1$, $forall tge 0$ ($e_m$ is the $m$th vector of the canonical basis of $Bbb R^k$). What $langlegamma, x_trangle<0$ would mean for $tto+infty$?
- Other inequality: $-vin X$.
answered 2 days ago
A.Γ.
21.1k22355
answered 2 days ago
A.Γ.
21.1k22355
answered 2 days ago
A.Γ.
21.1k22355
answered 2 days ago
A.Γ.
21.1k22355
21.1k22355
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
2 days ago
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
2 days ago
1
@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=langlezeta_1,vrangle$ and $y=langlezeta_2,vrangle$, for dependent $zeta_i$ we can find $gamma_1$, $gamma_2$ such that $gamma_1x+gamma_2y=langlegamma_1zeta_1+gamma_2zeta_2,vrangle=0$. However, if (a) is true, the line cannot go in the third quadrant, which is $K_1$.
– A.Γ.
2 days ago
add a comment |
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
2 days ago
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
2 days ago
1
@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=langlezeta_1,vrangle$ and $y=langlezeta_2,vrangle$, for dependent $zeta_i$ we can find $gamma_1$, $gamma_2$ such that $gamma_1x+gamma_2y=langlegamma_1zeta_1+gamma_2zeta_2,vrangle=0$. However, if (a) is true, the line cannot go in the third quadrant, which is $K_1$.
– A.Γ.
2 days ago
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
2 days ago
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
2 days ago
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
2 days ago
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
2 days ago
1
1
@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=langlezeta_1,vrangle$ and $y=langlezeta_2,vrangle$, for dependent $zeta_i$ we can find $gamma_1$, $gamma_2$ such that $gamma_1x+gamma_2y=langlegamma_1zeta_1+gamma_2zeta_2,vrangle=0$. However, if (a) is true, the line cannot go in the third quadrant, which is $K_1$.
– A.Γ.
2 days ago
@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=langlezeta_1,vrangle$ and $y=langlezeta_2,vrangle$, for dependent $zeta_i$ we can find $gamma_1$, $gamma_2$ such that $gamma_1x+gamma_2y=langlegamma_1zeta_1+gamma_2zeta_2,vrangle=0$. However, if (a) is true, the line cannot go in the third quadrant, which is $K_1$.
– A.Γ.
2 days ago
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005579%2fan-aplication-of-the-hahn-banach-separation-theorem-multiplier-rule%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
