Quadratic programming: Fold equality constraints into objective function?
Hi, the quadratic programming solver qpsolve in Scilab has an argument for specifying equality constraints, while also requiring that
the quadratic form $Q$ be positive definite. I've done some
manipulations (similar to the ones on Wikipedia ), and the equality
constraints can be "folded into" $Q$, so that it can go from not being
positive definite to being positive definite. Could the requirement that
$Q$ be positive definite be relaxed?
way to "eliminate" the equality constraints $Ax = b$ is to solve $Ax =
b$ by finding a vector $x_0$ and a matrix $K$ such that $Ax_0=b$ and $K$
is the kernel of $A$ (this is what the `linsolve` function does). You can then do the substitution $x = x_0 + K u$
where $u$ is an arbitrary column vector with compatible dimensions. The
substitution is done inside both the objective function and the
inequality constraints. The quadratic program then tries to optimize in
terms of the variable $u$. Since $u$ has fewer dimensions than $x$, this
results in a quadratic program with fewer dimensions. Once the optimal
$u^*$ is found, compute $x^*$ by $x^* = x_0 + K u^*$.