# simple-looking non-convex optimization problem

I want to solve the following problem: Maximize $\sum_{i=1}^n\log(1+\lambda_i^2)$ subject to $\lambda_i >0$ and $\sum_{i=1}^n\lambda_i = M$. I was wondering how I could cast it as a convex problem.

One thought came to mind of treating $\lambda_i^2$ as variables instead of $\lambda_i$. To modify the sum constraint, I could only think of using the Cauchy-Schwarz inequality to get $\sum_{i=1}^n\lambda_i^2 \geq \frac{M^2}{n}$. (Additionally, we always have: $\sum_{i=1}^n\lambda_i^2 \leq M^2$.)

My guess (or hope) is that the solution is $\lambda_i = \frac{M}{n}$ for all $i$. Can anyone see this?

-
Looking at a plot of your function for $n=2$ and $M=e$, it doesn't seem to me like there would be any way to cast this as a convex problem. What you might be able to do is prove that local maxima can only occur at $\big(\frac Mn, \frac Mn, \ldots, \frac Mn\big)$ and at permutations of $(M, 0, \ldots, 0)$, and then figure out which would be the global optimum for specified $M$ and $n$. – Rahul Apr 22 '12 at 23:57
On the other hand, if you have strict positivity constraints on $\lambda_i$, then you may not always have a solution at all when $M$ is small. This is like minimizing $x$ subject to $x>0$: the global optimum cannot be attained because your domain is not closed. – Rahul Apr 23 '12 at 0:04
Thanks, you are right. The problem in its original form is: "For a given $M$, assuming that we know the correct number $n$ of non-zero $\lambda_i$'s, maximize ...". So we can assume that $M$ has appropriate value. – rk2 Apr 23 '12 at 16:03

Consider the case $n=2$, so $\lambda_2 = M - \lambda_1$, and you want to maximize $f(\lambda_1) = \log(1+\lambda_1^2) + \log(1 + (M-\lambda_1)^2)$ for $0 \le \lambda_1 \le M$. Now $f'(0) < 0$ and $f'(M) > 0$. The critical points are at $\lambda_1 = M/2$ and (if $M > 2$) at $(M \pm \sqrt{M^2-4})/2$. If $M \le 2$, the only critical point is a local minimum and the maxima are at $\lambda_1 = 0$ or $M$. If $M > 2$, $M/2$ is a local maximum, but it is not the global maximum unless $M \ge 2 \sqrt{2}$.

EDIT: for the case $n=3$ with $M=3$, a plot shows that the maximum occurs at the three points $(3/2,3/2,0)$, $(3/2,0,3/2)$ and $(0,3/2,3/2)$. This was plotting $\log(1+x^2) + \log(1+y^2)+\log(1+(3-x-y)^2)$ for $0 \le x \le 3$, $0 \le y \le 3-x$.

-

EDIT: Sorry I was too quick to jump this problem. I have indicated the step where this proof fails and have not been able to recover it, apologies.

~~~~~~~~

I haven't done any convex analysis, but have you considered using Lagrange Multipliers? Let $$f(\lambda_1,\ldots,\lambda_n) := \sum_{i=1}^n \log(1+\lambda_i^2)$$ and $$g(\lambda_1,\ldots, \lambda_n) := \sum_{i=1}^n \lambda_i.$$

Then we must have $\nabla f = \mu \nabla g$. Calculating $$\frac{\partial f}{\partial \lambda_k} = \frac{2\lambda_k}{1+\lambda_k^2}$$ and $$\frac{\partial g}{\partial \lambda_k} = 1.$$

Thus we must have $$\frac{2\lambda_k}{1+\lambda_k^2} = \mu\cdot 1 = \mu$$ for all $k$.

(This step is unjustified/invalid) It follows that at the maximum we will have $$\lambda_1=\cdots = \lambda_n.$$ Since they are all the same, let $\lambda:=\lambda_1$ be the common value. Then the constraint may be rewritten as $$n\lambda = M \iff \lambda = \frac{M}{n}$$ so you were correct in your initial analysis. You must also check that this is in fact a maximum and not a minimum, I will leave this to you though.

-
Thanks, I did use Lagrange multipliers and got to the point where you got the quadratic equation in $\lambda_k$. So $\lambda_k$ can be either of the 2 roots $\frac{1\pm \sqrt{1-\mu^2}}{\mu}$. Rightaway we can only say that some of the $\lambda_k$'s may be one value and the remaining ones can be the other value. I am not able to argue that all of them have to be equal to the same root. – rk2 Apr 22 '12 at 19:15
Technically, the way to arrive at the quadratic equation in $\lambda_k$ would also involve Lagrange multipliers for the non-negativity constraints, but in this case (from the context of the problem), I know that all $\lambda_k$ can be considered to be non-zero, so complementary slackness yields the same quadratic equation. – rk2 Apr 22 '12 at 19:26
Since this is not a convex problem, apriori KKT conditions are known only to be necessary (not sufficient) for an optimal point. So even though all $\lambda_k$ being equal satisfies the KKT conditions, it is required to show that it is the only point that does so in order to claim that it is optimal. (Or show that KKT is sufficient for this problem.) – rk2 Apr 22 '12 at 19:30
Sorry I didn't clarify as much as I could, let me be more clear as to how I found that all the $\lambda_i$ are equal. I will edit my post very shortly. – nullUser Apr 22 '12 at 20:12
I should have made this clear earlier, the non-negativity constraints are actually strict positivity constraints, sorry about this. Otherwise, choosing $\{M,0,\ldots,0\}$ is better than all $=\frac{M}{n}$ for small values of $M$. – rk2 Apr 22 '12 at 21:00

The following is a beginning.

We want to maximize the quantity $$\Phi:=\sum_{i=1}^n \log(1+\lambda_i^2)$$ under the constraints $\lambda_i\geq0$ $\ (1\leq i\leq n)$ and $\sum_{i=1}^n\lambda_i=M$. Writing $\lambda_i=:x_i^2$ we have to maximize $$\Phi=\sum_{i=1}^n \log(1+x_i^4)$$ on the $(n-1)$-sphere $S$ given by $\sum_{i=1}^n x_i^2=M$.

Note that $S$ is compact and that the constraint is regular in all points of $S$. This implies that necessarily the maximum of $\Phi$ takes place in a conditionally stationary point. This is a point $x\in S$ where $\nabla\Phi(x)$ is orthogonal to the tangent plane of $S$, i.e., is parallel to $x$. It follows that we have to look for points $x=(x_1,\ldots,x_n)\in S$ that satisfy equations of the form $${4x_i^3\over 1+x_i^4}=2\lambda x_i\qquad(1\leq i\leq n)$$ for some $\lambda>0$. Therefore we have to solve $$2x_i\bigl(2x_i^2-\lambda(1+x_i^4)\bigr)=0\qquad(1\leq i\leq n)\ .$$ The solutions are $$x_i=0\ ,\quad x_i^2={1+\sqrt{1-\lambda^2}\over\lambda}=:\mu\geq1\ ,\quad x_i^2={1\over\mu}\ .$$ This means that for each conditionally stationary point $x$ there is a $\mu\geq1$ such that a certain number $p\geq0$ of the $x_i^2$ are $=\mu$ , a number $q\geq0$ of the $x_i^2$ are $={1\over\mu}$, and the rest of the $x_i$ are $=0$. Therefore our $\Phi$ becomes $$\Phi=p\log(1+\mu^2) + q\log\bigl(1+{1\over\mu^2}\bigr)\ ,$$ and this has to be maximized under the constraints $$p, q\in{\mathbb N}_{\geq0}\ ,\quad p+q\leq n\ ,\quad p\mu+{q\over\mu}=M\ .$$ Solving the last condtion for $\mu$ shows that necessarily $4pq\leq M^2$; so if $M<2$ necessarily one of $p$ and $q$ has to be $=0$. Numerical experiments show that for large $M$ the integers $p$ and $q$ should be as equal and as large as possible under the given constraints, which means that one should choose $p\dot=q\dot=\min\{n,M\}/2$.

-