Study On Homotopy Method For A Local Minimum Of Nonconvex Programming Problem

Since the combined homotopy interior point(CHIP) method has been published, we have proved the existence of homotopy path to the K-K-T point for nonconvex programming in bounded or unbounded set under the normal cone condition( or quasi-mormal cone condition even psendo-cone condition). Because extremum of the function doesn't have homotopy invariability, we can only get the K-K-T point of the nonconvex programming by the predictor-corrector algorithm. However, we prefer to local minimum or global minimum. In this paper, we study that, under what conditions, a local minimum can be obtained by the homotopy algorithm.Consider the following nonconvex programming problem:where f(x) is nonconvex smooth function, andwhere x ∈ Rⁿ, f(x),g_i(x)(i = 1, . m) are nonconvex smooth functions.For unconstrained optimization problem(UP), when n is an odd number, we construct homotopy equation as follows:H(t, x, x⁽⁰⁾) = (1 - t)(?)/(x) + t(x - z⁽⁰⁾) =0 (1)where H : [0,1] × Rⁿ → Rⁿ, x⁽⁰⁾ ∈ Rⁿ.When n is an even number, for unconstrained optimization problem:we construct homotopy equation as follows:H|-(t, X, X⁽⁰⁾) = (1 - t)(?)F(X) + t(X - X⁽⁰⁾) = 0 (2)where X<°) = | (0) | Gn+For constrained nonconvex programming problem(CiVCP), let Q = {x € i?" : gt(x) <0,t€{l,2--- ,m}}, fi° = {a;G/T :&(*)< 0,i € {1,2, ? ,m}},arc = n\n°.When n is an odd number, we construct homotopy equation as follows:( (lt)\yf(x) + Vg(x)y] + t(xxP)\ H(t,w) = I 1=0, (3)V Y{) tY{0)({°]) )where w =l (x,y) = (xT,yT)T efixi^, w^ =* {x^,y^) ï¿¡fi°x R?+, t ï¿¡ [0,1], g{x) = (9l{x), â–  gm(x))T, y = (yu â–  ym)T, Y = diag(y), and Vy(x) = (Vgi{x),---Vgm(x)).When n is an even number, we consider the following constrained nonconvex programming problem:min F(X) = f(x) + |a$+1s.t. gi(x) <0,i = 1,2, ?â– â– m. (CNCF)-1 < xn+1 < 1Let: ^(X) < 0,i E {1,2? ,m + 2}}, H° = {X € Rn+1 : ft(X) < 0, i G {1,2, â–  ? ? , m + 2}}. We construct homotopy equation as follows:Y"x -tr*> â–  x*> = ° (4)whereW =' (X,y') efix R?+2, W, y'W) 6 H° x i??+2, i e [0,1],V' = (l/i, â–  â–  ? ,yro+2)r, Y' = diagO/'), ff'PO = (Pi(z), ? ? â– gm(x),9m+i(X),gm+2(X))T, andV^'(X) = (V9l(x), â–  â–  â–  Vgm(x), Vgm+1(X), Vgm+2(X)). The basic assumptions in this paper:Assumption 1(Ai) 0° is nonempty(Slater's condition);(j42) {Vgi(x),i 6 I(x)} is a matrix of full column rank (regularity of the constraints);(A3) (The normal cone condition of Q)Vx G dfl, the normal cone of Q at x meets fi only at x, i.e. Vx G dï¿¡l,9i(x)Vi â–  Vi > 0, i € /(x)} f) O = {x};There is no solution at infinity for nonconvex programming in unbounded set;(A5) In this paper, we can eliminate saddle points in predictor-corrector algorithm.Under the Assumption 1, we have following main results:Theorem 1 For one-dimension searching problem in unbounded set, if we construct homotopy equation as (1), when the initialization point z^ is not a stationary point of f{x), the iterative points {x^} make {/(z^)} decrease monotonously in predictor-corrector algorithm, and when tk —* 0, {x^} converges to a local minimum of f{x).Theorem 2 For unconstrained optimization problem {UP), if homotopy map H is a regular map, and (UP) has no solution at infinity, when n is an odd number, we construct homotopy equation as (1), and when n is an even number, we construct homotopy equation as (2),then the K-K-T point x* obtained by homotopy algorithm is a local minimum.Theorem 3 For constrained nonconvex programming problem (CNCP), if homotopy map H is a regular map, and Assumption 1 holds, when n is an odd number, we construct homotopy equation as (3), and when n is an even number, we construct homotopy equation as (4),then the K-K-T point x* obtained by homotopy algorithm is a local minimum.Corollary 1 For constrained nonconvex programming problem (CNCP), if homotopy map if is a regular map, and Assumption 1 holds, when the objective function is convex, we construct homotopy equation as (3), then the K-K-T point x* obtained by homotopy algorithm is a local minimum.Corollary 2 For constrained nonconvex programming problem (CNCP), if homotopy map H is a regular map, and Assumption 1 holds, when all the K-K-T points are on the boundary of the feasible set, we construct homotopy equation as (3), then the K-K-T point x* obtained by homotopy algorithm is a local minimum.We use a predictor-corrector procedure for numerically tracing the homotopy path, and calculate the numerical solutions of some examples, and verify that the results is correct. Meantime, we find that, when n is an odd number, we construct homotopy equation for unconstrained programming problem as follows:H(t, x, x(0)) = (1 - t)Vf(x) - t(x - x^) = 0 (5)and when n is an even number, we construct as follows:H(t, X, X(o)) = (1 - t)VF(X) - t(X - X(o)) = 0 (6)where F(X) in (6) should be consructed as F(X) = f(x) — \x"^+v Under some proper conditions, when the algorithm is convergent, it must converge to a local maximum after we eliminate saddle points in the algorithm.When n is an odd number, we construct homotopy equation for constrained nonconvex programming problem as follows:Yg(x) - r<°>(??) jand when n is an even number, we construct as follows:H(t, W)=({1-t)|VFW " V'