Convex Optimization problem with sum of absolute value constraints

How to solve the optimization problem written below?

\begin{align} &\operatorname{argmax}\limits_{a}\; a^T b - \frac{1}{2} a^T X a\\ &\text{subject to } \sum_i |a_i|=4,\; \sum_i a_i = 0 \end{align}

where $a$, $b$ are $n$-vectors and $X$ is a $n\times n$ matrix. Also, $b$ and $X$ are constants.

My main issue is about the absolute values. Without absolute values, there is actually an analytic solution. I guess with absolute values, I have to use iterative approach such as quadratic programming but still not sure how to express the problem to call relevant optimization procedures.

Unfortunately, your problem isn't a convex optimization problem because the constraint $\Sigma_{i} | a_{i}|=4$ describes a non-convex feasible region. If you could change this to $\Sigma_{i} | a_{i} | \leq 4$, you'd have a convex constraint.

If the constraint were $\Sigma_{i} | a_{i} | \leq 4$, then you can introduce auxiliary variables $t_{i}$, and add the constraints

$\Sigma_{i} t_{i} \leq 4$

$t_{i} \geq a_{i}$ for all $i$

$t_{i} \geq -a_{i}$ for all $i$

This is a standard reformulation technique in convex optimization.

Another issue with your original problem statement is that $X$ must be positive semidefinite to ensure concavity of the objective function.

Assuming that $X$ is positive semidefinite, you've now got a linear constrained convex quadratic programming problem which is solvable by lots of solvers.

• I see your point. Let's say the constraint is changed to Σi|ai|≤4, how then it should be solved? – Bill Z Jul 30 '15 at 3:48
• see my expanded answer. – Brian Borchers Jul 30 '15 at 4:11
• what if you had another constraint sum(abs(a))>=2? – citynorman Sep 10 '17 at 13:24
• That set described by $\sum | a_{i} | \geq 2$ isn't a convex set, and this your problem couldn't be formulated as a convex optimization problem. – Brian Borchers Sep 10 '17 at 16:47
• @BrianBorchers Thanks for the answer. Out of interest, do you have a text book reference for this? – spinkus Feb 13 '19 at 1:40