Browsing by Author "Lawrence, Craig T."
Results Per Page
Sort Options
Item A Computationally Efficient Feasible Sequential Quadratic Programming Algorithm(1998) Lawrence, Craig T.; Tits, Andre; ISRThe 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.
Item A Computationally Efficient Feasible Sequential Quadratic Programming Algorithm(1998) Lawrence, Craig T.; Tits, A.; ISRA Sequential Quadratic Programming (SQP) algorithm generatingfeasible iterates is described and analyzed.What distinguishes this algorithm from previous feasible SQP algorithms proposed by various authors is a drastic reduction in the amountof computation required to generate a new iteratewhile the proposed scheme still enjoys the same global and fast local convergence properties.A preliminary implementation has been tested and somepromising numerical results are reported.Item Feasible Sequential Quadratic Programming for Finely Discretized Problems from SIP(1997) Lawrence, Craig T.; Tits, A.L.; ISRA sequential Quadratic Programming algorithm designed to efficiently solve nonlinear optimization problems with many inequality constraints, e.g. problems arising from finely discretized Semi-Infinite Programming, is described and analyzed. The key features of the algorithm are (i) that only a few of the constraints are used in the QP sub-problems at each iteration, and (ii) that every iterate satisfies all constraints.Item Nonlinear Equality Constraints in Feasible Sequential Quadratic Programming(1995) Lawrence, Craig T.; Tits, A.L.; ISRA simple scheme is proposed for handling nonlinear equality constraints in the context of a previously introduced sequential quadratic programming (SQP) algorithm for inequality constrained problems, generating iterates satisfying all constraints. The key is an idea due to Mayne and Polak (Math. progr., vol. 11, pp 67- 80, 1976) by which nonlinear equality constraints are treated as ﳣﱠtype constraints to be satisfied by all iterates, thus precluding any positive value, and an exact penalty term is added to the objective function which penalizes negative values. Mayne and Polak obtain a suitable value of the penalty parameter by iterative adjustments based on a test involving estimates of the KKT multipliers. We argue that the SQP framework allows for a more effective estimation of these multipliers, and we provide convergence analysis of the resulting algorithms. Numerical results, obtained with the FSQP/CFSQP code, are reported.Item A Primal-Dual Interior-Point Method for Nonconvex Optimization with Multiple Logarithmic Barrier Parameters and with Strong Convergence Properties(1998) Urban, T.; Tits, A.L.; Lawrence, Craig T.; ISRIt is observed that an algorithm proposed in the 1980s for thesolution of nonconvex constrained optimization problems is in fact aprimal-dual logarithmic barrier interior-point method closely related tomethods under current investigation in the research community. Its maindistinguishing features are judicious selection and update of the multiplebarrier parameters (one per constraint), use of the objective function asmerit function, and careful bending of the search direction. As a payoff,global convergence and fast local convergence ensue. The purpose of thisshort note is to describe the algorithm in the interior-point framework andlanguage and to provide a preliminary numerical evaluation. The latter showsthat the method compares well with algorithms recently proposed by otherresearch groups.Item A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties(2001) Tits, A.L.; Urban, T.J.; Bakhtiari, Sasan; Lawrence, Craig T.; ISRA scheme---inspired from an old idea due to Mayne and Polak (Math. Prog.,vol.~11, 1976, pp.~67--80)---is proposed for extending to general smoothconstrained optimization problems a previously proposed feasibleinterior-point method for inequality constrained problems.It is shown that the primal-dual interior point framework allows for asignificantly more effective implementation of the Mayne-Polak idea thanthat discussed an analyzed by the originators in the contextof first order methods of feasible direction. Strong global and localconvergence results are proved under mild assumptions. In particular,the proposed algorithm does not suffer the Wachter-Biegler effect.Item A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties(2002) Tits, Andre L.; Wachter, Andreas; Bakhtiari, Sasan; Urban, Thomas J.; Lawrence, Craig T.; ISRAn exact-penalty-function-based scheme|inspired from an old ideadue to Mayne and Polak (Math. Prog., vol. 11, 1976, pp. 67{80)|isproposed for extending to general smooth constrained optimizationproblems any given feasible interior-point method for inequality constrained problems.It is shown that the primal-dual interior-point framework allows for a simpler penalty parameter update rule than that discussed and analyzed by the originators of the scheme in the context of first order methods of feasible direction. Strong global and local convergence results are proved under mild assumptions.
In particular,(i) the proposed algorithm does not suffer a common pitfall recently pointed out by Wachter and Biegler; and (ii) the positive definiteness assumption on the Hessian estimate, made in the original version of the algorithm, is relaxed, allowing for the use of exact Hessian information, resulting in local quadratic convergence. Promisingnumerical results are reported.
Note: This report is a major revision to TR 2001-3, "A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties," by A.L. Tits, T.J. Urban, S. Bakhtiari, C.T. Lawrence.
Item User's Guide for CFSQP Version 2.0: A C Code for Solving (Large Scale) Constrained Nonlinear (Minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints(1994) Lawrence, Craig T.; Zhou, J.L.; Tits, A.L.; ISRCFSQP is a set of C functions for the minimization of the maximum of a set of smooth objective functions (possibly a single one) subject to general smooth constraints. If the initial guess provided by the user is infeasible for some inequality constraint or some linear equality constraint, CFSQP first generates a feasible point for these constraints; subsequently the successive iterates generated by CFSQP all satisfy these constraints. Nonlinear equality constraints are turned into inequality constraints (to be satisfied by all iterates) and the maximum of the objective functions is replaced by an exact penalty function which penalizes nonlinear equality constraint violations only. When solving problems with many sequentially related constraints (or objectives), such as discretized semi- infinite programming (SIP) problems, CFSQP gives the user the option to use an algorithm that efficiently solves these problems, greatly reducing computational effort. The user has the option of either requiring that the objective function (penalty function if nonlinear equality constraints are present) decrease at each iteration after feasibility for nonlinear inequality and linear constraints has been reached (monotone line search), or requiring a decrease within at most four iterations (nonmonotone line search). He/She must provide functions that define the objective functions and constraint functions and may either provide functions to compute the respective gradients or require that CFSQP estimate them by forward finite differences.CFSQP is an implementation of two algorithms based on Sequential Quadratic Programming (SQP), modified so as to generate feasible iterates. In the first one (monotone line search), a certain Armijo type arc search is used with the property that the step of one is eventually accepted, a requirement for superlinear convergence. In the second one the same effect is achieved by means of a "nonmonotone" search along a straight line. The merit function used in both searches is the maximum of the objective functions if there is no nonlinear equality constraints, or an exact penalty function if nonlinear equality constraints are present.