[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] About Quadratic Programming

From: Michael Hennebry
Subject: Re: [Help-glpk] About Quadratic Programming
Date: Fri, 19 Jul 2013 11:37:58 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

My superscripting seems to have gotten mangled the first time.

On Fri, 19 Jul 2013, bruce.loski wrote:

I checked the current version 4.52 and didn't find it support quadratic programming.Is there any plans to add quadratic programming feature to glpk?

If by quadratic programming you mean linearly constrained
programming with a quadratic objective,
iterative linear programming might be able do the job for you.
     T     T
min c x + x Mx
becomes min z
              T     T            T       T                               n
   s.t   z>=(c + 2x0 M)(x0-x) + c x0 + x0 Mx0  for all x0 in S subsetof R

M must be positive positive semidefinite.
The true objective can be evaluated for any x.
Any feasible x will provide a pessimistic bound.
For any S, an optimal solution to the LP provides an optimistic bound, z,
                                 T     T
as well as a pessimistic bound, c x + x Mx.
If they are not close enough, add x to S and resolve.

Note that when significant x0's become close together,
the problem will become ill-conditioned.
At that point, one can probably tell which constraints will be tight.
Those constraints will determine the dimensionality
of the smallest face containing the optimum.

Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily

reply via email to

[Prev in Thread] Current Thread [Next in Thread]