Affine Trust Region Method And Research On Filter Line Search For Linear Constrained Optimization Problems

Trust-region method and line search technique are two fundamental strategies for solving the global convergence of nonlinear optimization problems.The trust-region concept minimizes an appropriate quadratic model that approximates the objective function in a region centered at current iterate point.By updating the trust region radius,we can obtain acceptable step.It can be used to solving non-convex approximate models and have strong convergence properties.Line search technique chooses its candidate step lengths which must satisfy strict feasibility easily by using a so-called backtracking approach and the computation is small when the new iteration point is determined.Filter method was initially introduced by Fletcher and Leyffer to guarantee the global convergence of the algorithm for solving nonlinear constrained programming and its main idea is that if the trial points improve the objective function or reduce the constraint violation degree,then the trial point is accepted.Such method is described by use of the dominance concept of multiobjective optimization,instead of a penalty parameter whose adjustment can be problematic.The nonmonotone technique can be embedded in the framework of trust-region or filter line search to solve nonlinear optimization problems.As point out by many researchers,nonmonotone schemes can improve the likelihood of finding a global optimum.A nonmonotonic criterion should bring about speed up the convergence progress in some ill-condition cases.In this thesis,we propose an affine scaling interior trust-region method combining with nonmonotone line search filter technique for linear inequality constrained minimization,this algorithm has global convergence and fast local convergence rate under some reasonable conditions.The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.Derivative-free algorithm does not force gradient information of objective function.Therefore,for complex function,the computational cost of method performance could be reduced.Chen and Sun proposed a dwindling multidimensional filter line search method for unconstrained optimization.Their idea is to introduce the inexact line search step-length into the multidimensional filter and let the envelope of the filter become thinner and thinner as the step-length approaches zero.In this thesis,an affine scaling interior derivative-free trust-region method with nonmonotone line search dwindling filter technique is considered for solving nonlinear optimization problems subject to bounds on variables in the absence of nondegeneracy assumption.The proposed algorithm is designed to take advantage of the problem structured by building polynomial interpolation models for the objective function.The proposed new method assures global convergence for firstand second-order critical points without using the switching condition used in the traditional line search filter technique.An identification function is introduced for the definition of the new affine scaling matrix in order to avoid nondegeneracy.The proposed method is shown to be locally quadratically convergent under the strong second order sufficiency condition without assuming nondegeneracy of the solution.Preliminary numerical results are reported indicating the practical viability and show the effectiveness of the proposed algorithm.There is a variety of evidence supporting the claim that randomized models can yield both practical and theoretical benefits for deterministic optimization.Most contemporary randomized methods generate random directions along which all that may be required is some minor level of descent in the objective function.Within direct search,the use of random positive spanning sets has also been recently investigated with gains in performance and convergence theory for nonsmooth problems.In this thesis,an affine scaling interior derivative-free trust-region method based on probabilistic with nonmonotone line search dwindling filter technique is considered for solving optimization problems subject to bounds on variables.This algorithm has global convergence and fast local convergence rate under some reasonable conditions.The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.The last chapter concludes the main results of this thesis and proposes some further research directions about our work.