The Complexity Analysis For The Homotopy Method Of Non-convex Programming

Application optimization is a very broad range of disciplines, the method has been widely used in science, engineering and economic and other important areas, as government departments, research institutions and industry a powerful tool for scientific decision making. Non-convex optimization problems and complexity of the effective analysis method is an important research direction.Complexity theoretical results on the use and development of the algorithm has some inspiration. The field of complexity theory design and analysis of efficient algorithms on the one hand, the other from the perspective of two opposing algorithm problem. An efficient algorithm can be directly used to solve the problem and the problem itself, is an effective proof of the solvability. Instead, the goal of complexity theory difficult problem is to prove that with limited resources can not be resolved.Most existing algorithms on constrained optimization can only find the local minimum (or stationary point), but many of the practical problems demanding global minimum. We learn from some of the methods in global optimization the financial value decreased levels of thinking on the problem of a class of nonconvex global optimization algorithm is studied.We know that with the combination method of convex programming found that without adding other conditions can get the corresponding global convergence algorithm; and the usual assumption (from the harmonious conditions), by segment analysis techniques, homotopy path to overcome the difficulties caused by non-monotonic, has been similar to other interior point polynomial complexity estimation, but also the corresponding linear complementarity problem and the complexity of nonlinear complementarity problems estimates has also been a similar outcome. But for non-convex case the complexity of the algorithm is also without any results, this study is necessary.This paper studies the feasible region to meet the conditions of the non-convex cone Homotopy planning complexity of the algorithm, in ordinary conditions,non-convex programming proved Homotopy complexity of the algorithm. Secondly, the use of polynomial matrix of the second discrimination, based on the level of decline in the value of ideas, build a polynomial function minimization problem of global optimization algorithms, numerical experiments show that the new algorithm is very effective.