3
$\begingroup$

I need an algorithm to solve a Quadratic Programming optimization problem where the unknowns are allowed to be negative. I have an implementation of the Philip Wolfe simplex algorithm based on his article http://pages.cs.wisc.edu/~brecht/cs838docs/wolfe-qp.pdf, but it assumes x >= 0. In other places describing similar algorithms it always assumes non-negativity. I have seen descriptions of the QP problems without such restriction, but no links to the algorithms there.

I tried to extend Wolfe's algorithm by allowing unrestricted values in the simplex tableau (the same way I would do it for the linear case), and it gives me some results, but I don't know whether it is correct or whether it will work reliably.

So basically I need to know if simplex algorithm can be enhanced to handle unrestricted unknowns, and if so, I want to see the mathematical proof that this enhanced algorithm works.

If the answer is no, then I would like some suggestions of how to approach this problem. Do I need to use a combinatoric approach where some variables are non-negative and others non-positive, and try all combinations? Or is there more efficient way?

$\endgroup$

2 Answers 2

1
$\begingroup$

You could replace each unrestricted variable x by (y-z) where y and z are each restricted to be positive.

$\endgroup$
3
  • $\begingroup$ This is the standard approach in the linear case. It seems like it should work in the quadratic case, too. $\endgroup$ Oct 19, 2010 at 16:56
  • $\begingroup$ Thanks, it looks like it indeed works. I knew about this approach in linear case, I just worried that in quadratic case it would spoil the required properties of the matrix. However, I did some analysis and found that it should be fine. So I implemented it and tested. I also found that Excel solver can do it too, and I tested my code against Excel. Now I believe that Excel Solver uses the same thing. $\endgroup$ Oct 19, 2010 at 18:39
  • $\begingroup$ If you have several free (unrestricted) variables, you can use the standard trick for each of them and reuse one of the two variables in the differences ; in other words, replace $x_1, x_2, x_3, \ldots$ by $y_1-z, y_2-z, y_3-z, \ldots$ with nonnegative $y_i$ and $z$. $\endgroup$
    – F_G
    Oct 19, 2010 at 21:57
2
$\begingroup$

If you consider the following standard formulation of Quadratic Programming $$\min \frac12 x^T Q x + b^T x \quad \text{s.t.} \quad A x = b \text{ and } x \ge 0$$ (where matrix $Q$ is assumed positive semidefinite) and remove the nonnegativity constraints, the resulting problem $$\min \frac12 x^T Q x + b^T x \quad \text{s.t.} \quad A x = b$$ can be solved easily: simply write down the optimality conditions (KKT) $$Q x + b = A^T \lambda \text{ and } A x = b$$ which are necessary and sufficient. No need to apply a (modified) simplex algorithm, simply solve a linear system.

$\endgroup$
7
  • $\begingroup$ Small quip: depends on your definition of easy; for example if the matrices $Q$ and $A$ are huge, or ill-conditioned, then...; anyhow, I know, that is besides the point. $\endgroup$
    – Suvrit
    Oct 19, 2010 at 20:08
  • $\begingroup$ If I'm not mistaken, this is exactly what the Philip Wolfe algorithm mentioned by the OP does: It solves this linear system based on the KKT conditions. I think the OP was primarily concerned with whether the standard approach for dealing with unrestricted variables in the linear case would "in quadratic case ... spoil the required properties of the matrix." It appears the answer is no. $\endgroup$ Oct 19, 2010 at 20:11
  • $\begingroup$ Suvrit: I mean "easy" in the sense that it boils down to linear algebra, with no optimization method needed Mike: The algorithm proposed by Wolfe indeed relies on the KKT conditions, but because the original problem involves inequalities, those conditions involve both inequalities and complementarity constraints, which implies they cannot be solved by simple linear algebra $\endgroup$
    – F_G
    Oct 19, 2010 at 20:57
  • $\begingroup$ @FG: Point taken. Interesting observation. $\endgroup$ Oct 19, 2010 at 21:11
  • $\begingroup$ Thanks FG, I give you the points for your answer. However, I indeed have to solve a problem with constraints. I need to allow negative values, but I have other constraints, equalities and inequalities. Therefore, I do need to follow Wolfe's procedure, which requires to modify the simplex method: that complementary "v" vector must be orthogonal to "x", i.e. corresponding components of x and v cannot be in the basis at the same time. This orthogonality requirement is essentially non-linear, but fortunately it can be achieved by modifying the algorithm, according to Wolfe. $\endgroup$ Oct 19, 2010 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.