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$?
3
-
$\begingroup$ Can you get away by solving the dual problem? Do you really mean $\|v\|_k=(\sum_i |v_i|^k)^{1/k}$? $\endgroup$– DeathbreathCommented Mar 27, 2012 at 16:12
-
$\begingroup$ Yes, I meant the norm as you defined it. $\endgroup$– EmreCommented Mar 27, 2012 at 20:16
-
$\begingroup$ 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. $\endgroup$– Geoff OxberryCommented Mar 27, 2012 at 21:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
7
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.
-
2$\begingroup$ The problem is not necessarily convex without the equality constraint: $P$ must also be positive definite or at least positive semi-definite. $\endgroup$ Commented Mar 27, 2012 at 11:05
-
$\begingroup$ @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. $\endgroup$ Commented Mar 27, 2012 at 21:31
-
$\begingroup$ @Deathbreath: No - the projection changes the problem to a different one! $\endgroup$ Commented Mar 28, 2012 at 9:55
-
$\begingroup$ @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. $\endgroup$ Commented Mar 28, 2012 at 15:16
-
1$\begingroup$ @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$). $\endgroup$ Commented Mar 30, 2012 at 16:16