Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
This is the standard approach in the linear case. It seems like it should work in the quadratic case, too. –  Mike Spivey Oct 19 '10 at 16:56
    
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. –  Leonid Ilyevsky Oct 19 '10 at 18:39
    
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$. –  F_G Oct 19 '10 at 21:57
add comment

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.

share|improve this answer
    
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. –  Suvrit Oct 19 '10 at 20:08
    
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. –  Mike Spivey Oct 19 '10 at 20:11
    
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 –  F_G Oct 19 '10 at 20:57
    
@FG: Point taken. Interesting observation. –  Mike Spivey Oct 19 '10 at 21:11
    
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. –  Leonid Ilyevsky Oct 19 '10 at 21:40
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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