Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Dont know if this helps, but this sort of combination of L^2 and L^1 norm is known in statistics as the lasso, so you can google for that and see if some of the algorithms developed for the lasso can be applied. –  kjetil b halvorsen Oct 5 '12 at 20:13
    
@kjetilbhalvorsen: I'm aware of the LASSO and the related subjects in statistics, but I don't think they really apply here as randomness is central in their arguments, while my problem is completely deterministic. Namely, matrix $A$ is not drawn from some random ensemble of matrices. –  S.B. Oct 5 '12 at 21:23
    
... but their algorithms could still apply ... the algorithms in itself do not care about randomnes, they only see the data, not the model. –  kjetil b halvorsen Oct 5 '12 at 22:08
    
@kjetilbhalvorsen: It's true that their algorithm may apply, but we cannot guarantee it actually produces an accurate solution to the original problem. The randomness is what allows them to provide guarantees of accuracy. Regardless of this issue, the problem I have is a maximization of a convex quadratic, which is a non-convex optimization problem. The LASSO is a convex optimization formulation. –  S.B. Oct 6 '12 at 0:33
    
If $c$ is "sufficiently small" (i.e. smaller than $1$), then you can just get rid of the $\lVert u\rVert_2\le1$ constraint, can't you? Then the problem reduces to quadratic programming, and you can maybe even just iterate over the (explicitly known) facets of the feasible polytope. –  Rahul Jan 27 '13 at 1:06

1 Answer 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.

share|improve this answer
    
This change of variable helps avoiding the non-smooth $\ell_1$-norm, but it does doesn't simplify the entire problem. –  S.B. Oct 10 '12 at 11:41
    
@S.B. Please look at the edited Attempt –  dineshdileep Oct 15 '12 at 7:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.