Non-linear programming Non-smooth problems
CIS 418
Simon Business School CIS-418 Ricky Roet-Green
Reminder: Linear Programming
Both objective and constraints are linear functions of decision variables. x2
4
3
2
1
0
Simon Business School
Optimal solution
Feasible Area
x1
CIS-418 Ricky Roet-Green
12345
2
Non-linear optimization
objective function level curve
optimal solution
objective function level curve
optimal solution
Feasible Region
Feasible Region
linear objective, nonlinear constraints
nonlinear objective, linear constraints
objective function level curve
optimal solution
objective function level curves
optimal solution
Feasible Region
Feasible Region
nonlinear objective, linear constraints
nonlinear objective, nonlinear constraints
Simon Business School
CIS-418
Ricky Roet-Green
3
Solution Strategy: Improving Direction
X2
C B
D
E
objective function level curves
Feasible Region
A
(the starting point)
X1
One of the solution strategies for handling non-linear problems is to move as far as
possible in improving direction – and find a global solution
Simon Business School CIS-418 Ricky Roet-Green
4
Non-Smooth Problems
X2
Local optimal solution
C
F
B
Local and global optimal solution
Feasible Region
A
D
E
G
X1
• With a non-smooth problem, the algorithm may not be able to find the global optimum.
• The starting point influences the local optimal solution obtained.
Simon Business School CIS-418 Ricky Roet-Green
5
Example for a non-smooth problem: Snoey Software
Product Cost Data
High-Speed
Large-Scale
Educational
Product Completion Cost
$ 150,000
$ 100,000
$-
Variable Cost
$ 36
$ 20
$ 10
Market Data
Marketing Costs
Willingness to pay for software version
Market Segment
Segment Size
High-Speed
Large-Scale
Educational
Large Companies
6,000
$ 100,000
$ 2,500
$ 1,000
$ 150
Small Companies
24,000
$ 100,000
$ 500
$ 250
$ 75
Consultants
12,000
$ 200,000
$ 750
$ 500
$ 100
Laboratories
1,200
$ 200,000
$ 1,000
$ 300
$ 125
Students
400,000
$ 300,000
$ 75
$ 40
$ 25
Simon Business School CIS-418 Ricky Roet-Green
6
Formulate the problem
• Objective:
– Maximize profit
• Decisions:
– How to price each version
• Constraints:
• Calculations:
– Revenue
– Marketing costs
– Production costs
– Variable costs
Go to the excel file and calculate the optimal solution using solver
Simon Business School CIS-418 Ricky Roet-Green
7
The computer algorithm can run into a Local Optimum
Data Table Analysis Varying Two Prices (assumes High Speed Version price $2500)
Educational Version Price
$ 5,748,000
$ 25
$ 75
$ 100
$ 125
$ 150
Large- Scale Version Price
$ 40
7,864,000 7,864,000 7,864,000 7,864,000 7,864,000
$ 250
9,518,000
9,236,000 9,236,000 9,236,000 9,236,000
$ 300
10,418,000
5,978,000
4,548,000
4,776,000 4,776,000
$ 500
8,438,000
4,598,000
8,148,000
8,178,000 8,240,000
$ 1,000
5,748,000
2,208,000
1,228,000
528,000
14,534,000
Maximum
14,534,000
Simon Business School
CIS-418
Ricky Roet-Green
8
Moving anywhere
in the immediate vicinity of this point
does not
improve profit
The computer algorithm can run into a Local Optimum
Data Table Analysis Varying Two Prices (assumes High Speed Version price $2500)
Educational Version Price
$ 5,748,000
$ 25
$ 75
$ 100
$ 125
$ 150
Large- Scale Version Price
$ 40
7,864,000 7,864,000 7,864,000 7,864,000 7,864,000
$ 250
9,518,000
9,236,000 9,236,000 9,236,000 9,236,000
$ 300
10,418,000
5,978,000
4,548,000
4,776,000 4,776,000
$ 500
8,438,000
4,598,000
8,148,000
8,178,000 8,240,000
$ 1,000
5,748,000
2,208,000
1,228,000
528,000
14,534,000
Maximum
14,534,000
Simon Business School
CIS-418
Ricky Roet-Green
9
Moving anywhere
in the immediate vicinity of this point
does not
improve profit
The computer algorithm can run into a Local Optimum
Data Table Analysis Varying Two Prices (assumes High Speed Version price $2500)
Educational Version Price
$ 5,748,000
$ 25
$ 75
$ 100
$ 125
$ 150
Large- Scale Version Price
$ 40
7,864,000 7,864,000 7,864,000 7,864,000 7,864,000
$ 250
9,518,000
9,236,000 9,236,000 9,236,000 9,236,000
$ 300
10,418,000
5,978,000
4,548,000
4,776,000 4,776,000
$ 500
8,438,000
4,598,000
8,148,000
8,178,000 8,240,000
$ 1,000
5,748,000
2,208,000
1,228,000
528,000
14,534,000
Maximum
14,534,000
Simon Business School
CIS-418
Ricky Roet-Green
10
Moving anywhere
in the immediate vicinity of this point
does not
improve profit
The computer algorithm can run into a Local Optimum
Data Table Analysis Varying Two Prices (assumes High Speed Version price $2500)
Educational Version Price
$ 5,748,000
$ 25
$ 75
$ 100
$ 125
$ 150
Large- Scale Version Price
$ 40
7,864,000 7,864,000 7,864,000 7,864,000 7,864,000
$ 250
9,518,000
9,236,000 9,236,000 9,236,000 9,236,000
$ 300
10,418,000
5,978,000
4,548,000
4,776,000 4,776,000
$ 500
8,438,000
4,598,000
8,148,000
8,178,000 8,240,000
$ 1,000
5,748,000
2,208,000
1,228,000
528,000
14,534,000
Maximum
14,534,000
Simon Business School CIS-418 Ricky Roet-Green
11
This is the global maximum