The following program calculates the minimum point of a multi-variable function using random search method coupled with a linear search. The latter part enhances significantly the efficiency of the random walk.
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:
1. Minimum value for each variable:.
2. Maximum value for each variable:.
3. The maximum number of iterations per cycle.
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 results:
1. The coordinates of the minimum value.
2. The minimum function value.
3. The number of iterations
4. The function tolerance.
Here is a sample session to find the minimum of function:
f(x) = x1 - x2 + 2 * x1 ^ 2 + 2 * x1 * x2 + x2 ^ 2
Using the initial value of 0, range of (-5, 5) for each variable, and using a maximum number of 1000000 iterations and a function tolerance of 1e-7. Here is the sample console screen:
Here is the BASIC 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_RandomSearch2
{
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[] { - 5, - 5 };
double[] fXHi = new double[] { 5, 5 };
double fEpsFx = 0.0000001;
int nIter = 0;
int nMaxIter = 1000000;
int i;
double fBestF;
string sAnswer;
CRandomSearch2 oOpt;
MyFxDelegate MyFx = new MyFxDelegate( Fx3);
SayFxDelegate SayFx = new SayFxDelegate( SayFx3);
oOpt = new CRandomSearch2();
Console.WriteLine("Random Search (with linear 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({0}) = {1}", i + 1, fX[i]);
Console.WriteLine("X low({0}) = {1}", i + 1, fXlo[i]);
Console.WriteLine("X high({0}) = {1}", i + 1, fXHi[i]);
}
Console.WriteLine("Maximum iterations = {0}", nMaxIter);
Console.WriteLine("Function tolerance = {0}", fEpsFx);
}
else
{
for (i = 0; i < nNumVars; i++)
{
fX[i] = GetIndexedDblInput("X", i + 1, fX[i]);
fXlo[i] = GetIndexedDblInput("X Low", i + 1, fXlo[i]);
fXHi[i] = GetIndexedDblInput("X High", i + 1, fXHi[i]);
}
nMaxIter = GetIntInput("Maximum iterations", nMaxIter);
fEpsFx = GetDblInput("Function tolerance", fEpsFx);
}
Console.WriteLine("******** FINAL RESULTS *************");
fBestF = oOpt.CalcOptim(nNumVars, ref fX, ref fParam, ref fXlo, ref fXHi, nMaxIter, 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 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_RandomSearch2
{
public delegate double MyFxDelegate(int nNumVars, ref double[] fX, ref double[] fParam);
public delegate string SayFxDelegate();
public class CRandomSearch2
{
MyFxDelegate m_MyFx;
protected double MyFxEx(int N, ref double[] fX, ref double[] fParam, ref double[] fDeltaX, double fLambda)
{
int i;
double[] fX2;
fX2 = new double[N];
for (i = 0; i < N; i++)
{
fX2[i] = fX[i] + fLambda * fDeltaX[i];
}
return m_MyFx(N, ref fX2, ref fParam);
}
protected bool LinSearch_DirectSearch(int N, ref double[] fX, ref double[] fParam, ref double fLambda, ref double[] fDeltaX, double fInittep, double fMinStep)
{
double F1, F2;
object temp_object = fX;
double[] temp_double = (double[]) temp_object;
object temp_object4 = fParam;
double[] temp_double4 = (double[]) temp_object4;
object temp_object7 = fDeltaX;
double[] temp_double7 = (double[]) temp_object7;
F1 = MyFxEx(N, ref temp_double, ref temp_double4, ref temp_double7, fLambda);
do
{
F2 = MyFxEx(N, ref fX, ref fParam, ref fDeltaX, fLambda + fInittep);
if (F2 < F1)
{
F1 = F2;
fLambda = fLambda + fInittep;
}
else
{
F2 = MyFxEx(N, ref fX, ref fParam, ref fDeltaX, fLambda - fInittep);
if (F2 < F1)
{
F1 = F2;
fLambda = fLambda - fInittep;
}
else
{
// reduce search step size
fInittep = fInittep / 10;
}
}
} while (!(fInittep < fMinStep));
return true;
}
public double CalcOptim(int nNumVars, ref double[] fX, ref double[] fParam, ref double[] fXLo, ref double[] fXHi, int nMaxIter, double EpsFx, ref int nIter, MyFxDelegate MyFx)
{
double[] fDeltaX;
double fInitStep = 0.1;
double fMinStep = 0.00001;
double F, fBestF, fLastBestF, fLambda;
double[] fBestX;
int i;
Random objRand = new Random();
m_MyFx = MyFx;
fDeltaX = new double[nNumVars];
fBestX = new double[nNumVars];
for (i = 0; i < nNumVars; i++)
{
fBestX[i] = fX[i];
}
// calculate and display function value at initial point
fBestF = MyFx(nNumVars, ref fBestX, ref fParam);
if (fBestF > 0)
{
fLastBestF = fBestF + 100;
}
else
{
fLastBestF = 100 - fBestF;
}
nIter = 0;
do
{
nIter++;
if (nIter > nMaxIter)
{
break;
}
for (i = 0; i < nNumVars; i++)
{
fX[i] = fXLo[i] + objRand.NextDouble() *(fXHi[i] - fXLo[i]);
fDeltaX[i] = fX[i] - fBestX[i];
}
fLambda = 0.1;
LinSearch_DirectSearch(nNumVars, ref fBestX, ref fParam, ref fLambda, ref fDeltaX, fInitStep, fMinStep);
for (i = 0; i < nNumVars; i++)
{
fX[i] = fBestX[i] + fLambda * fDeltaX[i];
}
F = MyFx(nNumVars, ref fX, ref fParam);
if (F < fBestF)
{
for (i = 0; i < nNumVars; i++)
{
fBestX[i] = fX[i];
}
fBestF = F;
// test function value convergence
if (Math.Abs(fBestF - fLastBestF) < EpsFx)
{
break;
}
fLastBestF = fBestF;
}
} while (true);
return fBestF;
}
}
}
Copyright (c) Namir Shammas. All rights reserved.