1.       

Course title

Information technologies.
Foundations of linear programming

2.       

Year of study, study programme

3,

1-31 03 09  Computer Mathematics and Systems Analysis

3.       

Semester of study

6

4.       

Number of credits

2

5.       

Lecturer

Lavrova Olga Anatolievna

6.       

Course Objective

Formation of theoretical knowledge and practical skills for solving problems of convex and linear programming.

As a result of studying the student should be able to

–         construct extremal problems on convex sets of finite-dimensional spaces subject to the equalities and inequalities constraints;

–         solve problems of linear and convex programming by polynomial-time methods.

7.       

Prerequisites

Calculus. Algebra and Number Theory. Geometry. Computer Mathematics. Optimization Methods. Numerical Methods

8.       

Course content

1.  Geometry of linear programing problems.   Decomposition of polyhedra. Connection between the decomposition of polyhedra and solution of linear programming problems. Characteristic cone. Polytop. Lineality space. Faces. Facets. Minimal faces. Vertices. Extremal rays. Extremal points. The simplex method.

2.  Polynomial-time methods for convex programming problems.  Khachiyan’s method (the ellipsoid method). The binary search algorithm for a sequence of solvability problems. Algorithmic representation for the convex body. Theoretical and practical complexity of the ellipsoid method. The interior-point method. Inner scalar product. A concordant function as a barrier-function. The barrier-function for polyhedral sets. Theoretical complexity of the inner-point method.

9.       

Recommended Literature

1.  Materials to the course «Einfürung in die Mathematische Optimierung», Prof. Kaibel, Otto-von-Guericke University, Magdeburg, Germany 2013/14: video-lectures in German, slides for lectures, homework tasks.

2.  R. T. Rockafellar, Convex Analysis. Princeton University Press, 1970.

3.  A. Ruszcynski, Nonlinear Optimization. Princeton University Press, 2006.

4.  A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986.

5.  J. Matousek, B. Gärtner, Using and Understanding Linear Programming, Springer, 2006.

6.  V. Chvatal, Linear Programming, Freeman, 1983.

7.  M. Grötschel, L. Lovàsz, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1988.

10.   

Teaching Methods

Lectures, laboratory classes

11.   

Teaching language

Russian, German, English

12.   

Requirements, current control

Control of the student’s work takes place in the form of tests. Credits are held orally.

13.   

Method of certification

Credit