Font Size: a A A

Trust Region Interior Point Algorithms For Nonlinear Constrained Optimization Problems

Posted on:2005-02-13Degree:MasterType:Thesis
Country:ChinaCandidate:Y M GuFull Text:PDF
GTID:2120360122980535Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Optimization is an important tool in decision science and in the analysis of physical systems. It has the wide (and growing) applications in science, engineering, economics and industry, etc. Nonlinear programming is an important and active branch of optimizations. In this thesis, we propose three trust region interior algorithms for three different nonlinear optimizations, respectively.Both line search and trust region are well-accepted methods in the nonlinear programming to assure global convergence. In this thesis we propose a scaling trust region interior point algorithm for linear constrained optimization subject to bounds on variable. We use a scaling matrix which make the algorithm generate sequences of point in trust region and the interior of the feasible set. Because of the boundedness of the trust region, trust region algorithm can use non-convex approximate models. A solution that minimizes the model function within the trust region is solved as a trial step. If the actual reduction achieved on the objective function / at this point is satisfactory comparing with the reduction predicted by the quadratic model, then the point is accepted as a new iterate, and hence the trust region radius is adjusted and the procedureis repeated. Otherwise, the trust region radius should be reduced and a new trial point needs to be determined. We show the proposed algorithm is globally convergent and locally fast convergent rate even if conditions are reasonalbe. The results of numerical experiment are reported to show the effectiveness of the proposed algorithm for linear constrained optimization subject to bounds on variable.We also propose an affine scaling trust region interior point algorithm via double dogleg path for nonlinear optimization subject to bounds on variables. It is posssible that the trust region subproblem needs to be resolved many times before obtaining an acceptable step for the traditional trust region method, and hence the total computation for completing one iteration might be expensive. Nocedal and Yuan suggested a combination of the trust region and line search method for unconstrained optimization. This mixed technique is called backtraking. The plausible remedy motivateds to switchto the line search method by employing the backtracking steps at an unsuccessful trial step. Of course, the prerequisite for being able to making this shift is that although the trial step is unacceptable as next iterative point, it should provide a direction of sufficient descent. For problems whose objective function or constraint functions have sharp curves on their contour maps (such as the Rosenbrock's function which has banana shape contours), monotonicity may cause a series of very small steps, causing a huge number of iteration to reach their solutions. By using the nonmonotone technique, we get the sequence of successful interative point which should make the objective function mono-tonically decreasing. Hence, we use both trust region strategy and line search technique and make each iterate generate an acceptable trial step in interior feasible set as next interative point. The double dogleg path method, which makes use of the information of Cauch step and Newton step, was proposed by Dennis and Mei. Based on double dogleg path, the iterative direction is always obtained in the intersection of double dogleg path and bound of trust region by solving the affine scaling trust region subproblem. By giving some properties of the double dogleg path, we prove the global convergence and fast local convergence rate of the proposed algorithm under some reasonable conditions. A nonmonotonic criterion is used to speed up the convergence progress in some ill-conditioned cases. The results of numerical experiment are reported to show the effectiveness of the proposed algorithms.Reduced Hessian algorithm has became one of the very popular and most effecive methods for solving nonlinear equality constrained programming. Recently, Chaya Gur-witz proposed the two-piece update of a projected Hessian matrix...
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