[SOLVED] CS algorithm Goal:

Goal:
A Financial Engineering Problem
How to use LP to model multiperiod 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 (contd)
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 (contd)
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.
IntroducetheconceptofShadowPriceandits 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 (contd)
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 (contd)
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 (contd)
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 (contd)
* (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 (contd)
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 bakers 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 PrimalDual InteriorPoint Method for LP
Motivation: fast polynomialtime method for large LP problems
InteriorPoint 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

PrimalDual 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 (contd)
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 InteriorPoint 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