1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ If you were solving an ordinary system of equations and at some point deduced that $x_1=-1$ then you would substitute this value for $x_1$ in all other places. This situation is no different. $\endgroup$ – Michal Adamaszek Sep 12 at 12:48
  • $\begingroup$ Note that $x_{1}$ appears in cross terms with $x_{2}$, $x_{3}$, etc. You can't simply drop those terms since these do depend on the remaining variables. $\endgroup$ – Brian Borchers Sep 12 at 13:47
1
$\begingroup$

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

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