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

点击翻译按钮获取中文摘要

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