Constrained Linear Optimization problem in python

Question

Objective - using given max values and coefficients, solve the linear equation within the constraints

Problem - defining the constraint

Code:

 import numpy as np
    coefficients = np.array([
          [0, 9, 6, 9, 4, 0 ],
          [0, 9, 7, 7, 3, 2 ],
          [0, 9, 5, 9, 3, 2 ],
          [0, 11, 2, 6, 4, 5],
          [0, 11, 1, 7, 2, 7],
          [1, 10, 1, 5, 3, 8]
    ])

    maxPoints = np.array([
        [4239100],
        [4204767],
        [4170434],
        [4136101],
        [4101768],
        [4067435]
    ])
    x = np.linalg.solve(coefficients, maxPoints)
    print(x)

Output

[[256694.51339286]
 [213778.26339286]
 [140820.63839286]
 [123654.13839286]
 [89321.13839286]
 [80737.88839286]]

The issue is that i want to apply a constraint making it so that:

x[0] <= x[1] <= x[2] <= x[3] <= x[4] <= x[5]

Another issue is that this currently only solves this smaller matrix and I need this to work with a much larger matrix were my maxPoints are 1 column by 32 rows and my coefficients are 6 columns by 32 rows. Using the linalg method above it would not solve this.

Heres the error message:

Traceback (most recent call last):
File "Untitled-1.py", line 74, in 
X = np.linalg.solve(coefficients, maxPoints)
File "<__array_function__ internals>", line 6, in    solve
File "/home/comfortablynumb/.local/lib/python3.7/site-packages/numpy/linalg/linalg.py", line 390, in solve
_assertNdSquareness(a)
File "/home/comfortablynumb/.local/lib/python3.7/site- packages/numpy/linalg/linalg.py", line 213, in  _assertNdSquareness
raise LinAlgError('Last 2 dimensions of the array must be square')
numpy.linalg.LinAlgError: Last 2 dimensions of the array must be square

Thanks for the help.

Edit:

Here is the full data set I'm working with

`maxPoints = np.array([
        [4239100],
        [4204767],
        [4170434],
        [4136101],
        [4101768],
        [4067435],
        [4033102],
        [3998769],
        [3964436],
        [3930103],
        [3895770],
        [3861437],
        [3827104],
        [3792771],
        [3758438],
        [3724105],
        [3689772],
        [3655439],
        [3621106],
        [3586773],
        [3552440],
        [3518107],
        [3483774],
        [3449441],
        [3415108],
        [3380775],
        [3346442],
        [3312109],
        [3277776],
        [3243443],
        [3209110],
        [3174777]])`

    `coefficients = np.array([ 
        [0, 9, 6, 9, 4, 0 ],
        [0, 9, 7, 7, 3, 2 ],
        [0, 9, 5, 9, 3, 2 ],
        [0, 11, 2, 6, 4, 5],
        [0, 11, 1, 7, 2, 7],
        [1, 10, 1, 5, 3, 8],  
        [2, 9, 1, 5, 2, 9 ],
        [2, 8, 2, 4, 3, 9 ],
        [2, 8, 2, 3, 4, 9 ],
        [2, 8, 1, 4, 1, 12],
        [3, 6, 1, 5, 1, 12],
        [4, 5, 1, 5, 0, 13],
        [5, 4, 1, 5, 0, 13],
        [5, 4, 0, 5, 1, 13],
        [5, 4, 1, 4, 1, 13],
        [5, 4, 2, 3, 1, 13],
        [5, 4, 2, 3, 1, 13],
        [6, 3, 2, 3, 1, 13],
        [6, 3, 2, 2, 1, 14],
        [6, 3, 2, 1, 2, 14],
        [6, 4, 1, 1, 2, 14],
        [6, 4, 1, 1, 0, 16],
        [6, 3, 2, 1, 0, 16],
        [6, 4, 1, 1, 0, 16],
        [6, 4, 1, 1, 0, 16],
        [6, 4, 1, 1, 0, 16],
        [6, 4, 1, 1, 0, 16],
        [7, 3, 1, 1, 0, 16],
        [7, 3, 1, 1, 0, 16],
        [7, 3, 1, 1, 0, 16],
        [7, 3, 1, 1, 0, 16],
        [7, 3, 1, 1, 0, 16]
     ])`

soyapencil · Accepted Answer

Constraints

Presuming that you are referring to a linear system of equations of the form:

ax = b

where a is a matrix of values (coefficients) in your code snippet, and b is a vector of constants (maxPoints) in your code, then you are solving for x.

Adding constraints doesn't really make sense here, as the system is soluble if:

coefficients is invertible (or at least, has a pseudoinverse).
All elements of maxPoints are finite.

The LinAlgError

In essence, you can think of numpy.linalg.solve(a,b) doing the following:

Solve: ax = b for x

One can think of this in a sense as numpy computing the inverse of the matrix a. Here, numpy raised a LinAlgError because the matrix was not square, and therefore the inverse is poorly defined. numpy actually does some other little bits behind the scenes (see LAPACK), but this is close enough for discussion here.

What I think may be the issue

You have the following problem:

The number of columns in coefficients is 6, and the number of rows is 32.
The number of rows in maxPoints is 32.
This is an over-determined problem.

A first step would be to use numpy.linalg.lstsq (see here). You can use exactly the same syntax.

x_ls = np.linalg.lstsq(coefficients, maxPoints)

This solver yields an answer which minimizes the squared Euclidean 2-norm. Instead you want to minimize using the constraint that x[j] <= x[j+1] for all j < len(x).

Some steps towards a solution

I may come back and edit this later with a Github snippet, as it's quite an interesting problem.

Edit: trust-constr seemed to work much better for this than SLSQP.

I think you should have a bit of a further read of the optimization documentation in scipy, particularly the trust-constr algorithm. I think you pretty much want to do a least squares solution on part of your matrix, then iterate forward. As a plausible algorithm:

Solve using trust-constr on the problem with 2 columns only (corresponding to x[4] and x[5]). Bounds (choose BOUND freely):
- x[4]: [-np.inf,BOUND]
- x[5]: [BOUND, np.inf]
Solve again with 3 columns (x3, x[4], x[5]). Bounds (with _p denoting value obtained from previous step):
- x3: [-np.inf,x_p[4]]
- x[4]: [x_p[4],x_p[5]]
- x[5]: [x_p[5],np.inf]
Repeat similarly until you solve for the full 6 columns.

It's not the best algorithm in the world, however, your constraint will be satisfied, and the iterative nature will correct a little bit if you do pick a bad value of BOUND to start with. If you wish to obtain a global solution, you can repeat for many different values of bound, and see which one returns the lowest error in the final trust-constr fit.

Edit: for an implementation:

import numpy as np
from scipy.optimize import minimize
from scipy.optimize import Bounds

# Set up bounds and make a,b objects
a,b = coefficients, maxPoints[:,0]

# Set acceptable bounds to be whatever you like here.
# I've chosen -100000 to 100000 in steps of 10000.
iter_of_acceptable_bounds = range(-100000,100000,10000)

def e2n(x,*args):
    'Compute the sum of the residuals (Euclidean 2-norm).'
    a,b = args
    return np.inner(b-a@x,b-a@x)

solutions, errors = [], []
for BOUND in iter_of_acceptable_bounds:   
    # Repeat the algorithm for each initial choice of bounds.

    # Generate an array for the bounds, based no the initial choice.
    bounds_arr = np.concatenate(([-np.inf],[BOUND,BOUND],[np.inf]))

    for i in range(2,a.shape[1]+1):
        # Initial guess of 0.
        x0 = [0 for j in range(i)]

        # Start with 2 columns, end at a.shape[1]
        # (a.shape[1]==6 for the example).

        bounds = Bounds(
                *bounds_arr.reshape(i,2).T.tolist()
                )

        # Slice up a accordingly
        A = a[:,-i:]

        # Minimize using trust-constr, and unpack the solution
        xr = minimize(e2n,x0,
                 args=(A,b),
                 bounds=bounds,
                 method='trust-constr').x

        # Generate a new array for the bounds, dynamically based on the previous choices.
        bounds_arr = np.concatenate(
                        [[-np.inf]] + [(xr[j],xr[j]) for j in range(i)] + [[np.inf]]
                        )

    # Save the solution and error from the full matrix
    solutions.append(xr)
    errors.append(np.sqrt(e2n(xr,a,b)))

This seems to perform fairly well. If we make a quick plot:

import matplotlib.pyplot as plt

# lstsq, for comparison (no constraints)
lstsq_fit, lstsq_res, *_ = np.linalg.lstsq(a,b)
lstsq_err = np.sqrt(lstsq_res)

# Plot errors
plt.plot(iter_of_acceptable_bounds,100*(errors-lstsq_err)/lstsq_err)
plt.xlabel('Starting choice of BOUND for algorithm')
plt.ylabel('Increase in error compared to numpy.linalg.lstsq')
plt.show()

In general, numpy.linalg.lstsq will solve this problem fairly well (it is just a linear regression problem), however it doesn't have the desired constraint. However, generally speaking this algorithm is okay -- the data fits only around 40% worse than numpy.linalg.lstsq for some of our choices of BOUND.

From this coarse search, the best values were given by:

>>> my_sol = solutions[errors.index(min(errors))]
>>> print(my_sol) 
array([-186017.00778511,    6680.13364168,  184099.89046232,
        220587.55247874,  257275.09670101,  257275.09670101])

Constrained Linear Optimization problem in python

Answers (2)

Step 1: Formulate a mathematical model

Step 2: Implementation, i.e. write some code

Related Questions