LP and Non-LP Issues

Linear Programming

• Mathematical method used for optimization problems
• Main applications are to maximize profits and minimize costs
• Objective function is linear when:
• Optimum always attained at constraint boundaries
• A local optimum is also global optinum
• Other applications
• operational research - solve multi-commodity flow issues and network flow
• strategic games - chess, manufacturing, resource conservation, transportation systems for buses and trains, and military budgeting
• microeconomics
• Assumptions:
• all variables have non-negative values
• A negative value will be written as a function of two non negative values
• ie. If $x = -5$, then we let $x_1 = 0$, $x_2=5$ and assign $x = x_1 - x_2$
• Advantages:
• Works with inequalities with non negative coefficients. As long as the inequalities are changed into standard form
• The simplex algorithm can determine if there is no solution to the problem (if pivot can't be made)
• Algorithm is easy to program in a computer
• Disadvantages:
• The algorithm becomes inefficient if too many variables are used. It may require an exponential number of steps.
• Strict inequalities might not work in LP
• Example: same example as earlier, using x as the first pivot

Non Linear LP

• Objective function is non linear when:
• Optimum may be interior as well as at boundaries of constraint 
• A local optimum is not necessarily the global optinum
• Nonlinearity came from
• multiplication of variables: economies of scale, transaction costs
• quadratic terms: variances, interest rates mean-variance optimization
• nonlinear functions: quantiles in common risk measures
• Approach to nonlinear optimization: iterative method
• Basic Numerical methods: Solving for non linear functions
• Other methods: 
• Steepest Descent Method
• Newton's Method 
• Quasi-Newton Method
• Lagrange multipliers 
• Conjugate Gradient Method
• Penalty Function Method
• In general, optimization problems are unsolvable.
• "It's the user's responsibility to choose an algorithm that is appropriate for the specific applications

Take-aways

• revised way of pivoting starting with $x$ in the simplex method
• What if the constraints are less than the unknown? Will there be a difference in the simplex method?
• Always check on the assumptions coz it might not gonna work because of wrong constraints
• the answer might not be exactly the solution to the problem at hand. We might be creating more problems than the solution of the problems
• Portfolio optimization technique - "robustness"
• The methods are just tools for the user to use. The question is, is the user using the right tools for the problem at hand?

Resources: Class groups ppt.