Is the optimum of this problem unique?

595 Views Asked by At

I have a convex optimisation problem:

$$\min_{x_i} \sum_{i=1}^N a_i \exp(-x_i/b_i)\quad\text{ s.t. }\sum_{i=1}^N x_i=x\text{ and } x_i\ge 0$$

The KKT conditions are: $$\lambda=\begin{cases} a_i/b_i \exp(- x_i/b_i) &\text{ if }a_i/b_i>\lambda \\ a_i/b_i+\mu_i &\text{ else }\end{cases},$$

where $\lambda>0$ and $\mu_i\ge 0$.

I am able to characterise the interior solution ($x_i>0\ \forall i$), but I am unable to see if the solution is unique and under what circumstances. What is the unique optimum for this problem and how is it dependent on the parameters?

2

There are 2 best solutions below

2
On BEST ANSWER

Since the set over which you are minimizing is compact, there exists a minimizer. Since the set is convex and the objective function is convex, the set of minimizers is convex.

The KKT conditions now tell you what the form of any minimizer must be: Either $x_i = 0$ or the numbers $a_i/b_i \exp(-x_i/b_i)$ must all equal the same value $\lambda> 0$. This doesn't prove uniqueness yet, but let's see further:

To find the minimizer, proceed as follows. Define $g_i(\lambda) = \max(0,- b_i \log (\frac{b_i \lambda}{a_i}))$ for $i = 1, \dots, N$. These functions are strictly decreasing for $\lambda < a_i/b_i$ and equal to 0 for $\lambda \ge a_i/b_i$. (I have simply solved each KKT condition for $x_i$.) Now consider the expression $$ F(\lambda) = \sum_{i=1}^N g_i(\lambda) -x. $$ This function is therefore strictly decreasing for $\lambda < \max_i \frac{a_i}{b_i}$ when it reaches the value $-x$. Also, $F(\lambda)$ is positive for $\lambda$ close to 0. Therefore, there is a unique $\lambda_0$ where $F(\lambda_0) = 0$. Set $$ \boxed{x_i = g_i(\lambda_0)}$$ and that is your solution. By this argument, the solution is unique.

I don't see how one can get a closed form solution, but your minimization problem has now been reduced to that of finding the zero of a well-defined scalar function. Moreover it shows how the solution changes as $x$ changes: For large $x>0$, all $x_i$ are positive. As $x$ decreases, all $x_i$ decrease as well (at different rates) until they hit 0 one after the other. For very small $x$, only a single $x_i$ is positive.

1
On

Hint: A strictly convex function has at most one (global) minimum.