Nonlinear Programming

A.K. Bardhan
Faculty of Management Studies
University of Delhi

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 1

 Linear Programming Model

Maximize c1 x1  c2 x2  .....  cn xn ASSUMPTIONS:

subject to
• Proportionality Assumption
a11 x1 + a12 x 2 + ... +a1n xn  b1 – Objective function
– Constraints
a 21 x1 + a 22 x 2 + ... +a 2n xn  b 2
• Additivity Assumption
– Objective function
am1 x1 + a m 2 x 2 + ... +amn xn  b m – Constraints

x1 , x2 , ..., xn  0

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 2

 What is a non-linear program?
• maximize 3 ex + xy + y3 - 3z + log z
Subject to x2 + y2 = 1
x + 4z  2
z 0

• A non-linear program is permitted to have non-linear

constraints or objectives.
• A linear program is a special case of non-linear
programming!

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 3

A U-shaped cost function
 Nonlinear Programs (NLP)

Let x   x1 , x2 , , xn 
Max f ( x)
gi ( x)  bi , i  1, 2, , m

Nonlinear objective function f(x) and/or Nonlinear constraints

gi(x).

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 5

 NLP
• A general nonlinear programming problem (NLP) can be
expressed as follows:

Find the values of decision variables x1, x2,…xn that

max (or min) z = f(x1, x2,…,xn)

s.t. g1(x1, x2,…,xn) (≤, =, or ≥)b1
s.t. g2(x1, x2,…,xn) (≤, =, or ≥)b2
.
.
.
gm(x1, x2,…,xn) (≤, =, or ≥)bm

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 6

 NLP
• As in linear programming f(x1, x2,…,xn) is the NLP’s
objective function, and g1(x1, x2,…,xn) (≤, =, or
≥)b1,…gm(x1, x2,…,xn) (≤, =, or ≥)bm are the NLP’s
constraints.
• An NLP with no constraints is an unconstrained NLP.
• The feasible region for NLP above is the set of points (x1,
x2,…,xn) that satisfy the m constraints in the NLP. A point in
the feasible region is a feasible point, and a point that is not
in the feasible region is an infeasible point.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 7

 Unconstrained nonlinear programming models

• Unconstrained optimization over linear objective function is

always unbounded (except in the trivial case where is
objective is constant)
• Unconstrained nonlinear programs can have finite optimal
solution

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 8

 Unconstrained Facility Location
This is the warehouse location problem with a single
warehouse that can be located anywhere in the plane.
Distances are “Euclidean.”
y

16 C (2)
Loc. Dem.
14
A: (8,2) 19 D (5)
12
(7)
B: (3,10) 7 10
B
C: (8,15) 2 8
P ?
6
D: (14,13) 5
4
P: ? 2 A (19)
0 x
0 2 4 6 8 10 12 14 16

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 9

 An NLP
• Costs proportional to distance;
known daily demands

d(P,A) = ( x  8)2  ( y  2)2

…

d(P,D) = ( x  14)2  ( y  13)2

minimize 19 d(P,A) + … + 5 d(P,D)

subject to: P is unconstrained

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 10

 Here are the objective values for 55 different
locations.

350

300 x=0
Objective value

250 x=2

200 x=4
x=6
150
x=8
100 x = 10
50 x = 12

0
values
for y

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 11

 Facility Location. What happens if P must be within a
specified region?
y

16 C (2)
14
D (5)
12
(7)
10
B
8
P ?
6

2 A (19)
0 x
0 2 4 6 8 10 12 14 16

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 12

 The model

Minimize 19 ( x  8)2  ( y  2)2 + …+

5 ( x  14)  ( y  13)
2 2

Subject to x  7
5  y  11
x + y  24

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 13

 Some comments on non-linear models

• The fact that non-linear models can model so much is

perhaps a bad sign
– How can we solve non-linear programs if we have trouble
with integer programs?
– Recall, in solving integer programs we use techniques that
rely on the integrality.

• Fact: some non-linear models can be solved, and

some are WAY too difficult to solve.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 14

 Exercise

• Buy a machine and keep it for t years, and then sell

it. (0  t  10)
– all values are measured in $ million
– Cost of machine= 1.5
– Revenue = 4(1 - .75t)
– Salvage value = 1/(1 + t)

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 15

 Machine values

4.5
4
Millions of dollars

3.5
3 revenue
2.5
salvage
2
1.5 total
1
0.5
0
1

9
0.2

1.8
2.6
3.4
4.2

5.8
6.6
7.4
8.2

9.8
Time

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 16

 How long should we keep the machine?

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 17

 Non-linearities Because of Time
• Discount rates
• decreasing value of equipment over time
– wear and tear, improvements in technology
• Tax implications (Depreciation)
• Salvage value

Secondary focus of the previous model(s): Finding the right

model can be subtle

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 18

 Non-linearities in Pricing
• The price of an item may depend on the number sold
– quantity discounts for a small seller
– price elasticity for monopolist
• Complex interactions because of substitutions:
– Lowering the price of GM automobiles will decrease the demand for
the competitors

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 19

 Example
• If a company charges a price p for a product, then it can
sell 3e-p thousand units of the product. Then, f(p) = 3000 p
e-p is the company’s revenue if it charges a price p.

1. For what values of p is f(p) decreasing? For what values of

p is f(p) increasing?
2. Suppose the current price is Rs. 4 and the company
increases the price by Re. 0.50. By approximately how
much would the company’s revenue change?

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 20

 Example
• The demand f(p, a) = 30,000 p-2 a(1/6) for a product depends
on p = product price (in rupees) and a = rupees spent
advertising the product. Is demand an increasing or
decreasing function of price? Is demand an increasing or
decreasing function of advertising expenditure?
• If p = 10 and a = 1,000,000, then by how much
(approximately) will a Re. 1, cut in price will increase
demand?

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 21

 Non-linearities because of “penalties”

• Consider any linear equality constraint:

e.g., 3x1 + 5x2 + 4x3 = 17

Suppose it is a “soft” constraint and we permit

solutions violating it. We can then write:

3x1 + 5x2 + 4x3 - y = 17

And we may include a term of –10y2 in the objective

function.

– This adds flexibility to the solution by discourages

violation of our “goals”

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 22

 Portfolio Optimization
• Portfolio optimization or Asset allocation are often
formulated as NLPs
• The key concept is that risk can be modeled using non-
linear equations
• This is one of the most famous applications of non-linear
programming

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 23

 Risk vs. Return
• In finance, one trades of risk and return. For a given
rate of return, one wants to minimize risk.

• For a given rate of risk, one wants to maximize

return.

• Return is modeled as expected value. Risk is

modeled as variance (or standard deviation.)

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 24

 Expectations Add

• Suppose that X and Y are random variables

• E(X + Y) = E(X) + E(Y)

• Interpretation:
– Suppose that the expected return in one year for Stock 1
is 9%.
– Suppose that the expected return in one year for Stock
2 is 10%
– If you put Rs. 100 in Stock 1, and Rs. 200 in Stock 2,
your expected return is Rs. 9 + Rs. 20 = Rs. 29.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 25

 Rp = R1x1 + R2x2 + … + Rnxn

Ri : Random return earned during a year on one Rupee

invested in investment i.
x1 : Fraction of money invested in investment i.
p : Portfolio

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 26

 Variances do not add (at least not simply)

• Suppose that X and Y are random variables

• Var(aX + bY) =
a2 Var(X) + b2 Var(Y) + 2ab Cov(X, Y)

• Example. The risk of investing in “umbrellas” and

“sunglasses” is less than the risk of either investment
by itself.

• In general:
 Var ( X i )   i  j 2Cov( X i , X j )
n
Var(X1 + X2 + …+ Xn) = i 1

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 27

 Reducing risk
• Diversification is a method of reducing risk, even when
investments are positively correlated (which they often are).

• If only two investments are made, then the risk reduction

depends on the covariance.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 28

 Portfolio Selection (cont’d)

• Two Methods are commonly used:

– Min Risk
s.t. Expected Return  Bound

– Max Expected Return - q (Risk)

where q reflects the tradeoff between return and risk.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 29

 Portfolio Selection Example

• There are 3 candidate assets for out portfolio, X, Y and Z.

The expected returns are 30%, 20% and 8% respectively (if
possible we would like at least a 12% return). Suppose the
covariance matrix is:

X Y Z
• What are the variables? X 3 1 0.5
Y 1 2 0.4
Z  0.5  0.4 1
Let X,Y,Z be percentage of portfolio of each asset.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 30

 Portfolio Selection Example

Min 3 X 2  2Y 2  Z 2  2 XY  XZ  0.8YZ

st 1.3 X  1.2Y  1.08Z  1.12

X Y  Z 1
X  0, Y  0, Z  0

Max
1.3 X  1.2Y  1.08Z
st  q (3 X 2  2Y 2  Z 2  2 XY  XZ  0.8YZ )

X Y  Z 1
X  0, Y  0, Z  0
Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 31
 More on Portfolio Selection

• There can be institutional constraints as well, especially

for mutual funds.

• No more than 15% in the energy sector

• Between 20% to 25% high growth
• At most 3% in any one firm
• etc.
• We end up with a large non-linear program.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 32

 Regression
Estimate for Midterm = x * HW3 + y
Find the best linear fit for
Midterm = x * HW3 + y + residual estimating the midterm grade
from the homework grades
x y
0.6 40

HW3 Estimate Midterm 1 Residual Residual squared

91 94.6 89 -5.6 31.36
80 88 97.5 9.5 90.25
61 76.6 58.5 -18.1 327.61
88 92.8 92 -0.8 0.64
86 91.6 93.5 1.9 3.61
56 73.6 87 13.4 179.56
60 76 99 23 529
87 92.2 85 -7.2 51.84
50 70 67 -3 9

sum of squares 1222.87

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 33
 Writing regression as an NLP

• Minimize Sj (rj)2

• subject to Minimize Sj (rj)2

r1 = (91x + y) – 89
r2 = (80x + y) – 97.5
subject to
r3 = (61x + y) – 58.5 r j = H j x + y – Mj
… for each j
r9 = (50x + y) – 67

In an optimization
framework, one can
constrain coefficients.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 34

 Midterm 2 vs Homeworks (2002)

100

90

80
Midterm Grade

70

60

50
r2 =.082
40

30
30 40 50 60 70 80 90 100
Avg of last 3 homeworks

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 35

 Midterm 1 vs. homework 3 (2001)

100

90
midterm grades

80

70

60

r2 =.29
50

40
40 50 60 70 80 90 100
homework 3 grades

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 36

 An application of regression to finance

• A famous application in Finance of determining the best linear fit is

determining the b of a stock.

• CAPM assumes that the return of a stock s in a given time period is

rs = a + b rm + e,
rs = return on stock s in the time period
rm = return on market in the time period
b = a 1% increase in stock market will lead to a b%
increase in the return on s (on average)

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 37

 What is beta of a stock?
• Beta measures a stock's volatility, the degree to which its price
fluctuates in relation to the overall market. In other words, it gives a
sense of the stock's market risk compared to the greater market.
Beta is used also to compare a stock's market risk to that of other
stocks. Investment analysts use the Greek letter 'ß‘
• Essentially, beta expresses the fundamental tradeoff between
minimizing risk and maximizing return. Let's give an
illustration. Say a company has a beta of 2. This means it is two
times as volatile as the overall market. Let's say we expect the
market to provide a return of 10% on an investment. We would
expect the company to return 20%. On the other hand, if the market
were to decline and provide a return of -6%, investors in that
company could expect a return of -12% (a loss of 12%). If a stock
had a beta of 0.5, we would expect it to be half as volatile as the
market: a market return of 10% would mean a 5% gain for the
company.

Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 38

 Regression, and estimating b

Return on Stock A vs. Market Return

80.00%

60.00%

40.00%
Stock

20.00%

0.00%
-40.00% -20.00% 0.00% 20.00% 40.00% 60.00% 80.00%
-20.00% What is the best linear fit for
this data? What does one mean
-40.00%
by best?
-60.00%
Market 39
Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi
 Regression, and estimating b

Return on Stock A vs. Market Return

80.00%

60.00%

40.00%
Stock

20.00%

0.00%
-40.00% -20.00% 0.00% 20.00% 40.00% 60.00% 80.00%
The value b is the slope of the
-20.00% Market

-40.00% regression line. Here it is around

.6 (lower expected gain than the
-60.00% market, and lower risk.)
Dr. A.K. Bardhan, Faculty of Management Studies, University of Delhi 40