Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] acem_v1_0.gz(60 Kbytes)
Manuscript Title: CONCON: a code for constrained minimization without derivative computation.
Authors: A. Buckley
Program title: CONCON
Catalogue identifier: ACEM_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 29(1983)231
Programming language: Fortran.
Computer: CDC CYBER 835.
RAM: 6K words
Word size: 60
Keywords: General purpose, Optimization, Minimization, Linear constraints, Non-derivative, Conjugacy.
Classification: 4.9.

Nature of problem:
The problem is mathematical rather than physical, although the source of the mathematical problem can be any one of a number of fields of physics or engineering. The problem solved by CONCON is that of minimizing a nonlinear function f(x), where x may (but need not) be subject to a set of linear constraints of the form cTi(x)>bi, i=1,... ,m. Here x is a vector of n variables. Some of the constraints may be equalities or they may be simple bounds x1>0, which may be written as eTi(x) >0 to fit the above form.

Solution method:
The method of solution is completely described in a related pubilication (see Buckley). In the unconstrainted case, the method is essentially the method of conjugate directions due to Powell. This code adapts Powell's method to the case where linear constraints on the variables must be satisfied. The code also includes some of the refinements of Brent.

Restrictions:
There are no restrictions imposed by the code itself, except that of course the problem must fit the form stated. All work arrays which are required are passed to the subroutines; therefore, the user may make them sufficiently large to solve the problem at hand. However, it is known that there is a heuristic restriction on the method. In the unconstrained case, Powell's technique is known to suffer degradation in its performance as n increases. It is hard to state a specfic value for n at which this occurs, since it is of course problem dependent. Nonetheless, it is probably fair to say that Powell's conjugacy method becomes significantly less effective for n>= 10. In the constrainted case, the same is likely true, although it is not n that is relevant, but rather the dimension of the manifold in which the minimum occurs.

Unusual features:
The program uses a number of routines of the LINPACK package.

Running time:
This is highly problem dependent. The only guideline here is to observe the execution time recorded when executing the test problems included with CONCON. Remember though that the evaluation of "real-live" functions may be noticeably more complex and time consuming than that of the test functions used here.