Font Size: a A A

Feasibility Safeguard Methods For Nonlinear Programming With Applications

Posted on:2014-01-02Degree:DoctorType:Dissertation
Country:ChinaCandidate:S Q QiuFull Text:PDF
GTID:1220330398471299Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
This paper is concerned with the properties, numerical performances and applica-tions of a new class of penalty-free algorithms for nonlinear constrained optimization.One of the characteristics of these algorithms is that they do not use any penaltyfunction to balance the objective function and the constraints. Hence, the difcultyof choosing proper penalty factor is avoid. Nor do these algorithms uses the filtertechniques. Therefore, the additional calculation caused by maintaining and updatingfilters and the blocking of productive steps by entries in filters are circumvented. Forthese reasons, this class of algorithms have the potential to be developed into practicalapplications.The key idea of the proposed algorithms is the control of the infeasibility of theiterates. In constrained optimization, the minimization of infeasibility always has prior-ity. Algorithms here require the infeasibility measure of iterates not to exceed an presetupper limit and try to reduce the value of objective function under the constraints ofinfeasibility limit. Global convergence is achieved by reducing the infeasibility limitdynamically.Another important idea of these algorithms is how to keep the balance betweenthe feasibility and the optimality. To achieve this purpose, these algorithms comparethe measures of infeasibility and optimality or the predicted reductions of infeasibilityand optimality. After comparison, the algorithms decide whether to improve feasibilityor to reduce the objective function. Besides, the reduction achieved by trial step shouldbe comparable to the current constraint violation.Some algorithms in this paper follow SQP trust region approaches while othersbelong to the interior point methods. SQP methods and interior point methods are twoclasses of well studied and widely used methods in constrained optimization. Firstly, weintroduce the original ideas of the algorithms in a framework of Byrd-Omojokun-typecomposite trust region method for equality constrained optimization. An improvementof the original algorithm and an deeper convergence analysis are given in the nextchapter. Then the basic ideas of this algorithm are applied to solving problem withequality and box constraints and inequality constrained problem respectively. Somenumerical tests are implemented which show that the performance of these algorithmsare encouraging.Other algorithms belong to the interior point methods. A barrier function interior point method and a central neighborhood interior point method are given in two chap-ters. The first algorithm combines the ideas of the previously presented algorithmsand the classical barrier function interior point methods. Global convergence is shownand numerical results are reported. In the part of central neighborhood interior pointmethod, we discuss how to avoid the blocking of productive steps as possible as itcan be. The algorithm presented in this part keep the basic ideas of the feasibilitysafeguard algorithms but with some important modifications in the efort of avoidingblocking of good steps. Global and local convergence are analyzed.As an application, we try to use this class of algorithms to solve nonlinear com-plementarity problems. We convert the nonlinear complementarity problem into anonlinear constrained optimization problem with a simple objective function. The lat-ter problem satisfies MFCQ at all feasible points and thus is easy to be solved. Aclass of penalty-free sequential programming methods are developed. In practice, wealso suggest some ways to prevent the algorithm from converging to local optimum.We also test these algorithms in a set of test problems collected from some publishedliteratures.
Keywords/Search Tags:Feasibility safeguard method, SQP trust region algorithm, primaldual interior point method, global convergence, local superlinear convergence, nonlinearcomplementarity problem
PDF Full Text Request
Related items