From Formulas to Airplanes

In unconstrained optimization so-called quasi-Newton methods have been very succesfull and are widely used. They alleviate the need to evaluate second derivatives and, at the same time, reduce the linear algebra effort for computing each new iteration point from cubic to quadratic with respect to n .

For constrained optimization, classical SQP implementations salvage only the first but not the second desirable feature in the more general context of constrained optimization. Also, they require at each iteration the evaluation of all constraint gradients, which is in general m times as expensive as evaluating the constraint functions as such.

The 'total quasi-Newton' approach combines the selective evaluation of cheaply available derivatives via Algorithmic Differentiation (AD) with the approximation of the Jacobian and Hessian matrices by new, linearly invariant update formulas. As a result the linear algebra cost per iteration is only quadratic with respect to n+m, and the evaluation effort is bounded by a small multiple of that needed to compute the objective and derivative values by themselves. Due to the heredity property of the updates equality constrained quadratic programs are solved exactly in n steps for almost all initializations of primal and dual variables as well as Jacobian and Hessian approximations.

We intend to develop an NLP solver that requires only the input of an evaluation program for objective and constraints with first and second derivative vectors being computed by AD. It should be highly competetive for problems with n and m in the thousands, where dense Jacobians and Hessians can be stored in main memory and thus efficiently manipulated. For larger problems data sparse matrix representations of the kind suggested in are envisaged. Moreover, sparse preconditioning that renders the relative matrix discrepancies compact must be incorporated for structured problem classes, such as those arising in optimal control.

Category:

Education

Tags:

• 2010
• MIF
• C12
• en
• web
• From
• Formulas
• to
• Airplanes
• berlin
• dfg
• research
• center
• matheon
• mathematic
• andreas
• griewank