Mixing
Rational point at optimum
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
$$beginarrayll textmaximize & displaystyleprod_i=1^r P_i\ textsubject to & x_1 + x_2 + dots + x_n = 1\ & x_1, x_2, dots, x_n geq 0endarray$$
where each $P_i$ is a sum of some $x_k$'s. Is it true that we can always choose all $x_i$'s to be rational so as to maximize this expression?
(It is not true that the $x_i$'s must always be rational. For example, if $n=2$ and the expression is just $x_1+x_2$, then we can choose $x_1=a$ and $x_2=1-a$ for any $a$. But we can also choose $a$ to be rational.)
Also, is it true that each $P_i$ will be at least $frac 1r$ at the optimum?
inequality optimization nonlinear-optimization rational-numbers
edited Aug 1 at 21:57
Rodrigo de Azevedo
12.6k41751
asked Jul 30 at 12:14
nan
456213
add a comment |Â
up vote
1
down vote
favorite
$$beginarrayll textmaximize & displaystyleprod_i=1^r P_i\ textsubject to & x_1 + x_2 + dots + x_n = 1\ & x_1, x_2, dots, x_n geq 0endarray$$
where each $P_i$ is a sum of some $x_k$'s. Is it true that we can always choose all $x_i$'s to be rational so as to maximize this expression?
(It is not true that the $x_i$'s must always be rational. For example, if $n=2$ and the expression is just $x_1+x_2$, then we can choose $x_1=a$ and $x_2=1-a$ for any $a$. But we can also choose $a$ to be rational.)
Also, is it true that each $P_i$ will be at least $frac 1r$ at the optimum?
inequality optimization nonlinear-optimization rational-numbers
edited Aug 1 at 21:57
Rodrigo de Azevedo
12.6k41751
asked Jul 30 at 12:14
nan
456213
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
$$beginarrayll textmaximize & displaystyleprod_i=1^r P_i\ textsubject to & x_1 + x_2 + dots + x_n = 1\ & x_1, x_2, dots, x_n geq 0endarray$$
where each $P_i$ is a sum of some $x_k$'s. Is it true that we can always choose all $x_i$'s to be rational so as to maximize this expression?
(It is not true that the $x_i$'s must always be rational. For example, if $n=2$ and the expression is just $x_1+x_2$, then we can choose $x_1=a$ and $x_2=1-a$ for any $a$. But we can also choose $a$ to be rational.)
Also, is it true that each $P_i$ will be at least $frac 1r$ at the optimum?
inequality optimization nonlinear-optimization rational-numbers
edited Aug 1 at 21:57
Rodrigo de Azevedo
12.6k41751
asked Jul 30 at 12:14
nan
456213
$$beginarrayll textmaximize & displaystyleprod_i=1^r P_i\ textsubject to & x_1 + x_2 + dots + x_n = 1\ & x_1, x_2, dots, x_n geq 0endarray$$
where each $P_i$ is a sum of some $x_k$'s. Is it true that we can always choose all $x_i$'s to be rational so as to maximize this expression?
(It is not true that the $x_i$'s must always be rational. For example, if $n=2$ and the expression is just $x_1+x_2$, then we can choose $x_1=a$ and $x_2=1-a$ for any $a$. But we can also choose $a$ to be rational.)
Also, is it true that each $P_i$ will be at least $frac 1r$ at the optimum?
inequality optimization nonlinear-optimization rational-numbers
edited Aug 1 at 21:57
Rodrigo de Azevedo
12.6k41751
asked Jul 30 at 12:14
nan
456213
edited Aug 1 at 21:57
Rodrigo de Azevedo
12.6k41751
edited Aug 1 at 21:57
Rodrigo de Azevedo
12.6k41751
edited Aug 1 at 21:57
Rodrigo de Azevedo
12.6k41751
12.6k41751
asked Jul 30 at 12:14
nan
456213
asked Jul 30 at 12:14
nan
456213
asked Jul 30 at 12:14
nan
456213
456213
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
It is not true that $P_i geq 1/n$ at the optimum. Take $P_1=x_1$ and $P_i=x_2$ for $i geq 2$. The objective is then $x_1 x_2^r-1 = (1-x_2)x_2^r-1$. This is maximized at $x_2=(r-1)/r$, so $P_1 = 1/r$, which for $r > 2$ is less than 0.5.
Maximizing the product of $P_i$ is equivalent to maximizing the sum of the logarithm of $P_i$, which is concave:
$$max_x left sum_k log(P_k(x)) : e^T x = 1, x geq 0 right$$
Since this problem is convex, the KKT conditions are necessary and sufficient:
$$sum_k fracP'_k(x)P_k(x)+lambda + mu_i = 0 text (stationarity)$$
$$lambda(e^Tx-1)=0, ; mu_i x_i = 0 text (complementary slackness)$$
$$sum_i x_i=1, ; x geq 0 text (primal feasibility)$$
$$mu geq 0 text (dual feasibility)$$
where the derivative is taken with respect to $x_i$, so each $P'_k(x)$ is either $0$ or $1$. This essentially the same as identifying a subset $S$ of the variables such that:
$$sum_k : x_i in P_k frac1P_k(x)+lambda = 0 quad forall i in S$$
$$sum_k : x_i in P_k frac1P_k(x)+lambda leq 0 quad forall i notin S$$
$$sum_i in S x_i = 1, ; x geq 0$$
where I abuse the notation $x_i in P_k$ to indicate that the sum $P_k$ contains $x_i$. I do not see why there is always a rational solution to these equations.
answered Jul 30 at 14:39
LinAlg
5,4111319
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
It is not true that $P_i geq 1/n$ at the optimum. Take $P_1=x_1$ and $P_i=x_2$ for $i geq 2$. The objective is then $x_1 x_2^r-1 = (1-x_2)x_2^r-1$. This is maximized at $x_2=(r-1)/r$, so $P_1 = 1/r$, which for $r > 2$ is less than 0.5.
Maximizing the product of $P_i$ is equivalent to maximizing the sum of the logarithm of $P_i$, which is concave:
$$max_x left sum_k log(P_k(x)) : e^T x = 1, x geq 0 right$$
Since this problem is convex, the KKT conditions are necessary and sufficient:
$$sum_k fracP'_k(x)P_k(x)+lambda + mu_i = 0 text (stationarity)$$
$$lambda(e^Tx-1)=0, ; mu_i x_i = 0 text (complementary slackness)$$
$$sum_i x_i=1, ; x geq 0 text (primal feasibility)$$
$$mu geq 0 text (dual feasibility)$$
where the derivative is taken with respect to $x_i$, so each $P'_k(x)$ is either $0$ or $1$. This essentially the same as identifying a subset $S$ of the variables such that:
$$sum_k : x_i in P_k frac1P_k(x)+lambda = 0 quad forall i in S$$
$$sum_k : x_i in P_k frac1P_k(x)+lambda leq 0 quad forall i notin S$$
$$sum_i in S x_i = 1, ; x geq 0$$
where I abuse the notation $x_i in P_k$ to indicate that the sum $P_k$ contains $x_i$. I do not see why there is always a rational solution to these equations.
answered Jul 30 at 14:39
LinAlg
5,4111319
add a comment |Â
up vote
0
down vote
It is not true that $P_i geq 1/n$ at the optimum. Take $P_1=x_1$ and $P_i=x_2$ for $i geq 2$. The objective is then $x_1 x_2^r-1 = (1-x_2)x_2^r-1$. This is maximized at $x_2=(r-1)/r$, so $P_1 = 1/r$, which for $r > 2$ is less than 0.5.
Maximizing the product of $P_i$ is equivalent to maximizing the sum of the logarithm of $P_i$, which is concave:
$$max_x left sum_k log(P_k(x)) : e^T x = 1, x geq 0 right$$
Since this problem is convex, the KKT conditions are necessary and sufficient:
$$sum_k fracP'_k(x)P_k(x)+lambda + mu_i = 0 text (stationarity)$$
$$lambda(e^Tx-1)=0, ; mu_i x_i = 0 text (complementary slackness)$$
$$sum_i x_i=1, ; x geq 0 text (primal feasibility)$$
$$mu geq 0 text (dual feasibility)$$
where the derivative is taken with respect to $x_i$, so each $P'_k(x)$ is either $0$ or $1$. This essentially the same as identifying a subset $S$ of the variables such that:
$$sum_k : x_i in P_k frac1P_k(x)+lambda = 0 quad forall i in S$$
$$sum_k : x_i in P_k frac1P_k(x)+lambda leq 0 quad forall i notin S$$
$$sum_i in S x_i = 1, ; x geq 0$$
where I abuse the notation $x_i in P_k$ to indicate that the sum $P_k$ contains $x_i$. I do not see why there is always a rational solution to these equations.
answered Jul 30 at 14:39
LinAlg
5,4111319
add a comment |Â
up vote
0
down vote
up vote
0
down vote
It is not true that $P_i geq 1/n$ at the optimum. Take $P_1=x_1$ and $P_i=x_2$ for $i geq 2$. The objective is then $x_1 x_2^r-1 = (1-x_2)x_2^r-1$. This is maximized at $x_2=(r-1)/r$, so $P_1 = 1/r$, which for $r > 2$ is less than 0.5.
Maximizing the product of $P_i$ is equivalent to maximizing the sum of the logarithm of $P_i$, which is concave:
$$max_x left sum_k log(P_k(x)) : e^T x = 1, x geq 0 right$$
Since this problem is convex, the KKT conditions are necessary and sufficient:
$$sum_k fracP'_k(x)P_k(x)+lambda + mu_i = 0 text (stationarity)$$
$$lambda(e^Tx-1)=0, ; mu_i x_i = 0 text (complementary slackness)$$
$$sum_i x_i=1, ; x geq 0 text (primal feasibility)$$
$$mu geq 0 text (dual feasibility)$$
where the derivative is taken with respect to $x_i$, so each $P'_k(x)$ is either $0$ or $1$. This essentially the same as identifying a subset $S$ of the variables such that:
$$sum_k : x_i in P_k frac1P_k(x)+lambda = 0 quad forall i in S$$
$$sum_k : x_i in P_k frac1P_k(x)+lambda leq 0 quad forall i notin S$$
$$sum_i in S x_i = 1, ; x geq 0$$
where I abuse the notation $x_i in P_k$ to indicate that the sum $P_k$ contains $x_i$. I do not see why there is always a rational solution to these equations.
answered Jul 30 at 14:39
LinAlg
5,4111319
It is not true that $P_i geq 1/n$ at the optimum. Take $P_1=x_1$ and $P_i=x_2$ for $i geq 2$. The objective is then $x_1 x_2^r-1 = (1-x_2)x_2^r-1$. This is maximized at $x_2=(r-1)/r$, so $P_1 = 1/r$, which for $r > 2$ is less than 0.5.
Maximizing the product of $P_i$ is equivalent to maximizing the sum of the logarithm of $P_i$, which is concave:
$$max_x left sum_k log(P_k(x)) : e^T x = 1, x geq 0 right$$
Since this problem is convex, the KKT conditions are necessary and sufficient:
$$sum_k fracP'_k(x)P_k(x)+lambda + mu_i = 0 text (stationarity)$$
$$lambda(e^Tx-1)=0, ; mu_i x_i = 0 text (complementary slackness)$$
$$sum_i x_i=1, ; x geq 0 text (primal feasibility)$$
$$mu geq 0 text (dual feasibility)$$
where the derivative is taken with respect to $x_i$, so each $P'_k(x)$ is either $0$ or $1$. This essentially the same as identifying a subset $S$ of the variables such that:
$$sum_k : x_i in P_k frac1P_k(x)+lambda = 0 quad forall i in S$$
$$sum_k : x_i in P_k frac1P_k(x)+lambda leq 0 quad forall i notin S$$
$$sum_i in S x_i = 1, ; x geq 0$$
where I abuse the notation $x_i in P_k$ to indicate that the sum $P_k$ contains $x_i$. I do not see why there is always a rational solution to these equations.
answered Jul 30 at 14:39
LinAlg
5,4111319
answered Jul 30 at 14:39
LinAlg
5,4111319
answered Jul 30 at 14:39
LinAlg
5,4111319
answered Jul 30 at 14:39
LinAlg
5,4111319
5,4111319
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%2f2866954%2frational-point-at-optimum%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