The function $f(x)$ is the larger eigenvalue of sum of two rank-one matrix. My aim is to get the upper bound of the eigenvalue.
The problem can be described by $$ \max_{x} f(x)=b^Tx+\sqrt{x^TAx}\\ s.t -{\bf{1}} \leq x\leq {\bf{1}} $$ where $A \in \mathbb{R}^{n\times n}$ is symmetrical positive semi-definite matrix and the entries of $b\in\mathbb{R}^{n\times1}$ are positive. The ${\bf{1}}$ is a $n\times1$ with all entries one.
My question are:
- how to get the maximum of $f(x)$ with the inequality constraint, hopufully a close form solution?
- what conditions should be fullfiled to make the maximum point lie at the $x={\bf 1}$?
I have tried the KKT conditions. $$ b+\frac{Ax}{\sqrt{x^TAx}}-\mu_1+\mu_2=0\\ \mu_1^i(x^i-1)=0\\ \mu_2^i(x^i+1)=0\\ \mu_1\geq 0\\ \mu_2\geq 0 $$ with $\mu_1 \in \mathbb{R}^{n\times1}$ and $\mu_2 \in \mathbb{R}^{n\times1}$ corresponding to the slackness coefficients of the inequality constraint $x\leq {\bf 1}$ and $x\geq-{\bf 1}$. $x^i$ denotes the $i$-th entry of the vector $x$.
I found it is hard to see the solution of the above equations.
Thanks very much for any hints.
The answer I have is simple, but results in a high complexity. The maximum of a convex function over a convex set, if exists, is attained at an extreme point, which in your case are the vertices of the feasible polyhedron ($x_i = \pm 1$). Unfortunately, you have $2^n$ vertices to check, and I do not know of a more efficient simple algorithm.
However, you may try a branch and bound algorithm, since the constraints can be formulated as $x_i = \pm 1$ instead of $-1 \leq x_i \leq 1$. Bounding from below is easy using the sub gradient inequality for convex functions.
Regarding your second question, it is easy to see that a sufficient condition for optimality of $\bf 1$ is that $\bf 1$ is an eigenvector associated with the maximum eigenvalue of $A$, and $b$ is a multiple of $\bf 1$