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