Weak Pseudo-normal Cone Condition Of Non-convex Programming Homotopy Interior Point Method

Optimization is an application of a wide range of subject,it discussed the best choice for the characteristic of the decision-making problems,structured calculation method to find optimal solution,researched theoretical and practical calculation of the performance of these calculation methods. With the rapid development of a computer and the progress of optimization calculation, the increasing size of the optimization problem has been solved. Because the optimization problem was broadly based on economic planning, engineering design, production management, transportation, defense and other important areas, it has been highly valued by government departments, research institutions and industrial sectors.The idea used the homotopy method to solve optimization problems began in 1979, but initially did not get a good response, until the discovery Karmarkar algorithm is essentially a homotopy method, the homotopy algorithm used to solve the optimization problems can be really active. Over the last decade, numerous researchers absorbed and carried forward the advantage of barrier function method and the center method, especially with the integration into the global convergence of homotopy methods, got a variety of interior-point path-following algorithm for solving the optimization problem. Since the 80 years to the late, Monterio & Adler, Kojima and others, respectively, extended the center of tracking linear programming primal-dual interior point algorithm to quadratic programming and a special class of convex programming problem. Subsequently, Kortanek, Potra & Ye, Wang Yu and others have also independently extended to general convex programming problem. Sonnevend & Stoer, Jarre and others extended the center of linear programming method to a convex programming problem, proposed the "analytic center method." Me Cormic, Fiacco & Mc Cormick and others have also established corresponding path tracking algorithm based on the convex programming problem in Karmarkar algorithm for linear programming. The above path-following method to prove convergence required the established logarithm obstacles function is strictly convex, and the solution set of the convex programming are bounded. In order to research the overall solution of non-convex programming problems,1993 Feng Guo-Chen, Yu Bo and Lin Zheng-hua proposed using the Combined Homotopy Interior Point Method which composed by Newton-homotopy and fixed-points homotopy for Solving Non-convex programming problem, and in the feasible region to fit the "cone condition",proved the algorithm convergenced the K-K-T point of the non-convex programming problems. Since then, when Yu Bo, Lin Zheng-hua and Feng Guo-Chen researching Combined Homotopy Interior Point Method of fixed points on non-convex region,they found the cone condition can be weakened to the proposed method cone, or even pseudo-cone conditions.This first chapter gives an overview of the development of the homotopy algorithm, the second chapter introduced the homotopy curve equation initial value problem of differential equationsdemand, as well as the specific steps of the path tracking algorithm, and gave some of the most basic concepts of optimization problems. In order to better research the optimal solution of homotopy equations for solving non-convex programming problem, the third chapter showed the definition of hair mapping, and gave a number of nature of the hair mapping,and gives the definition of hair mapping capacitive and prove some hair mapping have capacitive.Chapter four major researched to using the homotopy method for solving non-convex programming problems'K-K-T point. In the existing theories and based on the proof of the weak pseudo-cone conditions, proof the homotopy path existence and convergence. And constructed hair mapping to fit the conditions of weak pseudo-cone, in the feasible region bounded case, proof the homotopy algorithm can converge to K-K-T point of the demand problem. And gave concrete steps to achieve the algorithm, programmed and calculated the numerical examples.