Prof  Tibor Illes,
Budapest University of Technology and Economics,
will offer a PhD course on  “Interior point methods for linear programming” 
(room: Aula Seminari del Dipartimento di Ingegneria Industriale – via di  S. Marta 3 – first floor, ALA EST)
 
Monday September 14th,  15-17
Tuesday September 15th,10-12, 15-17
Wednesday September 16th, 10-12
For information: fabio.schoen@unifi.it

Interior point methods for linear programming

Erasmus graduate mini course in continuous optimization

Firenze, September 14-16, 2015

Tibor Illés

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.

References:

  1. C. Roos, T. Terlaky and J.-Ph. Vial: Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley & Sons, New York, 1997
  2. 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
  3. 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.

http://www.cs.elte.hu/opres/orr/download/IT-LP-belsopontos-jegyzet-20140824.pdf

image_print
PhD Course on “Interior point methods for linear programming”