| The mathematical programs with equilibrium constraints(MPEC)is a special optimization problem. In recent years, it is regarded more and more by people since the MPEC problems are of extensive and important application in economics and engineering. However, this class of optimization problems are very complicate. The complexity of constraints is the main difference between the MPEC problem and the general program problems, that is, its constraints include the equilibrium constraints besides the accustomed equation and inequality constraints. Therefore, serious attention has recently been paid to them. Theoretically, some new stationarity conditions are proposed under new constraint qualifications. On the other hand, the development of numerical methods for the solution of MPEC is at a less advanced stage than optimality theory. The main work of this paper is that the combined homotopy interior-point method is presented for solving several MPEC problems under appropriate conditions. This dissertation is organized as follows:Chapter 1: We introduce the past and the present in the theory and algorithm about the mathematical programs with equilibrium constraints and the difficult in the research. On the other hand, we describe the developmental process of the homotopy method. Chapter 2: We study the combined homotopy interior-point method for solving a class of mathematical programs with variational inequality constraints.In this chapter, we consider the following mathematical programs with variational inequality constraints:min f(x, y)s.t. x∈Z, (1)y∈S(x)≡SOL(F(x,.),C(x)),where f:Rn+m→R and F: Rn+m→Rm are continuously differentiable functions, Z = {x∈Rn : g(x)≤0} is a nonempty closed set, C(x) = {y∈Rm : G(x, y)≤0} is a closed convex set.First, we are inspired by [115] and construct the following combined homotopy equations for the lower-level constraints of the problem (1) under Assumption 2.2.1:thus the problem (1) is equivalent to the following one-level optimization problem:min f(x,y)s.t. g(x)≤0, (2)h(θ,t) = 0.Further, we construct the new combined homotopy equations for the problem (2) as follows:and under certain conditions, we prove that the homotopy (3) determines a smooth interior path from a given interior point to a KKT point of the problem (1). Theorem 1 Suppose that f, g and G are Cr(r > 2) functions, and Assumption A.2.2.1 hold, then the KKT system of (1) has solution asμis descending to 0, for almost allω0∈Ω(t), Hω00-1(0) contains a smooth curveΓω00, which stars from (ω0, 1). As t→0, the limit set is nonempty, and every point of (?) is a solution of (1), i.e., the KKT solution. Especially, ifΓω00 is finite, and (ω*,0) is the end point ofΓω00, thenω* is a KKT solution of(1)Second, we notice that the homotopy normal cone condition was on the homotopy mapping and not on the problem itself, so we are inspired by [57] and set the upper-level constraints of the problem (1) as follows:Z = {x∈Rn : h(x)≤0},C(x) = {y∈Rm: g(x,y)≤0},under Assumption A.2.3.1 and Assumption A.2.3.1, utilizing the smooth technique, we introduce the NCP functionφμ: R2→R :then the problem (1) is reformulated as an equivalent one-level smooth optimization problem , and the lower-level constraints become the following formSo we construct the new combined homotopy equations as follows:Under the normal cone condition, we prove the existence and large-scale convergence of the homotopy path. Theorem 2 Suppose that f and h are Cr(r>2) functions, and Assumption A.2.3.1 and the normal cone condition hold, then the KKT system of (1) has solution asμis descending to 0, for almost allω0∈Ω10×R++s×Rm+l+l, contains a smooth curveΓω0, which stars from (ω0, 1). Asμ→0, the limit set (?)×{0} (?)Ω1×R+s×Rm+l+l×{0} ofΓω0 is nonempty, and every point of (?) is a solution of (1), i.e., the KKT solution. Especially, ifΓω0 is finite, and (ω*,0) is the end point ofΓω0, thenω* is a generalized KKT solution of (1).Comparing with the combined homotopy interior-point method proposed under the homotopy normal cone condition, the assumption conditions of the combined homotopy interior-point method proposed under the normal cone condition are ordinary and more easily applied to the other problems.Finally, we further loosen up the assumption conditions and construct the homotopy equation as follows:Under the quasi normal cone condition, we prove the existence and large-scale convergence of the homotopy path.Theorem 3 Suppose that f and h are Cr(r > 2) functions, and Assumption A.2.3.1 and the quasi normal cone condition hold, then the KKT system of (1) has solution asμis descending to 0, for almost allω0∈Ω10×R++s×Rm+l+l, contains a smooth curveΓω0, which stars from (ω0,1). Asμ→0, the limit set (?)×{0} (?)Ω1×R+s×Rm+l+l×{0} ofΓω0 is nonempty, and every point of (?) is a solution of (1), i.e., the KKT solution. Especially, ifΓω0 is finite, and (ω*, 0) is the end point ofΓω0, thenω* is a generalized KKT solution of (1).The combined homotopy interior-point method proposed under the quasi normal cone condition extend the field of solving the MPEC through constructing the appropriate positive independent mapsη(x).Some numerical result are presented to show the effectiveness of three combined homotopy interior-point methods.Chapter 3: We study the combined homotopy interior-point method for solving a class of mathematical programs with complementarity constraints.In this chapter, we consider the following mathematical programs with complementarity constraints:min f(x, y)s.t. h(x)≤0, (7)0≤F(x,y)⊥y≥0,where f : Rn+m→R, h : Rn→Rs, F : Rn+m→Rm are continuously differen-tiable functions.First, we transform the problem (7) to the following nonsmooth optimization problemmin f(x,y) s.t. h(x)≤0,F(x,y)-z = 0, -2min(z,y) = 0,then through utilizing the smooth technique, we introduce the NCP function (4) and define the nonlinear operatorthen the problem (8) is transformed into the following optimization problemmin f(x,y)s.t. h(x)≤0, (9)Hμ(θ) = 0. Thus we construct a homotopy equation for solving the problem (9) as follows:Under ordinary conditions, we prove the existence and large-scale convergence of the homotopy path.Theorem 4 Suppose that f and h are Cr(r > 2) functions, and Assumption A.3.4-1 hold, then the KKT system of (?) has solution asμis descending to 0, for almost allω0∈Ω10×R++s×Rm+m, (H|)ω00-1(0) contains a smooth curveΓω0, which stars from (ω0,1). Asμ,→0, the limit set (?)×{0} (?)Ω1×R+s×Rm+m×{0} ofΓω0 is nonempty, and every point of (?) is a solution of (?), i.e., the KKT solution. Especially, ifΓω0 is finite, and {ω*,0) is the end point ofΓω0, thenω* is a generalized KKT solution of (?).At last we give some computational results.Chapter 4: We study the combined homotopy interior-point method for solving a class of bilevel programming problem.In this chapter, we consider the following bilevel programming problem: where (x,y)∈Rn+m, f : Rn+m→R and F : Rn+m→R are the upper-level objective function and the lower-level objective function respectively. g = (g1,…,gs)T : Rn→Rs and G = (G1,…,Gl)T : Rn+m→Rl are the upper-level constraints and the lower-level constraints.We present the combined homotopy interior-point method for solving the problem (11) under certain assumptions. First, the problem (11) is transformed into an equivalent one-level nonsmooth optimization problem through the KKT system of lower-level optimization problem. In order to avoid the difficult of solving the nonsmooth constraints, we introduce the NCP function (4) to make it become the smooth optimization problem. Further we construct the combined homotopy equations as follows:Finally, we prove that the existence of the combined homotopy pathway is ordinary, and that this combined homotopy method large-scale converges to a generalized KKT point of (11). Numerical tracing homotopy pathway gives a globally convergent algorithm.Theorem 5 Suppose that f, g and h are Cr(r > 2) functions, and Assumption A.4.2.1 and the normal cone condition hold, then the KKT system of (11) has solution asμis descending to 0, for almost allω0∈Ω10×R++s×Rm+l+l, (H|)ω00-1(0) contains a smooth curveΓω0, which stars from (ω0,1). Asμ→0, the limit set (?)×{0} (?)Ω1×R+s×Rm+l+l×{0} ofΓω0 is nonempty, and every point of 0 is a solution of (11), i.e., the KKT solution. Especially, ifΓω0 is finite, and (ω*,0) is the end point ofΓω0, thenω* is a generalized KKT solution of (11).The combined homotopy interior-point method proposed under weaker conditions in Chapter 4 improves the assumption conditions, which are used by the homotopy method proposed in [115], and its assumption conditions are ordinary and more easily applied to the other problems. Some preliminary computational results are reported.
|
PDF Full Text Request