Combining Trust Region and Affine Scaling Linearly ConstrainedNonconvex Minimization

Abstract

An interior point method is proposed for a general nonlinear (nonconvex) minimization with linear inequality constraints. This method is a combination of the trust region idea for nonlinearity and affine scaling technique for constraints. Using this method, the original objective function is monotonically decreased. In the proposed approach, a Newton step is derived directly from the complementarity conditions. A trust region subproblem is formed which yields an approximate Newton step as its solution asymptotically. The objective function of the trust region subproblem is the quadratic approximation to the original objective function plus an augmented quadratic convex term. Similar to an augmented Lagrangian function, this augmentation adds positive curvature in the range space of the constraint normals. The global convergence is achieved by possibly using trust regions with different shapes. A reflection technique, which accelerates convergence, is described. Explicit sufficient decrease conditions are proposed. Computational results of a two-dimensional trust region implementation are reported for large-scale problems. Preliminary experiments suggest that this method can be effective; a relatively small number of function evaluations are required for some medium and large test problems.