• Home

• About

  • Definitions

  • Organization

  • Development

  • Participation

• Model

  • Model Wiki

  • JSim Software

  • Model Archive

• Links

  • Websites

  • Print Publications

• News

  • Announcements

  • Conferences

• Search

JSim Optimization Algorithms

Introduction

There is no perfect optimization algorithm that is best for all problems. Optimization algorithms vary in their approach, efficiency, robustness and applicability to particular problem domains. This document describes the optimization algorithms currently supported by JSim in some detail so users can make intelligent use of them. JSim's currently available optimizers are Simplex, GGopt, GridSearch and Nelder-Mead. Other algorithms are in development.

Prerequisites:

• Introduction to the JSim Optimizer

Contents:

• Overview
• Simplex
• GGopt
• GridSearch (JSim version 1.6.67 and above)
• Nelder-Mead (JSim version 1.6.67 and above)
• Nl2sol (JSim version 1.6.80 and above)
• Sensop (JSim version 1.6.81 and above)
• Simulated Annealing (JSim version 1.6.82 and above)

Overview

Some terminology is useful when discussing the merits of optimization algorithms:

• Bounded algorithms are those that require upper and lower bounds for each parameter varied. Unbounded algorithms require no such bounds.
• Parallel algorithms are those that can take advantage of multiple system processors for faster processing. See Using JSim Multiprocessing for further information on JSim multiprocessing.

All of JSim's currently available optimization algorithms share the following control parameters:

• max # runs: The optimizer will stop if it has run the model this many times.
• min RMS error: The optimizer will stop if the mean RMS error between reference data and model output is less than this value.

Algorithm-specific control parameters are listed with each algorithm description.

Simplex

JSim's simplex is a bounded, non-linear steepest-descent algorithm. This algorithm does not currently support parallel processing. (description needs work)

Algorithm-specific control parameters:

• parameter initial step: default=0.01
• minimum par step: The optimizer will stop if it is considering a parameter step value that vary less than this value.

GGopt

GGopt is an unbounded non-linear algorithm originally written by Glad and Goldstein. This algorithm does not currently support parallel processing. (description needs work)

Algorithm-specific control parameters:

• minimum par step: The optimizer will stop if it is considering a parameter step value that vary less than this value.
• maximum # iterations: default=10
• minimum gradient: default=1e-6
• relative error: default=1e-6

Nelder-Mead

Nelder-Mead is an unbounded, steepest descent algorithm by Nelder and Mead. It is also called non-linear Simplex. This algorithm supports multiprocessing (MP) and is available in JSim versions 1.6.67 and above.

During each iteration in a P-parameter optimization, this algorithm performs a P or P+1 parmeter queries (model runs). Several additional single queries are also performed. Ideal MP speedup on an N-processor system on be roughly of order P (if P is a factor of N), or order N (if N is a factor of P).

This algorithm differs from the previously available JSim "Simplex" (above) in that:

• it is unbounded, while "Simplex" is bounded;
• it supports MP, while "Simplex" does not;
• it is a newer implementation of the algorithm (Java vs. Fortran).

Algorithm-specific control parameters:

• parameter initial step: default=0.01
• minimum par step: The optimizer will stop if it is considering a parameter step value that vary less than this value.

GridSearch

GridSearch is a bounded, parallel algorithm available in JSim 1.6.67 and above. The algorithm operates via progressively restricted search of parameter space on a regularly spaced grid of npoints per dimension. Each iteration, npoints^nparm points are searched for the minimum residual. Each parameter dimension is then restricted to one grid delta around that minimum and the search repeats until stopping criteria are met.

Search bounds in each dimension narrow by a factor of at least 2/(npoints-1) each iteration. Thus, npoints must be at least 4. Each iteration requires up to npoints^nparm residual calculations. Residual calculations are reused when possible, and this reuse is most efficient when npoints is 1 + 2^N for some N. Therefore, npoints defaults to 5, which is the smallest "efficient" value.

This algorithm is very not efficient for very smooth residual functions in high-dimensional space. It works well on noisy functions when low accuraccy situations (e.g. 3 significant digits required). With npoints large, it copes well with multiple local minima. An effective strategy may be to use several interations of GridSearch to estimate a global minimum, and then use a steepest-descent algorithm to fine tune the answer.

The number of points searched during each iteration is typically large compared to the number of available processors. Typical MP speedup on an N-processor system is therefore on the order of N.

Algorithm-specific control parameters:

• minimum par step: The optimizer will stop if it is considering a parameter step value that vary less than this value.
• max # iterations: stop after this many iterations, default=10.
• # grid points: npoints above, default=5.

Nl2sol

This version of Nl2sol is derived from NL2SOL, a library of FORTRAN routines which implement an adaptive nonlinear least-squares algorithm. It has been modified to perform all calculations in double precision. It is an unbounded optimizer. This optimizer does not support multi-processing and is available in JSim versions 1.6.80 and above.

Algorithm-specific control parameters:

• maximum # runs: default=50
• relative error: default=1e-6

Sensop

Sensop is a variant of Levenberg-Marquardt algorithm that utilized the maximum parameter sensitivity to determine step size. It is a bounded optimizer, supporting multiprocessing and is available in JSim versions 1.6.81 and above.

Algorithm-specific control parameters:

• minimum gradient: default=50
• minimum par step: The optimizer will stop if it is considering a parameter step value that vary less than this value.

Simulated Annealing

Simulated annealing is an algorithm inspired by the annealing process in metullurgy. As the problem "cools" from its initial "temperature", random fluctuations of model parameters are reduced. JSim implements a bounded version of this algorithm that supports multiprocessing and is available in JSim versions 1.6.82 and above.

Algorithm-specific control parameters:

• initial temperature:default=100. This parameter has no physical meaning (e.g. Kelvin), but must be positive.

[This page was last modified 03Mar08, 3:11 pm.]

Model development and archiving support at physiome.org provided by the following grants: NIH/NHLBI T15 HL88516-01 Modeling for Heart, Lung and Blood: From Cell to Organ, 4/1/07-3/31/11; NSF BES-0506477 Adaptive Multi-Scale Model Simulation, 8/15/05-7/31/08; NIH/NHLBI R01 HL073598 Core 3: 3D Imaging and Computer Modeling of the Respiratory Tract, 9/1/04-8/31/09; as well as prior support from NIH/NCRR P41 RR01243 Simulation Resource in Circulatory Mass Transport and Exchange, 12/1/1980-11/30/01 and NIH/NIBIB R01 EB001973 JSim: A Simulation Analysis Platform, 3/1/02-2/28/07.