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)
0xi 75K, i1,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, i1,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,i1,2,3
Exercise 2
Use the two-phase method to solve the following LP problem:
minP4x 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:
minP2x 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 PcTx subjectto Axb
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 Axb
 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 uTbvTb d
subjectto ATuATvc u0
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 Axb
11
Axb 22
Axb 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 PcTx  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 minPcTx
Dual LP Problem maxP bT
subjecttoAxb x0
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 solutionsx ,  suchthatcTxbT,then xandare 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 12 subjectto12 1 1, 2 0.
2/24/2020 @2020 New York University Tandon 142 School of Engineering

Theorem 2 of Strong Duality
Primal LP Problem minPcTx
Dual LP Problem maxP bT
subjecttoAxb x  0
d subjecttoA c
 free variable If one problem has an optimal solution, then
the other problem also has an optimal solution. Plus PcTx  P bT foroptimalx,.
d
2/24/2020 @2020 New York University Tandon 143 School of Engineering
T

Sketch of Proof
Letx beanoptimalbasicfeasiblesolutionfortheprimal *
xcolx x. *BN
NotingthatAB NandccolcB cN , then x B1bandthereducedcostscT cTB1N0.
BNB
It is direct to check that *  (B1)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)
*  (B1 )T cB is feasible because
T T1T 1T 1
T A*A(B)cB(BA)cBIBN cB
colcB (B1N)TcBcol(cB cN):c. *  (B1 )T cB is optimal because
P bT bT(B1)Tc (B1b)T c cTx P*. d* BB*
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 B1N  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 cAT*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:
minPx 2x 12
subjectto 2x x 2 12
x 2x 7 12
x3 1
x , x  0. 12

A Practical Example
A baker produces two types of cakes:
x elaborate and x simple. 12
maxP24x  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
2xx700 (labor) 12
x  0, x  0. 12

A Practical Example (cont’d)
Its dual LP problem is:
minPd 12001  10002 7003
subject to 31  42  23  24 (elaborate cake)
21 2 3 14 (simplecake) 1 0, 2 0, 3 0.
2/24/2020 @2020 New York University Tandon 150 School of Engineering

Answers
P8880, 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
P8880, 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 worth2 1.2$.Forthesereasons,thedualvariables are called shadow prices.
2/24/2020 @2020 New York University Tandon 152 School of Engineering

Answers
P8880, 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 cTB1N  0. NB

2/24/2020
@2020 New York University Tandon 156 School of Engineering
minPx 2x 12
An Example
Consider the linear programming problem
subjectto 2xx2, 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
B2 1 0,B10 0 1, 
0 1 0 1 0.5 1.5 
0 0 0.5 0.5 N10,B1N0 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,xB1b533,
B 213 Reduced costs:
T
T T1  T
cNcBBN12 (00) Optimal dual variables:
  B1 
T c 0 1 2 .
*B
T

An Example of Sensitivity Analysis
Consider the perturbed linear programming problem minPx 2x
12
subjectto 2xx2, 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
B1(bb)0, withb0 0 Or equivalently,
5 0.5 B1b  B1b  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 minPx 2x
12
subjectto 2xx2, 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): maxwbT 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 cAT y0. Or, equivalently,
Duality Gap : cT xbT y
xjsj 0, j1,,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 , j1,,n.
Remark1: 0givesinteriorpointsx0, s0.
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
AxbandA ysc,butxs , jj
find new estimates xx, yy, ss such that
Axxb  Ax0 (*) 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 xjsj sj
is approximated by linear equations:
sjxj xjsj xjsj *** Thus, these three equations determine the
directions x, y, s.

Update Parameter Law
k1 k, 01.
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 , ss, 
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?
minP2x 3x 2x x x 12345
3x 3x 4x 2x x 0, 12345
subjectto x x x 3x x 2, 12345
xi 0, i1,,5.
2/24/2020 @2020 New York University Tandon 172 School of Engineering