4
$\begingroup$

Given $x_5 \geq x_4 \geq x_3 \geq x_2 \geq x_1 \geq 0$, solve the following optimization problem in $p_1, p_2,\dots, p_5$.

$$\max p_1p_2p_3p_4p_5$$

subject to:

$$p_1 x_1 + p_2 (x_2 - x_1) + p_3(x_3-x_2) + p_4(x_4-x_3)+p_5(x_5-x_4) = 1 $$ $$0\leq p_5 \leq p_4 \leq p_3 \leq p_2 \leq p_1$$

Is there a closed form solution to this problem? I am not sure how to go about approaching it.

$\endgroup$
4
+50
$\begingroup$

With the help of the slack variables $\epsilon_i$ and calling

$$ L(p,\mu,\epsilon,\lambda)= p_1 p_2 p_3 p_4 p_5+\mu _5 \left(p_1-p_2-\epsilon _5^2\right)+\mu _4 \left(p_2-p_3-\epsilon _4^2\right)+\mu _3 \left(p_3-p_4-\epsilon _3^2\right)+\mu _2 \left(p_4-p_5-\epsilon _2^2\right)+\mu _1 \left(p_5-\epsilon _1^2\right)+\lambda \left(p_1 x_1+p_2 \left(x_2-x_1\right)+p_3 \left(x_3-x_2\right)+p_4 \left(x_4-x_3\right)+p_5 \left(x_5-x_4\right)-1\right) $$

and solving the sationary conditions

$$ \nabla L = 0 $$

we obtain a set of solutions jointly with a set of conditions $\epsilon_i^2\ge 0$ to qualify those solutions. To be feasible the solution requires that $\epsilon_i^2\ge 0$ Also when $\epsilon_i^2 = 0$ it means that the corresponding restriction is active.

Due to the length of the symbolic response, we leave a script in MATHEMATICA that summarizes the results. There are sixteen non trivial solutions in res0 with structure $\{p_i,\epsilon_i^2,p_1p_2p_3p_4p_5\}$

n = 5;
X = Table[Subscript[x, k], {k, 1, n}];
P = Table[Subscript[p, k], {k, 1, n}];
EE = Table[Subscript[epsilon, k], {k, 1, n}];
M = Table[Subscript[mu, k], {k, 1, n}];
vars = Join[Join[Join[P, M], EE], {lambda}]
prod = Product[P[[k]], {k, 1, n}]
L = prod
L += lambda (Sum[P[[k]] (X[[k]] - X[[k - 1]]), {k, 2, n}] + P[[1]] X[[1]] - 1)
L += Sum[M[[k]] (P[[n - k + 1]] - P[[n - k + 2]] + EE[[k]]^2), {k, 2, n}] + M[[1]] (P[[n]] - EE[[1]]^2)
grad = Grad[L, vars]
equs = Thread[grad == 0];
E2 = EE^2;
results = Join[Join[P, E2], {prod}];
sols = Quiet[Solve[equs, vars]];
results0 = results /. sols // FullSimplify;
For[i = 1; res = {}, i <= Length[results0], i++,
  If[NumberQ[results0[[i]][[2 n + 1]]] == False, AppendTo[res,results0[[i]]]]
]
res0 = Union[res];
res0 // MatrixForm

Results for $n = 3$

$$ \left[ \begin{array}{ccccccc} p_1&p_2&p_3&\epsilon_1^2&\epsilon_2^2&\epsilon_3^2&p_1p_2p_3\\ \frac{1}{3 x_1} & \frac{1}{3 \left(x_2-x_1\right)} & \frac{1}{3 \left(x_3-x_2\right)} & \frac{1}{3 \left(x_3-x_2\right)} & \frac{1}{3 x_2-3 x_3}+\frac{1}{3 \left(x_2-x_1\right)} & \frac{1}{3} \left(\frac{1}{x_1-x_2}+\frac{1}{x_1}\right) & \frac{1}{27 \left(x_1^2-x_1 x_2\right) \left(x_2-x_3\right)} \\ \frac{1}{3 x_1} & \frac{2}{3 \left(x_3-x_1\right)} & \frac{2}{3 \left(x_3-x_1\right)} & \frac{2}{3 \left(x_3-x_1\right)} & 0 & \frac{1}{3} \left(\frac{2}{x_1-x_3}+\frac{1}{x_1}\right) & \frac{4}{27 x_1 \left(x_1-x_3\right){}^2} \\ \frac{2}{3 x_2} & \frac{2}{3 x_2} & \frac{1}{3 \left(x_3-x_2\right)} & \frac{1}{3 \left(x_3-x_2\right)} & \frac{1}{3 x_2-3 x_3}+\frac{2}{3 x_2} & 0 & \frac{4}{27 x_2^2 \left(x_3-x_2\right)} \\ \frac{1}{x_3} & \frac{1}{x_3} & \frac{1}{x_3} & \frac{1}{x_3} & 0 & 0 & \frac{1}{x_3^3} \\ \end{array} \right] $$

Results for $n = 4$

$$ \left[ \begin{array}{ccccccccc} p_1 & p_2 & p_3 & p_4 & \epsilon_1^2&\epsilon_2^2&\epsilon_3^2&\epsilon_4^2&p_1p_2p_3p_4\\ \frac{1}{4 x_1} & \frac{1}{4 \left(x_2-x_1\right)} & \frac{1}{4 \left(x_3-x_2\right)} & \frac{1}{4 \left(x_4-x_3\right)} & \frac{1}{4 \left(x_4-x_3\right)} & \frac{1}{4 x_3-4 x_4}+\frac{1}{4 \left(x_3-x_2\right)} & \frac{1}{4 x_2-4 x_3}+\frac{1}{4 \left(x_2-x_1\right)} & \frac{1}{4} \left(\frac{1}{x_1-x_2}+\frac{1}{x_1}\right) & -\frac{1}{256 \left(x_1^2-x_1 x_2\right) \left(x_2-x_3\right) \left(x_3-x_4\right)} \\ \frac{1}{4 x_1} & \frac{1}{4 \left(x_2-x_1\right)} & \frac{1}{2 \left(x_4-x_2\right)} & \frac{1}{2 \left(x_4-x_2\right)} & \frac{1}{2 \left(x_4-x_2\right)} & 0 & \frac{1}{2 x_2-2 x_4}+\frac{1}{4 \left(x_2-x_1\right)} & \frac{1}{4} \left(\frac{1}{x_1-x_2}+\frac{1}{x_1}\right) & -\frac{1}{64 x_1 \left(x_1-x_2\right) \left(x_2-x_4\right){}^2} \\ \frac{1}{4 x_1} & \frac{1}{2 \left(x_3-x_1\right)} & \frac{1}{2 \left(x_3-x_1\right)} & \frac{1}{4 \left(x_4-x_3\right)} & \frac{1}{4 \left(x_4-x_3\right)} & \frac{1}{4 x_3-4 x_4}+\frac{1}{2 \left(x_3-x_1\right)} & 0 & \frac{1}{4} \left(\frac{2}{x_1-x_3}+\frac{1}{x_1}\right) & \frac{1}{64 x_1 \left(x_1-x_3\right){}^2 \left(x_4-x_3\right)} \\ \frac{1}{4 x_1} & \frac{3}{4 \left(x_4-x_1\right)} & \frac{3}{4 \left(x_4-x_1\right)} & \frac{3}{4 \left(x_4-x_1\right)} & \frac{3}{4 \left(x_4-x_1\right)} & 0 & 0 & \frac{1}{4} \left(\frac{3}{x_1-x_4}+\frac{1}{x_1}\right) & \frac{27}{256 x_1 \left(x_4-x_1\right){}^3} \\ \frac{1}{2 x_2} & \frac{1}{2 x_2} & \frac{1}{4 \left(x_3-x_2\right)} & \frac{1}{4 \left(x_4-x_3\right)} & \frac{1}{4 \left(x_4-x_3\right)} & \frac{1}{4 x_3-4 x_4}+\frac{1}{4 \left(x_3-x_2\right)} & \frac{1}{4 x_2-4 x_3}+\frac{1}{2 x_2} & 0 & \frac{1}{64 x_2^2 \left(x_2-x_3\right) \left(x_3-x_4\right)} \\ \frac{1}{2 x_2} & \frac{1}{2 x_2} & \frac{1}{2 \left(x_4-x_2\right)} & \frac{1}{2 \left(x_4-x_2\right)} & \frac{1}{2 \left(x_4-x_2\right)} & 0 & \frac{1}{2} \left(\frac{1}{x_2-x_4}+\frac{1}{x_2}\right) & 0 & \frac{1}{16 x_2^2 \left(x_2-x_4\right){}^2} \\ \frac{3}{4 x_3} & \frac{3}{4 x_3} & \frac{3}{4 x_3} & \frac{1}{4 \left(x_4-x_3\right)} & \frac{1}{4 \left(x_4-x_3\right)} & \frac{1}{4 x_3-4 x_4}+\frac{3}{4 x_3} & 0 & 0 & \frac{27}{256 x_3^3 \left(x_4-x_3\right)} \\ \frac{1}{x_4} & \frac{1}{x_4} & \frac{1}{x_4} & \frac{1}{x_4} & \frac{1}{x_4} & 0 & 0 & 0 & \frac{1}{x_4^4} \\\end{array} \right] $$

and for $n = 5$

$$ \left[ \begin{array}{ccccccccccc} p_1&p_2&p_3&p_4&p_5&\epsilon_1^2&\epsilon_2^2&\epsilon_3^2&\epsilon_4^2&\epsilon_5^2&p_1p_2p_3p_4p_5\\ \frac{1}{5 x_1} & -\frac{1}{5 \left(x_1-x_2\right)} & -\frac{1}{5 \left(x_2-x_3\right)} & -\frac{1}{5 \left(x_3-x_4\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & \frac{x_3-2 x_4+x_5}{5 \left(x_3-x_4\right) \left(x_4-x_5\right)} & \frac{x_2-2 x_3+x_4}{5 \left(x_2-x_3\right) \left(x_3-x_4\right)} & \frac{x_1-2 x_2+x_3}{5 \left(x_1-x_2\right) \left(x_2-x_3\right)} & \frac{2 x_1-x_2}{5 x_1 \left(x_1-x_2\right)} & \frac{1}{3125 x_1 \left(x_1-x_2\right) \left(x_2-x_3\right) \left(x_3-x_4\right) \left(x_4-x_5\right)} \\ \frac{1}{5 x_1} & -\frac{1}{5 \left(x_1-x_2\right)} & -\frac{1}{5 \left(x_2-x_3\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & 0 & \frac{2 x_2-3 x_3+x_5}{5 \left(x_2-x_3\right) \left(x_3-x_5\right)} & \frac{x_1-2 x_2+x_3}{5 \left(x_1-x_2\right) \left(x_2-x_3\right)} & \frac{2 x_1-x_2}{5 x_1 \left(x_1-x_2\right)} & \frac{4}{3125 x_1 \left(x_1-x_2\right) \left(x_2-x_3\right) \left(x_3-x_5\right){}^2} \\ \frac{1}{5 x_1} & -\frac{1}{5 \left(x_1-x_2\right)} & -\frac{2}{5 \left(x_2-x_4\right)} & -\frac{2}{5 \left(x_2-x_4\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & \frac{x_2-3 x_4+2 x_5}{5 \left(x_2-x_4\right) \left(x_4-x_5\right)} & 0 & \frac{2 x_1-3 x_2+x_4}{5 \left(x_1-x_2\right) \left(x_2-x_4\right)} & \frac{2 x_1-x_2}{5 x_1 \left(x_1-x_2\right)} & \frac{4}{3125 x_1 \left(x_1-x_2\right) \left(x_2-x_4\right){}^2 \left(x_4-x_5\right)} \\ \frac{1}{5 x_1} & -\frac{1}{5 \left(x_1-x_2\right)} & -\frac{3}{5 \left(x_2-x_5\right)} & -\frac{3}{5 \left(x_2-x_5\right)} & -\frac{3}{5 \left(x_2-x_5\right)} & -\frac{3}{5 \left(x_2-x_5\right)} & 0 & 0 & \frac{3 x_1-4 x_2+x_5}{5 \left(x_1-x_2\right) \left(x_2-x_5\right)} & \frac{2 x_1-x_2}{5 x_1 \left(x_1-x_2\right)} & \frac{27}{3125 x_1 \left(x_1-x_2\right) \left(x_2-x_5\right){}^3} \\ \frac{1}{5 x_1} & -\frac{2}{5 \left(x_1-x_3\right)} & -\frac{2}{5 \left(x_1-x_3\right)} & -\frac{1}{5 \left(x_3-x_4\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & \frac{x_3-2 x_4+x_5}{5 \left(x_3-x_4\right) \left(x_4-x_5\right)} & \frac{x_1-3 x_3+2 x_4}{5 \left(x_1-x_3\right) \left(x_3-x_4\right)} & 0 & \frac{3 x_1-x_3}{5 x_1 \left(x_1-x_3\right)} & \frac{4}{3125 x_1 \left(x_1-x_3\right){}^2 \left(x_3-x_4\right) \left(x_4-x_5\right)} \\ \frac{1}{5 x_1} & -\frac{2}{5 \left(x_1-x_3\right)} & -\frac{2}{5 \left(x_1-x_3\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & 0 & \frac{2 \left(x_1-2 x_3+x_5\right)}{5 \left(x_1-x_3\right) \left(x_3-x_5\right)} & 0 & \frac{3 x_1-x_3}{5 x_1 \left(x_1-x_3\right)} & \frac{16}{3125 x_1 \left(x_1-x_3\right){}^2 \left(x_3-x_5\right){}^2} \\ \frac{1}{5 x_1} & -\frac{3}{5 \left(x_1-x_4\right)} & -\frac{3}{5 \left(x_1-x_4\right)} & -\frac{3}{5 \left(x_1-x_4\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & \frac{x_1-4 x_4+3 x_5}{5 \left(x_1-x_4\right) \left(x_4-x_5\right)} & 0 & 0 & \frac{4 x_1-x_4}{5 x_1 \left(x_1-x_4\right)} & \frac{27}{3125 x_1 \left(x_1-x_4\right){}^3 \left(x_4-x_5\right)} \\ \frac{1}{5 x_1} & -\frac{4}{5 \left(x_1-x_5\right)} & -\frac{4}{5 \left(x_1-x_5\right)} & -\frac{4}{5 \left(x_1-x_5\right)} & -\frac{4}{5 \left(x_1-x_5\right)} & -\frac{4}{5 \left(x_1-x_5\right)} & 0 & 0 & 0 & \frac{5 x_1-x_5}{5 x_1 \left(x_1-x_5\right)} & \frac{256}{3125 x_1 \left(x_1-x_5\right){}^4} \\ \frac{2}{5 x_2} & \frac{2}{5 x_2} & -\frac{1}{5 \left(x_2-x_3\right)} & -\frac{1}{5 \left(x_3-x_4\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & \frac{x_3-2 x_4+x_5}{5 \left(x_3-x_4\right) \left(x_4-x_5\right)} & \frac{x_2-2 x_3+x_4}{5 \left(x_2-x_3\right) \left(x_3-x_4\right)} & \frac{3 x_2-2 x_3}{5 x_2 \left(x_2-x_3\right)} & 0 & -\frac{4}{3125 x_2^2 \left(x_2-x_3\right) \left(x_3-x_4\right) \left(x_4-x_5\right)} \\ \frac{2}{5 x_2} & \frac{2}{5 x_2} & -\frac{1}{5 \left(x_2-x_3\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & 0 & \frac{2 x_2-3 x_3+x_5}{5 \left(x_2-x_3\right) \left(x_3-x_5\right)} & \frac{3 x_2-2 x_3}{5 x_2 \left(x_2-x_3\right)} & 0 & -\frac{16}{3125 x_2^2 \left(x_2-x_3\right) \left(x_3-x_5\right){}^2} \\ \frac{2}{5 x_2} & \frac{2}{5 x_2} & -\frac{2}{5 \left(x_2-x_4\right)} & -\frac{2}{5 \left(x_2-x_4\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & \frac{x_2-3 x_4+2 x_5}{5 \left(x_2-x_4\right) \left(x_4-x_5\right)} & 0 & \frac{2 \left(2 x_2-x_4\right)}{5 x_2 \left(x_2-x_4\right)} & 0 & -\frac{16}{3125 x_2^2 \left(x_2-x_4\right){}^2 \left(x_4-x_5\right)} \\ \frac{2}{5 x_2} & \frac{2}{5 x_2} & -\frac{3}{5 \left(x_2-x_5\right)} & -\frac{3}{5 \left(x_2-x_5\right)} & -\frac{3}{5 \left(x_2-x_5\right)} & -\frac{3}{5 \left(x_2-x_5\right)} & 0 & 0 & \frac{5 x_2-2 x_5}{5 x_2 \left(x_2-x_5\right)} & 0 & -\frac{108}{3125 x_2^2 \left(x_2-x_5\right){}^3} \\ \frac{3}{5 x_3} & \frac{3}{5 x_3} & \frac{3}{5 x_3} & -\frac{1}{5 \left(x_3-x_4\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & \frac{x_3-2 x_4+x_5}{5 \left(x_3-x_4\right) \left(x_4-x_5\right)} & \frac{4 x_3-3 x_4}{5 x_3 \left(x_3-x_4\right)} & 0 & 0 & \frac{27}{3125 x_3^3 \left(x_3-x_4\right) \left(x_4-x_5\right)} \\ \frac{3}{5 x_3} & \frac{3}{5 x_3} & \frac{3}{5 x_3} & -\frac{2}{5 \left(x_3-x_5\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & -\frac{2}{5 \left(x_3-x_5\right)} & 0 & \frac{5 x_3-3 x_5}{5 x_3 \left(x_3-x_5\right)} & 0 & 0 & \frac{108}{3125 x_3^3 \left(x_3-x_5\right){}^2} \\ \frac{4}{5 x_4} & \frac{4}{5 x_4} & \frac{4}{5 x_4} & \frac{4}{5 x_4} & -\frac{1}{5 \left(x_4-x_5\right)} & -\frac{1}{5 \left(x_4-x_5\right)} & \frac{5 x_4-4 x_5}{5 x_4 \left(x_4-x_5\right)} & 0 & 0 & 0 & -\frac{256}{3125 x_4^4 \left(x_4-x_5\right)} \\ \frac{1}{x_5} & \frac{1}{x_5} & \frac{1}{x_5} & \frac{1}{x_5} & \frac{1}{x_5} & \frac{1}{x_5} & 0 & 0 & 0 & 0 & \frac{1}{x_5^5} \\ \end{array} \right] $$

$\endgroup$
  • 1
    $\begingroup$ Is there any way to summarize this at all for those of us without Mathematica? Perhaps give the results for $n=3$ or $n=4$? I’m curious to see the various cases. $\endgroup$ – David M. Apr 3 '19 at 3:23
  • $\begingroup$ Please—I should add! $\endgroup$ – David M. Apr 3 '19 at 3:35
  • $\begingroup$ It would be great if someone could translate this into an open source programming language. Maybe Python + sympy for example? $\endgroup$ – Anush Apr 3 '19 at 5:52
  • $\begingroup$ @DavidM. Added the results for $n = 3,4,5$ $\endgroup$ – Cesareo Apr 3 '19 at 8:05
  • $\begingroup$ Thanks! If I'm interpreting the results correctly, the $n=5$ table doesn't include the case covered in my answer (i.e. that $p_i=1/x_5$ for all $i=1,\dots,5$). Am I missing something? $\endgroup$ – David M. Apr 3 '19 at 14:17
2
$\begingroup$

Well you could try with Am-Gm inequality:

$$ 5\sqrt[5]{p_1p_2...p_5x_1(x_2-x_1)...(x_5-x_4)}\leq 1$$

So $$p_1p_2...p_5 \leq {1\over 5^5x_1(x_2-x_1)...(x_5-x_4)}$$

and this value is achivable if $$ p_1 ={1\over 5x_1}$$

$$ p_2 ={1\over 5(x_2-x_1)}$$ $$ p_3 ={1\over 5(x_3-x_2)}$$ $$...$$

$\endgroup$
  • 1
    $\begingroup$ I am not sure this satisfies the ordering constraints on the $p_i$ does it? $\endgroup$ – Arthur Mar 29 '19 at 20:38
2
$\begingroup$

This answer addresses the case when $$ \frac{5}{x_5}\geq\max_{i=1,\dots,4}\big\{\frac{i}{x_i}\big\}. $$ In this case, the solution using the AM-GM inequality fails to satisfy the ordering constraint. There are still other cases to be considered, for example, $x=(1,\;3,\;4.75,\;8.75,\;13.75)$ which produces the solution $p_1=1/5$, $p_2=p_3=8/75$, $p_4=1/20$ and $p_5=1/25$ (computed this solution numerically).


While the other answers are clever, I don't believe that they respect the ordering constraint $0\leq{p_5}\leq\dots\leq{p_1}$. My proposed solution is found using the KKT conditions. (Note: I assume $x_i>0$ for all $i$--the case when $x_i=0$ should following from a similar technique to what I use below).

Answer: $p_1=p_2=p_3=p_4=p_5=1/x_5$.

Solution: By taking the logarithm of the objective function, the given optimization problem can be formulated as a convex optimization problem in standard form: $$ \begin{array}{rl} \min & -\log(p_1)-\log(p_2)-\cdots-\log(p_5)\\ \text{s.t.} & p_1x_1+p_2(x_2-x_1)+p_3(x_3-x_2)+p_4(x_4-x_3)+p_5(x_5-x_4)-1=0\\ &p_2-p_1\leq0\\ &p_3-p_2\leq0\\ &p_4-p_3\leq0\\ &p_5-p_4\leq0\\ &\hspace{12pt}-p_5\leq0 \end{array} $$ Associate the multiplier $\lambda\in\mathbb{R}$ with the equality constraint, and $\mu_i\geq0$ with the remaining constraints $i=1,\dots,5$. The stationarity conditions for this optimization problem are \begin{align*} \frac{1}{p_1}&=\lambda{x_1}-\mu_1\\ \frac{1}{p_2}&=\lambda(x_2-x_1)+(\mu_1-\mu_2)\\ \frac{1}{p_3}&=\lambda(x_3-x_2)+(\mu_2-\mu_3)\\ \frac{1}{p_4}&=\lambda(x_4-x_3)+(\mu_3-\mu_4)\\ \frac{1}{p_5}&=\lambda(x_5-x_4)+(\mu_4-\mu_5)\\ \end{align*} A solution to the above system is \begin{align*} p_i&=\frac{1}{x_5}&&\text{for }i=1,\dots,5\\ \mu_i&=5x_i-i\cdot{x_5}&&\text{for }i=1,\dots,5\\ \lambda&=5 \end{align*} It's easy to verify that the other KKT conditions are satisfied (complementary slackness, etc.), and to check that the problem satisfies the Slater condition. Hence, we conclude that the proposed point is indeed globally optimal for this problem.

$\endgroup$
  • $\begingroup$ This is intriguing if true. However, is your answer compatible with math.stackexchange.com/a/3167600/387242 ? $\endgroup$ – Arthur Mar 31 '19 at 16:09
  • $\begingroup$ @Arthur Actually yes I must have made an assumption somewhere--forgive me, I did this rather quickly. In the case when the $x$s are spaced appropriately, Maria Mazura's answer is correct. My answer must make an additional assumption--will look over soon, hopefully. $\endgroup$ – David M. Mar 31 '19 at 16:10
  • $\begingroup$ Thanks so much! You are right of course that the other answers are ignoring the ordering constraint. $\endgroup$ – Arthur Mar 31 '19 at 16:11
  • 1
    $\begingroup$ @Arthur Indeed I made a mistake when checking the complementary slackness conditions. My solution addresses a special case (analogous to the case when $2x_1>x_2$ in the linked answer). I think there are more cases that need to be considered here. $\endgroup$ – David M. Mar 31 '19 at 16:47
0
$\begingroup$

Letting $y_1 = x_1$ and $y_i =x_i-x_{i-1}$ for $i>1$, this is $\sum_{i=1}^n p_iy_i =1 $ with $n=5, y_i \ge 0$.

As Maria Mazur suggested, using AM-GM gives $\prod_{i=1}^n p_iy_i \le (\frac1{n}\sum_{i=1}^n p_iy_i)^n =\frac1{n^n} $ with equality iff $p_iy_i =\frac1{n} $ or $p_i = \frac1{ny_i} $.

Note that there may be a problem if some $y_i = 0$; in this case, $p_i$ can be any value. Perhaps the conditions should be $y_i > 0$.

(Added after a comment)

Regarding the requirement that $p_{i+1} \le p_i$:

This will hold if $y_{i+1} \ge y_i$.

If not, perhaps use the same idea of defining $q_i = p_i-p_{i+1} $, rewriting in terms of the $q_i$, and requiring $q_i \ge 0$.

$\endgroup$
  • 1
    $\begingroup$ I think something has to happen to make sure the $p_i$ satisfy the order constraint. $\endgroup$ – Arthur Mar 29 '19 at 21:53
  • $\begingroup$ You are right - I overlooked that. I'll add something about it. $\endgroup$ – marty cohen Mar 29 '19 at 22:36

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.