Solving A Class Subproblem Euler Algorithm

Trust region algorithm is a class of important numerical methods for solvingunconstrained optimization problems. Researchers for nonlinear optimizationhave paid great attention to trust region method in the last twenty years since itsnew idea, reliability and strong convergence properties. At present, it and theline search method are two types of approaches to unconstrained optimizationproblems. In trust region algorithm, to solving the trust region subproblems isthe key for the realization of the trust region algorithm. And the solution of thetrust region subproblems affects the stability and convergence properties of thetrust region algorithm directly. After making great efforts, many kinds of modelsfor trust region subproblems have been proposed so far, such as quadratic model,conic model, new conic model, tensor model. However, the most basic andimportant model is quadratic model.At present, many methods have been proposed for solving trust regionsubproblems with quadratic model, for instance, accurate solution method,dogleg method, conjugate gradient method, and so on. Because the simple, lowcost and effective method is dogleg method. So it is commonly used for solvingtrust region subproblems with quadratic model. And this paper mostlyresearches the dogleg method for solving trust region subproblems withquadratic model. According to the idea of accurate solution method for solvingtrust region subproblems with quadratic model, a parametric equation of theoptimal curve is obtained. Then a differential equation model of the optimalcurve is constructed through the parametric equation. And three different Euler’stangents can be built by using Euler’s formula, implicit Euler’s formula andrectangle formula for solving differential equation, respectively. Then threeEuler’s algorithms are proposed for solving trust region subproblems withquadratic model. And the properties of the three Euler’s tangent paths aredemonstrated, the well-posedness about the three Euler’s algorithms areanalyzed, respectively. Numerical results also indicate that the three Euler’salgorithms are effective and practical.The content of this paper includes the following sections: In chapter one, the trust region algorithm, the trust region subproblems, theresearch status, the research hotspot and the work that we have done areintroduced, respectively.In chapter two, in the premise of Hessian matrix is positive definite, aparametric equation of the optimal curve is obtained according to the idea ofaccurate solution method for solving trust region subproblems with quadraticmodel. Then a differential equation model of the optimal curve is constructed bythe parametric equation.In chapter three, according the differential equation model of the optimalcurve in chapter two, an Euler’s tangent is built by using Euler’s formula. Thenan Euler’s tangent algorithm for solving trust region subproblems with quadraticmodel is proposed by using the Euler’s tangent instead of the optimal curve. Theproperties of Euler’s tangent paths are demonstrated, and the well-posednessabout Euler’s tangent algorithm is analyzed. And the numerical results alsoindicate that the Euler’s tangent algorithm is effective and practical.In chapter four, according to the differential equation model of the optimalcurve in chapter two, an implicit Euler’s tangent is constructed by using implicitEuler’s formula. Then an implicit Euler’s tangent algorithm is proposed forsolving trust region subproblems with quadratic model by using the implicitEuler’s tangent instead of the optimal curve. The properties of implicit Euler’stangent paths are demonstrated, and the well-posedness about implicit Euler’stangent algorithm is analyzed. And the numerical results also indicate that theimplicit Euler’s tangent algorithm is effective and practical.In chapter five, according to the differential equation model of the optimalcurve in chapter two, a mean Euler’s tangent is constructed by using rectangleformula. From the figure it can be seen that the mean Euler’s tangent is betweenthe Euler’s tangent and the implicit Euler’s tangent. Then a mean Euler’s tangentalgorithm is proposed for solving trust region subproblems with quadratic modelby using the mean Euler’s tangent instead of the optimal curve. The propertiesof mean Euler’s tangent paths are demonstrated, and the well-posedness aboutthe mean Euler’s tangent algorithm is analyzed. And the numerical results also indicate that the implicit Euler’s tangent algorithm is effective and practical.And the numerical results indicate that the mean Euler’s tangent algorithm iseffective and practical. And it also indicates that the mean Euler’s tangent ismuch closer to the optimal curve than the Euler’s tangent and the implicitEuler’s tangent.