Visualizing Downhill Simplex in 2D with Java and OpenCV: Implementing the Nelder-Mead

you can also read this article in Medium -> click here

Let's get straight to the point - Downhill Simplex is an optimization algorithm. It's used to find a function's local minimum (or maximum). It doesn't need complex math like gradients and it's very intuitive and easy to understand. It's perfect to play around with and that's exactly what we'll do in this article.

I like the real-life analogy normally used to explain this algorithm, so I'll start with this:

Imagine you and two of your friends are blindfolded and put on a hilly landscape. Your goal is to find the lowest point - like the bottom of a valley. You can't see the whole map, but you always have information on the current elevation above sea level. How do you figure out where the lowest point is?

The Nelder–Mead method 📐:

You and your friends spread around a bit and everybody shouts their current elevation. (You form an imaginary triangle in 2D space)
Find out which one sits the highest, the lowest, and the one who's in the middle of all three. We'll call these positions "best", "worst", and "good".
Now the one in the "worst" point reflects its position over the other two in an attempt to find a better (lower) spot.
- If that's good, maybe stretch a bit further ("expand")

If the "reflected" position is still bad, shrink a bit back ("contract" the position)
If nothing works, the "worst" and the "good" move a bit closer to the best position ("shrink" the imaginary triangle).
Repeat: Keep adjusting until the triangle that forms from those three points gets very small and surrounds the lowest point.

Makes sense right? That's a legit and very simple way you can find a local minimum of a function. The proposed algorithm is focused on the 2D space (that's why we use a triangle in our example), but the algorithm also works in any given dimension. The simplex from (Downhill Simplex) is the key to this algorithm - it is a geometric shape that has n+1 vertices in n dimensions - the simplest shape that can enclose a region in a number of dimensions. For example:

In 1D: A line segment (2 points).
In 2D: A triangle (3 points). - Our example
In 3D: A tetrahedron (4 points).
…

So all of this relates to function minimization like this:

In our example here, each "person" represents a set of coordinates (a point [x,y] in a 2-dimensional space). For a function, like f(x, y) = x² + y², the Nelder-Mead method evaluates the function at the triangle's vertices, compares their values, and adjusts the triangle accordingly. And this without needing gradient information. This is perfect when derivatives are hard to compute.

We'll create a visualization where we start from a random point in a 2D space, then follow the algorithm's steps and gradually end up in the minimum of the given function. For simplicity, we'll use this function in our example:

f(x, y) = x² + y² which has it's minimum at (0,0)

This is called the objective function and will be calculated on every step for all of the points in our triangle.

Visualize using Java and OpenCV

If you're a visual guy like me, seeing exactly how the triangle expands, shrinks, and moves toward the lowest point would help you understand this even better. I'll use Java and OpenCV to visualize the steps of the algorithm. If I'm being honest, this is a task I would normally approach using Python, but Java has evolved over the last few years and I must say fast prototyping is not out of the scope of the language anymore. I actually had a very nice time implementing this in Java and ended up with a very tidy, eye-pleasing code, that's easy to read and understand.

Let's get into it:

To start we need a simple Java gradle or Maven project and add the OpenCV dependency in build.gradle:

plugins {
    // Apply the application plugin to add support for building a CLI application in Java.
    id 'application'
}

repositories {
    // Use Maven Central for resolving dependencies.
    mavenCentral()
}

dependencies {
    implementation 'org.openpnp:opencv:4.9.0-0'
    ...

here is also the maven dependency to add in your pom.xml if you use maven:

<dependency>
    <groupId>org.openpnp</groupId>
    <artifactId>opencv</artifactId>
    <version>4.9.0-0</version>
</dependency>

Let’s set up some basics next, before moving to the actual implementation of the algorithm. At the heart of the Nelder-Mead are simple geometric transformations that help our simplex move toward the lower points.

Let’s implement the basic geometric operations we talked about when we explained the algorithm — “reflection”, “expansion”, and “contraction”. These are pretty straightforward, but I’d like to go through them briefly to keep things beginner-friendly.

Reflection

The most fundamental operation for this algorithm is calculating reflection points. This is how our simplex moves away from bad “high” positions. In order to calculate the reflection of our worst point, we first need to find the midpoint of the line that connects our two better points:

This mid-point is like a pivot for our reflection.

Midpoint Formula (Between Two Points): We have two points G(x,y) (for Good) and B(x,y) (for Best). The midpont M between them is:

Having the coordinates of the Best and Good points, we find the point exactly halfway between them by averaging their coordinates:

/**
 *   Midpoint of a line between a(x,y) and b(x,y):
 *   ( a + b ) / 2
 *   ( ( a.x + b.x ) / 2 ), ( (a.y + b.y) /2 )
 *   
 */
public static Point midPoint(Point a, Point b) {
    double midX = (a.x + b.x) / 2;
    double midY = (a.y + b.y) / 2;
 
    return new Point(midX, midY);
}

Now we can use this to calculate the reflection. Let’s think it through:

We have a point W(x,y) (for worst), and our newly calculated point M(x,y) (Midpoint). The goal is to find a new point R(x,y) (Reflected), which is the reflection of W over M, as if we flip W over M, to get a mirror image of it.

To reflect a point across a center point, take the center, double it, and subtract the original point. That gives the new point on the opposite side.

So R(x,y) (for Reflected) is calculated like this:

/**
 *   Calculate the reflected point's coordinates using the reflection formula:
 *  x' = 2 * midX - x, y' = 2 * midY - y
 *
 */
public static Point reflectionPoint(Point p, Point midPoint) {
    double xReflected = 2 * midPoint.x - p.x;
    double yReflected = 2 * midPoint.y - p.y;
 
    LOG.info("Reflection point: ("+xReflected+", "+yReflected+")");
    return new Point(xReflected, yReflected);
}

Expansion

After computing the reflected point, the Nelson Mead algorithm sometimes tries to go further in that direction — this is called expansion. If after reflection, the reflected point is the best point so far, we move even further in that direction.

We can calculate the expansion point, using the reflection point, very easily:

We need to move from the midpoint M in the same direction as the reflection R, but two times the distance (or more than two, we’ll call this factor gamma):

For simplitity, we set gamma always = 2 in our code:

/**
 * Calculates the expansion point using the reflected point.
 * This difference tells us: “From the midPoint, I moved N units right in x and M unit down in y to get to the reflected point.”
 * For expansion, we want to go further in that same direction. Let’s say we double the distance (gamma=2)
 *
 */
public static Point expansionPointFromReflection(Point p, Point midPoint) {
    return expansionPointFromReflection(p,midPoint,2);
}
public static Point expansionPointFromReflection(Point p, Point midPoint, double gamma) {
    Point reflected = reflectionPoint(p, midPoint); // Get R
    double xExpanded = midPoint.x + gamma * (reflected.x - midPoint.x);
    double yExpanded = midPoint.y + gamma * (reflected.y - midPoint.y);
 
    LOG.info("Expansion point: ("+xExpanded+", "+yExpanded+")");
    return new Point(xExpanded, yExpanded);
}

Contraction

The contraction is used when the reflection didn’t deliver a better result. It shrinks our triangle toward the middle point. There are two types:

Outside contraction: between the middle point (M) and the reflected point (R):

If the rho coefficient here is 0.5, we’ll end up with the following:

Inside contraction: between the middle point (M) and the worst point (W):

Again, If the rho coefficient here is 0.5, we’ll end up with the following:

Here the code in java (again, we’ll use 0.5 for rho for simplicity):

public static Point contractionPoint( Point p, Point midPoint, boolean isOutside ) {
    return contractionPoint(p, midPoint, 0.5, isOutside);
}
 
/**
 * Calculates the contraction point for a 2D downhill simplex (Nelder-Mead) optimization.
 * The contraction point shrinks the simplex toward the centroid. There are two types:
 * - Outside contraction: between the centroid (midPoint) and the reflected point (computed internally).
 * - Inside contraction: between the centroid (midPoint) and the worst point (p).
 * The formula is \( P_c = midPoint + rho * (endPoint - midPoint) \), where endPoint is either
 * the reflected point (outside) or the worst point (inside), and rho is the contraction coefficient.
 *
 * @param p          the worst vertex of the simplex
 * @param midPoint   the centroid of the remaining vertices
 * @param rho        the contraction coefficient (typically 0.5 in Nelder-Mead)
 * @param isOutside  true for outside contraction (uses reflected point), false for inside contraction (uses worst point)
 * @return a new Point object representing the contraction point
 */
public static Point contractionPoint(Point p, Point midPoint, double rho, boolean isOutside) {
 
    // Determine the endpoint: reflected point (outside) or worst point (inside)
    Point endPoint = isOutside ? reflectionPoint(p, midPoint) : p;
 
    // Calculate the contraction point:
    // x_c = midX + rho * (endX - midX)
    // y_c = midY + rho * (endY - midY)
    double xContracted = midPoint.x + rho * (endPoint.x - midPoint.x);
    double yContracted = midPoint.y + rho * (endPoint.y - midPoint.y);
 
    LOG.info("Contraction point: ("+xContracted+", "+yContracted+")");
    return new Point(xContracted, yContracted);
}

Shrinking

If reflection, expansion, and contraction all failed, we’ll try to shrink the triangle around the best point and try again.

The logic here is pretty straightforward. We find the midpoint between the worst and the best points and the midpoint between the good and the best points and set them to be the new “worst” and “good”.

// shrinking the triangle towards best point
PointValue s1 = new PointValue( midPoint ( worst.point(), best.point() ));
PointValue s2 = new PointValue( midPoint (good.point(), best.point()));
worst = s1;
good = s2;

Set Up Canvas with a grid in OpenCV

Alright, let’s prepare some code to visualize our algorithm. We’ll start small and first just create a canvas with size 600x600 and draw a grid on it:

import nu.pattern.OpenCV;
import org.opencv.core.*;
import org.opencv.highgui.HighGui;
 
import static com.tsvetkov.Utils.*;
 
public class Main {
 
    public static final short CANVAS_SIZE = 600;
    public static final short MIN_MAX_ALGORITHM_COORDINATES = 10;
 
    public static void main(String[] args) {
        OpenCV.loadLocally();
        try {
            mainDraw();
        } finally {
            HighGui.destroyAllWindows();
            System.exit(0);
        }
    }
 
    private static void mainDraw() {
        Mat canvas = new Mat(CANVAS_SIZE, CANVAS_SIZE, CvType.CV_8UC3, new Scalar(255, 255, 255)); // White background
 
        canvas.setTo(new Scalar(255, 255, 255));
        drawCoordinateGrid(canvas, -MIN_MAX_ALGORITHM_COORDINATES, MIN_MAX_ALGORITHM_COORDINATES, CANVAS_SIZE, CANVAS_SIZE);
 
        HighGui.imshow("Nelder-Mead Simplex", canvas);
        HighGui.waitKey(0); // Keep final image open until key press
    }
 
}

Now, in order to draw the grid and all the triangle points in the future, we need a function that takes the algorithm coordinates and converts them to pixel coordinates to be drawn on the canvas. For example, from scale (-10 to 10) to pixel coordinates (0 to 500). Here both utility functions used above:

// Convert algorithm coordinates to pixel coordinates
// scales the algorithm's x,y values (e.g., -2 to 2) to pixel coordinates (0 to 500).
public static Point toPixel(double x, double y, double min, double max, int width, int height) {
    double scaleX = width / (max - min);
    double scaleY = height / (max - min);
    int px = (int) ((x - min) * scaleX);
    int py = (int) ((y - min) * scaleY);
    return new Point(px, height - py); // Flip y-axis for image coordinates
}
// Draw coordinate grid with labels
public static void drawCoordinateGrid(Mat canvas, double minCoord, double maxCoord, int width, int height) {
    double gridStep = 1; // Grid lines every 0.5 units
    double labelStep = 1.0; // Labels every 1.0 unit to avoid clutter
 
    // Vertical lines (constant x)
    for (double x = minCoord; x <= maxCoord; x += gridStep) {
        Point start = toPixel(x, minCoord, minCoord, maxCoord, width, height);
        Point end = toPixel(x, maxCoord, minCoord, maxCoord, width, height);
        Imgproc.line(canvas, start, end, GRID_COLOR, 1);
    }
 
    // Horizontal lines (constant y)
    for (double y = minCoord; y <= maxCoord; y += gridStep) {
        Point start = toPixel(minCoord, y, minCoord, maxCoord, width, height);
        Point end = toPixel(maxCoord, y, minCoord, maxCoord, width, height);
        Imgproc.line(canvas, start, end, GRID_COLOR, 1);
    }
 
    // Draw axes (x=0, y=0) slightly darker
    Imgproc.line(canvas,
            toPixel(0, minCoord, minCoord, maxCoord, width, height),
            toPixel(0, maxCoord, minCoord, maxCoord, width, height),
            new Scalar(150, 150, 150), 1);
    Imgproc.line(canvas,
            toPixel(minCoord, 0, minCoord, maxCoord, width, height),
            toPixel(maxCoord, 0, minCoord, maxCoord, width, height),
            new Scalar(150, 150, 150), 1);
}

If you managed to follow along, you should see the following window after you execute your Main class:

Let’s start small and draw a single triangle on this grid. We’ll use the following (absolutely random) coordinates: (4,2), (5,4), (7,2). These will be our starting point. Here the updated mainDraw() method:

...
record PointValue(Point point, double value) {
    public PointValue(Point point) {
        this(point, objectiveFunction(point));
    }
    double x(){
        return point.x;
    }
    double y(){
        return point.y;
    }
}
...
 
public class Main {
 
...
 
private static void mainDraw() {
        Mat canvas = new Mat(CANVAS_SIZE, CANVAS_SIZE, CvType.CV_8UC3, new Scalar(255, 255, 255)); // White background
 
        canvas.setTo(new Scalar(255, 255, 255));
        drawCoordinateGrid(canvas, -MIN_MAX_ALGORITHM_COORDINATES, MIN_MAX_ALGORITHM_COORDINATES, CANVAS_SIZE, CANVAS_SIZE);
 
        PointValue a = new PointValue(new Point(4, 2));
        PointValue b = new PointValue(new Point(5, 4));
        PointValue c = new PointValue(new Point(7, 2));
 
        //draw triangle
        MatOfPoint trianglePoints = new MatOfPoint(toPixel(a.x(), a.y()), toPixel(b.x(), b.y()), toPixel(c.x(), c.y()));
        Imgproc.polylines(canvas, List.of(trianglePoints), true, RED_COLOR, 2);
 
        HighGui.imshow("Nelder-Mead Simplex", canvas);
        HighGui.waitKey(0); // Keep final image open until key press
    }
...

Now we have set up a window with a grid and we can draw triangles on the canvas using OpenCV. That’s all we need in order to implement our algorithm and visualize it.

Implementation

Our aim will be to find the (local) minimum of the following objective function: f(x, y) = x² + y²

Here the code to calculate it for every given point:

// Function to minimize: f(x, y) = x^2 + y^2
public static double objectiveFunction(Point point) {
    double x = point.x;
    double y= point.y;
    return x * x + y * y;
}

We’ll repeat the following in a loop until we reach the max number of iterations we have set:

Clear the canvas.
Draw triangle (the starting point will be the triangle (4,2), (5,4), (7,2) from above).
Calculate the objective function for every point of the triangle.
Assign Best, Good and Worst to the points of the triangle.
Calculate the Midpoint (M) between the Good and the Best point.
Calculate the Reflected Point (R), flipping the Worst point over the Midpoint

Now we need to branch out:

If the value of the objective function for the reflected point is better than the good point, then we either reflect or extend.
If the value of the objective function for the reflected point is not better than the good point, then we either contract or shrink.

We have set ourselves pretty good by now with all the functions we need to implement this. Here the final code:

private static void mainDraw() {
    Mat canvas = new Mat(CANVAS_SIZE, CANVAS_SIZE, CvType.CV_8UC3, new Scalar(255, 255, 255)); // White background
    Function<Point, Double> objectiveFunction = Functions::objectiveFunction;
 
    PointValue a = new PointValue(new Point(4, 2));
    PointValue b = new PointValue(new Point(5, 4));
    PointValue c = new PointValue(new Point(7, 2));
 
    for (int iter = 0; iter < MAX_ITERATIONS; iter++) {
        // clean  canvas
        canvas.setTo(new Scalar(255, 255, 255));
        drawCoordinateGrid(canvas, -MIN_MAX_ALGORITHM_COORDINATES, MIN_MAX_ALGORITHM_COORDINATES, CANVAS_SIZE, CANVAS_SIZE);
        //draw triangle
        MatOfPoint trianglePoints = new MatOfPoint(toPixel(a.x(), a.y()), toPixel(b.x(), b.y()), toPixel(c.x(), c.y()));
        Imgproc.polylines(canvas, List.of(trianglePoints), true, RED_COLOR, 2);
 
        List<PointValue> sorted = Stream.of(a,b,c).sorted(Comparator.comparingDouble(PointValue::value)).toList();
 
        // Assign best, good, worst
        PointValue best = sorted.get(0);
        PointValue good = sorted.get(1);
        PointValue worst = sorted.get(2);
        
        //Start algorithm
        Point midPoint = midPoint(good.point(), best.point());
 
        //calculate reflected point
        PointValue reflected = new PointValue(Functions.reflectionPoint(worst.point(), midPoint));
 
        if(reflected.value() < good.value()) {
            //either reflect or extend
            if(best.value() < reflected.value()) {
                //replace worst with reflected
                worst = reflected;
            } else {
                // compute extended
                PointValue extended = new PointValue(expansionPointFromReflection(worst.point(), midPoint));
                if(extended.value() < good.value()) {
                    //replace worst with extended
                    worst = extended;
                } else {
                    //replace worst with reflected
                    worst = reflected;
                }
            }
 
        } else {
            //either contract or shrink
            if(reflected.value() < worst.value()) {
                // make worst to be the reflected point (flip triangle)
                worst = reflected;
            }
 
            // compute contraction
            PointValue contractionInner = new PointValue(contractionPoint(worst.point(), midPoint, false));
            PointValue contractionOuter = new PointValue(contractionPoint(worst.point(), midPoint, true));
 
            PointValue contraction = contractionInner.value() < contractionOuter.value() ? contractionInner : contractionOuter;
            if(contraction.value() < worst.value()) {
                //contraction
                worst = contraction;
            } else {
                // shrinking the triangle towards best point
                PointValue s1 = new PointValue( midPoint ( worst.point(), best.point() ));
                PointValue s2 = new PointValue( midPoint (good.point(), best.point()));
                worst = s1;
                good = s2;
            }
 
        }
 
        a = best;
        b = good;
        c = worst;
 
        HighGui.imshow("Nelder-Mead Simplex", canvas);
        HighGui.waitKey(0); // Pause for 500ms to observe each step
    }
 
    // Show the canvas
    HighGui.waitKey(0); // Keep final image open until key press
}

If you run this, you’ll see the triangle moving closer and closer to (0,0), which is the minimum of our objective function f(x, y) = x² + y².

Conclusion

The simplicity of this method really makes it stand out. It’s easy to understand and play around with. You’ll be surprised how many real-world applications actually use this method — from robotics and navigation to medical imaging — for example in Image Registration, to find the best transformation matrix.

Hope you managed to deeply understand the concept and had fun with this — I know I did!

Thanks for reading!