Skip to main content
14 votes

Do convex quadratic problems always have sparse solutions?

Consider the convex QP $$\min \lbrace \sum_{i=1}^n x_i^2 : x\in \mathbb{R}^n, \sum_{i=1}^n x_i = 1\rbrace.$$ The solution is $$x = (\frac{1}{n},\dots,\frac{1}{n}),$$which is fully dense.
prubin's user avatar
  • 39.6k
7 votes

Do convex quadratic problems always have sparse solutions?

Not in general. In quadratic programming (and in nonlinear programming, more general), we have basic, non-basic and super-basic variables. These superbasics can be interpreted as non-basic but between ...
Erwin Kalvelagen's user avatar
6 votes
Accepted

Do convex quadratic problems always have sparse solutions?

Consider the unconstrained convex QP $$ \min \|x - x_0\|_2^2. $$ The solution is $$ x = x_0 $$ which is also fully dense for dense $x_0$.
xd y's user avatar
  • 1,196
5 votes
Accepted

How to transform a binary QP into an MILP?

For simplicity, lets assume $Q$ is a $2$ dimensional matrix: $$ x^TQx = \begin{pmatrix} x_1 & x_2 \\ \end{pmatrix} \begin{pmatrix} q_{11} & q_{12} \\ q_{12} & q_{22} \end{pmatrix} \begin{...
Kuifje's user avatar
  • 13.5k
4 votes
Accepted

How to show that minimizing the epsilon-insensitive loss is equivalent to a quadratic program with inequality constraints?

Consider a simpler problem where you are given a constant $k\ge 0$ and want to find $x\in \mathbb{R}$ to minimize the (convex piecewise-linear) loss function $$\max(x-k,-k-x,0)=\begin{cases} x-k &\...
RobPratt's user avatar
  • 32.8k
4 votes
Accepted

How to model this constraint for a QP problem?

I assume that $x$ is binary. A more natural indexing would be $x_{ur}$, in which case you can introduce binary decision variables $y_r$ and impose linear constraints: \begin{align} x_{ur} &\le ...
RobPratt's user avatar
  • 32.8k
2 votes
Accepted

How to do the scaling to remove bias in QP problem?

If $x$ is binary vector, you have $x^T D x = d^T x$ for any diagonal matrix $D$ with diagonal $d$. This has two important consequences: You can assume Q to be convex without loss of generality. In ...
Henrik Alsing Friberg's user avatar
2 votes

Is the linearization with first-order Taylor approximation correct?

Let's assume that, per Rob Pratt's comment, your $Q$ is symmetric and positive definite. Your approximation is correctly derived, and you can certainly try it. Due to convexity, the linear ...
prubin's user avatar
  • 39.6k
1 vote

Bilinear programming

You can "merge" to a single maximization over all variables. Then use Gurobi (which can solve bilinear problems such as this to global optimality, given enough time and memory) or a general ...
Mark L. Stone's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible