Date: Tue, 09 Sep 1997 07:46:15 -0700
From: Hans D Mittelmann <mittelmann@asu.edu>
Subject: Concave Minimization: software needed
Hi,
unfortunately there is a mistake in your argument, but it can be corrected. inv(Pi)=inv(C)inv(C') and not the other way around. So we have to find the maximal eigenvalue of inv(C)inv(C') or the reciprocal of the minimum eigenvalue of C*C' which is a positive semidefinite matrix, so that the eigenvalue is nonnegative. In fact it is positive because Pi is positive definite, so C is regular. The best way to find this minimum eigenvalue is Rayleigh-quotient inverse iteration. Start with x_0=(1,.....1) or so. Then iterate
C*C' y_k = x_k, lambda_k = x_k'y_k/(y_k'y_k)
set x_k+1 = y_k/norm(y_k)
and continue. When converged, the desired solution is x and the objective function value is 1/lambda. One may introduce a shift if convergence needs to be accelerated.
The solution of the linear system is accomplished with two triangular solves, of course. Cz = x_k, C'y_k = z.
Date: Mon, 08 Sep 1997 12:03:43 -0700
From: "Hans D. Mittelmann" <mittelmann@asu.edu>
Subject: Complementary Pivot Method
http://plato.la.asu.edu/guide.html
To solve the QP subproblems you may use dualqp in f77 or C versions or another of the recommended codes. To solve the entire problem you may use donlp2 or another code such as LOQO which has a Matlab interface.
Date: Tue, 02 Sep 1997 07:00:36 -0700
From: Hans D Mittelmann <mittelmann@asu.edu>
Subject: Quadratic optimisation procedures
Hi, here is a recent announcement
Announcing LOQO 3.07 and a MATLAB interface for LOQO.
Dear Friends/Colleagues:
I'm pleased to announce the availability of a new version of LOQO, version 3.07, which has dramatically enhanced capabilities. This new version solves convex optimization problems to optimality and nonconvex ones to local optimality. While a subroutine library still exists, the simplest way to feed a nonlinear optimization problem to LOQO is via the math programming language AMPL. This is the default mode of operation. This new AMPL interface makes nonlinear optimization with LOQO just as easy as linear optimization. As usual, LOQO is free for academic use and can be downloaded directly from my home page:
http://www.princeton.edu/~rvdb
Preliminary results showing performance superior to both MINOS and LANCELOT on most large problems will be presented in Lausanne.
I'm also pleased to announce that there is now a LOQO/MATLAB5 interface which allows matlab users to call LOQO from within matlab to solve large-scale sparse quadratic programming problems. The syntax for calling LOQO from within matlab is the same as for matlab's qp(), found in matlab's optimization toolbox, except that the constraint matrix A and the Hessian H are assumed to be stored as sparse matrices:
[x,lambda,how] = loqo(H,c,A,b,l,u,x0,neqcstr,display);
I think you'll find loqo() to be vastly superior to qp() in terms of both speed and robustness. Further details/instructions can be obtained by visiting my home page.
Date: Mon, 08 Sep 1997 10:43:59 -0700
From: Eric ten Siethoff <esiethof@vt.edu>
Subject: Complementary Pivot Method
I am attempting to minimize a quadratic cost function with nonlinear
constraints by sequentially linearizing the constraints and solving the
quadratic programming subproblem. I am currently looking for a code
that implements the Complementary Pivot Method to solve the Kuhn-Tucker
conditions. I'd like it in a Matlab m-file, but FORTRAN, C, or C++
would be o.k. Anyone with info please e-mail me or post something in
the newsgroup. I'd also appreciate any suggestions on this kind of
problem in general.
Thanks,
Eric ten Siethoff
Date: 31 Jan 1997 10:14:45 GMT
From: jamesk@cs.ust.hk (James Kwok)
Subject: large-scale QP
Hi all,
I have a QP problem (with linear equality and inequality constraints) in which the matrix is large (around 10000*10000) and is semi-definite. I would like to know if there is any method and/or public domain software that can solve my problem. Any help or comments are welcome.
Thanks a lot in advance.
James
James Kwok | Department of Computer Science |
Internet: jamesk@cs.ust.hk | The Hong Kong University of |
| Science and Technology |
Date: Fri, 31 Jan 1997 08:08:24 -0700
From: "Hans D. Mittelmann" <mittelmann@asu.edu>
Subject: large-scale QP
Hi
you may use LOQO. Just set up an extended MPS-format input file for this code as described in the included documentation.
http://www.princeton.edu/~rvdb/loqoexecs.html
Hope that helps,
Hans Mittelmann
Hi again, we both did not address the issue of sparseness (as I often find iquiries a bit incompletely formulated). If your matrix is sparse and semidefinite, as you say, LOQO should be fine. If, however, it is full you may look at the paper
ftp://plato.la.asu.edu/pub/donlp2/large_scale_qp.ps.gz
Hans Mittelmann
Date: Thu, 18 Jul 1996 10:14:19 +0200
From: Daniel Hilding <danhi@ikp.liu.se>
Subject: Quadratic Programming
Hello!
I have a large QP problem with sparse constraints.
Thanks in advance
Daniel Hilding
Link=F6ping Institute of Technology, Sweden
E-mail: danhi@ikp.liu.se
Date: 18 Jul 1996 18:52:48 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: Quadratic Programming
LOQO of R.J. Vanderbei does that job quite well. It is however
not public domain source code. Rather there are executables
for some platforms.
if your QP is convex you may try LOQO. Link is on the webpage
http://plato.la.asu.edu/guide.html
Hans Mittelmann (on vacation at Carleton U./Ottawa/Canada)
Date: 3 Aug 1996 21:27:28 GMT
From: hmittelm@ccs.carleton.ca (hmittelm)
Subject: Quadratic Programming
There is one crucial point that should not be overlooked.
LOQO and nearly all other codes listed on the web-page listed below (http://plato.la.asu.edu/guide.html) are public domain and may be used in a self-contained way as source code or in a few cases as libraries or binaries. cGOP is one of the programs that require commercial codes to link up with! Its main difference to, say, LOQO, is that it tries to find global optima. Hans Mittelmann (still on vacation at Carleton U./Ottawa/Canada)
Date: Sun, 4 Aug 1996 11:44:43 +0100
From: Robin Becker <robin@jessikat.demon.co.uk>
Subject: Quadratic Programming
I would be interested to know if there's a Linux-elf version of the LOQO stuff; if not I would be willing to build such a thing if source is available.
Robin Becker