0
$\begingroup$

I intend to solve for vector $ x \in \mathbb{R}^{N \times 1} $ by solving the following optimization problem

\begin{align} \arg \min_{x} \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x} \end{align} \begin{align} \text{S.t. } & x_{i}^{min} \leq x_{i} \leq x_{i}^{max} \\ \end{align}

\begin{align} \text{S.t. } & \|x\|_0 \leq k\\ \end{align} where $\mathbf{Q} \in \mathbb{R}^{N \times N}$ is a positive definite matrix, and $\mathbf{c} \in \mathbb{R}^{N \times 1}$.

Obviously if I remove the second constraint it is possible to solve the above using regular constrained quadratic programming (like quadprog command in MATLAB).

I know the $l_{0}$-norm makes the problem non-convex but I was hoping if someone can give me a hint how I could find the solution to this?

$\endgroup$
0
$\begingroup$

One option is to use integer programming -- add binary variables $y_i$ with constraints $x^{min}_i y_i \leq x_i \leq x^{max}_i y_i$. Then, your cardinality constraint becomes $\sum_i y_i \leq k$. You now have a mixed-integer quadratic program with linear constraints. It is harder to solve than a continuous QP, but at least this is a well-known class of optimization problems and there are already solvers out there that can tackle it; for example, the Gurobi suite has an MIQP solver. You will have to worry about all the usual issues that arise in IP.

$\endgroup$

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.