Study notes: constraints in Quipu Nelder-Mead solver

In my previous post, I went over the recent changes I made to my F# Nelder-Mead solver, Quipu. In this post, I want to explore how I could go about handling constraints in Quipu.

First, what do I mean by constraints? In its basic form, the solver takes a function, and attempts to find the set of inputs that minimizes that function. Lifting the example from the previous post, you may want to know what values of $(x,y)$ produce the smallest value for $f(x,y)=(x-10)^2+(y+5)^2$. The solution happens to be $(10,-5)$, and Quipu solves that without issues:

#r "nuget: Quipu, 0.2.0"
open Quipu.NelderMead

let f (x, y) = (x - 10.0) ** 2.0 + (y + 5.0) ** 2.0
NelderMead.minimize f
|> NelderMead.solve

val it: Solution = Optimal (2.467079917e-07, [|9.999611886; -4.999690039|])

However, in many situations, not every value will do. There might be restrictions on what values are valid, such as “x must be positive”, or “y must be less than 2”. These are known as constraints, and typically result in an inequality constraint, in our case something like $g(x,y) \leq 0$. How could we go about handling such constraints in our solver?

Version 0.2 of the Quipu Nelder-Mead solver

Back in April ‘23, I needed a simple solver for function minimization, and published a basic F# Nelder-Mead solver implementation on NuGet. I won’t go over the algorithm itself, if you are curious I wrote a post breaking down how the Nelder-Mead algorithm works a while back.

In a nutshell, the algorithm takes a function, and finds the set of inputs that produces the smallest output for that function. The algorithm is not foolproof, but it is very useful, and has the benefit of being fairly simple.

After dog-fooding my library for a bit, I found some rough spots, and decided it was time to make improvements. As a result, the API has changed a bit - hopefully for the better! In this post, I’ll go over some of these changes.

Basic usage

Imagine that you are interested in the following function:

$ f(x,y)=(x-10)^2+(y+5)^2 $

Specifically, you would want to know what values of $(x,y)$ produce the smallest value for $f$.

This is how you would go about it with Quipu in an F# script:

#r "nuget: Quipu, 0.2.0"
open Quipu.NelderMead

let f (x, y) = (x - 10.0) ** 2.0 + (y + 5.0) ** 2.0
NelderMead.minimize f
|> NelderMead.solve

This produces the following output:

val it: Solution = Optimal (2.467079917e-07, [|9.999611886; -4.999690039|])

The solver has found an Optimal solution, for $x=9.999,y=-4.999$, which yields $f(x,y)=2.467 \times 10^{-7}$, very close to the correct answer, $f(10,-5)=0$.

Data Science in F# 2023: an Ode to Linear Programming

In September, I had the great pleasure of attending the Data Science in F# conference in Berlin. I gave a talk and a workshop on Linear Programming, and figured I would make the corresponding material available, in case anybody is interested:

• Presentation: An Ode to Linear Programming
• Workshop: 4 levels of Linear Programming

Game of Life in Avalonia, MVU / Elmish style, take 2

This is a follow-up to my recent post trying to implement the classic Conway Game of Life in an MVU style with Avalonia.FuncUI. While I managed to get a version going pretty easily, the performance was not great. The visualization ran OK until around 100 x 100 cells, but started to degrade severely beyond that.

After a bit of work, I am pleased to present an updated version, which runs through a 200 x 200 cells visualization pretty smoothly:

As a side note, I wanted to point out that the size change is significative. Increasing the grid size from 100 to 200 means that for every frame, the number of elements we need to refresh grows from 10,000 to 40,000.

In this post, I will go over what changed between the two versions.

You can find the full code here on GitHub

WIP: Game of Life in Avalonia, MVU / Elmish style

A couple of days ago, I came across a toot from Khalid Abuhakmeh, showcasing a C# + MVVM implementation of the Game of Life on Avalonia. I have been experimenting with Avalonia funcUI recently, and thought a conversion would be both a fun week-end exercise, and an interesting way to take a look at performance.

Long story short, I took a look at his repository as a starting point, and proceeded to rewrite it in an Elmish style, shamelessly lifting the core from his code. The good news is, it did not take a lot of time to get it running, the less good news is, my version has clear performance issues.

In this post, I will go over how I approached it so far, and where I think the performance issues might be coming from. In a later post, I’ll try to see if I can fix these. As the French saying goes, “A chaque jour suffit sa peine”.

You can find the full code here on GitHub