Mathematical Programming in Go

June 07 2023

Objective

The goal of this article is to introduce a new project that I've begun sketching out on GitHub: MatProGo.

Simply put, MatProGo is a collection of Go modules for performing Mathematical Programming in Go. Mathematical Programming is a field of study that is concerned with the optimization of mathematical functions.

What is Mathematical Programming?

Mathematical Programming is a field of study that is concerned with the optimization of mathematical functions.

An extensive amount of research has gone into how to solve a specific type of mathematical programs (convex programs) efficiently. This is the class of problems that MatProGo will help you solve.

There is also a large amount of research that has gone into how to solve non-convex programs efficiently. Some support for doing this will be available in MatProGo, but it is not the primary function.

Consider the following general problem:

\begin{array}{rl} \underset{x}{\text{arg min}} & f(x) \\ \text{subject to} & g_i(x) \leq 0, \quad i = 1, \dots, m \\ & h_i(x) = 0, \quad i = 1, \dots, p \end{array}

which comes from the formulation in Boyd and Vandenberghe's seminal textbook Convex Optimization (Section 4.1). \(f(x)\) is the objective function (convex in x), \(g_i(x)\) are linear functions used in the inequality constraints and \(h_i(x)\) are linear functions in the equality constraints. This is a template mathematical program and can be used to represent a variety of important decision-making problems.

Some examples of problems that can be represented in this form are:

• Selecting the Action that Minimized Motor Torques While Making Progress Towards a Robot's Goal Region
• Deciding How Much Money To Allocate To Assets in a Portfolio

How does MatProGo work?

In the MatProGo framework, you will

1. Defina model (i.e., all of the values for the objective function and constraints)
2. Provide your model to a solver which will solve it.

For example, if you wanted to solve the optimization problem below:

\begin{array}{rl} \underset{x \in \mathbb{R}^2}{\text{min}} & x^\top \begin{bmatrix} 1 & 0.25 \\ 0.25 & 0.25 \end{bmatrix} x + \begin{bmatrix} 0 & 0.97 \end{bmatrix} x + 2 \\ \text{subject to} & 0 \leq x_1 \leq 2 \\ & 1 \leq x_2 \leq 3 \end{array}

Then you would construct its model with MatProGo's MatProInterface.go as follows:

        
// Constants
modelName := "mpg-qp1"
m := optim.NewModel(modelName)
x := m.AddVariableVector(2)

// Create Vector Constants
c1 := optim.KVector(
    *mat.NewVecDense(2, []float64{0.0, 1.0}),
)

c2 := optim.KVector(
    *mat.NewVecDense(2, []float64{2.0, 3.0}),
)

// Use these to create constraints.

vc1, err := x.LessEq(c2)
if err != nil {
    t.Errorf("There was an issue creating the proper vector constraint: %v", err)
}

vc2, err := x.GreaterEq(c1)
if err != nil {
    t.Errorf("There was an issue creating the proper vector constraint: %v", err)
}

// Create objective
Q1 := optim.Identity(x.Len())
Q1.Set(0, 1, 0.25)
Q1.Set(1, 0, 0.25)
Q1.Set(1, 1, 0.25)

obj := optim.ScalarQuadraticExpression{
    Q: Q1,
    X: x,
    L: *mat.NewVecDense(x.Len(), []float64{0, -0.97}),
    C: 2.0,
}

// Add Constraints
constraints := []optim.Constraint{vc1, vc2}
for _, constr := range constraints {
    err = m.AddConstraint(constr)
    if err != nil {
        t.Errorf("There was an issue adding the vector constraint to the model: %v", err)
    }
}

// Add objective
err = m.SetObjective(optim.Objective{obj, optim.SenseMinimize})
if err != nil {
    t.Errorf("There was an issue setting the objective of the Gurobi solver model: %v", err)
}

// Solve using the solver of your choice!
        
    

And then you can provide the model to a solver like Gurobi to solve it!

There aren't that many solvers available now. When will they be added?

They will most likely be added if you either send an email, create an issue or create it yourself! We are willing to incorporate external collaborators work, because there are so many solvers that exist and we don't have the time to implement them all.