New Trust Region SQP Methods for Continuous and Integer Optimization
Oliver Exler · EPub Bayreuth (University of Bayreuth) · 2013
In this thesis new algorithms are presented that address nonlinear optimization problems.The algorithms belong to the class of sequential quadratic programming (SQP) methods.Two problem formulations that arise frequently in real-world applications are considered.Both have in common that functions are nonlinear and the formulations contain equality and inequality constraints.For the one class of problems the domain of all variables is R.These problems are called nonlinear programming (NLP) problems.Many applications also require that some of the featured variables are restricted to the domain Z. Problems with additional integer variables are called mixed-integer nonlinear programs (MINLP) and are also considered here.This work is motivated by the advancement of an algorithm for solving MINLPs that was first discussed by Exler and Schittkowski [37].The algorithm adapts concepts of SQP methods to mixed-integer nonlinear optimization.The new approach replaces the continuous quadratic problems by mixed-integer quadratic problems.The aim is to profit from the fast local convergence properties of SQP methods at least with respect to the continuous variables when integer variables remain fixed.Two new versions of the underlying algorithm of Exler and Schittkowski are presented.It is well-known that SQP methods might not converge for any arbitrary starting point.To obtain global convergence, techniques of trust region methods are employed by the new algorithms.The first version of an algorithm for MINLPs presented in this thesis employs the L ∞ -penalty function as merit function.Applying this penalty function might lead to a slow convergence.The so-called Maratos effect requires the reduction of the step length so that fast convergence is lost.Hence, safeguards have to be added.The presented algorithm calculates additional second order correction (SOC) steps.Calculating SOC steps is a frequently used approach to obtain fast local convergence.There also exist other techniques.The SOC steps require additional function evaluations.Frequently, function values of mixed-integer problems arising in the field of engineering are evaluated by running time-consuming simulation tools, where a single function evaluation can take minutes or even hours.Thus, the goal of the development of an efficient method has to be that the number of needed function evaluations is as small as possible.For that reason the investigation of methods that obtain fast local convergence without calculating SOC steps is the key aspect of this thesis.As a fundamental theory is available for NLPs, whereas MINLPs lack in most of these concepts, the main part of this thesis presents and analyzes a new trust region SQP algorithm addressing NLPs.The algorithm proposed here avoids the calculation of SOC steps by using an augmented Lagrangian function as merit function.In trust region methods a differentiable merit function, such as an augmented Lagrangian function, was employed in the past for equality constrained problems.Methods that also treat inequality constraints, transform these constraints into equality constraints.The new algorithm does not reformulate the underlying problem.The proposed algorithm for NLPs is described in detail.The global and local conv vi