The internal point method is a method that allows solving convex optimization problems with conditions specified in the form of inequalities, reducing the original problem to a convex optimization problem.
It is used in solving problems of sopromat , mathematical modeling and econometrics.
The von Neumann method, first proposed by John von Neumann, did not have polynomial complexity , nor was it effective. In practice, it was even inferior to the simplex method , which also did not have polynomial complexity [1] . However, in 1984, the linear programming algorithm proposed by the Indian mathematician Narendra Karmarkar demonstrated a polynomial time that even exceeded the simplex method.
According to the methods of the internal point (otherwise called the methods of barrier functions), the starting point for the search can be selected only within an admissible region.
The choice of the starting point of the search is carried out depending on the formulation of the problem. In the absence of restrictions or their conversion to penalty functions with an external point, the starting point is arbitrarily selected. If there are restrictions or their conversion to fine functions with an internal point, the starting point is selected inside the valid area
In this case, the set of points is divided into permissible and unacceptable depending on the restrictions. In turn, the set of permissible points, depending on the restrictions, is also divided into boundary and internal.
Content
Logarithmic Barrier and Central Path
The origins of the central path algorithms go back to K. Frisch’s idea of including penalty terms in the form of logarithm-inequality-inequalities with a parameter that decreases monotonically to zero in the objective function.
The appearance of the Karmarkar algorithm [51] prompted researchers to actively use the functions of the logarithmic barrier in linear programming problems.
Barrier Method
The Karmakar method is similar to the logarithmic-barrier method.
Phase 1
To start the barrier method, you must specify the starting internal point, i.e. a point x such that fi (x) <0 ∀i. In the general case, finding the inner point x may turn out to be a nontrivial task. Methods for solving this problem are called methods of the first phase. These include the barrier method and the direct-dual Newton method.
See also
- Newton's method
Notes
- ↑ Dantzig, George B. Linear Programming 2: Theory and Extensions / George B. Dantzig, Mukund N. Thapa. - Springer-Verlag, 2003.
Literature
- System analysis and operations research. Authors: Yu. Chernikov
- Bonnans, J. Frédéric. Numerical optimization: Theoretical and practical aspects / J. Frédéric Bonnans, J. Charles Gilbert, Claude Lemaréchal ... [and others. ] . - Second revised ed. of translation of 1997 French. - Berlin: Springer-Verlag, 2006 .-- P. xiv + 490. - ISBN 3-540-35445-X . - DOI : 10.1007 / 978-3-540-35447-5 .
- Karmarkar, N. Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84 ( journal ) : journal. - 1984 .-- P. 302 . - ISBN 0-89791-133-4 . - DOI : 10.1145 / 800057.808695 . Archived December 28, 2013. Archived December 28, 2013 on the Wayback Machine
- Mehrotra, Sanjay. On the Implementation of a Primal-Dual Interior Point Method (Eng.) // SIAM Journal on Optimization: journal. - 1992. - Vol. 2 , no. 4 . - P. 575 . - DOI : 10.1137 / 0802028 .
- Nocedal, Jorge. Numerical Optimization. - New York, NY: Springer, 1999 .-- ISBN 0-387-98793-2 .
- Press, WH. Section 10.11. Linear Programming: Interior-Point Methods // Numerical Recipes: The Art of Scientific Computing / WH Press, SA Teukolsky, WT Vetterling ... [ and others. ]. - 3rd. - Cambridge University Press, 2007. - ISBN 978-0-521-88068-8 .
- Wright, Stephen. Primal-Dual Interior-Point Methods. - Philadelphia, PA: SIAM, 1997 .-- ISBN 0-89871-382-X .
- Boyd, Stephen. Convex Optimization / Stephen Boyd, Lieven Vandenberghe. - Cambridge University Press, 2004.