Quipu 0.2.2, a Nelder-Mead solver with a side of NaN

The main reason I created Quipu is that I needed a Nelder-Mead solver for a real-world project. And, as I put Quipu through its paces on real-world data, I ran into some issues, revolving around “Not a Number” floating point values, aka NaN.

tl;dr: the latest release of Quipu, version 0.2.2, available on nuget, should handle NaN values decently well, and has some minor performance improvements, too.

In this post, I will go over some of the changes I made, and why. Fixing the main issue made me realize that I didn’t know floating point numbers as well as I thought, even though I have been using them every working day for years. I will take some tangents to discuss some of my learnings.

So let’s dig in. My goal with Quipu was to implement the Nelder-Mead algorithm in F#. The purpose of Nelder-Mead is to find a numeric approximation of values that minimize a function. As an illustration, if we took the function $f(x) = x ^ 2$, we would like to know what value of $x$ produces the smallest possible value for $f(x)$, which happens to be $x = 0$ in this case.

Quipu handles that case just fine:

open Quipu.NelderMead

let f x = x ** 2.0
f
|> NelderMead.minimize
|> NelderMead.solve

val it: Solution = Optimal (0.0, [|0.0|])

So far, so good. Now, what about a function like $f(x) = \sqrt{x}$?

That function is interesting for 2 reasons:

• $f(x)$ has a minimum, for $x = 0$.
• $f(x)$ is defined only for $x \ge 0$: it is a partial function.

Sadly, the previous version of Quipu, version 0.2.1, failed to find it. It would go into an infinite loop instead.

Network maximum flow in F#

An old math problem I had not seen since my university days resurfaced the other day, the Maximum Flow problem. It came up in the context of analyzing some industrial process. For illustration purposes, let’s say we are producing sausages, following these steps: we grind some meat, add some seasoning, then stuff and tie the sausage casings, and split them into delicious sausage links.

We could represent this process as a graph, like so:

``` mermaid
graph TD;
    grind_meat --> season_meat;
    season_meat --> stuff_casing;
    stuff_casing --> cut_links;

Now the question is, how many sausages per minute could we produce?

Assuming each operation is performed by a separate person, this is not very complicated. We are going to be as slow as the slowest link. So if for instance we could

• grind meat for 20 sausages / minute,
• season meat for 15 sausages per minute,
• stuff 5 sausages per minute, and
• cut 20 sausages per minute,

we would end up running at 5 sausages / minute at best, the bottleneck being stuffing.

Now we might be able to get a better throughput with some parallelization. For instance, we could organize production like so:

``` mermaid
graph TD;
    grind_meat --> season_meat_1;
    grind_meat --> season_meat_2;
    season_meat_1 --> stuff_casing1;
    season_meat_1 --> stuff_casing2;
    season_meat_2 --> stuff_casing2;
    season_meat_2 --> stuff_casing3;
    stuff_casing1 --> cut_links_1;
    stuff_casing2 --> cut_links_1;
    stuff_casing3 --> cut_links_1;

This is still not overly complicated, but it is beginning to be hairy, and you can imagine how with a few more processes added, the question “how much work can I process through this network” will soon become impractical to handle by hand.

This is essentially what the Maximum Flow problem is about. Given a directed graph, with capacity limitations, how much throughput (flow) can we achieve? In the rest of this post, I’ll go through one way you could answer that question, using Linear Programming.

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