Development of numerically stable primal-dual interior point algorithms for solving nonlinear semidefinite programming problems

本研究的目的是发展数值稳定的原始-对偶内点方法来求解非线性半定规划问题。半定规划问题是一个在闭凸锥上的优化问题，它不是线性规划问题的多面体。由于这个原因，我们经常观察到一个问题，它有一个渐近最优解，但没有最优解，即，目标值收敛到最佳值的任何序列都发散。这给我们应用内点算法求解该问题时确定最优性带来了数值上的困难。如果我们采用该问题作为组合优化问题或鲁棒优化问题的近似模型，则该问题的最优解的高精度是至关重要的。为了克服这个困难，已经提出了许多技术来获得数值稳定的算法。当我们解决非线性半定规划问题时，这些技术被寄予厚望。为了提供这样的技巧之一，我们引入了非线性半定规划问题的齐次模型，并证明了对于齐次模型，（a）存在具有平凡起点的有界路径，（B）路径的任何聚点都是齐次模型的解，c如果原问题是可解的，则它给出有限解，（d）如果原问题是强不可行的，那么它给了我们一个证明不可行的有限证明，以及（e）一类用于数值跟踪（a）中的路径的算法在适度假设下以多项式迭代次数解决了问题

The aim of this research is to develop numerically stable primal-dual interior point methods foe solving nonlinear semidefinite programming problems. The semidefinite programming problem is an optimization problem over a closed convex cone that is not polyhedral unlike the linear programming problem. By this reason, we often observe a problem which has an asymptotic optimal solution but no optimal solution, I.e., any sequence on which the object value converges to the optimal value diverges. This brings us a numerical difficulty in determining the optimality when we apply interior point algorithms to solve the problem. A high accuracy of an optimal solution of the problem is critical if we adopt the problem as an approximation model of a combinatorial optimization problem or a robust optimization problem. To overcome the difficulty, many techniques have been proposed for obtaining a numerical stability of the algorithms. Such techniques are more highly expected when we solve nonlinear semidefinite programming problems. In order to provide one of such techniques, we introduced a homogeneous model for the nonlinear semidefinite programming problem, and showed that for the homogeneous model, (a) a bounded path having a trivial starting point exists, (b) any accumulation point of the path is a solution of the homogeneous model, c if the original problem is solvable then it gives us a finite solution, (d) if the original problem is strongly infeasible, then it gives us a finite certificate proving infeasibility, and (e) a class of algorithms for numerically tracing the path in (a) solves the problem in a polynomial number of iterations under a moderate assumption