MATH2070: Optimization and Financial Mathematics

Assessments:

-     Assignment (10%) 2 weeks. Due on September 19, 2022

-     Quiz (5%) 40 minutes. Due on October 24, 2021

-     Computer Project (15%) 3 weeks. Due on November 4, 2022

-     Final exam (70%) 2 hours. Exam period

PART I  Some expected knowledge

PART 1.1 Optimising differentiable function of on variable

First derivative test

a) If a maximum or minimum of f(x) occurs at an interior x0, then x0 must be a critical point.

b) A point x0 is a local maximum or local minimum of f(x), if f(x)  ≤  f(x0) or f(x)  ≥  f(x0) for all  x in some neighbourhood of x0 .

Second  derivative test

The second derivative f''(x)  can be used to test for a local maximum or local minimum:

a) If f'(x0)  = 0 and f''(x0)  < 0 , then x0 is a local maximum.

b) If f'(x0)  = 0 and f''(x0)  > 0 , then x0 is a local minimum.

c) If f''(x0)  = 0 , then the test fails, and higher derivatives must be examined or some other test for optimality must be used.

PART II  Gauss-Jordan elimination for solving linear equation

PART 2.1 Revision of solving linear equations

Consider the systems of linear equations:

Ax  =  b

where x  e R ,  b  e R , A  e R

Assume A is an invertible square matrix, then the solution is given by:

−1

PART 2.2 Gauss-Jordan elimination

Gauss-Jordan elimination

Gauss-Jordan elimination is a procedure of solving a system of linear equation by performing a sequence of pivot operations.

Elementary row operations

a) Multiply (divide) any row by non-zero constant

b) Add a multiple of one row to another row

c) Interchange two rows

The combination of the 3 elementary row operations is called pivot operation.

Steps of a pivot operation

a) Decide on a pivot element aij  ≠ 0

b) Divide row i by aij

c) For rows k  ≠  i, transform a    to zero

PART 2.3 What ifA is not a square matrix

Full rank assumption

The rank of a matrix refers to the number of linearly independent column or row vectors in the matrix.

Let Ax  =  b, where A is an m-by-n matrix and m < n. The system Ax  =  b has a solution if the row vectors of A are linearly independent, or ank(A)   =  m. However, the solution is not unique.

Alternative views

a) View A as a set of row vectors  1,  2,  3,  ..., m

b) View A as a set of column vectors C1,  C2,  C3,  ...,  Cn

Some definitions

For the system above:

a) The solution (Xb , 0 ) is called a basic solution of AX  =  b

b) The components of x associated with the columns of B are called basic variables

c) The remaining n  − m variables are called non-basic variables

d) The choice of basic variables is rather arbitrary Example 1:

PART III Linear programming problem setup

PART 3.1 Standard form of linear programming

Maximise  Z  = c1x1  + c2x2  +... + cnxn

Subject to  a11x1  + a12x2  +... + a1nxn  ≤ b1

a21x1  + a22x2  +... + a2nxn  ≤ b2

… …

am1x1  + am2x2  +... + amnxn  ≤ bm

with      x1, x2,  ... , xn  ≥  0

Definitions

a) Objective function

b) Decision variables

c) Cost coefficients

d) Constraint matrix

e) Resource vector

f) Feasible solution

g) Feasible region

h) Optimal solution

Exercise 2: the following is the final simplex tableau for linear programming problem:

a) What are the non-basic variables?

b) What is the optimal value of the objective functions?

c) Identify the solution vertex (x1, x2, x3 )

Part 3.2 The simplex algorithm

Algebraic representation of corner points

a) At the corner point, basic variables are non-zero and non-basic variables are zero.

b) Two corner points are adjacent if they differ in precisely one non-basic variable (or equivalently, in precisely one basic variable)

The simplex algorithm

Aim: move from one FCP to an adjacent FCP with largest potential increase in the objective function

Z

.

a) Initialization: start on a feasible corner point (FCP).

i.e by setting decision variables to zero and slack variables to resource constraints b) Iteration steps: move to an adjacent FCP with best potential increase of Z.

1)   Which non-basic variable enters the basis?

Largest coefficient rule: increasing the non-basic variable Xl to Xl  >  0 with the largest cost coefficient cl might yield the largest increase of Z

2)   Which basic variables leave the basis?

Choose X  such that    bl     is minimal

c) Stopping rule: stop at FCP if its Z is greater than the Z-value of all its adjacent FCPs. Stop when all

modified cost coefficient c  ≥  0.