The following program calculates the minimum point of a multi-variable function using the grid search method. This method performs a multi-dimensional grid search. The grid is defined by a multiple dimensions. Each dimension has a range of values. Each range is divided into a set of equal-value intervals. The multi-dimensional grid has a centroid which locates the optimum point. The search involves multiple passes. In each pass, the method local a node (point of intersection) with the least function value. This node becomes the new centroid and builds a smaller grid around it. Successive passes end up shrinking the multidimensional grid around the optimum.
Click here to download a ZIP file containing the project files for this program.
The program prompts you to either use the predefined default input values or to enter the following for each variable (i.e. dimension):
1. The values that define the lower and upper limits of a search range for a variable,
2. The number of divisions for a range.
3. The minimum range value, used to determine when to stop searching..
The program also asks you to enter the function tolerance. The program uses this value to possible stop iterating when successive best function values are close enough.
In case you choose the default input values, the program displays these values and proceeds to find the optimum point. In the case you select being prompted, the program displays the name of each input variable along with its default value. You can then either enter a new value or simply press Enter to use the default value. This approach allows you to quickly and efficiently change only a few input values if you so desire.
The program displays the following final results:
1. The coordinates of the minimum point.
2. The minimum function value.
3. The number of iterations
Here is a sample session to find the minimum of function:
f(x) = x1 - x2 + 2 * x1 ^ 2 + 2 * x1 * x2 + x2 ^ 2
Using, for each variable, the range of (-10, 10), initial range divisions of 4, minimum step size of 1e-5. The solution also uses a function tolerance of 1e-7. Here is the sample console screen:
Here is the listing for the main module. The module contains several test functions:
using System.Diagnostics;
using System.Data;
using System.Collections;
using Microsoft.VisualBasic;
using System.Collections.Generic;
using System;
namespace Optim_GridSearch1
{
sealed class Module1
{
static public void Main()
{
int nNumVars = 2;
double[] fX = new double[] { 0, 0 };
double[] fParam = new double[] { 0, 0 };
double[] fXLo = new double[] { - 10, - 10 };
double[] fXHi = new double[] { 10, 10 };
int[] nNumDiv = new int[] { 4, 4 };
double[] fMinDeltaX = new double[] { 0.00001, 0.00001 };
int nIter = 0;
double fEpsFx = 0.0000001;
int i;
object fBestF;
string sAnswer;
CGridSearch oOpt;
MyFxDelegate MyFx = new MyFxDelegate( Fx3);
SayFxDelegate SayFx = new SayFxDelegate( SayFx3);
oOpt = new CGridSearch();
Console.WriteLine("Grid Search Optimization");
Console.WriteLine("Finding the minimum of function:");
Console.WriteLine(SayFx());
Console.Write("Use default input values? (Y/N) ");
sAnswer = Console.ReadLine();
if (sAnswer.ToUpper() == "Y")
{
for (i = 0; i < nNumVars; i++)
{
Console.WriteLine("X Low({0}) = {1}", i + 1, fXLo[i]);
Console.WriteLine("X High ({0}) = {1}", i + 1, fXHi[i]);
Console.WriteLine("Divisions({0}) = {1}", i + 1, nNumDiv[i]);
Console.WriteLine("MinStepSize({0}) = {1}", i + 1, fMinDeltaX[i]);
}
Console.WriteLine("Function tolerance = {0}", fEpsFx);
}
else
{
for (i = 0; i < nNumVars; i++)
{
fXLo[i] = GetIndexedDblInput("X low", i + 1, fXLo[i]);
fXHi[i] = GetIndexedDblInput("X high", i + 1, fXHi[i]);
nNumDiv[i] = GetIndexedIntInput("Number of divisions", i + 1, nNumDiv[i]);
fMinDeltaX[i] = GetIndexedDblInput("Minimum step size", i + 1, fMinDeltaX[i]);
}
fEpsFx = GetDblInput("Function tolerance", fEpsFx);
}
Console.WriteLine("******** FINAL RESULTS *************");
fBestF = oOpt.CalcOptim(nNumVars, ref fX, ref fParam, ref fXLo, ref fXHi, ref nNumDiv, ref fMinDeltaX, fEpsFx, ref nIter, MyFx);
Console.WriteLine("Optimum at");
for (i = 0; i < nNumVars; i++)
{
Console.WriteLine("X({0}) = {1}", i + 1, fX[i]);
}
Console.WriteLine("Function value = {0}", fBestF);
Console.WriteLine("Number of iterations = {0}", nIter);
Console.WriteLine();
Console.Write("Press Enter to end the program ...");
Console.ReadLine();
}
static public double GetDblInput(string sPrompt, double fDefInput)
{
string sInput;
Console.Write("{0}? ({1}): ", sPrompt, fDefInput);
sInput = Console.ReadLine();
if (sInput.Trim(null).Length > 0)
{
return double.Parse(sInput);
}
else
{
return fDefInput;
}
}
static public int GetIntInput(string sPrompt, int nDefInput)
{
string sInput;
Console.Write("{0}? ({1}): ", sPrompt, nDefInput);
sInput = Console.ReadLine();
if (sInput.Trim(null).Length > 0)
{
return (int) double.Parse(sInput);
}
else
{
return nDefInput;
}
}
static public double GetIndexedDblInput(string sPrompt, int nIndex, double fDefInput)
{
string sInput;
Console.Write("{0}({1})? ({2}): ", sPrompt, nIndex, fDefInput);
sInput = Console.ReadLine();
if (sInput.Trim(null).Length > 0)
{
return double.Parse(sInput);
}
else
{
return fDefInput;
}
}
static public int GetIndexedIntInput(string sPrompt, int nIndex, int nDefInput)
{
string sInput;
Console.Write("{0}({1})? ({2}): ", sPrompt, nIndex, nDefInput);
sInput = Console.ReadLine();
if (sInput.Trim(null).Length > 0)
{
return (int) double.Parse(sInput);
}
else
{
return nDefInput;
}
}
static public string SayFx1()
{
return "F(X) = 10 + (X(1) - 2) ^ 2 + (X(2) + 5) ^ 2";
}
static public double Fx1(int N, ref double[] X, ref double[] fParam)
{
return 10 + Math.Pow(X[0] - 2, 2) + Math.Pow(X[1] + 5, 2);
}
static public string SayFx2()
{
return "F(X) = 100 * (X(1) - X(2) ^ 2) ^ 2 + (X(2) - 1) ^ 2";
}
static public double Fx2(int N, ref double[] X, ref double[] fParam)
{
return Math.Pow(100 * (X[0] - X[1] * X[1]), 2) + Math.Pow((X[1] - 1), 2);
}
static public string SayFx3()
{
return "F(X) = X(1) - X(2) + 2 * X(1) ^ 2 + 2 * X(1) * X(2) + X(2) ^ 2";
}
static public double Fx3(int N, ref double[] X, ref double[] fParam)
{
return X[0] - X[1] + 2 * X[0] * X[0] + 2 * X[0] * X[1] + X[1] * X[1];
}
}
}
Notice that the user-defined functions have accompanying helper functions to display the mathematical expression of the function being optimized. For example, function Fx1 has the helper function SayFx1 to list the function optimized in Fx1. Please observe the following rules::
The program uses the following class to optimize the objective function:
using System.Diagnostics;
using System.Data;
using System.Collections;
using Microsoft.VisualBasic;
using System.Collections.Generic;
using System;
namespace Optim_GridSearch1
{
public delegate double MyFxDelegate(int nNumVars, ref double[] fX, ref double[] fParam);
public delegate string SayFxDelegate();
public class CGridSearch
{
public double CalcOptim(int nNumVars, ref double[] fXCenter, ref double[] fParam, ref double[] fXLo, ref double[] fXHi, ref int[] nNumDiv, ref double[] fMinDeltaX, double fEpsFx, ref int nIter, MyFxDelegate MyFx)
{
double[] fDeltaX;
double[] fX;
double[] fBestX;
double F, fBestF, fLastBestF;
int i;
bool bGoOn, bGoOn2;
fDeltaX = new double[nNumVars];
fX = new double[nNumVars];
fBestX = new double[nNumVars];
for (i = 0; i < nNumVars; i++)
{
fXCenter[i] = (fXLo[i] + fXHi[i]) / 2;
fBestX[i] = fXCenter[i];
fDeltaX[i] = (fXHi[i] - fXLo[i]) / nNumDiv[i];
fX[i] = fXLo[i];
}
// calculate and display function value at initial point
fBestF = MyFx(nNumVars, ref fXCenter, ref fParam);
if (fBestF > 0)
{
fLastBestF = 100 + fBestF;
}
else
{
fLastBestF = 100 - fBestF;
}
nIter = 0;
do
{
bGoOn2 = true;
do
{
nIter++;
F = MyFx(nNumVars, ref fX, ref fParam);
if (F < fBestF)
{
fLastBestF = fBestF;
fBestF = F;
for (i = 0; i < nNumVars; i++)
{
fBestX[i] = fX[i];
}
}
//*****************************************************
// The next For loop implements a programming tricks
// that simulated nested loops using just one For loop
//*****************************************************
// search next grid node
for (i = 0; i < nNumVars; i++)
{
if (fX[i] >= fXHi[i])
{
if (i < (nNumVars - 1))
{
fX[i] = fXLo[i];
}
else
{
bGoOn2 = false;
}
}
else
{
fX[i] += fDeltaX[i];
break;
}
}
} while (bGoOn2);
for (i = 0; i < nNumVars; i++)
{
fXCenter[i] = fBestX[i];
fDeltaX[i] = fDeltaX[i] / nNumDiv[i];
fXLo[i] = fXCenter[i] - fDeltaX[i] * nNumDiv[i] / 2;
fXHi[i] = fXCenter[i] + fDeltaX[i] * nNumDiv[i] / 2;
fX[i] = fXLo[i]; // set initial fX
}
// fBestF = MyFx(XCenter, N)
bGoOn = false;
for (i = 0; i < nNumVars; i++)
{
if (fDeltaX[i] > fMinDeltaX[i])
{
bGoOn = true;
}
}
bGoOn = bGoOn &&(Math.Abs(fBestF - fLastBestF) > fEpsFx);
} while (bGoOn);
return fBestF;
}
}
}
Copyright (c) Namir Shammas. All rights reserved.