An Aggregate Homotopy Interior Point Method For Nonconvex Constrained Min-Max Problems

Consider the following nonconvex constrained Min-Max problom: min Fix) s.t. gi(x) ≤ 0 i = 1, … , m. (1)where x ∈ Rⁿ and F(x) = max{f_j(x), j = 1, … ,p}.The following assumptions are used in this paper.(c1) f_j(x)(j = 1, … ,p) and g_i(x)(i = 1, … ,m) are all two times continuously differentiable function;(c2) Ω is bounded and Ω⁰ is nonempty (slater condition);(c3) For any x ∈(?)Ω,, the matrix {(?)g_i(x) : i = 1, … , m} has a full column rank (regularity of (?)Ω);(c4) There exists a closed subset Ω|^, (?) Ω⁰ with nonempty interior (Ω|^)⁰, such that Ω satisfies the weak nomal cone condition w.r.t. Ω|^.In this paper ,using the advantages of the combined homotopy interior point method for nonconvex programming and the effectivities of the aggregate function for smooth programming, we present an aggregate homotopy interior point method for nonconvex constrained Min-Max problems. We have proved that for almostall #(°) G ft0,the aggregate homotopy epuation generates a smooth curve Fw(o) starting from (w^°\ 1). And it limits to a K-K-T point. Tracing numerically Fw(o) ,one can find a solution of (1) .Firstly ,we construct the following aggregate function introduced in ([3],[50],[51]):F(x,t)=t\nJ2exp(fj(x)/t). (2)andG(x, 9t) = 0* In V exp(gi(x)/0t). (3)where B G (0,1] .When t —> 0, F(x,t) and G(x,0t) converge monotoically anduniformly to Fix) and G(x) = max {&(#)}, respectively.\c3 hold, then there exists a 6 G (0,1], such that for any t € (0,1], the boundary of Q,e(t), i.e., Vx G dQ9(t), VxG(x,6t) ^ 0 .proposition 1.4 If assumptions (cl),(c2) and (c4) hold, then for any closed subset N C Cl, there exists a 9 E (0,1], such for any Vt G (0,1], Q,e(t) satisfies the weak normal cone condition w.r.t. N.Secondly,by utilizing aggregate function,we construct the following aggregate homotopy equation:where w = (x,y) G Rn+\w^ = (x<°\ y<°)) G Q°e(t) x R\+ and ^ G (0,1] is a given constant.We refer (4) as the" aggregate homotopy " and the corresponding algorithm as the " aggregate homotopy interior point method " because the equation is defined by aggregate function and it is also a homotopy equation.Under the assumptions , we can prove that the aggregate homotopy path is existence and boundedness and the aggregate homotopy interior point method is globally convergent.lemma 1.1 // assumptions (cl) (c4) hold , Hw{o)(w,i) is defined as (3.1). then for almost all i^ G Sle(t) and y^> > 0, 0 is a regular value of Hw?? : Sle(t) x R\+ x (0,1] -)? Rn+1, and #^l(0) consists of some smooth curves . Among them ,a smooth curve ,say Twis>), is starting from {w^\ 1).lemma 1.2 // assumption (cl) (c4) hold, for a given w^ G ^M^)> if 0 is a regular value of Hw{o), then Vw{o) is a bounded curve in Q°d(t) x R}++ x (0,1] .theorem 1.1 (Convergence of the method) If assumptions (cl) (c4) hold, then (2.13) has at least one solution. For almost all it/0) 6 Q° x -R++, the zero-point set H^lo)(0) of homo-topy map (3.1) contains a smooth curve Tw(o) C f2° x R\+ x (0,1], which starts from (w^°\ 1) . As t ->â–  0+ , the limit set T x {0} C Q° x R\ x {0} ofVw(o) is nonempty,and every point in T is a solution of (2.13).Specifically, if the lenth ofTw(0) is finite and {w*,0) is the end point ofTw(o), then w* is a solution of (2.13) .