# CS计算机代考程序代写 algorithm Goal:

Goal:

A Financial Engineering Problem

How to use LP to model multi‐period cash management in financial firms?

2/24/2020 @2020 New York University Tandon 123 School of Engineering

Problem Setting:

A firm, named Firm X, must determine investment strategy for the firm during the next 3 years. At present (time 0), $100K is available for investment. Five investments named A, B, C, D and E are available, with the cash flow per $1 investment as follows:

2/24/2020

@2020 New York University Tandon School of Engineering

124

year 0 1 2 3

A ‐$1

B $0

C ‐$1

D ‐$1

E $0

+$0.50 +$1 ‐$1 +$0.50 +$1.2 $0

$0 $0

$0 ‐$1

$0 +$1 $0 +$1.9 +$1.5

Hypotheses:

1. The maximum investment for each category is $75K.

2. The firm is NOT allowed to borrow money to invest.

3. The interest rate for uninvested money is 8%.

Objective:

Maximize cash on hand at the end of year 3.

2/24/2020 @2020 New York University Tandon 125 School of Engineering

Unknown Variables:

x $ amount invested in investment A; 1

x2 $amountinvestedininvestmentB;

x $amountinvestedininvestmentE; 5

Solution

St $amountinvestedinguaranteed8%-returnattimet. Objective function:

P x 1.9x 1.5x 1.08S 2452

2/24/2020 @2020 New York University Tandon 126 School of Engineering

Constraints:

Solution (cont’d)

0xi 75K, i1,2,,5; 0 St , t 0,1, 2;

x x x S 100K; 1340

(year0)

0.5x 1.2x 1.08S x S; 13021

(year1) (year2).

x 0.5x 1.08S x S 12152

(cash available) (cash invested)

2/24/2020 @2020 New York University Tandon 127 School of Engineering

Maximizing solution:

Solution (cont’d)

P* 218,500; with

x* 60,000; x * 30,000; x * 40,000;

124

x* 75,000; 5

x* S* S* S* 0. 3012

2/24/2020 @2020 New York University Tandon 128 School of Engineering

2/24/2020

@2020 New York University Tandon 129 School of Engineering

x x x 5, 123

x 0, i1,2,3 i

Exercise 1

Use the simplex method to find a basic and feasible solution to the following system of linear inequalities:

2x 3x 2x 3, 1 2 3

2/24/2020

@2020 New York University Tandon 130 School of Engineering

2x x 3x 30, 123

x 2x 4x 40, 123

xi 0,i1,2,3

Exercise 2

Use the two-phase method to solve the following LP problem:

minP4x 2x 8x 123

2/24/2020

@2020 New York University Tandon 131 School of Engineering

3 x 1 2 x 2 1 8 , 2x x 2x 4

x 0 i

123

Exercise 3

State the following LP problem in standard form and solve it using the simplex method:

minP2x x 5x subjectto 123

x 2x x 8, 123

Goals:

Duality

• RevealtheRelationshipsbetweenthePrimaland Dual LP Problems.

• Introducetheconceptof“ShadowPrice”andits importance via solving the dual LP problem.

• IntroducetheDualSimplexMethod(iftime permits)

2/24/2020 @2020 New York University Tandon 132 School of Engineering

Primal and Dual LP Problems

Primal LP Problem (“canonical form”):

min PcTx subjectto Axb

x 0. Dual LP Problem:

Goals:

max P bT y d

• •

Make explicit the effects of changes in the constraints on the cost

subject to AT y c y 0.

Develop the “interior-point” software via combination of primal and dual info

2/24/2020 @2020 New York University Tandon 133 School of Engineering

2/24/2020

@2020 New York University Tandon 134 School of Engineering

Dual of a LP in Standard Form

First, notice that a linear program in standard form can be rewritten as:

min P cT x subjectto Axb

Ax b x 0.

2/24/2020

@2020 New York University Tandon 135 School of Engineering

Dual of a LP in Standard Form (cont’d)

Then, its “canonical” dual LP is:

maxP uTbvTb d

subjectto ATuATvc u0

Or,

v 0.

d

maxP bT T

subjectto A c

u v free variable!

2/24/2020

@2020 New York University Tandon 136 School of Engineering

An LP with Mixed Constraints

What is the “canonical” dual of the following LP:

min P cT x subjectto Axb

11

Axb 22

Axb 33

x 0.

2/24/2020

@2020 New York University Tandon 137 School of Engineering

An LP with Mixed Constraints (cont’d)

The dual LP problem is:

maxP bT y bT y bT y d112233

TTT subject to A y A y A y c

112233

y 0, y 0, y unrestricted. 123

Then

freevariable PcTx P bT foranyfeasiblex,.

2/24/2020

@2020 New York University Tandon 138 School of Engineering

Theorem 1 of Weak Duality (on the standard form)

Consider the primal and dual problems:

Primal LP Problem minPcTx

Dual LP Problem maxP bT

subjecttoAxb x0

d subjecttoA c

d

T

Relation of primal and dual values:

Dual values Primal values

P

2/24/2020 @2020 New York University Tandon School of Engineering

139

Comments

1. If the dual is unbounded, then the primal is infeasible.

2. If there is a pair of feasible solutionsx , suchthatcTxbT,then xandare optimal for their respective problems.

2/24/2020 @2020 New York University Tandon 140 School of Engineering

Consider the primal problem

An Example

min P x 1

subjecttox 1 1

What is its dual problem? Unbounded?

2/24/2020 @2020 New York University Tandon 141 School of Engineering

x 1 1

x 0. 1

The dual problem is

An Example (cont’d)

maxPd 12 subjectto12 1 1, 2 0.

2/24/2020 @2020 New York University Tandon 142 School of Engineering

Theorem 2 of Strong Duality

Primal LP Problem minPcTx

Dual LP Problem maxP bT

subjecttoAxb x 0

d subjecttoA c

free variable If one problem has an optimal solution, then

the other problem also has an optimal solution. Plus PcTx P bT foroptimalx,.

d

2/24/2020 @2020 New York University Tandon 143 School of Engineering

T

Sketch of Proof

Letx beanoptimalbasicfeasiblesolutionfortheprimal *

xcolx x. *BN

NotingthatAB NandccolcB cN , then x B1bandthereducedcostscT cTB1N0.

BNB

It is direct to check that * (B1)T cB is feasible and optimal for the dual and has the same optimal primal value,

as shown below.

2/24/2020 @2020 New York University Tandon 144 School of Engineering

Sketch of Proof (cont’d)

* (B1 )T cB is feasible because

T T1T 1T 1

T A*A(B)cB(BA)cBIBN cB

colcB (B1N)TcBcol(cB cN):c. * (B1 )T cB is optimal because

P bT bT(B1)Tc (B1b)T c cTx P*. d* BB*

2/24/2020 @2020 New York University Tandon 145 School of Engineering

xTB

2/24/2020

@2020 New York University Tandon 146 School of Engineering

An Equivalence Result

From the proof, we obtain:

Primal optimality condition cT cT B1N 0 NB

The dual feasibility condition T

T 1

A * c, with * B cB

Complementary Slackness

Let x* be the optimal primal (in standard form) and * the optimal dual. Then, it holds:

x*T cAT*0.

2/24/2020 @2020 New York University Tandon 147 School of Engineering

2/24/2020

@2020 New York University Tandon 148 School of Engineering

An Example

Verify the strong duality theorem on the LP:

minPx 2x 12

subjectto 2x x 2 12

x 2x 7 12

x3 1

x , x 0. 12

A Practical Example

A baker produces two types of cakes:

x elaborate and x simple. 12

maxP24x 14x 12

subject to 3x 2x 1200 (basic ingredients) 12

2/24/2020

@2020 New York University Tandon 149 School of Engineering

4x x 1000 (fancier ingredients) 12

2xx700 (labor) 12

x 0, x 0. 12

A Practical Example (cont’d)

Its dual LP problem is:

minPd 12001 10002 7003

subject to 31 42 23 24 (elaborate cake)

21 2 3 14 (simplecake) 1 0, 2 0, 3 0.

2/24/2020 @2020 New York University Tandon 150 School of Engineering

Answers

P8880, x 160, x 360 12

P 8880, 6.4, 1.2, 0. d123

1) For this problem, there are 20 hours of excess labor available,

as at the optimal solution 700 2x* x* 20. So, 12

additional labor has no value to the baker 3 0.

2/24/2020 @2020 New York University Tandon 151 School of Engineering

Answers

P8880, x 160, x 360 12

P 8880, 6.4, 1.2, 0. d123

2) In case the baker wants to purchase additional quantities of the ingredients, each pound of basic ingredients will be worth 1 6.4$ in profit,

while each pound of fancy ingredients will be worth2 1.2$.Forthesereasons,thedualvariables are called shadow prices.

2/24/2020 @2020 New York University Tandon 152 School of Engineering

Answers

P8880, x 160, x 360 12

P 8880, 6.4, 1.2, 0. d123

3) The dual problem can also be understood as the “price” a company should pay to take over the baker’s business.

2/24/2020 @2020 New York University Tandon 153 School of Engineering

Sensitivity

Goal: Understand the effects of parameter variations on the optimal solution.

2/24/2020 @2020 New York University Tandon 154 School of Engineering

•

Key Observations The current basis is feasible if

•

It is optimal if

2/24/2020

@2020 New York University Tandon 155 School of Engineering

1

B b 0.

xB

cT cTB1N 0. NB

2/24/2020

@2020 New York University Tandon 156 School of Engineering

minPx 2x 12

An Example

Consider the linear programming problem

subjectto 2xx2, 12

x 2x 7, 12

x 3, 1

x , x 0. 12

From Lecture 3, the last step in applying the Simplex Method yields (Optimal solution):

Basic x x x3 x4 x rhs 125

-P 0 0 0 1 2 13

x2 x1

0 1 0 1/2 1/2 5 100013 0 0 1 -1/2 3/2 3

x3 2/24/2020

@2020 New York University Tandon School of Engineering

157

2/24/2020

@2020 New York University Tandon 158 School of Engineering

T CurrentBasis:x x , x, x , with

B213

1 2 1 0 0.5 0.5

B2 1 0,B10 0 1,

0 1 0 1 0.5 1.5

0 0 0.5 0.5 N10,B1N0 1,

0 1 0.5 1.5

TT cB 2 10 , cN 0 0 .

2/24/2020

@2020 New York University Tandon 159 School of Engineering

Optimal primal variables:

TT x x,x,xB1b533,

B 213 Reduced costs:

T

T T1 T

cNcBBN12 (00) Optimal dual variables:

B1

T c 0 1 2 .

*B

T

An Example of Sensitivity Analysis

Consider the perturbed linear programming problem minPx 2x

12

subjectto 2xx2, 12

x 2x 7, 12

x 3, 1

x , x 0. 12

Show that the optimal basis remains unchanged as long as 10, 6.

2/24/2020 @2020 New York University Tandon 160 School of Engineering

A Short Proof

Observe that the optimality condition remains unchanged for this special type of perturbations.

The feasibility condition requires that T

B1(bb)0, withb0 0 Or equivalently,

5 0.5 B1b B1b 3 0

implying the claimed range for .

3 0.5

2/24/2020 @2020 New York University Tandon 161 School of Engineering

An Example of Sensitivity Analysis

Validate the above claim by solving the perturbed LP problem minPx 2x

12

subjectto 2xx2, 12

x 2x 7, 12

x 3, 1

x , x 0. 12

for different perturbations : 4, 8, 1, 4.

2/24/2020 @2020 New York University Tandon 162 School of Engineering

The Primal‐Dual Interior‐Point Method for LP

Motivation: fast polynomial‐time method for large LP problems

Interior‐Point Method by N. Karmarkar (1984):

Search for optimal solution through interior points,

instead of extreme points.

2/24/2020 @2020 New York University Tandon 163 School of Engineering

Primal‐Dual Problems

The Primal Problem (P): min z cT x

subject to Ax b, x 0. (A: full row-rank)

The Dual Problem (D): maxwbT y

subject to AT y s c, s 0 slack variables.

2/24/2020 @2020 New York University Tandon 164 School of Engineering

Complementary Slackness Conditions

For optimal solution x to (P) and optimal solution y to (D), the “complementary slackness” condition must hold:

xT cAT y0. Or, equivalently,

Duality Gap : cT xbT y

xjsj 0, j1,,n.

2/24/2020 @2020 New York University Tandon School of Engineering

165

Key Idea of the PD Interior Method

For positive 0, approximate the optimal solution with x, y, s satisfying:

A x b , x 0

P D A T y s c , s 0

xjsj , j1,,n.

Remark1: 0givesinteriorpointsx0, s0.

Remark 2 : 0 gives the optimal solution!

2/24/2020 @2020 New York University Tandon 166 School of Engineering

to the optimal solutions.

Duality Gap

cT x bT y xT s n.

The above duality gap measures the closeness

2/24/2020 @2020 New York University Tandon 167 School of Engineering

Algorithm

Given estimates x 0, y and s 0, with T

AxbandA ysc,butxs , jj

find new estimates xx, yy, ss such that

Axxb Ax0 (*) T

Similarly, A y s 0. **

2/24/2020 @2020 New York University Tandon 168 School of Engineering

2/24/2020

@2020 New York University Tandon 169 School of Engineering

Algorithm (cont’d)

In addition, the nonlinear complementary slackness

xj xjsj sj

is approximated by linear equations:

sjxj xjsj xjsj *** Thus, these three equations determine the

directions x, y, s.

Update Parameter Law

k1 k, 01.

2/24/2020 @2020 New York University Tandon 170 School of Engineering

Comment

In practice, we often adopt: x , x x ,

y , y y ,

s , ss,

where is a step length, chosen to ensure that x, s are positive (i.e. interior points).

More to come at the end of NL programming:

Interior-point methods for convex programming

2/24/2020 @2020 New York University Tandon 171 School of Engineering

Exercise

Can you solve the following problem using both the Simplex and the Interior‐Point methods?

minP2x 3x 2x x x 12345

3x 3x 4x 2x x 0, 12345

subjectto x x x 3x x 2, 12345

xi 0, i1,,5.

2/24/2020 @2020 New York University Tandon 172 School of Engineering