-1

I just stumbled across the following optimization problem with boundary conditions:

$$\begin{array}{ll} \text{extremize} & \prod_i x_i\\ \text{subject to} & \sum_i x_i = 1\\ & x_i > 0\end{array}$$

How can I approach this problem?

Rodrigo de Azevedo
  • 1
Gilfoyle
  • 401

3 Answers3

2

Hint: Try using AM-GM rule i.e. $AM \geq GM$ $$\ \left(\prod_i x_i\right)^{1/n} \leq \frac{\sum_{i=1}^{n}x_i}{n} $$

Shiv Tavker
  • 1,612
  • 7
  • 19
1

Note that the strict positivity constraints $x_i>0$ are slack, because the point $1/N$ satisfies the constraints and gives a strictly positive value of the objective, while if any $x_i = 0$, the objective takes the value zero. So ignore those constraints.

Then, any strictly increasing transformation of a function has the same set of optimizers, so that if we take $\log()$ of the objective to get $$ \sum_{i=1}^N \log(x_i) $$ instead of the product things will be easier.

Now, substitute your constraint into your objective, as $x_1 = 1 - \sum_{i =2}^N x_i$ to get $$ \max_{x_2,...,x_N} \log\left(1 - \sum_{i=2}^N x_i \right) + \sum_{i=2}^N \log(x_i). $$ You could use a Lagrangian, but this gives the right answer without the extra work.

Now maximize with respect to each variable $x_k$, getting an FONC $$ -\dfrac{1}{1-\sum_{i=2}^N x_i} + \dfrac{1}{x_k} = 0. $$ Re-arrange a bit to get, for each $x_k$, $$ x_k = 1-\sum_{i=2, i \neq k}^N x_i - x_k, $$ or $$ 2x_k = 1-\sum_{i=2, i \neq k}^N x_i. $$ Take some other variable $x_j \neq x_i$, and rewrite the above conditions as $$ 2x_k = 1-\sum_{i=2, i \neq k,j}^N x_i - x_j. $$ $$ 2x_j = 1-\sum_{i=2, i \neq k, j}^N x_i - x_k. $$ and subtract to get $$ 2x_k - 2x_j = - x_j + x_k $$ or $$ x_k = x_j $$ at the optimum. So all the $x_i$'s have the same value at the optimum.

Now return to the FONC $$ 2x^* = 1-\sum_{i=2, i \neq k}^N x^* \rightarrow 2x^* = 1-(N-2) x^* $$ and solve to get $$ x^* = \dfrac{1}{N} $$ for each $i$.

0

Maybe look at a related lifted problem for the matrix $X$:

$\max_X \log\det(X)$ such that $\text{tr}(X)=1$, $X_{ii} > 0$, and $X_{ij}=0$.

Log of determinant is concave for symmetric positive definite matrices, and these constraints describe a subset of SPD matrices.

Another way to look at it is just think about the case where $x\in\mathbb{R}^2$. The constraints say that the point is in the positive orthant on the line $y = 1-x$. So the sup is $1/2$ and the inf is $0$. So I think in $\mathbb{R}^n$ the sup will be $1/n$ and the inf will be $0$.

2016applicant
  • 11