What methods are suggested to solve problems of the form $\min || {A} x - y ||_k$, subject to $x^T P x \leq c$, and/or $x^T Q x = d$?

• Can you get away by solving the dual problem? Do you really mean $\|v\|_k=(\sum_i |v_i|^k)^{1/k}$? – Deathbreath Mar 27 '12 at 16:12
• Yes, I meant the norm as you defined it. – Emre Mar 27 '12 at 20:16
• As it stands, the problem is non-convex, so there will be a duality gap. Solving the dual problem may not yield a desirable solution. – Geoff Oxberry Mar 27 '12 at 21:34

In case of an inequality constraint only and semidefinite $P$, your problem is convex, and there may be better alternatives (CVX mentioned in the answer by Victor Liu, or the methods of arXiv:1009.2065 (which has at thre end a reference to a an implementation).

If $1<k<\infty$, you can use standard nonlinear programming software (see, e.g. http://neos-server.org/neos/ ); in case of an equality constraint or an inequality constraint with indefinite $P$, you are very unlikely to do better with other codes.

Otherwise, if $k=1$ or $k=\infty$, you need to introduce an extra variable $z$ for an upper bound on the objective, and minimize $z$ subject to your constraints and a bunch of linear constraints equvalent to $\|Ax-b\|_k\le z$, and again use standard nonlinear programming software. Alternatively, you might use a nonsmooth optimization code; don't know what to recommend there, but a list of codes is at http://www.mat.univie.ac.at/~neum/glopt/software_l.html#nonsm

Without the equality constraint, the problem is convex, and any standard interior point convex optimization package can be applied to solve this efficiently, such as the high level modeling software CVX.

With the equality constraint, the problem is no longer convex. However, you may approximate the solution by repeatedly solving a bunch of convex problems. One simple approach is to approximate the ellipsoid $x^TQx=d$ as a polyhedron and solve the optimization problem on all the facets of the polyhedron, then taking the best solution among all facets.

• The problem is not necessarily convex without the equality constraint: $P$ must also be positive definite or at least positive semi-definite. – Aron Ahmadia Mar 27 '12 at 11:05
• @AronAhmadia: For $c\ge 0$ and $P$ Hermitian, the negative subspace trivially fulfills the inequality, i.e., it can be projected out and the problem is convex. – Deathbreath Mar 27 '12 at 21:31
• @Deathbreath: No - the projection changes the problem to a different one! – Arnold Neumaier Mar 28 '12 at 9:55
• @ArnoldNeumaier: How so? If $Q_-$ is the projector onto the subspace for which $x^TPx\le0$, then $x^TQ_-PQ_-x \le c$ describes the same feasibility space and is convex. – Deathbreath Mar 28 '12 at 15:16
• @Deathbreath: This doesn't settle the difficulties. In the 2D toy example I posed, if you set $y=0$ you get the wrong solution $x=0$ instead of the correct solution $x=5$ (and $|y|\ge 5$). – Arnold Neumaier Mar 30 '12 at 16:16