A Computationally Efficient Feasible Sequential Quadratic Programming Algorithm

Thumbnail Image


PhD_98-5.pdf (1.33 MB)
No. of downloads: 4591

Publication or External Link






The role of optimization in both engineering analysis and designis continually expanding. As such, faster and more powerful optimization algorithms are in constant demand. In this dissertation, motivated by problems from engineering analysis and design, new Sequential Quadratic Programming (SQP) algorithms generating feasible iterates are described and analyzed. What distinguishes these algorithms from previous feasible SQP algorithms is a dramatic reduction in the amount of computation required to generate a new iterate while still enjoying the same global and fast local convergence properties.

First, a basic algorithm which solves the standard smooth inequality constrained nonlinear programming problem is considered. The main idea involves a simple perturbation of the Quadratic Program (QP) for the standard SQP search direction. The perturbation has the property that a feasible direction is always obtained and fast local convergence is preserved. An extension of the basic algorithm is then proposed which solves the inequality constrained mini-max problem. The algorithm exploits the special structure of the problem and is shown to have the same global and local convergence properties as the basic algorithm.

Next, the algorithm is extended to efficiently solve problems with very many objective and/or constraint functions. Such problems often arise in engineering design as, e.g., discretized Semi-Infinite Programming (SIP) problems. The key feature of the extension is that only a small subset of the objectives and constraints are used to generate a search directionat each iteration. The result is much smaller QP sub-problems and fewer gradient evaluations.

The algorithms all have been implemented and tested. Preliminary numericalresults are very promising. The number of iterations and function evaluations required to converge to a solution are, on average, roughly the same as for a widely available state-of-the-art feasible SQP implementation, whereas the amount of computation required per iteration is much less. The ability of the algorithms to effectively solve real problems from engineering design is demonstrated by considering signal set design problems for optimal detection in the presence of non-Gaussian noise.