Primal-dual interior-point methods for large-scale optimization

Many important problems may be expressed in terms of nonlinear multivariate inequality constrained optimization. The basic inequality constrained optimization problem is to minimize a real-valued function f( x) over all vectors $x\in Rn$ where the solution must satisfy a set of nonlinear constraints c(x) ≥ 0, with $c:Rn\to Rm$. In this thesis we formulate and analyze two methods for large-scale optimization. The first is a modified conjugate-gradient method for large-scale unconstrained optimization. The search directions generated by this method satisfy standard conditions used to establish convergence to points satisfying the second-order necessary conditions for optimality. The second method is a primal-dual interior method for both convex and nonconvex problems with bound constraints. This primal-dual method is applied to the optimization of systems arising in the finite-element discretization of certain elliptic variational inequalities. In this situation, the primal-dual linear systems have the same zero/nonzero structure as the associated discretized partial differential equations. This property allows the interior method to exploit existing efficient, robust and scalable multilevel algorithms for the solution of partial differential equations. New methods are formulated and analyzed for the initialization of the primal-dual iteration following the use of uniform and adaptive mesh refinement.