# Is the following optimization problem convex? If not, what is it? [closed]

Sorry if the question is trivial. I have the following optimization problem which I think is not convex because of the binary constraints. But I do not know what is this problem then. Here is the optimization problem.

$$\text{minimize } ||Ax - b||_2 \\ s.t. \sum\limits_{i=1}^{n} x_i = \ell,\\ x \in \lbrace 0,1\rbrace$$

In fact, the goal is to only select $\ell$ points from $A$, such that the sum of those selected points is close to $b$.

## closed as off-topic by apnorton, Claude Leibovici, user91500, Watson, user223391 Oct 10 '16 at 22:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – apnorton, Claude Leibovici, user91500, Watson, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

• Your objective is currently a vector-valued function. Do you want to add some norm to that, or is this a multi-objective problem? – LinAlg Oct 7 '16 at 21:54
• Thanks for mentioning that. I actually edited the objective function now, minimize L2 norm of $Ax-b$. Any help is appreciated on what is this problem and how to solve it. – Erin Oct 7 '16 at 22:13

## 1 Answer

It's a mixed-integer second order cone optimization problem. MOSEK is arguably the best solver for this problem. If $\ell$ is small, you could brute-force the solution.

• Thanks a lot for your response @LinAlg and Beached Whale. I have another question as well. Let's say I consider a relaxed version of this problem by removing the binary constraints. Is this relaxed version a CVX optimization problem? – Erin Oct 8 '16 at 17:59
• Yes, that's a second order cone optimization problem (which is convex). MOSEK solves the integer problem by solving a sequence of relaxed problems (with $0\leq x_i\leq1$). – LinAlg Oct 8 '16 at 20:14
• What is it exactly? quadratic linear programming? Or semi-definite quadratic? – Erin Oct 15 '16 at 22:54
• A second order cone optimization problem (or a convex quadratic optimization problem if you will). – LinAlg Oct 16 '16 at 1:20