Linear Constrained Optimization Problem Of The Affine Subspace Trust Region Algorithm

Optimization is an important tool in decision science and system analysis, and can be widelyused in many domains. In this thesis, we propose an affine scaling subspace trust region approachin association with interior backtracking line search technique for nonlinear optimization subjectto linear equality 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 formu-late a similar subproblem. Recently, Coleman and Li present a trust region affine scaling interiorpoint algorithm for the minimization problem subject only to linear inequality constraints. Byusing affine scaling to formulate an appropriate quadratic function and trust region subproblem,difficulties imposed by constraints are overcome. And furthermore, the authors analyzed andproved convergence properties of the proposed method. But in that article, the authors didn't giveany material method to solve the subproblem. In fact, it is obvious the trust region subproblemwith strictly feasible constraints 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 difficult. In order to overcome a series of difficulties brought by solving the trustregion subproblem, we may resort to use subspace method, trust region algorithm and interiorback-tracking line search technique to search for acceptable strict interior feasible steps. Due tothe special structures of the subspace technology, the method can be applied to solve very largescale problems.In this paper, we firstly review some relative concepts, theories and techniques as the ba-sic knowledge for further study, then introduce a relevant affine scaling matrix, and formulate anappropriate quadratic function and a trust region subproblem. Upon the subspace technique, wesolve the trust region subproblem in the proposed subspace to obtain trial steps. Furthermore, com-bine the interior back-tracking line search strategy to finally get an acceptable step length whichis strictly feasible and makes the objective function monotonically decrease. Follow that, basedon good properties of the subspace method, weak global convergence and strong global conver-gence and local convergence rate of the proposed method are established under some reasonableconditions. Numerical results indicate that the algorithm is useful and effective in practice.