The Unconstrained NLO Problem

The Problem: min f(x), n=dim(x)

The picture shows the level set representation of Beale's testfunction

f(x,y)=(1.5-x(1-y))^2+(2.25-x(1-y^2))^2+(2.625-x(1-y^3))^2.
It has a unique global minimizer at (3,0.5) and a saddle point at (0,0). There is a further saddle point at (0.100538,-2.644514). For x=0 or y=1 it is constant with value 14.203125. In x<0 there exists an arc y(x)>0, where f decreases monotonically as x-> -INF. Initial values near x=0 for large |y| or x<0, y>0 will let descent methods fail.

The methods listed here all restrict themselves to finding one solution of grad f(x)=0. For trust region based methods one often can show that this solution automatically satisfies the second order necessary conditions.

f is a "general" twice continuously differentiable function, but gradient is not available:

The methods implicitly all assume that f is twice continuously differentiable. They may fail or converge very slowly if this is not the case. Read M. Powell's and M. Wright's papers on Direct Search methods.

	FMIN	Brent's direct search method, one variable.
	UOBYQA	Powell's unconstrained optimization by quadratic approximation (f77/C)
	WEDGE	Interpolation/trust region method for moderate dimensions(Matlab)
	netlib/opt/praxis	f depends on few variables, the "principal axis method", tries to approximate the curvature of f
	MCToolbox	three direct search methods incl Nelder-Mead, Matlab
	nelmead	f depends on few variables, Nelder-Mead simplex-search method (no sound theoretical basis), f77
	netlib/opt/subplex	f depends on few variables, modification of the Nelder-Mead simplex-search method (no sound theoretical basis), MATLAB
	fminsi	modified Nelder-Mead, LGPL-licensed, source, testdriver
	DFO	derivative free method of Conn, Scheinberg, and Toint
	APPSPack	Asynchronous and Fault Tolerant Parallel Pattern Search (LGLP, C++, serial or PVM or MPI)

f is only Lipschitz continuous, n not too large

	NDA	Four different routines for Lipschitz continuous functions and for (small) minimax problems
	ACCPM	Analytic center cutting plane method, requires oracle to be written in C. Solaris, Linux, Win32 binaries of library

The gradient of f is available or finite difference approximations are applicable : n not too large (<= some hundred say)

	domin	Spellucci's implementation of BFGS, different versions, exact/automatic/numerical gradients, f77/C
	netlib/toms/500	the Shanno-Phua version of BFGS plus CG
	netlib/toms/611	trust region BFGS, this is a reliable and fairly efficient code.
	netlib/toms/739	tensor model quasi-Newton method, may be better for strongly nonquadratic f
	UCMINF	several methods, paper (Matlab)

f is convex differentiable, n large:

netlib/opt/ve08

f is a sum of convex differentiable functions each of which has considerably less variables than n (partially separable problem) (also for bound constraints), special quasi Newton method

n large, f general, but not too wildly behaved :

	netlib/toms/630 updated version in f90	A combined limited memory qN/cg method (degrades for nonconvex f, nevertheless applicable; for ill-conditioned problem an individual preconditioner must be provided)
	MINPACK-2	A limited memory quasi Newton method. Directories contain software, drivers and manuals. (dcsrch.f, the step-size-algorithm, must be added; to be found e.g. in the following code)
	LBFGS	a limited memory quasi Newton method using a new matrix representation; directory contains software, drivers and a user's manual. Not to be recommended for ill-conditioned problems. Add your own preconditioner! Java version, f90-version
	CG+	three basic cg methods, PREQN (preconditioning package)
	LM	Several limited memory f77-routines for unconstrained and box-constrained optimization; also for least squares

n large, f strongly nonquadratic :

	netlib/opt/tn C-version	Nash's truncated Newton method based on the Lanczos method, without explicit eigenvalue computation. takes directions of negative curvature into account.
	netlib/toms/702	truncated Newton based on the Lanczos process
	TRON	trust region Newton, preconditioned cg, also for bound constraints
	PL2	truncated Newton method using the Lanczos process with direct computation of a truncated spectral decomposition, uses a so called three directions method from Heinrich, uses directions of negative curvature. for large dimensional problems.

f noisy :

	IFFCO	implicit filtering subject to box constraints and with multiple minima
	DIRECT	the DIRECT algorithm
	netlib/opt/praxis	often applied to noisy problems although not directly designed for such
	UOBYQA	Powell's unconstrained optimization by quadratic approximation (f77/C)
	netlib/opt/subplex	f depends on few variables, modification of the Nelder-Mead simplex-search method (no sound theoretical basis), MATLAB

f expensive to evaluate :

	SPACE	global optimization through meta-modeling: fitting, cross-validation, prediction, minimization etc (C++)
	DACE	Matlab toolbox to construct a kriging approximation (surrogate) to computer models