3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\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 '15 at 3:48
  • $\begingroup$ see my expanded answer. $\endgroup$ – Brian Borchers Jul 30 '15 at 4:11
  • $\begingroup$ what if you had another constraint sum(abs(a))>=2? $\endgroup$ – citynorman Sep 10 '17 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$ – Brian Borchers Sep 10 '17 at 16:47
  • $\begingroup$ @BrianBorchers Thanks for the answer. Out of interest, do you have a text book reference for this? $\endgroup$ – spinkus Feb 13 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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