Course Outline
Optimization
OPTIMIZATION
Elements of convex optimization
- Convex sets and functions in Rn, global and constrained optimality. Algorithms for unconstrained convex optimisation: gradient descent, Newton’s algorithm. Introduction to convex optimisation on a convex set, the barrier method. Examples. [3]
Lagrangian methods & duality
- General formulation of constrained problems; the Lagrangian sufficiency theorem. Interpretation of Lagrange multipliers as shadow prices. The dual linear problem, duality theorem in a standardized case, complementary slackness, dual variables and their interpretation as shadow prices. Relationship of the primal simplex algorithm to dual problem. Examples. [3]
Linear programming in the nondegenerate case
- Convexity of feasible region; sufficiency of extreme points. Standardization of problems, slack variables, equivalence of extreme points and basic solutions. The primal simplex algorithm and the tableau. Examples. [3]
Applications of linear programming
- Two person zero-sum games. Network flows; the max-flow min-cut theorem; the Ford–Fulkerson algorithm, the rational case. Network flows with costs, the transportation algorithm, relationship of dual variables with nodes. Examples. Conditions for optimality in more general networks. The formulation of simple practical and combinatorial problems as linear programming or network problems. [3]
Appropriate books
- † M.S. Bazaraa, J.J. Jarvis and H.D. Sherali Linear Programming and Network Flows. Wiley 1988
- D. Luenberger Linear and Nonlinear Programming. Addison–Wesley 1984
- S. Boyd and L. Vandenberghe Convex Optimization. Cambridge University Press 2004
- D. Bertsimas, J.N. Tsitsiklis Introduction to Linear Optimization. Athena Scientific 1997
sooo0oooys 