15.

053x Week 6

Optimization Methods
in Business Analytics

Nonlinear Programming

1
 Nonlinear Optimization

Minimum  
value  
Thanks  to  Rob  Freund  and  Juan  Carlos  
Ferrer  for  sharing  their  slides  
2
 Overview
• Por8olio  op:miza:on.  

• Convex  func:ons  and  convex  sets.  

• Local  op:miza:on  vs.  global  op:miza:on.  

– Convex  minimiza:on  problems  are  “easy.”  

• More  applica:ons  of  nonlinear  programming  

3
  
 
Por8olio  op:miza:on  1:    Intro  
 

4  
 Por8olio  op:miza:on  
• Important  topic  in  Finance  

• 1990  Nobel  Prize  in  Economics  

– Miller,  Sharpe,  and  Markowitz  

• Knowledge  about  probability  and  random  variables  

will  be  useful,  but  it  is  not  required  for  these  videos.  
5  
 Por8olio  op:miza:on  1  
Investment choice: 3 stocks.
Data: expected returns, standard deviations (5 yr)
Assumption (for now): stock returns are
independent of each other (uncorrelated).

Five Year Expected Standard Dev. of Return

Company Return (%) (%)
IBM 65 15
Prudential 80 18
Raytheon 50 10 6  
 Five Year Expected Standard Dev. of Return
Company Return (%) (%)
IBM 65 15
Prudential 80 18
Raytheon 50 10

65%  expected  return:    “on  average,”  for  every  dollar  invested,  the  
investor  will  have  $1.65  aVer  five  years.    

15%  standard  devia:on:    can  be  roughly  interpreted  as  follows.  The  
“return”  of  $1  invested  aVer  five  years  is  likely  (approximately  2/3  
chance)  to  be  between  65%  -­‐  .15%    and    65%  +  .15%,  (50%  and  80%)      
7  
 Objec:ves  
• Create  a  por8olio  
• Maximize  expected  return  
• Minimize    risk  (standard  dev.  of  por8olio)  

Assump:on.      Investments  with  a  higher  expected  

return  and  lower  “risk”  are  preferable.      
 This  assump:on  is  not  always  true  in  prac:ce.  
8  
 Which  lodery  would  you  prefer?  
Lodery  1.        
• A  90%  chance  of  winning  $1,000,000     Exp.  Return:  $890,000      
• A  10%  chance  of  losing  $100,000   s.d.                                  $285,000      
 
Lodery  2.        
• A  50%  chance  of  winning  $1,000,000     Exp.  Return:  $550,000      
• A  50%  chance  of  winning  $100,000   s.d.                                  $355,000      
9  
  
 
Por8olio  op:miza:on  2:    A  model    
 

10  
 The  three  random  variables    
XI = 5-year return on investing in IBM
XP = 5-year return on investing in Prudential
XR = 5-year return on investing in Raytheon

E[XI]  =  65 SD[XI]  =  15

XI,  XP,  XR  are    
E[XP]  =  80 SD[XP]  =  18
random  variables.  
E[XR]  =  50 SD[XR]  =  10
11  
 Expected  values  
Suppose  X  and  Y  are  any  random  variables.    
 
Then    E(X  +  Y)  =  E(X)  +  E(Y).      
   

12  
 Standard  devia:ons  and  variances  
Suppose  that  X  is  a  random  variable.  
• Let  VAR(X)  denote  Variance  of  X  
• VAR(X)  =  SD(X)2                SD(X)  =  VAR(X)1/2  
– The  math  of  variances  is  simpler  than  that  of  standard  devia:ons  

Suppose  X  and  Y  are  independent  random  variables.    

Then    VAR(X  +  Y)  =  VAR(X)  +  VAR(Y).      
– Not  true  for  standard  devia:ons.    SD(X  +  Y)  ≠  SD(X)  +  SD(Y).    
– Not  true  for  dependent  random  variables.     13  
 The  decision  variables  
I    =  propor:on  of  por8olio  invested  in  IBM.        
P  =  propor:on  of  por8olio  invested  in  Pruden:al  
R  =  propor:on  of  por8olio  invested  in  Raytheon  
       
I  +  P  +  R  =  1  
I  ≥  0,  P  ≥  0,  R  ≥  0    

14  
 Returns  and  expected  returns  
W      =  return  of  the  en:re  por8olio  
       =    I  XI    +    P  XP    +    R  XR  
 
E[W]    =   I * E(XI) + P * E(XP) + R * E(XR)
= 65 I + 80 P + 50 R  

15  
 Standard  devia:on  and  variance  
SD(  P  XP  )          =    SD(XP)  ×  P  =  18  P  
VAR(  P  XP  )          =    VAR(XP)  ×  P2  =  182  P2  
 
VAR(W)      =  Variance  of  the  en:re  por8olio  
           =    VAR(XI)  ×  I2    +    VAR(XP)  ×  P2  +  VAR(XR)  ×  R2        

VAR(W)    =  225 I2      +    324  P2    +    100  R2  

SD(W)      =  VAR(W)1/2.     16  
 The  por8olio  op:miza:on  model  
min      VAR(W)  =            225 I2      +    324  P2    +    100  R2  
s.t.                E(W)      =    65  I          +        80  P        +        50    R        ≥    65  
                         I          +                  P          +                    R        =      1  
                           I    ≥  0,                P  ≥  0,                  R  ≥  0          

“65”  is  the  target  value.      

We  would  op:mize  for  mul:ple  target  values.  
17  
  
 
Por8olio  op:miza:on  3:    Analysis  
 

18  
 Risk    as  a  func:on  of   Expected  return  as  a  
expected  return   func:on  of  risk  
20   80  
stand  dev.  of  por8olio  

Risk  is  a  convex  

Op:mal  5-­‐year  return    

18  
func:on  of  return   75  
16  
14   70  
12   65  
10   Return  is  a  concave  
60  
8   func:on  of  risk  
6   55  
6   8   10   12   14   16   18  
55   60   65   70   75   80  
stand  dev.  of  por8olio  
Op:mal  5-­‐year  return    
 Risk    as  a  func:on  of   Op:mal  por8olio  as  
expected  return   func:on  of  exp.  return  
20   1.00  
stand  dev.  of  por8olio  

18  
0.80  
16   Ray  
14   0.60  
Prud  
12   0.40  
10   IBM  
0.20  
8  
6   0.00  
55   60   65   70   75   80   55  
1        62  0        63  
5        74  
0          75  5          86  0  

Op:mal  5-­‐year  return     Op:mal  expected  return  

20  
 The  SR  Report   The  reduced  cost  is  called  a  
  Final   Reduced   reduced  gradient  in  a  
Name   Value   Gradient   nonlinear  program.  
IBM   0.320   0  
Pruden:al   0.340   0  
Raytheon   0.340   0   The  shadow  price  is  called  a  
Lagrange  mul:plier  in  a  
nonlinear  program.  
  Final   Lagrange  
Name   Value   Mul:plier  
These  are  deriva:ves  (slopes).  
     100%  invested   1.00   -­‐185.80  
They  are  most  accurate  for  
     return  >=    R   65.00   5.08   VERY  small  changes  in  the  R21  HS.    
  
 
Por8olio  op:miza:on  4:      
Correlated  returns  
 

22  
 30  simula:ons  of  5  years  
Uncorrelated  returns  
130.00  
Pruden:al  returns  
120.00  
110.00  
100.00  
90.00  
80.00  
70.00  
60.00  
50.00  
40.00  
30.00   50.00   70.00   90.00   110.00  
IBM  returns   23  
 30  simula:ons  of  5  years  
Correlated  returns  
120.0  
110.0  
Pruden:al  returns  

100.0  
90.0  
80.0  
70.0  
60.0  
50.0  
40.0  
30.0   40.0   50.0   60.0   70.0   80.0   90.0   100.0   110.0  

IBM  returns   24  
What  happens  if  RVs  are  not  independent?  
• The  updated  model  is  the  same  as  before  except  that  the  
formula  for  the  VAR(W)  is  modified.  

IBM Pruden:al Raytheon

IBM 225 150 -­‐75
Pruden:al 150 324 60
Raytheon -­‐75 60 100
Covariance  Matrix   25  
 Var(W)  if  the  RVs  are  not  independent.  
VAR(W) = ∑ ∑ COV(i, j)× i × j
! i∈{I ,P ,R} j∈{I ,P ,R}

=    225  I2  +  324  P2  +  100  R2      +    

   +      (2  ×  150  ×  I  ×  P)  +  (2  ×  -­‐75  ×  I  ×  R)    +  (2  ×  60  ×  P  ×  R)        

IBM Pruden:al Raytheon

IBM 225 150 -­‐75
Pruden:al 150 324 60
Raytheon -­‐75 60 100
Covariance  Matrix   26  
 The  por8olio  op:miza:on  model  
min      VAR(W)  =            225  I2  +  324  P2  +  100  R2      +    
                                     +      (2  ×  150  ×  I  ×  P)  +  (2  ×  -­‐75  ×  I  ×  R)    +  (2  ×  60  ×  P  ×  R)  
s.t.                E(W)      =    65  I          +        80  P        +        50    R        ≥    Target  
                         I          +                  P          +                    R        =      1  
                           I    ≥  0,                P  ≥  0,                  R  ≥  0          

27  
 Risk  vs  Return  
(correlated  returns)  
stand  dev.  of  por8olio  

18  
16  
14  
12  
10  
8  
6  
55   60   65   70   75   80  

5-­‐year  return  of  por8olio  

28  
 Risk  vs  Return  
Independent  vs  correlated  returns  
stand  dev.  of  por8olio  

18  
16   To  achieve  the  
14   same  return  
12   The  tradeoff  
curve  with  
with  posi:vely  
10  
uncorrelated   correlated  
8  
returns.   variables,  the  
6  
55   60   65   70   75   80   risk  increases.  

5-­‐year  return  of  por8olio  

29  
  
 
Por8olio  op:miza:on  5:      
A  common  error  in  es:ma:ng  “returns”  

30  
 On  es:ma:ng  returns  
We  don’t  know  the  expected  returns  or  the  covariance  
matrix.      We  es:mate  them  from  data.  
Five Year Expected Standard Dev. of Return
Company Return (%) (%) The  es:mate  of  expected  
IBM 65 15 return  for  each  stock  is  
Prudential 80 18
Raytheon 50 10 unbiased.  

IBM Pruden*al Raytheon It  is  equally  likely  to  be  too  

IBM 225 150 675 high  or  too  low.    
Pruden*al 150 324 60
Raytheon 675 60 100
31  
 The  expected  return  of  the  best  
performing  stock  is  very  biased.  
Suppose  we  select  the  stock  with  the  best  return.    

Our  es:mate  of  this  stock  is  VERY  biased.  

The  expected  return  in  reality  is  much  lower  than  our  
es:mate.  

32  
 Simula:on  of  the  stock  market  
Suppose  we  simulated  returns  from  the  stock  market  
• We  can  toss  a  coin  12  :mes  to  simulate  1  year.      
• Heads  (tails)  on  toss  j:      
– our  stock  has  a  beder  (worse)  return  than  the  S&P  500  in  
month  j.  
• Keep  track  of  number  of  heads  and  tails.  

For  any  given  simulated  stock,  the  expected  number  of  months  
it  outperforms  the  stock  market  is  6.  
33  
 We  simulated  500  stocks  for  one  year  
120   The  op:mal  por8olio  will  
Number  of  stocks  

100   select  from  among  the  

beder  performing  stocks,  
80  
and  will  overes:mate  the  
60   expected  return.    
40  
20   best  performing  
0   stocks  
0   1   2   3   4   5   6   7   8   9   10   11   12  

Number  of  months  in  which  a  simulated  stock  

beats  the  average  return  on  the  S&P  500.     34  
 Past  performance  
• Conclusion:    if  one  selects  stocks  (or  mutual  funds)  based  on  
past  performance,  one  may  be  selec:ng  stocks  that  usually  
perform  well,  or  choosing  stocks  that  were  “lucky  in  the  
past.”  

• It  is  an  issue  that  arises  in  por8olio  op:miza:on.  

• Dealing  with  this  issue  is  beyond  the  scope  of  this  course.  

35  
 Final  comments  on  por8olio  op:miza:on  
• Varia:ons  of  this  type  of  model  used  worldwide.  

• Special  case  of  CAPM  (Capital  Asset  Pricing  Model).  

• Important  example  of  nonlinear  programming  

36  
  
 
Convex  sets  and  convex  func:ons  

37  
 Convex Sets
A set S is convex if for every p1, p2 ∈ S, the line
segment from p1 to p2 is also in the set;
y
3 If p1, p2 ∈ S, then so is (1 - λ)p1 + λp2 for λ ∈ [0,1].

 “λ  =  .5”  induces  the  midpoint.  

2
p1 p1 + p2
.5p1 + .5p2 =
1 ! 2
p2

1 2 3 4 x
38
 Convex  sets  

Non-­‐convex  sets   39  
 Convex  func:ons  
Suppose  f  is  defined  on  domain  D.  
A  func:on  f  is  convex  if  for  all  x,  y  ∈  D,  and  all  λ  ∈  [0,1]  
 
f ( λ x + (1 − λ )y ) ≤ λ f (x ) + (1 − λ )f (y )
   

A  func:on  f  is  strictly  convex  if  for  all  x,  y  ∈  D,  and  all  
λ  s.t.  0  <  λ  <  1  

f ( λ x + (1 − λ )y ) < λ f (x ) + (1 − λ )f (y )
f(x) = x2 f(x) = x3 for x ≥ 0 f(x) = |x|
Strictly  convex  func:ons     Convex    

Step Function f(x)  =  x.5   whatever

Non-­‐convex  func:ons   41  
 More  convex  func:ons  
• f(x)  =  1  
• f(x)  =  ax  +  b            for  all  a,  b  
• f(x)  =  x2  +  bx  +  c          for  all  b,  c  
• f(x)  =  |x|  
• f(x)  =  1/x                for  x  >  0  
• f(x)  =  −ln(x)              for  x  >  0  
• f(x)  =  ax              for  all  a  >  0   42  
 More  on  convexity  
Suppose  that  f(x)  is  convex  and  if  g(x)  is  convex.    Then  
• f(x)  +  g(x)  is  convex  
• max  {f(x),  g(x)}  is  convex  

• But  min{f(x),  g(x)}  is  possibly  non-­‐convex.  

43  
 f(x)  =  x2   g(x)  =  2x  
1   2  
1  
0  
0  
-­‐1   -­‐1   0   1  
-­‐1   0   1  
-­‐2  

f(x)  =  x2.      0  ≤  x  ≤  1   g(x)  =  2x.      0  ≤  x  ≤  1  

f(x)  +    g(x)   min{f(x),  g(x)}  

max{f(x),  g(x)}  
2   1  
2  
1   0  
1   -­‐1   0   1  
0   -­‐1  
-­‐1   0   1   0  
-­‐1   -­‐1   0   1   -­‐2  
Convex   Convex   Not  convex   44  
 Connec:on  with  differen:ability  
If  f(x)  is  differen:able,  and  if  the  second  deriva:ve  of  
f(x)  is  posi:ve  for  all  x,  then  f(x)  is  convex.  
25   f(x)      =    x2    
15   f’(x)    =    2x  
5   f”(x)    =    2  
-­‐5   0  
-­‐5   -­‐4   -­‐3   -­‐2   -­‐1   1   2   3   4   5  

45  
Level  sets  of  convex  func:ons  are  convex  sets  
Suppose  that  f(x)  is  convex.  
Level  set  of  f(x)  at  α  is:    {x  :  f(x)  ≤  α  }.  
Theorem.      If  f(x)  is  convex,  then  each  level  set  is  a  convex  set.    

y  
Example:      f(x,  y)  =  x2  +  9y2   1  

           S(9)  =  {(x,  y)  :  f(x,  y)  ≤  9}   x  

-­‐3   3
-­‐1  
46  
  
 
Local  and  global  op:mality  for  
minimiza:on  problems  

47  
Global  minimum  for  a  minimiza:on  problem  

Min            f(x)   Problem  

s.t.      x  ∈  S   P  

We  say  that  x’  is  a  global  minimum  for  problem  P  if    

1. x’  ∈  S  
2. f(x’)  ≤  f(y)  for  all  y  ∈  S.  

48  
 ε  balls  in  a  feasible  region  
Let  x’  be  a  point  in  S.  
Let  B(S,  x’,  ε)  be  the  set  of  
all  points  in  S  that  are  
ε  
within  a  distance  of  ε  
from  x’.        
B(S,  x’,  ε)   B(S,  x”,  ε)  
B(S,  x’,  ε)  is  an  ε-­‐ball  in  S  
centered  at  x'.  
Feasible  region    
S  
49  
 Local  minima    
Min            f(x)   Problem  
s.t.      x  ∈  S   P  

x’  ∈  S   We  say  that  x’  is  a  local  minimum  

ε  
for  problem  P  if    
B(x’,ε)  
1. x’  ∈  S  
2. f(x’)  ≤  f(y)  for  all  y  ∈  B(S,  x’,  ε)    
Feasible  region     for  some  ε  >  0    
S  
50  
 Illustra:on  of  global  and  local  minimum  
30   20   10  

f(A)  =  30.   Isocost  lines  

A  is  a  local  minimum   for  f(  )  
A  
f(B)  =  20.  
B  is  the  global  minimum   B  

The  feasible  region  

51  
 Nonlinear  programming  algorithms    
and  local  minima  
Nonlinear  programming   30   20   10  

algorithms  generally  stop  

Isocost  lines  
when  they  find  a  local  
for  c(  )  
minimum.     A  
Best  minimiza:on  
problems:      those  for  which   B  
a  local  minimum  is  
guaranteed  to  be  a  global  
minimum.   The  feasible  region  
52  
 Convex  minimiza:on  problems  
A  nonlinear  programming  minimiza:on  problem  is  called  a  
convex  minimiza:on  problem  if  the  objec:ve  func:on  is  
convex  and  the  feasible  region  is  a  convex  set.  
 
Theorem.      If  x  is  a  local  minimum  for  a  convex  minimiza9on  
problem,  then  x  is  also  a  global  minimum.  
 
That  is,  convex  minimiza:on  problems  are  “easy  to  solve.”  
53  
 Concave  maximiza:on  problems  
Recall:    A  func:on  f(  )  is  concave  if  –f(  )  is  convex.  
 
A  nonlinear  programming  maximiza:on  problem  is  called  a  
concave  maximiza:on  problem  if  the  objec:ve  func:on  f(  )  is  
concave  and  the  feasible  region  is  a  convex  set.  
 
Theorem.      If  x  is  a  local  maximum  for  a  concave  maximiza9on  
problem,  then  x  is  also  a  global  maximum.  
54  
  
 
Two  applica:ons  of  nonlinear  
programming  

55  
 When  prices  depend  on  supplies  
MIT  Corp  sells  up  to  1,000  red  widgets  for  a  profit  of  $3.50  per  
widget.      It  can  sell  more.    For  every  δ  red  addi:onal  widgets  sold,  
the  profit  (for  each  of  the  1,000  +  δ  red  widgets)    is  reduced  by    
.002  ×  δ.    How  many  should  be  sold,  assuming  no  other  constraints?    

The  amount  sold  is  at  least  1000.  

56  
 price   quan:ty  
(
Profit(δ )! = 3.50 − .002 δ × 1,000 + δ
! ) ( )
!!!!!!!!!!!!!!!!!!
! = −.002 δ 2
+ 1.5 δ + 3,500
d(Profit)
= −.004 δ + 1.5
! dδ

To  find  the  maximum,  try  se†ng  the  deriva:ve  to  0.  

-­‐.004  δ  +  1.5  =  0  ⇒  δ  =  375.  
Profit  =  $3,781.25  
57  
If  price  depends  on  the  quan:ty  sold,  
then  the  profit  is  a  nonlinear  func:on.  

58  
 Op:mal  Facility  Loca:on  
Locate  a  new  warehouse  to  minimize  total  travel  costs  to  four  sales  
centers.      Travel  cost  =  $1  per  mile.  
 
Sales  Center                              Code/Coordinates          Daily  Truck  Deliveries  
Amherst                A  (8,2)                  9  
Boston                B  (3,10)                  7  
Colby                C  (8,15)                  2  
Dartmouth              D  (14,13)                5  

Where  should  the  firm  locate  the  new  warehouse?  

 y
 The  loca:on  of  the  
four  sales  centers  
16 C
14
D
12
B
10
Where  should  P  be  
8 P=(x,y) located?  
6
4
2 A

2 4 6 8 10 12 14 16 x
Let P = (x , y) be the location of the warehouse.

( x − 8) + ( y − 2)
2 2
The distance from P to A = (8, 2) is   d(P, A) =
!

d(P,  B),  d(P,  C),  d(P,  D)  are  defined  similarly.  

The optimal solution is :

Min            [9  d(P,  A)]  +    [7  d(P,  B)]    
                   +  [2  d(P,  C)]  +    [5  d(P,  D)]   P* = ( 6.95 , 7.47 )
s.t.                P  =  (x,  y)           Cost = $142.97

61  
 y
 The  loca:on  of  the  
four  sales  centers  
16 C
14
D
12
10
B The optimal solution is :
Op:mal  loca:on  of  P  
8   P=(x,y) P* = ( 6.95 , 7.47 )
6 P*  
4 Cost = $142.97
2 A

2 4 6 8 10 12 14 16 x
 y Suppose   that  zoning  
 The  loca:on   of  the  laws  required  it  to  be  
within  
four  stales  
he  4c-­‐sided  
enters  region  below.    How  do  
16 C the  model  and  op:mal  solu:on  change?  
14
D
12 Min            [9  d(P,  A)]  +    [7  d(P,  B)]    
B                    +  [2  d(P,  C)]  +    [5  d(P,  D)]  
10
8 P=(x,y) s.t.                P  =  (x,  y)  
6 P*                              x  ≥  10  
4                            4  ≤  y  ≤  10  
A                            x  +  y  ≤  24  
2

2 4 6 8 10 12 14 16 18   20   x
 y Suppose   that  zoning   laws  required  it  to  be  
 The  loca:on  
Suppose   of  the  
that  zoning   laws  required  it  to  be  
within  
four  tsthe  
he  4c-­‐sided  
ales   enters  region  below.    How  do  
within   4-­‐sided   region  below.    How  do  
16 C the  model  and  op:mal  solu:on  change?  
the  model  and  op:mal  solu:on  change?  
14   D
12
B Optimal is :
10
8
P* = (10.0, 7.4)
P=(x,y)
6 P*   Cost = $154.22
4 Cost has
2 A increased by
$11.25.
2 4 6 8 10 12 14 16 x
The$constrained$location$problem
Before  solving  
Decision$variables
the  problem.  
P"="(x,"y) x y
0.000 0.000
The$four$ Distance$ Weights$ Weighted$
points from$P (costs) distance
A 8 2 8.246 9 74.216
B 3 10 10.440 7 73.082
C 8 15 17.000 2 34.000
D 14 13 19.105 5 95.525

Total$weighted$distance 276.823
Constraints
x">="10 0.000 >= 10
y">="4 0.000 >= 4
y"<="10 0.000 <= 10
x+y"<="24 0.000 <= 24 65  
The$constrained$location$problem
AVer  solving  
Decision$variables
the  problem.  
P"="(x,"y) x y
10.000 7.400
The$four$ Distance$ Weights$ Weighted$
points from$P (costs) distance
A 8 2 5.759 9 51.829
B 3 10 7.467 7 52.270
C 8 15 7.858 2 15.717
D 14 13 6.882 5 34.408

Total$weighted$distance 154.224
Constraints
x">="10 10.000 >= 10
y">="4 7.400 >= 4
y"<="10 7.400 <= 10
x+y"<="24 17.400 <= 24 66  
67  
  
 
2nd  Order  Cone  Programming:  
An  easy  convex  minimiza:on  problem  

68  
 Euclidean  norms  
Nota:on:      Suppose  that  y  =  y1,  y2,  …,  yk    
         y  is  a  vector  of  k  decision  variables.  
1/2
⎛ 2⎞
k
Then! y = ⎜ ∑ y i ⎟
2
⎝ i=1 ⎠
( ) .
!

We  refer  to          y        2    as  the  Euclidean  norm  of  vector  y.      

!
69  
 Second  order  cone  program  (SOCP)  

Linear  program   SOCP  

• Linear  objec:ve   • same  as  LP  except  that  it  also    
• Linear  inequali:es     includes  constraints  such  as:  
and  equali:es.   “Euclidean  norm  +    
                 linear  constraint  ≤  RHS”**  

e.g.,   y 2 + 3x1 − x5 ≤ 10
!
**    A  slightly  more  general  form  is  permided.  
70  
 Second  order  cone  program  (SOCP)  
• Lots  of  applica:ons  
• Special  case  of  convex  minimiza:on  (or  concave  
maximiza:on)  
• Almost  as  easy  to  solve  as  linear  programs  
• Lots  of  available  soVware  
– CPLEX  
– Gurobi  
71  
 Example  1:  por8olio  op:miza:on  for  
independent  random  variables    
max E(W) = 65 I + 80 P + 50 R
s.t.                      SD(W) ≤ 12
I + P + R = 1
I ≥ 0, P ≥ 0, R≥0

“12”  is  the  target  value.      

We  would  op:mize  for  mul:ple  target  values.   72  
 Ge†ng  it  into  the  right  form  

   SD(W) = ( 225 I2      +    324  P2    +    100  R2  ).5 ≤ 12

y1  =  15  I;          y2  =  18  P;        y3  =  10  R  

y ≤ 12
! 2

73  
 Example  2:    Simple  linear  regression    
100.0   Es:mate  y  as  a  linear  
func:on  of  x.  
80.0  
Choose    β0  and  β1  
60.0  
y   and  es:mate  y  as  
(x1,  y1)   follows:    for  all  j:  
40.0  

20.0   ŷ j = β 0 + β 1 x j
!
0.0   N
0.0   50.0   100.0   150.0   200.0   min      ∑
      (y j − ŷ j )2
x:      independent  variable   ! j =1 74  
 Ge†ng  it  into  the  right  form  
N
min      ∑
      (y j − ŷ j )2
! j =1

We  need  to  move  the  quadra:c  term  to  the  constraints.  

w j = (y j − ŷ j )!!!!!!!for!all!j.
!
w ≤T
! 2
Itera:vely  search  for  the  least  value  of  T.  
75  
 SOCP  solves  much  faster  
• If  you  have  a  convex  minimiza:on  problem  that  can  
be  reformulated  as  a  SOCP,  then  do  so.  
• You  will  be  glad  you  did.  

76  
  
 
Guidelines  for  solving  nonlinear  problems  

78  
 Guidelines  in  Solving    Nonlinear  Problems  
Guideline  1:  Unlike  linear  op:miza:on,  nonlinear  op:miza:on  
may  be  difficult  to  solve  even  with  today’s  computers.  

Guideline  2:    Algorithms  for  solving  nonlinear  op:miza:on  rely  on  

calculus.    They  are  only  guaranteed  to  find  a  locally  op:mal  
solu:on,  which  is  not  necessarily  a  globally  op:mal  solu:on.    
 Guidelines  in  Solving    Nonlinear  Problems  
Guideline  3:    Some  nonlinear  op:miza:on  problems  are  easy  to  
solve,  others  are  difficult.  The  difficulty  depends  on  the  model’s  
mathema:cal  structure.    The  easiest  to  solve  are  convex  
minimiza:on  problems  (and  concave  maximiza:on  problems).    
and  the  easiest  of  these  are  SOCPs  and  LPs.  

Guideline  4:    SoVware  for  solving  nonlinear  op:miza:on  models  

varies  with  the  degree  of  func:onality  and  with  the  price.  The  
beder  soVware  packages  solve  nonlinear  models  with  many  
variables  and/or  constraints.