Simple Looking Non Convex Optimization Problem

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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$.