Remove fixed variable from quadratic program

95 Views Asked by At

I have a convex quadratic optimization problem with $n+1$ variables $x_i$

$$\text{minimize}\,f(x)=x^Tc+\frac{1}{2}x^TQx$$ $$s.t.$$ $$Ax=a$$ $$Bx\leq b$$

with exactly two equality constraints $$x_1=-1$$ $$\sum_{i=2}^{n+1}x_i=1$$ and inequality constraints all being of the form $$l_i\leq x_i\leq u_i$$ for potentially all $i\neq 1$. I.e. we have that $x_1$ is a fixed variable which does not occur in any other constraint.

From computation it looks like the problem can be reduced by completely removing $x_1$ and all corresponding elements in $c$ and $Q$, namely $c_1$, $Q_{1\cdot}$ and $Q_{\cdot 1}$.

My question is: Is it indeed correct that the above problem is equivalent to a problem with everything related to $x_1$ being removed? Either a quick explanation or a link to some literature would be really helpful.

Thanks in advance!

1

There are 1 best solutions below

0
On

Yes, eliminating fixed variables via substitution is a basic technique performed by a presolver that attempts to simplify the problem before the actual solve.