1
Decision Models & Analytics
8. Nonlinear Programming
Professor Jiawei Zhang
Agenda 2
Nonlinear function vs linear function
Global optimum vs local optimum
Well-behaved nonlinear program vs highly nonlinear program
GRG Nonlinear vs Evolutionary Solver
Linearization of Nonlinear Programs
Reading from Optimization Modeling
– Chapter 8
Templates: BeatTheMarket_Data.xls
Nonlinear Model 3
Nonlinear models are common in the real world
– Production cost is often not a linear function of production quantity
(economies of scale)
– Ordering cost is often not a linear function of order quantity (quantity
discount)
– Price of a stock option is a nonlinear function of the price of the
underlying stock
– Revenue is a nonlinear function of price
• Revenue is equal to price multiplied by demand
• But demand itself is a function of price
Most optimization models in statistics and data science exhibit nonlinearity.
Fit within Optimization Models 4
Linear Program: objective function and all constraints purely linear.
Mixed (Linear) Integer Program: objective function and all constraints
purely linear, but at least one variable is required to be an integer (binary).
Nonlinear Program: at least one nonlinear term appears in a constraint or
in the objective.
Nonlinear Integer Program: at least one nonlinear term appears
somewhere, and at least one variable is required to be integer.
Stochastic Program: involves parameters whose values are uncertain.
could be nonlinear and/or have integer variables.
Solver for Different Optimization Types 5
Linear program: Simplex LP
Linear integer program: Simplex LP
“Nice” nonlinear program: GRG Nonlinear
Highly nonlinear program: Evolutionary
Nonlinear integer program: Evolutionary or GRG Nonlinear
Stochastic program: Crystal Ball
Linear vs Nonlinear Functions 6
Assume that x and y are decision variables:
Function f(x, y) Linear?
2x+5y
2x+5xy
2 x2 + 5 y
x/y
If(x ≥ 50, 400 x, 450 x)
If(60 ≥ 50, 400 x, 450 x)
Max(x, 50) + y
Max(60, 50) + y
Sumproduct(50:60, x:y)
Sumproduct(50:x, 60:y)
Linear vs. Nonlinear Excel Formulas 7
Data cells are in D1:D6 and changing cells are in C1:C6.
Linear Formulas Nonlinear Formulas
SUMPRODUCT(D4:D6, C4:C6) SUMPRODUCT(C4:C6, C1:C3)
[(D1 + D2) / D3] * C4 [(C1 + C2) / C3] * D4
IF(D2 >= 2, 2*C3, 3*C4) IF(C2 >= 2, 2*C3, 3*C4)
SUMIF(D1:D6, 4, C1:C6) SUMIF(C1:C6, 4, D1:D6)
SUM(D4:D6) ROUND(C1)
2*C1 + 3*C4 + C6 MAX(C1, 0)
C1 + C2 + C3 MIN(C1, C2)
ABS(C1)
SQRT(C1)
C1 * C2
C1 / C2
C1 ^2
A Simple Example 8
Consider the following model in algebraic form
Maximize Profit = 0.5x5 – 6x4 + 24.5x3 – 39x2 + 20x
subject to x≤5
x≥0
It has a nonlinear objective function with bounds on the decision variable.
Solver Solution 1 9
If the initial solution is x=0
A B C D E
1 A Simple NLP
2
3 Maximum
4 x= 0.371 <= 5
5
6 Profit = 0.5x5-6x4+24.5x3-39x2+20x
7 = $3.19
Solver Solution 2 10
If the initial solution is x=3
A B C D E
1 A Simple NLP
2
3 Maximum
4 x= 3.126 <= 5
5
6 Profit = 0.5x5-6x4+24.5x3-39x2+20x
7 = $6.13
Solver Solution 3 11
If the initial solution is x=4.7
A B C D E
1 A Simple NLP
2
3 Maximum
4 x= 5.000 <= 5
5
6 Profit = 0.5x 5-6x 4+24.5x 3-39x 2+20x
7 = $0.00
Solver Message 12
If the initial solution is x=4.7, the Solver solution is x=5.
But it’s clear this is not an optimal solution!
Local vs Global Optima 13
Profit ($)
B
In this graph, points A=0.371, B=3.126, and
C=5 are called local maxima because the
function is larger at A, B and C than at
A
nearby points, respectively.
Only point B maximizes the function. It is
C called the global maximum.
x
The problem is that Solver can get stuck
near point A or C, concluding that A (or C)
maximizes the function.
The output solution depends on the starting
point!
A Nonlinear Function of Two Variables 14
Some Nonlinear Functions are “Nice” 15
Function
Local maximum is also global maximum!
Some Nonlinear Functions are “Nice” 16
Function
Local minimum is also global minimum!
Concave Maximization 17
For a maximization problem with linear constraints and a concave
objective function, Solver guarantees a global optimal solution.
Line joining any two points
is on or below the curve
A Concave Function
Convex Minimization 18
For a minimization problem with linear constraints and a convex objective
function, Solver guarantees a global optimal solution.
Line joining any two points
is on or above the curve
A Convex Function
Highly Nonlinear Functions 19
Try not to use GRG nonlinear solver, when there are following functions:
– If
– sumif
– and/or
– round
These functions usually are not smooth and have many local optimal
solutions.
Beat the Market 20
Portfolio managers often strive to outperform the market as a common
objective.
By assuming that past performance is indicative of future performance,
selecting a portfolio that has consistently outperformed the market in the
past increases the likelihood of achieving above-market returns in the
future.
Consider a portfolio of five large stocks traded on the New York Stock
Exchange (NYSE):
– Johnson & Johnson (JNJ)
– Mastercard Inc (MA)
– The Home Depot Inc (HD)
– Boeing Co (BA)
– ExxonMobil (XOM)
Beat the Market 21
The monthly performance (return) of each of these stocks over a three-year
period (1-36) and the performance of the market as a whole, as measured by
the NYSE Composite Index, are shown below.
B C D E F G H I J K
2 Market
3 Month Stock 1 Stock 2 Stock 3 Stock 4 Stock 5 (NYA)
4 1 -9.67% -8.01% -4.50% -13.56% -17.19% -9.06%
5 2 -1.87% -16.78% -14.29% -45.47% -25.13% -16.79%
6 3 14.42% 13.83% 18.53% -5.44% 22.39% 10.39%
7 4 -0.86% 9.60% 13.03% 3.43% -2.15% 3.79%
8 5 -4.80% -1.72% 0.82% 25.68% 0.26% 0.77%
9 6 3.65% 4.34% 6.61% -13.80% -5.90% 4.80%
10 7 5.25% 16.25% 7.36% 8.75% -5.09% 4.66%
11 8 -2.31% -5.59% -2.57% -3.82% -12.35% -2.63%
12 9 -7.91% -14.65% -3.45% -12.63% -4.98% -2.15%
13 10 5.52% 16.72% 4.01% 45.93% 16.89% 12.69%
14 11 9.53% 6.07% -4.25% 1.59% 10.71% 3.70%
15 12 3.65% -11.39% 2.51% -9.28% 8.78% -0.88%
16 13 -2.86% 12.02% -4.61% 9.18% 21.25% 4.26%
17 14 4.36% 0.62% 18.16% 20.15% 4.43% 3.94%
18 15 -0.99% 7.31% 6.70% -8.01% 2.53% 3.96%
19 16 4.01% -5.51% -1.47% 5.42% 1.97% 2.07%
20 17 -2.06% 1.25% -0.01% -3.02% 9.64% 0.11%
What mix of these five stocks will yield a portfolio that is likely to beat the
market in the future?
Refer to BeatTheMarket_Data.xls
Trial Solutions 22
Start with equal allocation: allocate 20% of your fund to each stock
– How many times you can beat the market? 16 times
– Run Solver. Does the solution change?
Try another allocation (10%,10%,10%,10%,60%)
– How many times you can beat the market? 16 times
– Run Solver. Does the solution change?
Try another allocation of your choice.
Local Optimal Solutions 23
For this model, (almost) every solution is a local optimal solution!
Why?
GRG Nonlinear Solver is no longer useful!
The use of IF function usually causes big troubles for GRG Nonlinear
Solver.