From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Newsgroups: sci.math.research Subject: Re: Quadratic Programming Date: 4 Jan 1999 11:44:20 GMT Keywords: What is Quadratic Programming (in numerical optimization) In article <76l43s$l4t$7@trex.antw.online.be>, "Lommens Kevin" writes: |> Could anyone tell me what quadratic programming is and where it is used? |> the standard quadratic programming problem is minimize f(x)=(1/2) x'Ax-b'x (.)' means transposition, x is in R^n subject to the constraints G'x+g_0 >= 0 H'x+h_0 = 0 i.e. mixed _linear_ equality and inequality constraints. If the matrix A is positive semidefinite, then the problem is convex and solvable routinely. If this is not the case, we have a problem in global optimization which is NP-hard. there exist rather simple algorithms to find second order necessary points for the general problem, (points satisfying the first order and second order necessary optimality conditions), but the global problem is quite hard and the subject of current research. such "quadratic" problems occur e.g. in diet-optimization, in the (quadratic) assignment, and as subproblems of more general optimization algorithms. fletchers book "practical methods of optimization", 2. ed., Wiley 1987, gives a nice introduction into this field. If the constriants contain also quadratic terms, one has a "generalized quadratic programming problem". again, in the convex case, there exist efficient algorithms (e.g. interior point methods) hope this helps peter ============================================================================== From: "N. Shamsundar" Newsgroups: sci.math.research Subject: Re: Quadratic Programming Date: Mon, 04 Jan 1999 16:56:38 -0600 Lommens Kevin wrote: > > Could anyone tell me what quadratic programming is and where it is used? > > Thanks, > Lommens Kevin > email: perez@digibel.org Find a vector X that minimizes the quadratic form X'AX + b X subject to constraints C_1 X =0 C_2 X >= 0 A is a square matrix, b is a vector, C_1 and C_2 are rectangular matrices. For more details on the subject and related topics, see http://www.mcs.anl.gov/otc/Guide/SoftwareGuide/ ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: Quadratic Programming Date: 1 Oct 1999 17:30:03 -0500 Newsgroups: sci.math.num-analysis,sci.math.research,sci.math In article <37F30687.AE1BB916@iway.fr>, actia writes: |> Hi all, |> |> Someone could give me some reference on |> the today best algorithm to solve : |> **** |> |> Optimization of a quadratic semidefinite positive |> under linear constraints ? snip , question "which is the best one" there is no best one universal solver for this (seemingly simple) problem. what to do depends much on the details: dimension conditioning of the Hessian or reduced Hessian sparsity. as long as the dimension does not exceed some 100 and the Hessian is positive definite , the method of Goldfarb and Idnani can be recommended. there are several implementations in the public domain. This method can be generalized to the semidefinite case as shown by Stoer in the early 90's, (numerical algorithms, if I remember right), but there is no ready to use implementation available for this version. for medium scale problems i would chose Goulds method, published in 1991 in JIMA Num Anal 11. This is part of the HARWELL library, but not public domain. This is a quite robust active set method. For large dimensions and sparse problems, an interior point method should be best, like BPMPD and LOQO, which both have meanwhile a QP-extension. For large and dense problems, things become very hard, but with some good and sparse preconditioner the method of martinez&santos published in 1994 in SINUM should work. this transforms the method in to a bound constrained quartic function , which then may be solved by a special solver , e.g. lbfgsb or pl2 (see the url below) see http://plato.la.asu.edu/guide.html http://plato.la.asu.edu/donlp2.html (for a paper on this) for more information. there is also a benchmark page available which might give you an impression on performances. hope this helps peter