Studies in large-scale optimization.

Abstract

Large-scale optimization problems arise in many scientific, engineering, and financial applications. Due to the size and complexity of those problems, they have not been effectively handled by the currently available software. In this dissertation, we study two large-scale optimization problems: bound-constrained optimization and semidefinite programming. For bound-constrained optimization, we develop a new trust region method based on projected gradients. For this method, the local quadratic convergence is proved for both degenerate and nondegenerate problems. Numerical implementation shows the new algorithm outperforms other current research software. For semidefinite programming, we propose a new primal-dual interior-point method for its solution. Theoretical polynomial convergence is proved and numerical behavior of the new algorithm is studied. We also apply this method to quadratic assignment problems (QAP), a combinatorial optimization problem. By proposing a new relaxation of QAP and adding combinatorial cuts, our SDP relaxation obtains the best lower bound for some problem instances. In addition, during the process of optimization, many numerical linear algebra issues arise. In our case large sparse and dense linear systems are to be solved. We use iterative methods, especially the preconditioned conjugate gradient method, to solve these linear systems. To improve the viability of using iterative methods, different preconditioners are used to improve the condition of the underlying matrices. Here we propose a new incomplete Cholesky factorization as the preconditioner and show that it is suitable for both sparse and dense linear systems.