Convex Optimization problem with sum of absolute value constraints

Question

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.

Answer 1

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.