Prime-dual method to solve entropy-linear programming problem

A. V. Chernov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Entropy-linear programming problems can be derived invarious applications (transport problems, chemical reactions research and etc.). These problems are usually defined as problems of maximization of entropy function (or minimization of minus entropy function) with affine constraints and with linear constraints-inequalities. In this article method used to solve this task is investigated which is based on the solution of the dual task with reconstruction of the solution of the prime task: for each point in dual set calculated by method related point is defined in the prime set. The upper estimate of the iterations required to solve the problem with predefined quality is found. Specified method can be used for the wider class of strongly convex functions with the similar feasible set.

Keywords: Entropy-linear programming, fast gradient method, dual task, prime-dual method.