| dc.description.abstract | The main objective of this thesis was to perform initial studies on a new approach for solving semidefinite programs. In this solution method, a nonsmooth representation of the optimality conditions of semidefinite programs is solved using the LP-Newton method, where a linear program (LP) is solved to find a search direction. As a part of the study, it was desired to evaluate its theoretical and numerical properties, and especially its potential to solve large-scale semidefinite programs.
This study was conducted in several parts. After an introduction to various theoretical concepts, different nonsmooth formulations of the optimality conditions were proposed. In addition, their representations using matrix vectorization along with their lexicographic derivatives were given. Then, an implementation of the solver was discussed, with focus on details added to exploit structure and sparsity as well as automatic differentiation for nonsmooth expressions. Moreover, the properties of the proposed optimality conditions were theoretically analyzed in the context of the required conditions for local Q-quadratic convergence of the LP-Newton method. Finally, a set of experiments were carried out in order to inspect the numerical properties, as well as the efficiency and accuracy, of the proposed solution approach.
The theoretical analysis showed that only a subclass of semidefinite programs fits into the convergence conditions of the LP-Newton method, because a full rank Jacobian matrix is required. Hence, the problems must have unique primal and dual solutions as well as to satisfy strict complementarity in the solution. In addition, only three out of nine proposed formulations of the complementary slackness condition can satisfy this rank condition. These conclusions were supported by the numerical results, as convergence was in general not observed for the formulations that gave a rank deficient Jacobian matrix. In addition, attempts to solve problems that lacked a unique or strictly complementary solution, resulting in a rank deficient Jacobian matrix in the solution, did in most cases not converge.
However, for problems that were nondegenerate and had a strictly complementary solution, local Q-quadratic convergence was observed in agreement with theory. Moreover, the obtained solutions were found to be more accurate than the most accurate solutions possible to obtain from a solver considered to be state-of-the-art. In accordance with expectations, the new solution approach showed to be slower than the primal-dual interior-point methods for problems of small scale. This is due to a potentially large number of linear equation systems that are solved in each iteration, compared to only one in the primal-dual interior-point methods. On the other hand, for large-scale systems of dimensions that interior-point methods can not handle, the solver was able to make progress, even though a solution was not found.
Semidefinite programs from models of physical phenomena, such as electronic structure problems, often do not satisfy nondegeneracy and strict complementarity. Hence, the new solution approach in its simplest form is not adequate to solve problems of practical importance, and further research into remedies for the rank deficiency of the Jacobian matrix is recommended. | en |
