Quadratic programming: Fold equality constraints into objective function?

classic Classic list List threaded Threaded
1 message Options
Ran Gutin Ran Gutin
Reply | Threaded
Open this post in threaded view

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 [1]), 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?

[1] - https://en.wikipedia.org/wiki/Quadratic_programming#Equality_constraints

The 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^*$.

dev mailing list
[hidden email]