Subject: Constrained Optimization Methods

From: Dongchul Lim <[email-masked]>
Date: Fri, 24 Mar 95 1:51:50 EST

There has been some discussion on the subject of 'optimization with
constraints' in this mailing list.
A while ago, I happened to be interested in "constrained optimization
without derivatives". Although this is about non-gradient optimization
methods, it is possible to use derivatives as well in most methods.
The following summary is what I collected from the usenet and private
communications.
I hope this information will be helpful.

Dongchul Lim, Department of Chemistry, Yale Univ.

< Summary of Constrained Optimization without Derivatives >
_________________________________________________________________________
>From [email-masked]  Fri Mar 10 08:20:02 1995
Try David Gay's dmnfb code from netlib.

_________________________________________________________________________
>From [email-masked]  Mon Mar 13 09:10:36 1995

The following newly published book is for
your possible interest.

    Title  :  "A NUMERICAL LIBRARY IN C FOR
               SCIENTISTS AND ENGINEERS"
              (ISBN 0-8493-7376-X), 1995
 Publisher :  CRC Press, Inc.
              2000 Corporate Blvd., N.W.
              Boca Raton, FL 33431
              USA
              telephone: (407)-994-0555

This book contains an extensive coverage of
computer programs in numerical computing, with
several hundred procedures including areas in
    Linear Algebra
    Ordinary and Partial Differential Equations
      (stiff and non-stiff systems)
    Optimization
    Parameter Estimation
    Special Functions in mathematical physics.
A diskette is included with all the source code.

_________________________________________________________________________
>From [email-masked]  Fri Mar 10 16:27:59 1995

I refer you to Fletcher's book, _Practical Methods of Constrained
Optimization_ (or something like that).  For simple bounds, the
algorithms will probably be BFGS with Active Set (to convert the
inequality constraints into equality constraints when the inequality
constraint is violated) and Lagrange multipliers to handle the
resulting equality constraints (or some other method for linear
constraints).

_________________________________________________________________________
>From [email-masked]  Fri Mar 10 16:03:48 1995

You inquired about direct search methods for minimizing
a function subject to constraints.

I have FORTRAN software available via anonymous ftp: see files readme.opt,
marq.f, stepit.f, and simplex.f in directory /pub/jpc at a.cs.okstate.edu .

MARQ is for nonlinear (or linear) least squares problems only.
STEPIT and SIMPLEX are direct search minimizers.
All allow the use of XMIN(J) and XMAX(J) limits on the parameters X(J).
STEPIT and SIMPLEX are interchangeable; MARQ is nearly so.

This software is robust, portable, and supported (by me).
It has been used at many sites for over twenty years.
It can be used and distributed freely.

If you have any further questions, send e-mail.

Good luck.
John Chandler

_________________________________________________________________________
>From [email-masked]  Fri Mar 10 13:28:17 1995

If the objective function is smooth, then you should consider an 
implementation of a quasi-newton method such as BFGS, using finite
difference approximations.  

If the objective function is not smooth, then you should look at methods
for "nonsmooth optimization".  

You should probably take a look at "Optimization Software Guide"
by More and Wright.  It has listing of dozens of optimization packages
for different types of problems.

_________________________________________________________________________
>From [email-masked]  Fri Mar 10 11:23:27 1995

Check out netlib by ftp to netlib.att.com, directory netlib.
There is a lot of numerical code there.  Specifically, if you
like C, in netlib/c/brent.shar.Z and serv.shar.Z there are
routines that will do what you ask.  (I think most of the code
in netlib is FORTRAN; you may prefer that anyway.)

_________________________________________________________________________
From: John D'Errico <[email-masked]>

I know this is not the best solution possible (so please cool the
flames) but a trick that has worked for me when I was looking to
constrain a variable in an optimization without resorting to a
constrained code is to introduce a transformation of variables.
If you want a variable x to be constrained to the interval [a,b],
simply substitute

x = a + (b-a)*(sin(z)+1)/2

When the optimizer returns z, run it through the transformation
to determine x. If all you want is to introduce a lower bound,
this can be accomplished by

x = a + z^2

(Do not try to use an absolute value function as it will introduce
a singularity at z=0. This will confuse gradient based methods to
no end.)

This allows you to use an unconstrained code on the variable z.
Again, I admit this method has its flaws, but it does work in a
pinch. You have to accept that there are suddenly many local
optima, though all of the ones so introduced will be equivalent.
You may also end up introducing significant extra curvature into
what was once a well behaved function. Finally, if you are using
this trick on a nonlinear least squares problem, then estimates
of confidence regions for the variables will no longer be correct.

_________________________________________________________________________
>From [email-masked]

John D'Errico suggests using penalty functions as a
quick-and-dirty (but extremely useful) way of getting
an unconstrained optimization software package to
do bounds-constrained problems.  He gives examples
of continuous penalty functions.

I'll point out that if you use an optimization algorithm
such as NelderMead Simplex or HookeJeeves (which doesn't
require the objective function to be differentiable),
then you can use DIScontinuous penalty functions and/or
barrier functions.  These have the advantage of not
introducing any false minima inside the constraint
boundaries, because they only modify the objective
function beyond the boundaries.

A simple example:
  find the minimum of y= tan(log(x) - 3x) * cos(1/x^2)
  subject to the constraints  x>=4.0  and x<10.0

  Discontinuous penalty function approach:
  let f(x) = tan(log(x) - 3x) * cos(1/x^2)

  if(x < 4.0)   then return(  f(4.0) * 10.0 * (1.0 + (4.0-x)^2) ) ;
  if(x >= 10.0) then return( f(10.0) * 10.0 * (1.0 + (x-10.0)^2) ) ;
  return( f(x) );

_________________________________________________________________________