Re: new function for quadratic programming: pqpnonneg

[Jonathan Stickel-5]

I finally got a round to checking this function out.  However, my
problem also has equality and inequality constraints in addition to
x>=0.  Is it possible to add constraints and use the same implementation

Thanks,
Jonathan


On 09/11/2009 help-octave-request@... wrote:

> Date: Fri, 11 Sep 2009 11:17:16 +0200
> From: Jaroslav Hajek <highegg@...>
> Subject: new function for quadratic programming: pqpnonneg
> To: Octave users list <help-octave@...>
> Message-ID:
>     <69d8d540909110217j423527ebrf6fe14f2b6b321a9@...>
> Content-Type: text/plain; charset=ISO-8859-1
>
> hi all,
>
> I just contributed a new function: pqpnonneg (Positive Quadratic
> Programming in NONNEGative variables).
> It can be used to solve problems of the form
>
> min 1/2*x'*A*x + b'*x, all (x >= 0)
> where A is a positive definite matrix. The implementation exploits a
> duality between least squares and positive qp problems; it is very
> similar to lsqnonneg except that it solves the dual system A \ -b and
> works with a Cholesky factorization instead of QR (via qrinsert &
> qrdelete).
>
> If applicable, there are two advantages against qp:
>
> 1. it is usually significantly faster
> 2. it will always converge in a finite number of iterations (I think
> this follows from the Lawson-Hanson proof and the duality)
>
> both of these are of course very desirable. Here's a small benchmark
> creating an artificial problem and solving it via both pqpnonneg and
> qp:

_______________________________________________
Help-octave mailing list
Help-octave@...
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave

[Jaroslav Hajek-2]

On Sat, Oct 31, 2009 at 4:23 PM, Jonathan Stickel <jjstickel@...> wrote:
> I finally got a round to checking this function out.  However, my problem
> also has equality and inequality constraints in addition to x>=0.  Is it
> possible to add constraints and use the same implementation
>
> Thanks,
> Jonathan
>

I don't think this can be done in full generality. It might be
possible to solve for the constraints first and then project the
quadratic form to the feasible space. If you're lucky and the feasible
space is a convex "corner", you can still use pqpnonneg.
The simple "corner-like" shape of the feasible space is where the
algorithm gets its good features from. A generalization to arbitrary
combination of lower and upper bounds is possible, but hasn't been
implemented yet. I'm planning to address this in the future.

hth


--
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz

_______________________________________________
Help-octave mailing list
Help-octave@...
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave