Solution Methods

Solution Methods

Richard Lusby

Department of Management Engineering Technical University of Denmark

Lecture Overview

(jg

Unconstrained Several Variables Quadratic Programming Separable Programming SUMT

One Variable Unconstrained Optimization

(jg

Let’s consider the simplest case: Unconstrained optimization with just a single variable x, where the differentiable function to be maximized is concave

The necessary and sufficient condition for a particular solutionx =x^∗ to be a global maximum is:

df

dx = 0 x=x^∗ If this can be solved directly you are done What if it cannot be solved easily analytically?

We can utilize search procedures to solve itnumerically

Bisection Method

One Variable Unconstrained Optimization(jg

Can always be applied when f(x) concave It can also be used for certain other functions

Ifx^∗ denotes the optimal solution, all that is needed is that df

dx >0 if x<x^∗ df

dx = 0 if x=x^∗ df

dx <0 if x>x^∗

These conditions automatically hold when f(x) is concave The sign of the gradient indicates the direction of improvement

Example

(jg

f(x) _df

dx = 0

Bisection Method

Overview(jg

Bisection

Given two values, x <x, with f⁰(x)>0, f⁰(x)<0 Find the midpoint ˆx = ^x+x₂

Find the sign of the slope of the midpoint The next two values are:

I x= ˆx iff⁰(ˆx)<0

I x= ˆx iff⁰(ˆx)>0

What is the stopping criterion?

x−x <2

Bisection Method

Overview(jg

Bisection

Given two values, x <x, with f⁰(x)>0, f⁰(x)<0 Find the midpoint ˆx = ^x+x₂

Find the sign of the slope of the midpoint The next two values are:

I x= ˆx iff⁰(ˆx)<0

I x= ˆx iff⁰(ˆx)>0

What is the stopping criterion?

x−x <2

Bisection Method

Example(jg

The Problem

maximize f(x) = 12x−3x⁴−2x⁶

Bisection Method

What does the function look like?(jg

0.5 1.0 1.5

1 2 3 4 5 6 7 8 9

−1

−2

Bisection Method

Calculations(jg

Iteration f⁰(ˆx) x x ˆx f(ˆx)

0 0 2 1 7.0000

1 -12.00 0 1 0.5 5.7812

2 10.12 0.5 1 0.75 7.6948

3 4.09 0.75 1 0.875 7.8439

4 -2.19 0.75 0.875 0.8125 7.8672

5 1.31 0.8125 0.875 0.84375 7.8829

6 -0.34 0.8125 0.84375 0.828125 7.8815 7 0.51 0.828125 0.84375 0.8359375 7.8839

x^∗≈0.836 0.828125<x^∗ <0.84375

f(x^∗) = 7.8839

Bisection Method

Continued(jg

Intuitive and straightforward procedure Converges slowly

An iteration decreases the difference between the bounds by one half Only information on the derivative of f(x) is used

More information could be obtained by looking atf⁰⁰(x)

Newton Method

Introduction(jg

Basic Idea: Approximatef(x) within the neighbourhood of the current trial solution by a quadratic function

This approximation is obtained by truncating the Taylor series after the second derivative

f(xi+1)≈f(xi) +f⁰(xi)(xi+1−xi) +f⁰⁰(xi)

2 (xi+1−xi)² Having set xi at iteration i, this is just a quadratic function of xi+1

Can be maximized by setting its derivative to zero

Newton Overview

max f(xi+1)≈f(xi) +f⁰(xi)(xi+1−xi) + f⁰⁰(xi)

2 (xi+1−xi)² f⁰(xi+1)≈f⁰(xi) +f⁰⁰(xi)(xi+1−xi)

xi+1=xi − f⁰(xi) f⁰⁰(xi) What is the stopping criterion?

|xi+1−xi|<

Newton Overview

max f(xi+1)≈f(xi) +f⁰(xi)(xi+1−xi) + f⁰⁰(xi)

2 (xi+1−xi)² f⁰(xi+1)≈f⁰(xi) +f⁰⁰(xi)(xi+1−xi)

xi+1=xi − f⁰(xi) f⁰⁰(xi) What is the stopping criterion?

|xi+1−xi|<

Same Example

(jg

The Problem

maximize: f(x) = 12x−3x⁴−2x⁶

f⁰(x) = 12−12x³−12x⁵ f⁰⁰(x) =−36x³−60x⁴

xi+1 =xi+1−x³−x⁵ 3x³+ 5x⁴

Newton Method

The function again(jg

0.5 1.0 1.5

1 2 3 4 5 6 7 8 9

−1

−2

Newton Method

Calculations(jg

Iteration xi f(xi) f⁰(xi) f^00(xi) f(ˆx)

1 1 7 -12 -96 0.875

2 0.875 7.8439 -2.1940 -62.733 0.84003 3 0.84003 7.8838 -0.1325 -55.279 0.83763 4 0.83763 7.8839 -0.0006 -54.790 0.83762

x^∗= 083763 f(x^∗) = 7.8839

Several variables

Newton still works(jg

Newton: Multivariable

Given x₁, the next iterate maximizes the quadratic approximation f(x1) +∇f(x1)(x−x1) + (x−x1)^TH(x1)(x−x1)

2 x₂=x₁−H(x1)⁻¹∇f(x1)^T

Gradient search

The next iterate maximizes f along the gradient ray

maximize: g(t) =f(x1+t∇f(x1)^T) s.t. t≥0 x₂=x₁+t^∗∇f(x1)^T

Example

(jg

The Problem

maximize: f(x,y) = 2xy+ 2y−x²−2y²

Example

Continued(jg

The vector of partial derivatives is given as

∇f(x) = ∂f

∂x1

, ∂f

∂x2

, . . . , ∂f

∂xn

Here ∂f

∂x = 2y−2x

∂f

∂y = 2x+ 2−4y

Suppose we select the point (x,y)=(0,0) as our initial point

∇f(0,0) = (0,2)

Example

Continued(jg

Perform an iteration

x = 0 +t(0) = 0 y = 0 +t(2) = 2t Substituting these expressions inf(x) we get

f(x+t∗ ∇f(x)) =f(0,2t) = 4t−8t² Differentiate wrt to t

d

dt(4t−8t²) = 4−16t = 0

∗ 1 1 1

Example

Perform a second iteration(jg

Gradient atx= (0,¹₂) is∇f(0,¹₂) = (1,0) Determine step length

x=

0,1 2

+t(1,0) Substituting these expressions inf(x) we get

f(x+t∗ ∇f(x)) =f

t,1 2

=t−t²+1 2 Differentiate wrt to t

d

dt(t−t²+1

2) = 1−2t = 0 Therefore t^∗ = ¹₂, andx= 0,¹₂

+¹₂(1,0) = ¹₂,¹₂

1 y

0,¹_{2 1}

2,¹₂

1

2,³_{4 3}

4,³₄

3

4,⁷_{8 7}

8,⁷₈

Quadratic programming

(jg

maximize: c^Tx−¹₂x^TQx

subject to: Ax ≤b (λ)

x ≥0 (µ) Q is symmetric and positive semidefinite

Lagrangian:

L(x,λ,µ) =c^Tx−1

2x^TQx+λ^T(b−Ax) +µ^Tx Applying KKT yields

Qx+A^Tλ−µ=c Ax+v=b

x,λ,µ,v≥0

x^Tµ= 0,λ^Tv= 0 complementarity constraints

Example

(jg

Problem

minimize: f(x) subject to: g₁(x) ≤0

g₂(x) ≤0 KKT Conditions

∇f(x) +u₁∇g₁(x) +u₂∇g₂(x) =0 u1g₁(x) =0

u₁≥0 u₂g₂(x) =0

QP solution

(jg

KKT Conditions

Qx+A^Tλ−µ =c Ax+v =b x,λ,µ,v ≥0 x^Tµ = 0 λ^Tv = 0

Add artificial variables to constraints with positivecj

Subtract artificial variables to constraints with negative bi

Initial basic variables are artificial variables some ofµ, and some ofv Do phase 1 of the Simplex method with a restricted entry rule,

I Ensures complementarity constraints are always satisfied

Example

(jg

The Problem

maximize: 15x+ 30y+ 4xy−2x²−4y²

subject to: x+ 2y ≤30

x,y ≥0

Example

Continued(jg

The Parameters are as follows:

c=

"

15 30

# ,A=

"

1 2

# ,x=

"

x y

# ,Q =

"

4 −4

−4 8

#

,b= 30 The Non-Linear Component of the objective function is

−1

2x^TQx=−2x²+ 4xy−4y²

Example

New Linear Program(jg

Minimize: Z =z1+z2

subject to: 4x−4y+λ1−µ1+z1 = 15

−4x+ 8y+ 2λ1−µ₂+z2 = 30

x+ 2y+v1 = 30

x,y, λ1, µ1, µ2,v1,z1,z2 ≥0 Complementarity Conditions

xµ1 = 0,yµ2 = 0,v1λ1 = 0

Modified Simplex

Initial Tableau(jg

BV Z x y λ₁ µ₁ µ₂ v1 z1 z2 rhs

Z -1 0 -4 -3 1 1 0 0 0 -45

z1 0 4 -4 1 -1 0 0 1 0 15

z2 0 -4 8 2 0 -1 0 0 1 30

v1 0 1 2 0 0 0 1 0 0 30

Modified Simplex

First Pivot(jg

BV Z x y λ₁ µ₁ µ₂ v1 z1 z2 rhs

Z -1 -2 0 -2 1 ¹₂ 0 0 ¹₂ -30

z1 0 2 0 2 -1 -¹₂ 0 1 ¹₂ 30 y 0 -¹₂ 1 ¹₄ 0 -¹₈ 0 0 ¹₈ ³⁰₈ v1 0 2 0 -¹₂ 0 ¹₄ 1 0 -¹₄ ⁴⁵₂

Modified Simplex

Second Pivot(jg

BV Z x y λ₁ µ₁ µ₂ v1 z1 z2 rhs Z -1 0 0 -⁵₂ 1 ³₄ 1 0 ¹₄ -¹⁵₂ z1 0 0 0 ⁵₂ -1 -³₄ -1 1 ³₄ ¹⁵₂

y 0 0 1 ¹₈ 0 -₁₆^{1 1}₄ 0 ₁₆^{1 75}₈ x 0 1 0 -¹₄ 0 ¹₈ ¹₂ 0 -¹₈ ⁴⁵₄

Modified Simplex

Final Tableau(jg

BV Z x y λ₁ µ₁ µ₂ v1 z1 z2 rhs

Z -1 0 0 0 0 0 0 1 1 0

λ1 0 0 0 1 -²₅ -₁₀³ -²₅ ²_{5 10}³ 3

y 0 0 1 0 ₂₀¹ -₄₀¹ ₁₀³ -₂₀¹ ₄₀¹ 9 x 0 1 0 0 -₁₀¹ ₂₀^{1 2}_{5 10}¹ -₂₀¹ 12

Separable Programming

(jg

The Problem

maximize: P

jfj(xj) subject to: Ax ≤b

x ≥0

Each fj is approximated by a piece-wise linear function f(y) =s1y1+s2y2+s3y3

y =y1+y2+y3

0 ≤y1 ≤u1

0 ≤y2 ≤u2

0 ≤y3 ≤u3

Separable Programming

Continued(jg

Special restrictions:

I y₂= 0 whenevery₁<u₁

I y₃= 0 whenevery₂<u₂ If eachfj is concave,

I Automatically satisfied by the simplex method Why?

Sequential Unconstrained Minimization Technique

(jg

The Problem

maximize: f(x) subject to: g(x) ≤b

x ≥0

For a sequence of decreasing positiver’s, solve maximizef(x)−rB(x)

B is a barrier function approaching∞ as a feasible point approaches the boundary of the feasible region

For example

B(x) =X

i

1

bi−gi(x) +X

j

1 xj

The Problem

maximize: xy subject to: x²+y ≤3

x,y ≥0

r x y

1 1

1 0.90 1.36

10⁻² 0.987 1.925 10⁻⁴ 0.998 1.993 Class exercise

Class exercises

(jg

Separable programming

maximize: 32x−x⁴+ 4y−y² subject to: x²+y² ≤9

x,y ≥0

Formulate this as an LP model using x= 0,1,2,3 and y = 0,1,2,3 as breakpoints for the approximating piece-wise linear functions

Class exercises

Continued(jg

Sequential Unconstrained Minimization Technique

Iff is concave and gi is convex ∀i, show that the following is concave f(x)−r



(X

i

1

bi−gi(x) +X

j

1 xj



