Canvas JavaScript
Function Minimization via the Simplex Method
This JavaScript program demonstrates how to minimize a function using the simplex method of Nelder and Mead. The steps of the method are displayed as triangles and the type of action taken at each step is displayed as a color. The level sets are drawn to make the minimum apparent.
FunctionMinimizationViaSimplexMethod.html
<!DOCTYPE html>
<html>
<head>
<title>XoaX.net's Javascript</title>
<script type="text/javascript" src="FunctionMinimizationViaSimplexMethod.js"></script>
</head>
<body onload="Initialize()">
<canvas id="idCanvas" width="600" height ="600" style="background-color: #F0F0F0;"></canvas>
</body>
</html>FunctionMinimizationViaSimplexMethod.js
class Graph2D {
constructor(dLowX, dHighX, dLowY, dHighY, iCanvasW, iCanvasH) {
this.mdLowX = dLowX;
this.mdHighX = dHighX;
this.mdLowY = dLowY;
this.mdHighY = dHighY;
this.miCanvasW = iCanvasW;
this.miCanvasH = iCanvasH;
}
XtoPixelX(dX) {
return ((dX - this.mdLowX)/(this.mdHighX - this.mdLowX))*this.miCanvasW;
}
YtoPixelY(dY) {
return (1 - (dY - this.mdLowY)/(this.mdHighY - this.mdLowY))*this.miCanvasH;
}
PixelW() {
return (this.mdHighX - this.mdLowX)/this.miCanvasW;
}
PixelH() {
return (this.mdHighY - this.mdLowY)/this.miCanvasH;
}
// Map the function a a level curve of the function z(x, y) = -y(x) + ...
async DrawGraphOver(qContext, fnF, fnGradF, iSamplesPerPixelX, iSamplesPerPixelY, dPenWidth, daLevels) {
var qImageData = qContext.createImageData(this.miCanvasW, this.miCanvasH);
const kdDxDp = this.PixelW();
const kdDyDp = this.PixelH();
let dMagPixel = Math.sqrt(kdDxDp*kdDxDp + kdDyDp*kdDyDp);
const kdDxDs = kdDxDp/iSamplesPerPixelX;
const kdDyDs = kdDyDp/iSamplesPerPixelY;
//const kdGraphZ = dLineDepth/2;
const kdSamplesPerPixel = iSamplesPerPixelX*iSamplesPerPixelY;
let iPixel = 0;
// Run over the y pixel values
for (let j = 0; j < this.miCanvasH; ++j) {
for (let i = 0; i < this.miCanvasW; ++i) {
// Get the position of the center of the pixel and subtract half of the samples distance.
let dPixelX = this.mdLowX + (i + .5)*kdDxDp - kdDxDs*(iSamplesPerPixelX - 1)/2;
let dPixelY = this.mdHighY - (j + .5)*kdDyDp - kdDyDs*(iSamplesPerPixelY - 1)/2;
let iCount = 0;
for (let iSx = 0; iSx < iSamplesPerPixelX; ++iSx) {
let dX = dPixelX + iSx*kdDxDs;
for (let iSy = 0; iSy < iSamplesPerPixelY; ++iSy) {
let dY = dPixelY + iSy*kdDyDs;
let dF = fnF(dX, dY);
let daGradF = fnGradF(dX, dY);
let dMagGradF = Math.sqrt(daGradF[0]*daGradF[0] + daGradF[1]*daGradF[1]);
let dCloseLevel = FindClosestLevel(dF, daLevels);//5*Math.round(dF/5);
// Check whether the function value is less than the magnitude of the gradient.
// This tells us if we reach zero within on unit.
// This is multiplied by the magnitude of the pixel in spatial unit to make the unit pixels
// Finally, this is multiple by the pen width in pixels to make the drawing the correct width.
if (Math.abs(dF - dCloseLevel) < dPenWidth*dMagPixel*dMagGradF) {
++iCount;
}
}
}
var uiPixelColor = Math.round(255*(1.0 - iCount/kdSamplesPerPixel));
qImageData.data[iPixel] = uiPixelColor;
qImageData.data[iPixel + 1] = uiPixelColor;
qImageData.data[iPixel + 2] = uiPixelColor;
qImageData.data[iPixel + 3] = 255 - uiPixelColor;
iPixel += 4;
}
}
// This version allows the image data to be alpha composited to allow the axes to show through
const qBitmap = await createImageBitmap(qImageData);
qContext.drawImage(qBitmap, 0, 0);
}
}
class CSimplex {
#mdaaV = [[0,0],[0,0],[0,0]];
#mqGraph = null;
#mqContext = null;
#miIndex = 0;
#miLastAction = 0;
constructor(dX0, dY0, dX1, dY1, dX2, dY2, qGraph, qContext) {
this.#mdaaV[0][0] = dX0;
this.#mdaaV[0][1] = dY0;
this.#mdaaV[1][0] = dX1;
this.#mdaaV[1][1] = dY1;
this.#mdaaV[2][0] = dX2;
this.#mdaaV[2][1] = dY2;
this.#mqGraph = qGraph;
this.#mqContext = qContext;
}
// Algorithm: "A Simple Method For Function Minimization" Nelder and Mead 1965
FindMinimum() {
let dMaxDist = 1;
while (dMaxDist > .01) {
let dDx = this.#mdaaV[0][0] - this.#mdaaV[1][0];
let dDy = this.#mdaaV[0][1] - this.#mdaaV[1][1];
dMaxDist = Math.sqrt(dDx*dDx + dDy*dDy);
for (let i = 1; i < 3; ++i) {
let dDx = this.#mdaaV[i][0] - this.#mdaaV[(i+1)%3][0];
let dDy = this.#mdaaV[i][1] - this.#mdaaV[(i+1)%3][1];
let dDist = Math.sqrt(dDx*dDx + dDy*dDy);
if (dDist > dMaxDist) {
dMaxDist = dDist;
}
}
this.Draw();
this.Advance();
}
console.log("Iterations = "+this.#miIndex);
console.log("V0 = ("+this.#mdaaV[0][0]+", "+this.#mdaaV[0][0]+")");
console.log("V1 = ("+this.#mdaaV[1][0]+", "+this.#mdaaV[1][0]+")");
console.log("V2 = ("+this.#mdaaV[2][0]+", "+this.#mdaaV[2][0]+")");
}
Draw() {
let daaP = [[0,0],[0,0],[0,0]];
for (let i = 0; i < 3; ++i) {
daaP[i][0] = this.#mqGraph.XtoPixelX(this.#mdaaV[i][0]);
daaP[i][1] = this.#mqGraph.YtoPixelY(this.#mdaaV[i][1]);
}
switch (this.#miLastAction) {
case 0:
this.#mqContext.strokeStyle = "black";
break;
case 1:
this.#mqContext.strokeStyle = "red";
break;
case 2:
this.#mqContext.strokeStyle = "green";
break;
case 3:
this.#mqContext.strokeStyle = "blue";
break;
case 4:
this.#mqContext.strokeStyle = "cyan";
break;
case 5:
this.#mqContext.strokeStyle = "magenta";
break;
}
this.#mqContext.lineWidth = "1";
this.#mqContext.beginPath();
this.#mqContext.moveTo(daaP[0][0], daaP[0][1]);
this.#mqContext.lineTo(daaP[1][0], daaP[1][1]);
this.#mqContext.lineTo(daaP[2][0], daaP[2][1]);
this.#mqContext.closePath();
this.#mqContext.stroke();
this.#miIndex += 1;
//if (this.#miIndex > 18) {
// throw 0;
//}
}
Advance() {
const kdEpsilon = 1.0e-5;
const kdAlpha = .75;
const kdGamma = 1.5;
const kdBeta = .6;
// Calculate the z-values
let daZ = [0, 0, 0];
for (let i = 0; i < 3; ++i) {
daZ[i] = F(this.#mdaaV[i][0], this.#mdaaV[i][1]);
}
// Find the indices of the highest and the lowest points
let iLow = 0
let iHigh = 0
for (let i = 1; i < 3; ++i) {
if (daZ[i] > daZ[iHigh]) {
iHigh = i;
}
if (daZ[i] < daZ[iLow]) {
iLow = i;
}
}
// Calculate the centroid or the other (not highest) points
let daC = [0, 0];
for (let i = 0; i < 3; ++i) {
if (i != iHigh) {
daC[0] += this.#mdaaV[i][0]/2;
daC[1] += this.#mdaaV[i][1]/2;
}
}
// Calculate the reflection
let daPr = [(1 + kdAlpha)*daC[0] - kdAlpha*this.#mdaaV[iHigh][0],
(1 + kdAlpha)*daC[1] - kdAlpha*this.#mdaaV[iHigh][1]];
let dZr = F(daPr[0], daPr[1]);
if (dZr > daZ[iLow] && dZr < daZ[iHigh]) { // Use Reflection
this.#mdaaV[iHigh][0] = daPr[0];
this.#mdaaV[iHigh][1] = daPr[1];
this.#miLastAction = 1;
} else if (dZr < daZ[iLow]) { // Expand across the minimum
let daPe = [kdGamma*daPr[0] + (1 - kdGamma)*daC[0], kdGamma*daPr[1] + (1 - kdGamma)*daC[1]];
let dZe = F(daPe[0], daPe[1]);
if (dZe < dZr) { // The expansion was successful
this.#mdaaV[iHigh][0] = daPe[0];
this.#mdaaV[iHigh][1] = daPe[1];
this.#miLastAction = 2;
} else { // The expansion failed, use the reflection
this.#mdaaV[iHigh][0] = daPr[0];
this.#mdaaV[iHigh][1] = daPr[1];
this.#miLastAction = 5;
}
} else {
// Count the number of points greater that Pr. It should be 2 or 3
let iGreaterCount = 0;
for (let i = 0; i < 3; ++i) {
if (dZr > daZ[i]) {
++iGreaterCount;
}
}
// If Pr is the second highest, replace Ph with it
if (iGreaterCount < 3) {
this.#mdaaV[iHigh][0] = daPr[0];
this.#mdaaV[iHigh][1] = daPr[1];
daZ[iHigh] = dZr;
}
// Calculate the beta contraction
let daPb = [kdBeta*this.#mdaaV[iHigh][0] + (1 - kdBeta)*daC[0],
kdBeta*this.#mdaaV[iHigh][1] + (1 - kdBeta)*daC[1]];
let dZb = F(daPb[0], daPb[1]);
if (dZb > daZ[iHigh]) { // The beta contraction failed
// Reduce the simplex to half size toward the low point
for (let i = 0; i < 3; ++i) {
if (i != iLow) {
this.#mdaaV[i][0] = (this.#mdaaV[i][0] + this.#mdaaV[iLow][0])/2;
this.#mdaaV[i][1] = (this.#mdaaV[i][1] + this.#mdaaV[iLow][1])/2;
}
}
this.#miLastAction = 3;
} else { // Use the beta contraction
this.#mdaaV[iHigh][0] = daPb[0];
this.#mdaaV[iHigh][1] = daPb[1];
this.#miLastAction = 4;
}
}
}
}
// z = (y - x)^2 + (1 - x)^2
function F(x, y) {
return (y - x)*(y - x) + (1 - x)*(1 - x);
}
function GradF(x, y) {
return [-2*(y - x) - 2*(1 - x), 2*(y - x)];
}
function FindClosestLevel(dZ, daLevels) {
let dClosestDistance = Math.abs(dZ - daLevels[0]);
for (let i = 1; i < daLevels.length; ++i) {
let dNextDistance = Math.abs(dZ - daLevels[i]);
if (dNextDistance < dClosestDistance) {
dClosestDistance = dNextDistance;
if (i == daLevels.length - 1) {
return daLevels[daLevels.length-1];
}
} else {
return daLevels[i-1];
}
}
return daLevels[0];
}
function Initialize() {
var qCanvas = document.getElementById("idCanvas");
var qContext2D = qCanvas.getContext("2d");
// Draw the axes
qContext2D.strokeStyle = "lightgray";
qContext2D.lineWidth = "1";
qContext2D.beginPath();
qContext2D.moveTo(0, qCanvas.height/2);
qContext2D.lineTo(qCanvas.width, qCanvas.height/2);
qContext2D.moveTo(qCanvas.width/2, 0);
qContext2D.lineTo(qCanvas.width/2, qCanvas.height);
qContext2D.stroke();
var qGraph2D = new Graph2D(-4, 4, -4, 4, qCanvas.width, qCanvas.height);
var daLevels = [0, .25, .5, 1, 2, 4, 8, 16, 32, 64];
qGraph2D.DrawGraphOver(qContext2D, F, GradF, 4, 4, .5, daLevels);
let qSimplex = new CSimplex(-1, -2, 1, -2, 0, -3, qGraph2D, qContext2D);
qSimplex.FindMinimum();
}
Output
© 2007–2025 XoaX.net LLC. All rights reserved.