How do I set a lower bound to the solution's norm in a quadratic program?

Question

I know that LASSO-regularization can be used to scale into an $L_1$ upper bound for a solution. But what if I want the norm to be within a specific range $[a,b]$? ie. I also want to set a lower bound?

In other words: I am looking for an efficient method to solve a QP problem with a constraint on the norm of the solution ($a\leq\|x\|\leq b$), not on the individual components of the solution ($AX\leq b$).

Answer 1

It cannot be done in a convex optimization or a standard quadratic programming framework. Lower bounds on the norm are non-convex. No efficient method exists that will reliably obtain the global solution to such a problem.

On the CVX Forum, a user asked a similar question here. Professor Stephen Boyd offered up an answer that is not specific to CVX, but can be used in any convex optimization setting. I will quote it here in full just in case the link goes dead some day.

mcg's answer is correct; the problem is not convex, and cannot be expressed in DCP format. more specifically, a constraint like $\|Aw\|_2 \leq P$ (with $A$ a constant matrix and $w$ a variable) is OK (convex, and DCP), but the converse constraint, $\|Aw\|_2 \geq P$, is not convex, and (therefore) not DCP.

i'd like to add that there are heuristic methods for "handling" such problems, using the so-called convex-concave procedure (see EE364b, lecture on sequential convex programming). this is a heuristic method, that uses convex optimization as a subroutine, to "solve" problems like this one. heuristic means the method can fail; the $w$ found need not be the global solution. but such methods can work well in practice.

for a reverse norm inequality like this, the method works as follows. we replace $\|Aw\|_2 \geq P$ with the convex (and DCP) constraint $q^T(Aw) \geq P$, where $q=(Aw^\mathrm{prev})/\|Aw^\mathrm{prev}\|_2$, where $w^\mathrm{prev}$ is the value of $w$ at the last iteration. solving the resulting convex problem gives us the new value of $w$. (you must start with a nonzero value of $w$. in fact, you might start the convex-concave procedure with several different values of $w$; you could well get different final results.)

our experience is that this works quite well in practice. but remember that this method does not find the global solution.

There is one other solution I can think of. You have not specified which norm you are considering. But if you would consider the $\ell_\infty$ norm $\|x\|_\infty=\max_i|x_i|$, then you can handle this constraint in a mixed-integer quadratic programming (MIQP) system. To see why, consider the following constraint: $$2ay_i+(a-b)z_i-a\leq x_i \leq a+(b-a)y_i-2az_i, \quad y_i,z_i\in\{0,1\},~y_i+z_i\leq 1$$ This constraint works as follows:

• if $y_i=z_i=0$, then $-a\leq x_i \leq a$; that is, $|x_i|\leq a$.
• if $y_i=1$, $z_i=0$, then $a\leq x_i\leq b$.
• if $y_i=0$, $z_i=1$, then $-b\leq x_i\leq -a$; that is, $a\leq -x_i\leq b$.
• $y_i=z_i=1$ is forbidden by the $y_i+z_i\leq 1$ constraint.

If we repeat these constraints for all $i=1,2,\dots, n$, then we ensure that $\|x\|_\infty\leq b$. And if we require that at least one $y_i,z_i$ is nonzero, then we are ensuring that $\|x\|_\infty\geq a$. Thus this system of constraints will ensure $a\leq\|x\|_\infty\leq b$: \begin{array}{cc} 2ay+(a-b)z-a\leq x \leq a+(b-a)y-2az \\ y_i,z_i\in\{0,1\},~y_i+z_i\leq 1,~i=1,2,\dots, n \\ \sum_i y_i + z_i \geq 1 \end{array} This is $3n+1$ inequalities, $n$ original variables, and $2n$ new binary variables. There are no theoretical guarantees of tractability, but in practice you can probably handle a reasonably large $n$.