Canonical coordinates method for equality-constrained nonlinear optimization

摘要

Feasible-points methods have several appealing advantages over the infeasible-points methods for solving equality-constrained nonlinear optimization problems. The known feasible-points methods however solve, often large, systems of nonlinear constraint equations in each step in order to maintain feasibility. Solving nonlinear equations in each step not only slows down the algorithms considerably, but also the large amount of floating-point computation involved introduces considerable numerical inaccuracy into the overall computation. As a result, the commercial software packages for equality-constrained optimization are slow and not numerically robust. We present a radically new approach to maintaining feasibility––called the canonical coordinates method (CCM). The CCM, unlike previous methods, does not adhere to the coordinate system used in the problem specification. Rather, as the algorithm progresses CCM dynamically chooses, in each step, a coordinate system that is most appropriate for describing the local geometry around the current iterate. By dynamically changing the coordinate system to suit the local geometry, the CCM is able to maintain feasibility in equality-constrained nonlinear optimization without having to solve systems of nonlinear equations. We describe the CCM and present a proof of its convergence. We also present a few numerical examples which show that CCM can solve, in very few iterations, problems that cannot be solved using the commercial NLP solver in MATLAB 6.1.