A class of polynomial variable metric algorithms for linear optimization
作者： T. Rapcsák , T. T. Thang
DOI: 10.1007/BF02592202
关键词: Metric (mathematics) 、 Algorithm 、 Interior point method 、 Linear programming 、 Vector field 、 Polynomial 、 Mathematics 、 Canonical form 、 Variable (mathematics) 、 Information geometry
摘要: In the paper, behaviour of interior point algorithms is analyzed by using a variable metric method approach. A class polynomial given achieving O ((n/β)L) iterations for solving canonical form linear optimization problem with respect to wide Riemannian metrics, wheren number dimensions and β fixed value. It shown that vector fields several negative gradient field potential or logarithmic barrier function suitable metrics.
springer.com
sci-hub.se 参考文章(12)
Masao Iri, Integrability of vector and multivector fields associated with interior point methods for linear programming Mathematical Programming. ,vol. 52, pp. 511- 525 ,(1991) , 10.1007/BF01582903
D. A. Bayer, J. C. Lagarias, The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories Transactions of the American Mathematical Society. ,vol. 314, pp. 499- 526 ,(1989) , 10.1090/S0002-9947-1989-1005525-6
D. Gabay, Minimizing a differentiable function over a differential manifold Journal of Optimization Theory and Applications. ,vol. 37, pp. 177- 219 ,(1982) , 10.1007/BF00934767
D. den Hertog, C. Roos, A survey of search directions in interior point methods for linear programming Mathematical Programming. ,vol. 52, pp. 481- 509 ,(1991) , 10.1007/BF01582902
Philip E. Gill, Walter Murray, Michael A. Saunders, J. A. Tomlin, Margaret H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method Mathematical Programming. ,vol. 36, pp. 183- 209 ,(1986) , 10.1007/BF02592025
Masao Iri, A proof of the polynomiality of the Iri-Imai method Journal of Complexity. ,vol. 9, pp. 269- 290 ,(1993) , 10.1006/JCOM.1993.1018
Masao Iri, Hiroshi Imai, A multiplicative barrier function method for linear programming Algorithmica. ,vol. 1, pp. 455- 482 ,(1986) , 10.1007/BF01840457
T. Rapcsák, T. T. Thang, Nonlinear coordinate representations of smooth optimization problems Journal of Optimization Theory and Applications. ,vol. 86, pp. 459- 489 ,(1995) , 10.1007/BF02192090
Hiroshi Imai, On the convexity of the multiplicative version of Karmarkar's potential function Mathematical Programming. ,vol. 40, pp. 29- 32 ,(1988) , 10.1007/BF01580721
D. A. Bayer, J. C. Lagarias, The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories Transactions of the American Mathematical Society. ,vol. 314, pp. 527- 581 ,(1989) , 10.1090/S0002-9947-1989-1005526-8