Monday September 14th, 15-17Tuesday September 15th,10-12, 15-17
Wednesday September 16th, 10-12
Interior point methods for linear programming
Erasmus graduate mini course in continuous optimization
Firenze, September 14-16, 2015
Budapest University of Technology and Economics
Interior point approach to some theoretical results of linear programming. Self-dual linear programming problems and their properties. Level sets, central path and their properties. Computation of the Newton-directions. Simple proof of the existence and uniqueness of the central path. Analitic center, Sonnevend theorem. ε-optimal solution.
Dikin-type affine scaling, primal-dual method and its polynomial complexity.
Primal-dual logarithmic barrier method with full Newton-step and its polynomial complexity.
Optimal partition. Description of the optimal solution set. Existence of strictly complementary solution. Strongly polynomial rounding procedure yielding strictly complementary solution from an ε-optimal solution.
Miscelluous topics: self-dual embedding.
- C. Roos, T. Terlaky and J.-Ph. Vial: Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley & Sons, New York, 1997
- T. Terlaky, An easy way to teach interior-point methods, European Journal of Operational Research, 130(1): 1-19, 2001. http://www.sciencedirect.com/science/article/pii/S0377221700000941
- T. Illés and T. Terlaky, Pivot versus interior point methods: Pros and cons, European Journal of Operational Research, 140(2): 170-190, 2002. http://www.sciencedirect.com/science/article/pii/S0377221702000619
Lecture based on the following (Hungarian) e-book:
Illés Tibor, Lineáris optimalizálás elmélete és belsőpontos algoritmusai, Operations Research Reports, 2014-04, pp. 1-95, Eötvös Loránd University, Budapest.