1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Hans. I guess a sufficient condition for interior solution will be: $\sum_j b_j \log(a_j/b_j)-(\sum_j b_j)\log(a_i/b_i)<x$, for all $i$. $\endgroup$ – Bravo Apr 2 '15 at 14:40
  • 1
    $\begingroup$ @Bravo - I think the inequality should be $>x$, not $<x$. Otherwise I agree. $\endgroup$ – Hans Engler Apr 2 '15 at 20:03
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I know that, but how is the minimum dependent on $a_i$s and $b_i$s? $\endgroup$ – Bravo Apr 2 '15 at 13:03

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.