Диссертации, представленные на защиту и подготовленные в НИУ ВШЭ

Interior point methods have a history of more than 35 years and their appearance made a major breakthrough in convex optimization. These methods are still actively used for solving large-scale optimization problems and remain out of competition.One of the important practical aspects of implementing any continuous optimization algorithm is the appropriate choice of the step length. This problem for interior point methods is the focus of this thesis. In this work, we propose to use an approach in which the problem of finding the optimal step of the method is formed as an optimal control problem and then optimal control theory is applied to solve it. We apply this approach to Newton’s method for minimizing self-concordant functions, because this method is used to solve the auxiliary problem in interior point methods where self-concordant barriers are employed to solve conic programming problems. We likewise apply the approach to the task of finding the optimal step for approaching the central path in problems with self-concordant barriers. The first problem has been solved analytically and the resulting step length is optimal for Newton’s method. The second problem has no closed-form solution and was solved numerically for the two-dimensional case.