$$\begin{array}{ll} \text{maximize} & \displaystyle\prod_{i=1}^r P_i\\ \text{subject to} & x_1 + x_2 + \dots + x_n = 1\\ & x_1, x_2, \dots, x_n \geq 0\end{array}$$

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?


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 \frac{P'_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} \frac{1}{P_k(x)}+\lambda = 0 \quad \forall i \in S$$ $$\sum_{k : x_i \in P_k} \frac{1}{P_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.


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.