Mixing
Minimize $f(x)=maxx_2$ subject to $g(x)=a_1x_1+a_2x_2+bleq 0$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
$$beginarrayll textminimize & f(x) := max x_2\\ textsubject to & g(x) := a_1 x_1 + a_2 x_2 + b leq 0endarray$$
where $f, g$ : $mathbbR^2rightarrow mathbbR$, and $a_1, a_2, b > 0$.
Since the global minimum of $f$, $(0,0)$, does not satisfy the constraint, and since $f$ is convex, the minimum is attained on the boundary of $C:=x mid g(x)leq 0$. Hence, the minimizer is a point of the form
$$left(frac-b-a_2x_2a_1,x_2right)$$
Intuitively, I can see that at the minimum, we must have $x_1=x_2$, giving us $left(frac-ba_1+a_2, frac-ba_1+a_2right)$ as the minimizer. How can I show this rigorously?
optimization convex-analysis convex-optimization nonlinear-optimization
edited Jul 16 at 19:21
Rodrigo de Azevedo
12.5k41751
asked Jul 16 at 19:14
jackson5
524312
add a comment |Â
up vote
1
down vote
favorite
$$beginarrayll textminimize & f(x) := max x_2\\ textsubject to & g(x) := a_1 x_1 + a_2 x_2 + b leq 0endarray$$
where $f, g$ : $mathbbR^2rightarrow mathbbR$, and $a_1, a_2, b > 0$.
Since the global minimum of $f$, $(0,0)$, does not satisfy the constraint, and since $f$ is convex, the minimum is attained on the boundary of $C:=x mid g(x)leq 0$. Hence, the minimizer is a point of the form
$$left(frac-b-a_2x_2a_1,x_2right)$$
Intuitively, I can see that at the minimum, we must have $x_1=x_2$, giving us $left(frac-ba_1+a_2, frac-ba_1+a_2right)$ as the minimizer. How can I show this rigorously?
optimization convex-analysis convex-optimization nonlinear-optimization
edited Jul 16 at 19:21
Rodrigo de Azevedo
12.5k41751
asked Jul 16 at 19:14
jackson5
524312
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
$$beginarrayll textminimize & f(x) := max x_2\\ textsubject to & g(x) := a_1 x_1 + a_2 x_2 + b leq 0endarray$$
where $f, g$ : $mathbbR^2rightarrow mathbbR$, and $a_1, a_2, b > 0$.
Since the global minimum of $f$, $(0,0)$, does not satisfy the constraint, and since $f$ is convex, the minimum is attained on the boundary of $C:=x mid g(x)leq 0$. Hence, the minimizer is a point of the form
$$left(frac-b-a_2x_2a_1,x_2right)$$
Intuitively, I can see that at the minimum, we must have $x_1=x_2$, giving us $left(frac-ba_1+a_2, frac-ba_1+a_2right)$ as the minimizer. How can I show this rigorously?
optimization convex-analysis convex-optimization nonlinear-optimization
edited Jul 16 at 19:21
Rodrigo de Azevedo
12.5k41751
asked Jul 16 at 19:14
jackson5
524312
$$beginarrayll textminimize & f(x) := max x_2\\ textsubject to & g(x) := a_1 x_1 + a_2 x_2 + b leq 0endarray$$
where $f, g$ : $mathbbR^2rightarrow mathbbR$, and $a_1, a_2, b > 0$.
Since the global minimum of $f$, $(0,0)$, does not satisfy the constraint, and since $f$ is convex, the minimum is attained on the boundary of $C:=x mid g(x)leq 0$. Hence, the minimizer is a point of the form
$$left(frac-b-a_2x_2a_1,x_2right)$$
Intuitively, I can see that at the minimum, we must have $x_1=x_2$, giving us $left(frac-ba_1+a_2, frac-ba_1+a_2right)$ as the minimizer. How can I show this rigorously?
optimization convex-analysis convex-optimization nonlinear-optimization
edited Jul 16 at 19:21
Rodrigo de Azevedo
12.5k41751
asked Jul 16 at 19:14
jackson5
524312
edited Jul 16 at 19:21
Rodrigo de Azevedo
12.5k41751
edited Jul 16 at 19:21
Rodrigo de Azevedo
12.5k41751
edited Jul 16 at 19:21
Rodrigo de Azevedo
12.5k41751
12.5k41751
asked Jul 16 at 19:14
jackson5
524312
asked Jul 16 at 19:14
jackson5
524312
asked Jul 16 at 19:14
jackson5
524312
524312
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
1
down vote
As we can observe in the attached figures for
$$
minleft(maxleft(|x|,|y|right)right);;mboxs. t.;; ax+by + cle 0
$$
with $a = -2,b = 1, c = 6$ first a spatial representation and second as the level surfaces and the feasible region in light blue,
if the origin is at the feasible region interior the the answer is $0$ otherwise the answer is at one of the solutions
$$
ax+by+c=0\
x+y = 0
$$
and
$$
ax+by+c=0\
x-y = 0
$$
or at
$$
minleft(left|fracca-bright|,left|fracca+bright|right)
$$
answered Jul 16 at 20:18
Cesareo
5,7822412
add a comment |Â
up vote
0
down vote
Let $(x_1,x_2):=(y_1,y_2)$ be a minimizing pair of $f(x_1,x_2)$ under $g(x_1,x_2)leq 0$. Clearly, $y_1leq 0$ or $y_2leq0$. If $y_1<y_2$, then $$(x_1,x_2)=left(y_1+epsilon,y_2-fraca_1a_2epsilonright)$$
is a solution for all real numbers $epsilon$. What happens if $epsilon$ is a very small positive real number, say
$$0<epsilonllfracy_2-y_11+fraca_1a_2,?$$ Do something similar when $y_1>y_2$.
answered Jul 16 at 19:35
Batominovski
23.2k22777
add a comment |Â
up vote
0
down vote
Generalizing and rephrasing slightly, we have the following optimization problem in $mathrm x in mathbb R^n$
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x leq bendarray$$
where vector $mathrm a in mathbb R^n$ has no zero entries. There are two cases to consider:
If the origin is in the feasible region, then the minimum is attained at the origin.
If the origin is not in the feasible region, then the minimum is attained at its boundary.
Hence, in the latter case, we have a least-norm problem in the $infty$-norm
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x = bendarray$$
In $mathbb R^2$, the feasible region of this least-norm problem is a line that is neither vertical nor horizontal (due to the restrictions on vector $mathrm a in mathbb R^2$). We would like to find the point on this line that is closest to the origin in the $infty$-norm. Since the level sets of $| mathrm x |_infty$ are squares centered at the origin, then the minimizer is a square's vertex and, thus, its entries have the same absolute value.
[ image source ]
answered Jul 16 at 20:11
Rodrigo de Azevedo
12.5k41751
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
As we can observe in the attached figures for
$$
minleft(maxleft(|x|,|y|right)right);;mboxs. t.;; ax+by + cle 0
$$
with $a = -2,b = 1, c = 6$ first a spatial representation and second as the level surfaces and the feasible region in light blue,
if the origin is at the feasible region interior the the answer is $0$ otherwise the answer is at one of the solutions
$$
ax+by+c=0\
x+y = 0
$$
and
$$
ax+by+c=0\
x-y = 0
$$
or at
$$
minleft(left|fracca-bright|,left|fracca+bright|right)
$$
answered Jul 16 at 20:18
Cesareo
5,7822412
add a comment |Â
up vote
1
down vote
As we can observe in the attached figures for
$$
minleft(maxleft(|x|,|y|right)right);;mboxs. t.;; ax+by + cle 0
$$
with $a = -2,b = 1, c = 6$ first a spatial representation and second as the level surfaces and the feasible region in light blue,
if the origin is at the feasible region interior the the answer is $0$ otherwise the answer is at one of the solutions
$$
ax+by+c=0\
x+y = 0
$$
and
$$
ax+by+c=0\
x-y = 0
$$
or at
$$
minleft(left|fracca-bright|,left|fracca+bright|right)
$$
answered Jul 16 at 20:18
Cesareo
5,7822412
add a comment |Â
up vote
1
down vote
up vote
1
down vote
As we can observe in the attached figures for
$$
minleft(maxleft(|x|,|y|right)right);;mboxs. t.;; ax+by + cle 0
$$
with $a = -2,b = 1, c = 6$ first a spatial representation and second as the level surfaces and the feasible region in light blue,
if the origin is at the feasible region interior the the answer is $0$ otherwise the answer is at one of the solutions
$$
ax+by+c=0\
x+y = 0
$$
and
$$
ax+by+c=0\
x-y = 0
$$
or at
$$
minleft(left|fracca-bright|,left|fracca+bright|right)
$$
answered Jul 16 at 20:18
Cesareo
5,7822412
As we can observe in the attached figures for
$$
minleft(maxleft(|x|,|y|right)right);;mboxs. t.;; ax+by + cle 0
$$
with $a = -2,b = 1, c = 6$ first a spatial representation and second as the level surfaces and the feasible region in light blue,
if the origin is at the feasible region interior the the answer is $0$ otherwise the answer is at one of the solutions
$$
ax+by+c=0\
x+y = 0
$$
and
$$
ax+by+c=0\
x-y = 0
$$
or at
$$
minleft(left|fracca-bright|,left|fracca+bright|right)
$$
answered Jul 16 at 20:18
Cesareo
5,7822412
answered Jul 16 at 20:18
Cesareo
5,7822412
answered Jul 16 at 20:18
Cesareo
5,7822412
answered Jul 16 at 20:18
Cesareo
5,7822412
5,7822412
add a comment |Â
add a comment |Â
up vote
0
down vote
Let $(x_1,x_2):=(y_1,y_2)$ be a minimizing pair of $f(x_1,x_2)$ under $g(x_1,x_2)leq 0$. Clearly, $y_1leq 0$ or $y_2leq0$. If $y_1<y_2$, then $$(x_1,x_2)=left(y_1+epsilon,y_2-fraca_1a_2epsilonright)$$
is a solution for all real numbers $epsilon$. What happens if $epsilon$ is a very small positive real number, say
$$0<epsilonllfracy_2-y_11+fraca_1a_2,?$$ Do something similar when $y_1>y_2$.
answered Jul 16 at 19:35
Batominovski
23.2k22777
add a comment |Â
up vote
0
down vote
Let $(x_1,x_2):=(y_1,y_2)$ be a minimizing pair of $f(x_1,x_2)$ under $g(x_1,x_2)leq 0$. Clearly, $y_1leq 0$ or $y_2leq0$. If $y_1<y_2$, then $$(x_1,x_2)=left(y_1+epsilon,y_2-fraca_1a_2epsilonright)$$
is a solution for all real numbers $epsilon$. What happens if $epsilon$ is a very small positive real number, say
$$0<epsilonllfracy_2-y_11+fraca_1a_2,?$$ Do something similar when $y_1>y_2$.
answered Jul 16 at 19:35
Batominovski
23.2k22777
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Let $(x_1,x_2):=(y_1,y_2)$ be a minimizing pair of $f(x_1,x_2)$ under $g(x_1,x_2)leq 0$. Clearly, $y_1leq 0$ or $y_2leq0$. If $y_1<y_2$, then $$(x_1,x_2)=left(y_1+epsilon,y_2-fraca_1a_2epsilonright)$$
is a solution for all real numbers $epsilon$. What happens if $epsilon$ is a very small positive real number, say
$$0<epsilonllfracy_2-y_11+fraca_1a_2,?$$ Do something similar when $y_1>y_2$.
answered Jul 16 at 19:35
Batominovski
23.2k22777
Let $(x_1,x_2):=(y_1,y_2)$ be a minimizing pair of $f(x_1,x_2)$ under $g(x_1,x_2)leq 0$. Clearly, $y_1leq 0$ or $y_2leq0$. If $y_1<y_2$, then $$(x_1,x_2)=left(y_1+epsilon,y_2-fraca_1a_2epsilonright)$$
is a solution for all real numbers $epsilon$. What happens if $epsilon$ is a very small positive real number, say
$$0<epsilonllfracy_2-y_11+fraca_1a_2,?$$ Do something similar when $y_1>y_2$.
answered Jul 16 at 19:35
Batominovski
23.2k22777
answered Jul 16 at 19:35
Batominovski
23.2k22777
answered Jul 16 at 19:35
Batominovski
23.2k22777
answered Jul 16 at 19:35
Batominovski
23.2k22777
23.2k22777
add a comment |Â
add a comment |Â
up vote
0
down vote
Generalizing and rephrasing slightly, we have the following optimization problem in $mathrm x in mathbb R^n$
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x leq bendarray$$
where vector $mathrm a in mathbb R^n$ has no zero entries. There are two cases to consider:
If the origin is in the feasible region, then the minimum is attained at the origin.
If the origin is not in the feasible region, then the minimum is attained at its boundary.
Hence, in the latter case, we have a least-norm problem in the $infty$-norm
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x = bendarray$$
In $mathbb R^2$, the feasible region of this least-norm problem is a line that is neither vertical nor horizontal (due to the restrictions on vector $mathrm a in mathbb R^2$). We would like to find the point on this line that is closest to the origin in the $infty$-norm. Since the level sets of $| mathrm x |_infty$ are squares centered at the origin, then the minimizer is a square's vertex and, thus, its entries have the same absolute value.
[ image source ]
answered Jul 16 at 20:11
Rodrigo de Azevedo
12.5k41751
add a comment |Â
up vote
0
down vote
Generalizing and rephrasing slightly, we have the following optimization problem in $mathrm x in mathbb R^n$
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x leq bendarray$$
where vector $mathrm a in mathbb R^n$ has no zero entries. There are two cases to consider:
If the origin is in the feasible region, then the minimum is attained at the origin.
If the origin is not in the feasible region, then the minimum is attained at its boundary.
Hence, in the latter case, we have a least-norm problem in the $infty$-norm
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x = bendarray$$
In $mathbb R^2$, the feasible region of this least-norm problem is a line that is neither vertical nor horizontal (due to the restrictions on vector $mathrm a in mathbb R^2$). We would like to find the point on this line that is closest to the origin in the $infty$-norm. Since the level sets of $| mathrm x |_infty$ are squares centered at the origin, then the minimizer is a square's vertex and, thus, its entries have the same absolute value.
[ image source ]
answered Jul 16 at 20:11
Rodrigo de Azevedo
12.5k41751
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Generalizing and rephrasing slightly, we have the following optimization problem in $mathrm x in mathbb R^n$
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x leq bendarray$$
where vector $mathrm a in mathbb R^n$ has no zero entries. There are two cases to consider:
If the origin is in the feasible region, then the minimum is attained at the origin.
If the origin is not in the feasible region, then the minimum is attained at its boundary.
Hence, in the latter case, we have a least-norm problem in the $infty$-norm
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x = bendarray$$
In $mathbb R^2$, the feasible region of this least-norm problem is a line that is neither vertical nor horizontal (due to the restrictions on vector $mathrm a in mathbb R^2$). We would like to find the point on this line that is closest to the origin in the $infty$-norm. Since the level sets of $| mathrm x |_infty$ are squares centered at the origin, then the minimizer is a square's vertex and, thus, its entries have the same absolute value.
[ image source ]
answered Jul 16 at 20:11
Rodrigo de Azevedo
12.5k41751
Generalizing and rephrasing slightly, we have the following optimization problem in $mathrm x in mathbb R^n$
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x leq bendarray$$
where vector $mathrm a in mathbb R^n$ has no zero entries. There are two cases to consider:
If the origin is in the feasible region, then the minimum is attained at the origin.
If the origin is not in the feasible region, then the minimum is attained at its boundary.
Hence, in the latter case, we have a least-norm problem in the $infty$-norm
$$beginarrayll textminimize & | mathrm x |_infty\ textsubject to & mathrm a^top mathrm x = bendarray$$
In $mathbb R^2$, the feasible region of this least-norm problem is a line that is neither vertical nor horizontal (due to the restrictions on vector $mathrm a in mathbb R^2$). We would like to find the point on this line that is closest to the origin in the $infty$-norm. Since the level sets of $| mathrm x |_infty$ are squares centered at the origin, then the minimizer is a square's vertex and, thus, its entries have the same absolute value.
[ image source ]
answered Jul 16 at 20:11
Rodrigo de Azevedo
12.5k41751
edited Jul 16 at 20:44
answered Jul 16 at 20:11
Rodrigo de Azevedo
12.5k41751
answered Jul 16 at 20:11
Rodrigo de Azevedo
12.5k41751
answered Jul 16 at 20:11
Rodrigo de Azevedo
12.5k41751
12.5k41751
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853747%2fminimize-fx-max-x-1-x-2-subject-to-gx-a-1x-1a-2x-2b-leq-0%23new-answer', 'question_page');
);
Post as a guest
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
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
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