Re: [Help-glpk] About Quadratic Programming

[Michael Hennebry]

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