| The problem of large-scale constrained optimization is addressed. A barrier function is used to transform the problem into a sequence of subproblems with nonlinear equality constraints. The method used here for each subproblem is similar to what the second-derivative method of Murray and Prieto (MP) reduces to when applied to equality-constrained problems. Second derivatives are used to generate a search direction and a direction of negative curvature for a curvilinear search. The MP method would be based on the KKT equations for the subproblem, but here we use the primal-dual transformation of those equations.; A key feature of our method is that only a single system of linear equations is solved at each subproblem iteration (as in barrier methods for linear programming). In contrast, a trust-region method applied to the subproblem may require the solution of several linear systems, and sequential quadratic programming (SQP) methods applied directly to the original problem require the solution of a quadratic program at each iteration. For small problems this is of little consequence, but for large problems, especially when iterative methods are necessary to solve the linear systems, it may prove a vital advantage. The advantage would be lost if the number of iterations were significantly more than for alternative methods. Since analysis cannot predict iteration counts for general nonlinear problems, an experimental MATLAB code named MELBA has been implemented to investigate this aspect of performance. MELBA is compared primarily to another second-derivative barrier method, KNITRO, whose subproblems are solved by a trust-region method. We also give results for SNOPT, which uses a quasi-Newton SQP method. For the common set of problems solved the results are encouraging because there is little to distinguish between the three sets of results, even though there is much room for refining the new method. It is shown that the method converges globally to a point satisfying the second-order necessary conditions, without an assumption that the iterates lie in a compact set. Moreover, the iterates converge at a quadratic rate. A feature of the method is that the implementation is close to that of the theoretical algorithm. |
