1D Simplex Minimization

The JavaScript code example demonstrates how to program the Nelder and Mead simplex algorithm to find the minimum of a function.

SimplexMethod.html

<!DOCTYPE html>
<html>
  <head>
    <title>XoaX.net's Javascript</title>
    <script type="text/javascript" src="SimplexMethod.js"></script>
  </head>
  <body>
  	<pre id="idOutput"></pre>
  </body>
</html>

SimplexMethod.js

function Begin() {
	SimplexMethod(Parabola, 2, .2)
}

function Parabola(dX) {
	return dX*dX;
}

// Using the algorithm from "A Simplex Method For Function Minimization" by Nelder and Mead
function SimplexMethod(fnF, dInitial, dDelta) {
	const kdEpsilon = 1.0e-5;
	const kdAlpha = .75;
	const kdGamma = 1.5;
	const kdBeta = .6;
	var qOutput = document.getElementById("idOutput");
	// Create the endpoints
	var daX = new Array(2);
	daX[0] = dInitial - dDelta;
	daX[1] = dInitial + dDelta;
	while (Math.abs(daX[0] - daX[1]) > kdEpsilon) {
		var dXR = 0.0;
		// Swap so that X1 = XH and X0 = XL
		if (fnF(daX[0]) > fnF(daX[1])) {
			var dSwap = daX[0];
			daX[0] = daX[1];
			daX[1] = dSwap;
		}
		// Now, the 0 index has the lower function value
		qOutput.innerHTML += "[X0, X1] = ["+daX[0]+", "+daX[1]+"]";
		dXR = (1.0 + kdAlpha)*daX[0] - kdAlpha*daX[1];
		// In this case, 
		var dYR = fnF(dXR);
		// XL is also the centroid of the remaining points by default.
		var dYL = fnF(daX[0]);
		var dYH = fnF(daX[1]);
		if (dYR < dYL) {
			// Perform an expansion
			var dXE = kdGamma*dXR + (1.0 - kdGamma)*daX[0];
			var dYE = fnF(dXE);
			// If the expansion is successful, use to replace the high value
			if (dYE < dYL) {
				qOutput.innerHTML += " - Expansion\n";
				daX[1] = dXE;
			} else { // The expansion failed, use the reflection.
				qOutput.innerHTML += " - Reflection on Failed Expansion\n";
				daX[1] = dXR;
			}
		} else if (dYR < dYH) {
			// Use the reflection to replace the high point
			qOutput.innerHTML += " - Reflection\n";
			daX[1] = dXR;
		} else {
			// Contraction
			var dXC = kdBeta*daX[1] + (1.0 - kdBeta)*daX[0];
			var dYC = fnF(dXC);
			if (dYC > dYH) {
				qOutput.innerHTML += " - Contraction to Half of the Size\n";
				daX[1] = (daX[0] + daX[1])/2.0;
			} else {
				qOutput.innerHTML += " - Contraction\n";
				daX[1] = dXC;
			}
		}
	}
}

// This begins the execution
window.onload = Begin;