Solving Linear and Quadratic Programming Problems by MATLAB

Introduction

Optimization is defined as Minimizing (or Maximizing) an objective function subject to some constraints .If the objective function and the all the constrains are linear it is called linear programming. If the objective function is quadratic and the all the constraints are linear, it is known as quadratic programming. Let us learn how to use the linear and quadratic programming routines of the MATLAB.

Linear programming

The command for implementing the matlab linear programming routine is ‘linprog’.

Let us consider a linear programming problem with ‘n’ variables, ‘m’ inequality constraints, ‘k’ equality constraints, and the lower ,upper bounds LB and UB.

The linear programming is defined in matlab like this

min f'*x    subject to:   A*x <= b, Aeq*x = beq ,LB≤ x ≤ UB

x-=[x₁ x₂ x₃ ….x_n]^T x is a column matrix of 1 X n) to be determined.  

f=[c₁ c₂ c₃ ….c_n]  f is a vector(row matrix of n X 1)

A is the matrix of inequalities having a size of m X n

Aeq is the matrix of equalities having a size of k X n

LB-=[l₁ l₂ l₃ ….l_n]^T x is a column matrix of 1 X n)

UB= [u₁ u₂, u₃ ….u_n]^T x is a column matrix of 1 X n)

Example

f=[10 5 12 13 20];

A= [10     6     1     0     8

     2     8     4     7     0

     6     9     8     4     7

     5     7     0     9     4

     9     2     1     5     8

     8     4     2     4     5

     5     9     2     8     7

     0     9     6     5     4

     8     4     3     2     3

     4     9     2     7     2];

b=[70    63   104    80    81    68   101    81    53    71]';

Aeq=[1 1 1 1 1]

beq=15;

LB=[0 0 0 0 0]'

UB=[20 20 20 20 20]'

X=linprog(f,A,b,Aeq,beq,LB,UB)

Solution

Optimization terminated.

X =

    2.1683

    0.0000

    9.6931

    2.8416

    0.2970

Quadratic programming

The command for implementing the matlab quadratic programming routine is ‘quadprog’.Let us consider a quadratic programming problem with ‘n’ variables, ‘m’ inequality constraints, ‘k’ equality constraints, and the lower, upper bounds LB and UB.

The quadratic programming is defined in matlab like this

   min 0.5*x'*H*x + f'*x    subject to:   A*x <= b, Aeq*x = beq ,LB≤ x ≤ UB

x-=[x₁ x₂ x₃ ….x_n]^T x is a column matrix of 1 X n) to be determined.  

H= is a square matrix of n X n

f=[c₁ c₂ c₃ ….c_n]  f is a vector(row matrix of n X 1)

A is the matrix of inequalities having a size of m X n

Aeq is the matrix of equalities having a size of k X n

LB-=[l₁ l₂ l₃ ….l_n]^T x is a column matrix of 1 X n)

UB= [u₁ u₂, u₃ ….u_n]^T x is a column matrix of 1 X n)

Example

Minimize x₁^2+x₁x₂+x₂₂+3x₁+5x₂

Subject to the constraints

x₁+x₂=20;

2x₁+3x₂≤100

[0 0]^T≤x₁,x₂≤[50 50]^T

H=[2 1;1 2];

f=[3 5];

A= [2 3];

b=[100];

Aeq=[1 1]

beq=20;

LB=[0 0 0 0 0]';

UB=[50 50]';

[X ff]=quadprog(H,f,A,b,Aeq,beq,LB,UB)

Solution

X =

   11.0000

    9.0000

ff is the objective function value

ff =  379.0000