UC San Diego

Trust-region methods are amongst the most commonly used methods in unconstrained mathematical optimization. Their impressive performance and sound theoretical guarantees make them suitable for a wide range of problem types. However, the computational complexity of existing methods for solving the trust-region subproblem prevents trust-region methods from being widely used in large-scale problems in both unconstrained and constrained settings. This dissertation introduces and analyzes three novel methods for solving the trust-region subproblem for large-scale constrained optimization problems. Convergence rates and proofs are presented where applicable. Furthermore, a trust-region approach is developed for the recently introduced all-shifted primal-dual penalty-barrier method for solving nonconvex, constrained optimization problems.

The three trust-region algorithms introduced are the shifted and inverted generalized Lanczos trust region algorithm, the locally optimal preconditioned conjugate gradient trust region, and the Jacobi-Davidson QZ trust region algorithm. Each new method exhibits improved performance over the existing standard methods and is best suited for problems too large for the traditional methods to handle efficiently. Furthermore, each method exhibits particular benefits for differently scaled problems.