Solving nonlinear problem in Excel II: Using downhill simplex method
Zhanshan Dong
Introduction
In Excel, there is an Add-in called Solver that can be used to solve nonlinear equations. I have experience to use it solve neural network problems and solving nonlinear regression equations. It provides a user-friendly interface that user can set all parameters that solver needs. The Solver is very handy for solving only one problem at a time. In the situation that I often encounter it is not very convenient. For example, I have a huge number of silking and shedding dynamic observations for thousands genetic lines. One logistic equation should be estimated based on the observations from one line. So there are thousands of equations are waiting for solving. If Solver is used, manual operation will kill users. How can we overcome the burden of manual operation and achieve an automatic way. One way might be to implement other optimization methods in Excel through Visual Basic for Application. In this article, I will introduce how to implement a derivative free method - Downhill Simplex optimization mothod - in Excel 2000.
Implementation of Downhill Simplex method
What is Downhill simplex method?
(the following paragraphs copied from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)
Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software.
A simplex is the geometrical figure consisting, in N dimensions, of N + 1 points (or vertices) and all their interconnecting line segments, polygonal faces, etc. In two dimensions, a simplex is a triangle. In three dimensions it is a tetrahedron, not necessarily the regular tetrahedron.
The downhill simplex method must be started not just with a single point, but with N + 1 points, defining an initial simplex. If you think of one of these points (it matters not which) as being your initial starting point P0, then you can take the other N points to be
Pi = P0 + λei (10.4.1)
where the ei’s are N unit vectors, and where λ is a constant which is your guess of the problem’s characteristic length scale. (Or, you could have different λ i’s for each vector direction.) The downhill simplex method nowtakes a series of steps, most steps just moving the point of the simplex where the function is largest (“highest point”) through the opposite face of the simplex to a lower point. These steps are called reflections, and they are constructed to conserve the volume of the simplex (hence maintain its nondegeneracy). When it can do so, the method expands the simplex in one or another direction to take larger steps. When it reaches a “valley floor,” the method contracts itself in the transverse direction and tries to ooze down the valley. If there is a situation where the simplex is trying to “pass through the eye of a needle,” it contracts itself in all directions, pulling itself in around its lowest (best) point. The routine name amoeba is intended to be descriptive of this kind of behavior; the basic moves are summarized in Figure 10.4.1.
Termination criteria can be delicate in any multidimensional minimization routine. Without bracketing, and with more than one independent variable, we no longer have the option of requiring a certain tolerance for a single independent variable. We typically can identify one “cycle” or “step” of our multidimensional algorithm. It is then possible to terminate when the vector distance moved in that step is fractionally smaller in magnitude than some tolerance tol. Alternatively, we could require that the decrease in the function value in the terminating step be fractionally smaller than some tolerance ftol. Note that while tol should not usually be smaller than the square root of the machine precision, it is perfectly appropriate to let ftol be of order the machine precision (or perhaps slightly larger so as not to be diddled by roundoff).
Note well that either of the above criteria might be fooled by a single anomalous step that, for one reason or another, failed to get anywhere. Therefore, it is frequently a good idea to restart a multidimensional minimization routine at a point where it claims to have found a minimum. For this restart, you should reinitialize any ancillary input quantities. In the downhill simplex method, for example, you should reinitialize N of the N + 1 vertices of the simplex again by equation (10.4.1), with P0 being one of the vertices of the claimed minimum.
How to implement it?
In order to generalize the method, it is implemented as a generic class. In which a generic model class is referred.
Amoeba Class
The Downhill Simplex method is implemented as a class – Ameoba class.
Data properties
To set the model object that will be trained by Amoeba, the Model property is provided.
Public Property Let Model(aModel As Object)
|
After the provided model is trained, the training results can be explored by using the following properties.
Public Property Get PStart(ByVal subs1 As Integer, ByVal subs2 As Integer) As Double
Public Property Get PEnd(ByVal subs1 As Integer, ByVal subs2 As Integer) As Double
Public Property Get YStart(ByVal subs1 As Integer) As Double
Public Property Get YEnd(ByVal subs1 As Integer) As Double
Public Property Get NumFunc() As Integer
|
Member functions
Usage
To use this class, you have to do the following things
1) Define a public class that defines the nonlinear model (in this example, it is LogisticModel)
2) Declare an instance of the model class and fill all necessary data fields
3) Assign the model instance to the model property of the Amoeba class
4) Call Amoeba's train method to fit the model
5) You can get the train results from two places: Amoeba's members and model's members
Model Class
To define a model class that can be used in Amoeba class, there two data members and one member function are requested.
To get the number of parameters in the model:
Public property numParams as interger
|
To get or set all parameters in the model:
Public property Param() as double
|
To evaluate the model, the following public function should be provided:
Public Function Eval(aParams() as double) as Double
|
For your convenience, you can set other public properties and functions for the model class.
[Download Amoeba VBA code][Download LogistModel VBA code]
©董占山Zhanshan Dong
|
