Improving MatProGo With Symbolic Math Tools

December 01 2023

Objective

The goal of this post is to list a few updates that were made to MatProInterface.go, a component of MatProGo. (If you want to learn more about MatProGo, then read this post or check out the GitHub organization.)

A Powerful Conceptual Shift: Defining Constraints and Objectives Using Symbolic Math

One of the challenges that made MatProGo difficult to use was in how we defined constraints. For example, consider the following snippet from the previous post:

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

// 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)
}
        
    

In this snippet, the programmer defined the objective as a scalar quadratic expression. This means that the programmer needed to do extra work to complete writing the program. Why do I say that? Because the programmer is usually given a problem of the form

\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}

And then they must do the work of figuring out if the function \(f(x)\) is quadratic (instead of linear, or constant, etc.).

What if we didn't need to know the form of the objective function before calling the solver? This is how things work on paper, we can write all sorts of objectives before knowing whether they are quadratic, linear, or anything else.

What I propose that we do is to define an API in Go, that enables us to write the objective as follows:

And then MatProGo can figure out how to structure this for you. This is not a particularly new idea. (It's been covered extensively in the symbolic math community.) But, it doesn't seem to have been implemented in Go, yet.

MatProInterface.go's optim package

My first attempt at a symbolic math package for Go is contained in the optim package within MatProInterface.go. Let's see how we might build the objective \(f_1(x)\) from above.

        
// Create an empty model.
model := optim.NewModel("empty1.model")

// Create Variables
x1 := model.AddRealVariable("x1")
x2 := model.AddRealVariable("x2")

// Create objective
f0, err := x1.Multiply(2)
if err != nil {
    t.Errorf("There was an issue creating the objective function: %v", err)
}

f1, err := f0.Plus(x1.Multiply(x1))
if err != nil {
    t.Errorf("There was an issue creating the objective function: %v", err)
}
        
    

and another example which is unrelated to \(f_1(x)\):

        
// Create an empty model.
model := optim.NewModel("empty2.model")

// Create Variables
x := model.AddVariableVector(2)

// Set Objective function
Q1 := *mat.NewDense(2, 2, []float64{1.0, 0.25, 0.25, 0.25})

prod1, _ := x.Transpose().Multiply(Q1)
prod2, err := prod1.Multiply(x)
if err != nil {
    panic(fmt.Sprintf("there was an issue creating product 2: %v", err))
}

sum, err := prod2.Plus(
    x.Transpose().Multiply(*mat.NewVecDense(2, []float64{0, -0.97})),
)
if err != nil {
    panic(fmt.Sprintf("There was an issue computing the final sum: %v", err))
}
        
    

Notice that it is possible to compose operations (e.g., Plus, Multiply, etc.) to create more complex expressions. This is a powerful feature of symbolic math packages.

There is another useful example of how to use the optim package in the QP1 Example in the Gurobi.go repository.

As usual, let me know if you have any questions or comments!