Skip to content

Linear, quadratic and nonlinear programming

Course exercises 112, 113, 115 · Part II

Problem

Solve three small optimisation problems with MATLAB's Optimization Toolbox, one per solver: a linear program with linprog, a quadratic program with quadprog, and a nonlinear problem with fmincon from two different starting points. These are the solvers behind every efficient frontier in the rest of this part.

Method

Solver Problem form Exercise
linprog \(\min f^\top x\) s.t. \(Ax \le b,\ x \ge 0\) 112: \(\min\, -5x_1 - 4x_2 - 6x_3\)
quadprog \(\min \tfrac12 x^\top H x + f^\top x\) s.t. \(Ax \le b,\ x \ge 0\) 113: \(\min\, x_1^2 + x_2^2 - x_1x_2 - 2x_1 - 6x_2\)
fmincon \(\min f(x)\) s.t. \(Ax \le b\) 115: \(\min\, x_1 x_2 x_3\)

For quadprog, \(H\) holds twice the coefficients of the squared terms on the diagonal and the cross-term coefficient off the diagonal, placed symmetrically.

Code

clear all, clc

% Point 1

   f = [ -5 -4 -6];

   A = [ 1 -1 1;
         3 2 4;
         3 2 0];

   b = [ 20; 42; 30];

   Aeq = [];
   beq = [];

   lb = zeros(length(f), 1);
   ub = [];

   [x, fval] = linprog(f,A,b,Aeq,beq,lb,ub)

clear all, clc

%% 1

H = [2 -1; -1 2] % squared terms: coefficient times 2;
                 % cross term: as it is, placed symmetrically

f = [-2 -6] % coefficients of the linear part

A = [1 1;
     -1 2;
     2 1] % coefficients of the inequality constraints

b = [2; 2; 3] % right-hand side of the inequality constraints

lb = zeros(2, 1)

[x,fval] = quadprog(H,f,A,b,[],[],lb,[])

clear all, clc

% Point 1

    fun = @(x) x(1) * x(2) * x(3)

    x01 = [2 4 8]

    A = [1 3 4; -2 -1 -1/2]

    b = [0 50]

    [x,fval] = fmincon(fun,x01,A,b,[],[],[],[])

% Point 2

    x02 = [-8 0 -3]

    [x,fval] = fmincon(fun,x02,A,b,[],[],[],[])

% fmincon (nonlinear programming) finds two different local minima from the
% two starting points, but not a global minimum (because of the shape of
% the function, which could be for example a "saddle")

import numpy as np
from scipy.optimize import linprog      # same name and almost the same arguments as MATLAB

# %% Point 1
f = np.array([-5, -4, -6])

A = np.array([[1, -1, 1],
              [3,  2, 4],
              [3,  2, 0]])

b = np.array([20, 42, 30])

lb = [(0, None)] * len(f)               # x >= 0 for each variable (None = no upper bound)

res = linprog(f, A_ub=A, b_ub=b, bounds=lb)   # MATLAB: [x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)
x = res.x
fval = res.fun
print("x =", x)
print("fval =", fval)

import numpy as np
from scipy.optimize import minimize     # scipy has no quadprog: minimize does the same job

# %% 1
H = np.array([[2, -1],
              [-1, 2]])                 # squared terms: coefficient times 2; cross term as it is
f = np.array([-2, -6])                  # coefficients of the linear part

A = np.array([[1, 1],
              [-1, 2],
              [2, 1]])                  # inequality constraints  A x <= b
b = np.array([2, 2, 3])

lb = [(0, None)] * 2                    # x >= 0

obj = lambda x: 0.5 * x @ H @ x + f @ x     # the quadratic objective that quadprog minimises
con = {'type': 'ineq', 'fun': lambda x: b - A @ x}   # scipy wants constraints written as  (something) >= 0

res = minimize(obj, np.zeros(2), method='SLSQP', bounds=lb, constraints=con)
x = res.x
fval = res.fun
print("x =", x)
print("fval =", fval)

import numpy as np
from scipy.optimize import minimize     # MATLAB's fmincon

# %% Point 1
fun = lambda x: x[0] * x[1] * x[2]      # MATLAB: @(x) x(1) * x(2) * x(3)

x01 = np.array([2, 4, 8])

A = np.array([[1, 3, 4],
              [-2, -1, -1/2]])
b = np.array([0, 50])

con = {'type': 'ineq', 'fun': lambda x: b - A @ x}   # A x <= b, written as  b - A x >= 0

res = minimize(fun, x01, method='SLSQP', constraints=con)
print("x =", res.x)
print("fval =", res.fun)

# %% Point 2
x02 = np.array([-8, 0, -3])

res = minimize(fun, x02, method='SLSQP', constraints=con)
print("x =", res.x)
print("fval =", res.fun)

# Two starting points, two different "solutions": see the note on the page
# (the problem has no minimum at all).

Results

Exercise Solution Objective
112, linear \(x = (0,\ 15,\ 3)\) −78
113, quadratic \(x = (0.667,\ 1.333)\) −8.00
115, from \(x_0 = (2, 4, 8)\) \(x = (-28.38,\ 5.15,\ 3.24)\) −472.6
115, from \(x_0 = (-8, 0, -3)\) \(x = (-8.33,\ -16.67,\ -33.33)\) −4,629.6

Exercise 115 has no minimum at all

The code's closing comment reads the two results as two local minima with no global one. The stronger statement is that the problem is unbounded below. Take \(x = (a,\ -(50 + 2.5a),\ a)\): both constraints hold for any \(a > 0\) (the second one with equality), and the objective \(-a^2(50 + 2.5a)\) goes to \(-\infty\). For \(a = 100\) it is already \(-3{,}000{,}000\), far below both points fmincon returns. Each run stops at a point where the local optimality conditions hold, which is all a local solver can guarantee.

Takeaways

  • The three solvers differ in what they accept: linear objective, quadratic objective, or any smooth function. Portfolio problems are built to fit the first two, because those are solved to the global optimum.
  • A nonlinear solver's answer depends on the starting point, and a "solution" can exist even when the problem has no minimum: checking boundedness is part of the modelling.