5
$\begingroup$

Let $A$ be a real symmetric positive-semidefinite matrix and suppose that $c>0$ is a sufficiently small number. I wonder if it is possible to solve the non-convex optimization $\arg\max_u\ u^\mathrm{T}Au\\ \mathrm{subject\ to\ }\left\Vert u\right\Vert_2\leq 1\\ \quad\quad\quad\quad\left\Vert u\right\Vert_1\leq c,$ efficiently.

For solving the optimization, I couldn't get farther than writing KKT conditions which do not help much in specifying the multipliers.

Given that without the $\ell_1$-norm constraint (i.e. $c\to\infty$), the problem reduces to finding the principal eigenvector of $A$ that can be solved efficiently (e.g., using power iteration method), we can think of the solution to the optimization above as "psuedo eigenvector".

  • 0
    @ℝⁿ: The problem is that I'm interested in problems where c>1. In fact, the $\ell_1$-norm constraint is a convex relaxation of $\ell_0$ constraint that induces sparsity. So for $\left\Vert u\right\Vert _0\leq s$ we should choose $c=\sqrt{s}\geq 1$ in the $\ell_1$-constrained form.2013-01-29

1 Answers 1

1

I am not sure about the objective function part. But for the constraints, May be this will help. Write $u=u^{+}-u^{-}$, where $u^{+}$ denotes positive part in $u$ and $u^{-}$ denotes the negative part. Now with this, the above problem will become

\begin{align} \arg\max_{u^{+},u^{-}}\ {u^{+}}^{T}Au^{+}+{u^{-}}^{T}Au^{-}-2{u^{-}}^{T}Au^{+} \\ subject ~~to& [1,1\ldots,1]^{T}({u^{+}}+{u^{-}}) <= c \\ & (u^{+}-u^{-})^{T}(u^{+}-u^{-})<=1 \\ & u^{+}>=0, u^{-}>=0 \end{align}

You can make the objective function linear by bringing in a variable $t$ and hence adding a non-convex quadratic constraint. All other linear constraints can be reformulated as quadratic constraints. I think then you can reformulate it as a semi-definite program. In details

\begin{align} \min_{t}~~ -t \\ subject~to~ &u^{H}Au \geq t \\ & [1,1\ldots,1]^{T}({u^{+}}+{u^{-}}) <= c \\ & (u^{+}-u^{-})^{T}(u^{+}-u^{-})<=1 \\ & u^{+}>=0, u^{-}>=0,t>=0 \end{align}

Note that this is equivalent to your original problem. Now the variables $u^{+},u^{-},t$ can be combined to form a single vector $x$ and I believe you can write all of them as a optimization problem with a linear objective and non-convex quadratic constraints. If it is possible, then Semi-definite Relaxation (SDR) is a very famous technique to deal with such non convex problems. Also in your case, SDR should give exact solutions. In details, you problem should look something like

\begin{align} \min_{x}~~ a^{T}x \\ subject~to~ &x^{H}F_{1}x \geq c_1 \\ & x^{H}F_{2}x \geq c_2\\ & x^{H}F_{3}x \geq c_3 \\ & x>=0 \end{align}

If you can reformulate your problem this way which I think is possible, then semi-definite relaxation will work.

  • 0
    @S.B. Please look at the edited Attempt2012-10-15