Least squares minimization subject to the constraint $\sum_j|u_j| \leq 1$

Question

I would like to learn about methods for minimizing the cost $L(u) = (f - Au)^{tr}M(f-Au)$, where $f \in R^m$ is a known vector, $u \in R^n$ is the argument of the minimization and $A \in R^{n\times m}$, $M \in R^{n\times n}$, subject to the constraint $\sum_j |u_j| \leq 1$.

Answer 1

The constraint $\sum_{j} | u_{j} | \leq 1$ is easy to convert to a system of linear inequalities. Introduce auxilliary variables $t_{j}$, $j=1, 2, \ldots, n$. Then add the constraints

$u_{j} \leq t_{j} $ for $j=1, 2, \ldots, n$

$-u_{j} \leq t_{j} $ for $j=1, 2, \ldots, n$

$\sum t_{j} \leq 1$.

This is a very standard problem transformation described in many textbooks on optimization.

The more important issue here is whether $A^{T}MA$ is positive semidefinite or indefinite.

If this matrix is indefinite, then you have a nonconvex linearly constrained quadratic optimization problem which can be hard to solve to optimality even for relatively small values of $n$ (e.g. it could be hard to solve for values $n$ in the thousands.) Typically, branch and bound algorithms using a convex underestimator are used to solve problems like this.

If the matrix is positive semidefinite, then you have convex linearly constrained quadratic optimization problem which should be relatively easy to solve even if $n$ is in the hundreds of thousands or millions. For relatively small values of $m$ and $n$, an active set method would be appropriate. For very large values of $m$ and $n$ (hundreds of thousands to millions), some kind of first order method would be best. In particular, since projecting onto the one-norm unit ball is easy, you might consider using a projected gradient method.