FE501 – 1005

Syllabus

Topics:

For each in x where x belongs to:

• Linear Programming (LP)
• Integer Linear Programming (ILP)
• Nonlinear Programming (NLP)
• Dynamic Programming (DP)

For each of the x:

1. formulation of x models
2. solution of x models
3. applications in finance and economics

Outline (week by week)

1. Introduction

2. LP

   1. Formulation
   2. Graphical Solution Procedure
   3. Simplex Method
   4. Exel-Solver
   5. GAMS Optimization Package

3. LP: Applications to Finance and Economics

4. Duality and Sensitivity

5. ILP

   1. Formulation
   2. Branch-and Bound method

6. ILP: Applications to Finance and Economics

7. Nonlinear Optimization

   1. Formulation
   2. Unconstrained and constrained NLP models
   3. Solution methods
   4. KKT conditions

8. Continue 7

9. Quadratic Programming and Portfolio Optimization

10. Thechniques for Calculating the Efficient Frontier

11. DP

    1. Formulation
    2. Solution

12. DP: Applications to Finance and Economics

13. Summary

Introduction

Typiclly optimization problems have the goal of allocating limited resources to alternative activitites in order to maximize the total benifit obtained from those activities.

Optimization is now being used as an effective management and decision-support tool.

Classes of optimization problems:

• Linear
• Quadratic
• Integer
• Dynamic
• Stochastic
• Conic
• Nonlinear

What is optimization?

Optimization is the process of finding the best way of making decisions that satisfy a set of constraints.

What is linear programming?

Linear Programming (LP) is also called linear optimization.

• minimize or maximize a linear objective
• subject to linear equalities and inequalities

Example:

A feasible solution satisfies all of the constraints. x = 1, y = 1 is feasible [1] ; x = 1, y = 3 is infeasible.

An optimal solution is the best feasible solution. The optimal solution for above problem is $x=4.8,y=0$$x=4.8, y=0$

Google Sheets Gile

What is decision variables? objective functions ?constraints ?

Example Problem Soling

Turing machine and NP-Hard (just hard…)

Knapsack Probelm

Q: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Target: Maximize the Total Utility

Possible solutions are called feasible solutions

To solve such a problem If the number of possible solutions are small then we can use:

• Brute-forch approach
• Complete enumeration
• Exhaustive enumeration

Problem Definition:

The model above (3) called integer linear model.

Generally A standard linear program will be:

Using Excel

Using Optimator

Fund allocation problem

Using optimator

Using Excel

Link to Excel File

Possible results from Excel Solver can be:

• Find the solution
• Multiple Optimal
• Optimal $-\mathrm{\infty }$$-\infin$ or $+\mathrm{\infty }$$+\infin$ (unbounded)
• No feasible solution.

Graphical method

"The Objective Cell values do not converge" means there is no limit to the objective function value.

1
import matplotlib.pyplot as plt
2
import numpy as np
3
x = np.linspace(-15,50)
4
y1 = 2+x
5
fig = plt.figure(dpi=300)
6
ax = fig.add_subplot(111)
7
ax.grid(True, which='both')
8
ax.axhline(y=0, color='k')
9
ax.axvline(x=0, color='k')
10
ax.plot(x,y1,label='y=x+2') # y = x+2
11
ax.plot(np.zeros(50),x,label='x=0') # x = 0
12
ax.plot(x,np.zeros(50),label='y=0') # y = 0
13
ax.plot(x,-x,label='y=-x+z (z=0)')
14
ax.plot(x,-x+10,label='y=-x+z (z=10)')
15
ax.plot(x,-x+20,label='y=-x+z (z=20)')
16
plt.legend()
17
plt.show()

Result: to maximize $x+y$$x+y$ either x or y can be infinite . So this problem dose not have a feasible solution.

MSR Marketing example

Decision variables :

• $x_T$$x_T$ : # of ad on TV
• $x_R$$x_R$ : # of ad on Radio
• $x_M$$x_M$ : # of ad on Mail
• $x_N$$x_N$ : # of ad on Newspaper

Objective function

*Minimize $z=500x_T+200x_R+250x_M+125x_N$$z=500x_T + 200x_R + 250x_M + 125x_N$

Constraints

1. $50x_T+25x_R+20x_M+15x_N\ge 1500$$50x_T + 25x_R + 20x_M + 15x_N \ge 1500$
2. $x_T\le 20$$x_T \le20$
3. $x_R\le 15$$x_R \le 15$
4. $x_M\le 10$$x_M \le 10$
5. $x_N\le 15$$x_N \le 15$
6. $x_T,x_R,x_M,x_N\ge 0$$x_T ,x_R, x_M, x_N \ge0$

Excel File

Scipy for Calculating the LineProg

​x
1
ask = input("Enter coefficients of the linear objective function (separate with space), enter 'q' to stop.")
2

3
objective_function_coefficients_str = ask.strip().split(" ")
4
objective_function_coefficients = [float(x) for x in objective_function_coefficients_str]
5
print(f"Objective Function Coefficients: {objective_function_coefficients}")
6

7
while True:
8
    optimization_type = input("Select Optimization Type: 1.Minimize, 2.Maximize ")
9
    if optimization_type in ['1', '2']:
10
        break
11

12
if optimization_type == '2':
13
    # This is a maximization problem and we need to invert it
14
    objective_function_coefficients = [-1 * x for x in objective_function_coefficients]
15

16
constraints_lhs_ineq = []
17
constraints_rhs_ineq = []
18

19
constraints_lhs_eq = []
20
constraints_rhs_eq = []
21

22
while True:
23

24
    lhs = input("Input constraints left hand side coefficients.")
25
    operator = input("Input operator for the equation.('le','ge','eq')")
26
    rhs = input("Input constraints right hand side coefficient.")
27

28
    lhs_str = lhs.strip().split(" ")
29
    lhs = [float(x) for x in lhs_str]
30

31
    rhs_str = rhs.strip()
32
    rhs = float(rhs_str)
33

34
    if operator == 'le':
35
        constraints_lhs_ineq.append(lhs)
36
        constraints_rhs_ineq.append(rhs)
37
    elif operator == 'ge':
38
        lhs = [-1 * x for x in lhs]
39
        rhs = -1 * rhs
40
        constraints_lhs_ineq.append(lhs)
41
        constraints_rhs_ineq.append(rhs)
42
    elif operator == 'eq':
43
        constraints_lhs_eq.append(lhs)
44
        constraints_rhs_eq.append(rhs)
45

46
    ask = input("Continue for other constraints? Y/N (Y)")
47

48
    if ask in ['N', 'n', 'q']:
49
        break
50

51
print("objective_function_coefficients", objective_function_coefficients)
52
print("constraints_lhs_ineq", constraints_lhs_ineq)
53
print("constraints_rhs_ineq", constraints_rhs_ineq)
54
print("constraints_lhs_eq", constraints_lhs_eq)
55
print("constraints_rhs_eq", constraints_rhs_eq)
56

57
for each in [constraints_lhs_eq, constraints_rhs_eq]:
58
    if each == []:
59
        each = None
60
        
61
opt = linprog(c=objective_function_coefficients, A_ub=constraints_lhs_ineq, b_ub=constraints_rhs_ineq, A_eq=constraints_lhs_eq, b_eq=constraints_rhs_eq)
62
print(opt)

Extra

1. MIT 18.310
2. MIT 15.053
3. 3
4. 4
5. https://web.mit.edu/15.053/www/