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.


1 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.

  • $\begingroup$ I see your point. Let's say the constraint is changed to Σi|ai|≤4, how then it should be solved? $\endgroup$
    – Bill Z
    Jul 30, 2015 at 3:48
  • $\begingroup$ see my expanded answer. $\endgroup$ Jul 30, 2015 at 4:11
  • $\begingroup$ what if you had another constraint sum(abs(a))>=2? $\endgroup$
    – citynorman
    Sep 10, 2017 at 13:24
  • $\begingroup$ 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. $\endgroup$ Sep 10, 2017 at 16:47
  • 1
    $\begingroup$ This is discussed in Vandenberghe and Boyd's textbook on Convex Optimization among others. $\endgroup$ Feb 13, 2019 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.