7
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\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.

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.