Font Size: a A A

Linearly Constrained Optimization Problems Interior Affine Scaling Optimal Path

Posted on:2006-06-13Degree:MasterType:Thesis
Country:ChinaCandidate:Y J WangFull Text:PDF
GTID:2190360152481592Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Optimization is an important tool in decision science and in the analysis of physical sys-tems. In this thesis, we propose an affine scaling optimal path approach in association with non-monotonic interior backtracking line search technique for nonlinear optimization subject to linearequality and inequality constraints.Trust region strategy is a well-accepted method in the nonlinear programming to assureglobal convergence. The idea behind a trust region method for unconstrained minimization isintuitive and simple. But for constrained minimization, constraints will make it difficult to for-mulate a similar subproblem. Recently, Coleman and Li presented a trust region affine scalinginterior point algorithm for the minimization problem subject only to linear inequality constraints.By using affine scaling to formulate an appropriate quadratic function and trust region, difficul-ties imposed by constraints are overcome. And furthermore, the authors analyzed and proved theconvergence properties of the proposed method. But in that article, the authors didn't give thematerial methods to solve the subproblem. In fact, it is possible the trust region subproblem withthe strictly feasible constraint needs to be resolved many times before obtaining an acceptablestrict interior feasible step, and hence the total computation for completing one iteration might beexpensive and difficulties. In order to overcome the difficulties brought by solving the trust regionsubproblem, we may resort to use some curvilinear paths to search for the trial steps, and usuallythese paths can be expressed by the eigenvalues and eigenvectors of the exact or inexact Hessianmatrix.In this paper, we introduce the affine scaling matrix, similar to the curvilinear path, to gen-erate an affine scaling optimal path in which we use the curvilinear search instead of the truststrategy. Using both the affine scaling optimal path search strategy and line search technique, thequadratic model at each iteration generates a backtracking step to obtain a new accepted step. Theenforcement of a monotonic decrease of the objective function values may have dangerous effectsin the minimization of highly nonlinear functions with the presence of steep-sided valleys, sincethe search for lower function values may cause any minimization algorithm to be trapped in thebottom of a valley. The nonmonotonic idea motivates to further study an affine scaling optimalpath approach in association with nonmonotonic interior backtracking line search technique fornonlinear optimization subject to linear equality and inequality constraints (1.2).In this theses, we firstly summarize some relative concepts and theories of optimization tech-nique, as the basis material for the further study, then propose an affine scaling optimal curvilinear...
Keywords/Search Tags:Nonlinear constrained programming, Global convergence, Local convergence rate, Trust region method, Nonmonotonic technique, Interior point method
PDF Full Text Request
Related items