PART I The Simplex Algorithm

PART 1.1 Standard form

Maximise  Z  = C1X1  + C2X2  +... + CnXn

Subject to  a11X1  + a12X2  +... + a1nXn  ≤ b1

a21X1  + a22X2  +... + a2nXn  ≤ b2

… …

am1X1  + am2X2  +... + amnXn  ≤ bm

with      X1, X2,  ... , Xn  ≥  0

PART 1.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.

PART II Non-standard Linear Programming

PART 2.1 Minimising the objective function

To minimise Z  =    ciXi, define Z = − Z, then minimising Z is equivalent to maximising Z :

i=1

min Z = max Z

Assignment Example:

PART 2.2 Negative resource elements

Suppose that for some constraint a1X1  + a2X2  + a3X3  +... + anXn  ≤  b  <  0, this is equivalent to −  a1X1  − a2X2  − a3X3  − ... − anXn  ≥  b  >  0

Assignment Example:

PART 2.3 Greater-than or equal-to constraints

For a constraint a1X1  + a2X2  + a3X3  +... + anXn  ≥  b  ≥  0, introduce a surplus variable Xn+1 such that

a1X1  + a2X2  + a3X3  +... + anXn  − Xn+1  =  b

Assignment Example:

PART 2.4 Negative decision variables

If x   ≤  0, introduce a variable x   = − x  ,  then x   ≥  0.

Assignment Example:

PART 2.5 Unrestricted decision variables

If x   is unrestricted in sign (x   ∈  R), introduce two new variables  x   ≥  0 and  x   ≥  0, then

k            k                k

Assignment Example:

PART 2.6 Absolute value in objective functions

If max Z  = − |f(x)| + g(y) or min Z  = |f(x)| + g(y), introduce U  = |x|, then U  ≥ x and U  ≥ − x.

Assignment Example:

PART III Duality

PART 3.1 Primal problem

PART 3.2 Dual Problem

PART 3.3 Fundamental duality theorem

Theorem 1 (weak duality theorem)

If  and  are feasible solutions of the primal and dual problems respectively, then

If  and  are feasible primal and dual solutions such that  , then  and  are primal and dual optimal solutions with V* = Z*.

Theorem 2

If both the primal and dual LP problems are feasible, then both have optimal solutions and the optimal values of the objective functions of the primal and dual are equal.

PART IV Assignment questions

PART V Nonlinear optimization without constraints

PART 5.1 Taylor’s theorem

Taylor’s theorem for one variable

Taylor’s theorem for multivariate functions

PART 5.2 Hessian matrix

Two-dimensional example

Multi-index notation

For α  =  (α1, α2, α3,..., αn), αi  ≥  0:

a) α! = α 1 ! α2 !... αn !

b) |α| = α 1  + α2  +... + αn

c) xα  = x1(α)1  x2(α)2  x xn(α)n

d) 

Multinomial theorem

For any x  =  (x1, x2, x3,..., xn)   ∈ R   and any positive integer k:

(x1  + x2  + x3  +... + xn)k  =    ∑   xα

|α|=k

Characterization of extrema

Critical point:

a) x0 is a local minimum if Q(ℎ, ℎ)  >  0,  ∀ℎ  ≠  0

b) x0 is a local minimum if Q(ℎ, ℎ)  <  0,  ∀ℎ  ≠  0

c) x0 is a saddle point if Q(ℎ, ℎ)  >  0 for some ℎ and Q(ℎ, ℎ)  <  0 for some other ℎ

d) No conclusion can be drawn if

-     Q(ℎ, ℎ)  ≥  0 for all ℎ and Q(ℎ, ℎ)  =  0 for at least one ℎ  ≠  0

-     Q(ℎ, ℎ)  ≤  0 for all ℎ and Q(ℎ, ℎ)  =  0 for at least one ℎ  ≠  0

If f is convex, any local minimizer is a global minimizer of f. If in addition f is differentiable, then any critical point a global minimizer of f.

-     The function f is a convex function if its domain D is a convex set, and if for any two points x and y in D, we have:

f(λx  +  (1  −  λ)y)  ≤  λf(x)  +  (1  −  λ)f(y),  ∀λ  ∈ [0, 1]

Lagrange’s method of completing the square of Q

Example 1: Given

Let H  = H(x0):

a) H is positive definite if and only if all of its eigenvalues are positive;

b) H is negative definite if and only if all of its eigenvalues are negative;

c) H is indefinite If and only If it has both positive and negative eigenvalues;

d) H is positive semidefinite if and only if all of its eigenvalues are non-negative and at least one eigenvalue is zero;

e) H is negative semidefinite if and only if all of its eigenvalues are non-positive and at least one eigenvalue is zero.

Example 2: Let Q  =  7x1(2)  + 4x1x2  + 4x2(2)  − 4x2x3  +  7x3(2)  −  8x1x3 . Rewrite the quadratic form Q as  , where B is a symmetric matrix and x  =  (x1, x2, x3). Is B positive definite? Check your           answer by completing the square in the quadratic form.