The Combined Homotopy Methods For Optimization Problem With Partial Reverse Convex Constraints

As a globally convergent method, the homotopy method has become an important tool for numerically solving nonlinear problems. For convex programming, combined homotopy interior point method(CHIP method)has exhibited its advantages. Under the normal cone condition or the quasi-normal cone condition, it has been proven, for nonconvex programming problem, that the algorithm generated by CHIP method exhibiting global convergence. When the feasible set of the nonconvex programming satisfy the quasi-normal cone is the key to realize CHIP method. However, it is complex to construct the quasi-normal cone , due to the complexity of the nonconvex programming, until now, there isn't universal method on how to construct the quasi-normal cone. We give respectively the structure method of the quasi-normal for two kinds partial reverse convex constraints feasible set, and construct conbined homotopy, apply predictor procedure and test it through examples.Consider the following nonconvex programming problem:min f(x)st g_i(x)≤0,i=1,…,m (1)where x∈R~n, and f,g_i are suffiently smooth functions. The following basic conditions are commonly used in this paper. A_q) Ω is bounded and connected , Ω~0 is nonempty (Slater'scondition);A2) yxedQ,{Vg(x)l\isI(x)} is a matrix of full column rank(regularity of the constraints) This paper consists of five chapters:Chapter I Introduction Which summarize the basic principles and knowledge of the homotopy method, the development history of the CHIP method in the optimization field,and the domestic and international research present situation,and introduce the basic knowledge of CHIP method briefly, It also introduce the content and research results of this passage briefly.Chapter II Ppreparatory Knowledge It will introduce the basic conceptions and theories of the CHIP. In this chaper, we have the following conditions:Ax) fi is bounded and connected , Q° is nonempty ( Slater' scondition);A2) Vxedn,C = {zzRn\zrVgl(x) (Cottle C.Q);A3) {Tjt(x)} is a positive irrelative co-rJ^g^x^QsM) . and Q,satisfy the quasi-normal cone condition a).rJ{rji(x)}. We construct combined homotopy as following:where g>{0) =(x(0),y{0))eQ° xR?+ o And prove that the homotopy (2), generates a smoothpath from almost all interior point to a solutionof the K-K-T. system of (1), We can trace this smooth path to find aK-K-T point of (l),We can trace this smooth path to find a K-K-Tpoint of (1) by some numerical continuation algorithm.Theorem 1 Suppose /,￡,(/em) are twice continuouslydifferentiable functions, and conditions^,), A2), ^3)hold, then {he K-K-T system of (1) has at least a solution. For almost all 0, thelimit set rx{0}cQxi?"x{0} is nonempty, every point in T is a solution of the K-K-T system.Specially , if the length of F (0) is finite and (a\ax -26, >a[a2 -2b2>0,2)#i(*) = 0 and g2(x) = O intersect with each other, and a] a2 - a\ a2+bl-b2<0,~°n ■ Q.1 a laTa 2b a' ~a° CQ.° a-aO||— a2 (?= ° includes ingo(;c)0, ]?>, >0}Dn° =O./e/(.t) iel(x)We adopt the predictor-corrector procedure and make up the computation procedure with the Matlab language, we have got a good digital result.Chapater IV For the partial reverse convex constraints (II), consider the following constrained functions:1 ... ...= -x'x-a!>x + bo0,We adopt the predictor-corrector procedure and make up the computation procedure with the Matlab language,we have got a good digital result.Chapter V Finally We sum up the major results of this paper, and make the suggestions for further research .