Abstract:
For a linear programming problem stated in the canonical form we consider the dual problem and describe a class of interior point algorithms which generate monotonically improving approximations to its solution. We theoretically substantiate the optimization process in the admissible domain under the assumption that the dual problem is non-degenerate. In addition, we describe subsets of algorithms that lead to relative interior points of optimal solutions. These algorithms have linear and superlinear convergence rates. Moreover, we obtain a special subset of algorithms which generate iterative sequences of approximations to a solution of the direct problem, whose convergence rate exceeds that of the sequences of monotonically improving approximations to a solution of the dual problem.
Keywords:
linear programming, dual interior point algorithms, relative interior.
This publication is cited in the following 6 articles:
V. I. Zorkal'tsev, “Interior point method: history and prospects”, Comput. Math. Math. Phys., 59:10 (2019), 1597–1612
V. S. Kolosov, “Metod posledovatelnoi aktivatsii ogranichenii v lineinom programmirovanii”, PDM, 2018, no. 41, 110–125
Domyshev A., Sidorov D., Panasetsky D., Sun Y., Ju P., Wu F., 2018 2Nd IEEE Conference on Energy Internet and Energy System Integration (Ei2), IEEE, 2018
Aleksandr Domyshev, Denis Sidorov, Daniil Panasetsky, Yonghui Sun, Ping Ju, Feng Wu, 2018 2nd IEEE Conference on Energy Internet and Energy System Integration (EI2), 2018, 1
Zorkal'tsev V., “Algorithms of the Interior Point Method”, 2017 Constructive Nonsmooth Analysis and Related Topics (Dedicated to the Memory of V.F. Demyanov) (Cnsa), ed. Polyakova L., IEEE, 2017, 385–388
Valery Zorkal'tsev, 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA), 2017, 1