REQUEST: constrained optimization of positive definite quadratic form

Thread View: sci.math.num-analysis

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by Enzo Liguori Tue, 01 Sep 1992 03:39

#395

Author: Enzo Liguori
Date: Tue, 01 Sep 1992 03:39

14 lines
841 bytes

I'd like suggestions on how to minimize a positive definite quadratic form with
the variable constrained to be within an interval like:
A<=Xi<=B
with A,B constants and Xi any variable of the quadratic form.
If there's a faster algorithm that works with simpler constraints like:
Xi<=0
Xj>=0
Xk unconstrained
that'll probably do.
Thanks in advance.

        Enzo

Enzo Liguori - Canon Information Systems Research Australia

Re: REQUEST: constrained optimization of positive definite quadratic form

#397

Author: samer Takriti
Date: Tue, 01 Sep 1992 14:11

28 lines
1768 bytes

In article <BtvrIE.IB8@research.canon.oz.au> enzo@research.canon.oz.au (Enzo Liguori) writes:
>I'd like suggestions on how to minimize a positive definite quadratic form with
>the variable constrained to be within an interval like:
>A<=Xi<=B
>with A,B constants and Xi any variable of the quadratic form.
>If there's a faster algorithm that works with simpler constraints like:
>Xi<=0
>Xj>=0
>Xk unconstrained
>that'll probably do.
>Thanks in advance.
>
>        Enzo
>
>Enzo Liguori - Canon Information Systems Research Australia

This problem is well known and has a systematic method for solving it.
The more general problem can also be solved (i.e., linear constraints
on the variable: a11x1+a12x2+...= b1 and so on).
You can refer to any non-linear programming book and look under "quadratic
programming". There is a book by K. G. Murty, "Linear complementarity, 
linear and nonlinear programming". Another book is "Nonlinear Programming
theory and algorithms" by Bazraa and Shetty.
By the way if the problem is uconstrained, write the system in the form
X^t.Q.X (t indicates transpose), then solve the system of equatios, 
Q.x = 0 ==> x=0 as a unique solution since Q is positive definite.
-Samer
.

Re: REQUEST: constrained optimization of positive definite quadratic form

#402

Author: T. Scott Thompson
Date: Tue, 01 Sep 1992 21:07

25 lines
1661 bytes

enzo@research.canon.oz.au (Enzo Liguori) writes:

>I'd like suggestions on how to minimize a positive definite quadratic form with
>the variable constrained to be within an interval like:
>A<=Xi<=B
>with A,B constants and Xi any variable of the quadratic form.

The following might prove helpful:

Jorge J. More and Gerardo Toraldo, "Algorithms for Bound Constrained
Quadratic Programming Problems," Numerische Mathematik 55, 377-400
(1989).

Jorge J. More, "Numerical Solution of Bound Constrained Problems," in
Computational Techniques & Applications: CTAC-87, J. Noye & C.
Fletcher (eds.), North-Holland, 29-37 (1988).

The former deals explicitly with your problem.  The simple nature of
your constraints can be exploited to get better performance than you
are likely to get with a QP algorithm that permits more general
constraints.
--
T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
Department of Economics        phone:  (612) 625-0119
University of Minnesota        fax:    (612) 624-0209

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads