Multilevel algorithms for nonlinear equations and equality constrained optimization

[摘要] A general trust region strategy is proposed for solving nonlinear systems of equations and equality constrained optimization problems by means of multilevel algorithms. The idea is to use the trust region strategy to globalize the Brent algorithms for solving nonlinear equations, and to extend them to algorithms for solving optimization problems. The new multilevel algorithm for nonlinear equality constrained optimization operates as follows. The constraints are divided into an arbitrary number of blocks dictated by the application. The trial step from the current solution approximation to the next one is computed as a sum of substeps, each of which must predict a Fraction of Cauchy Decrease on the subproblem of minimizing the model of each constraint block, and, finally, the model of the objective function, restricted to the intersection of the null spaces of all the preceding linearized constraints. The models of each constraint block and of the objective function are built by using the function and derivative information at different points. The merit function used to evaluate the step is a modified $ellsb2$ penalty function with nested penalty parameters. The scheme for updating the penalty parameters is a generalization of the one proposed by El-Alem. The algorithm is shown to be well-defined and globally convergent under reasonable assumptions. The global convergence theory for the optimization algorithm implies global convergence of the multilevel algorithm for nonlinear equations and a modification of a class of trust region algorithms proposed by Maciel, and Dennis, El-Alem and Maciel. The algorithms are expected to become flexible tools for solving a variety of optimization problems and to be of great practical use in applications such as multidisciplinary design optimization. In addition, they serve to establish a foundation for the study of the general multilevel optimization problem.

[发布机构] Rice University