Smoothing Homotopy Methods For Solving Several Mathematical Programming Problems

In this dissertation, some new smoothing homotopy methods for solving several math-ematical programming problems, including the mixed complementarity problem, the varia-tional inequality problem with polyhedral convex set, the nonlinear programming and the nonlinear semi-infinite programming, are proposed. Comparing with other existing homotpy methods, some of them are proven to be globally convergent under weaker assumptions, and some of them have higher efficiency under the same globally convergent conditions.In Chapter 1, we give a brief introduction of the background of the variational inequality problem, the nonlinear programming, the semi-infinite programming and related methods, especially the homotopy methods.In Chapter 2, a smoothing homotopy method based on the Robinson’s normal equation for solving mixed complementarity problems is proposed. We prove that if the smoothing projection operator is feasible, twice continuously differentiable and uniformly approximate to the projection operator, which can be satisfied for general smoothing projection oper-ators, and satisfies a special approximation property, then, under the condition that the mixed complementarity problem has no solution at infinity, the smoothing Robinson’s nor-mal operator satisfies the acute angle condition, for almost any starting point, existence and convergence of a smooth homotopy path are proven. Using a special example, we show that smoothing operators of other widely used equivalent nonsmooth equations may do not satisfy the acute angle condition, and their homotopy paths do not converge. We prove that the Chen-Harker-Kanzow-Smale smoothing projection operator satisfies the spe-cial approximation property, the smoothing Robinson’s normal operator satisfies the acute angle condition, and give a smoothing homotopy method for solving mixed complementarity problems. The global convergence condition of the proposed hoomotopy method is same to that of the homotopy method based on the equivalent KKT system, but the efficiency is higher. Numerical results on the MCPLIB test collection show that the proposed method is practicable, effective and robust.In Chapter 3, a smoothing homotopy method based on the Robinson’s normal equation for solving variational inequality problems with polyhedral convex set is proposed. We construct a new smoothing projection operator onto polyhedral convex set, which is feasible, twice continuously differentiable, uniformly approximate to the projection operator, and satisfies a special approximation property. It is computed by solving nonlinear equations in a neighborhood of the nonsmooth points of the projection operator, and solving linear equations with little variable coefficient matrices for other points, which makes it very efficient. Under the assumption that the variational inequality problem has no solution at infinity, existence and convergence of a smooth homotopy path from almost any starting point are proven. The global convergence condition of the proposed hoomotopy method is same to that of the homotopy method based on the equivalent KKT system, but the efficiency is higher. Preliminary test results show that the proposed method is practicable, effective and robust.In Chapter 4, to solve the nonlinear programming problem with many inequality con-straints, a flattened aggregate constraint function, a flattened aggregate constraint homo-topy method and a flattened aggregate shifting constraint homotopy method are presented. For the flattened aggregate constraint homotopy method, under the boundedness of the feasible set, positive linear independent constraint qualification and the normal cone con-dition for the feasible set, for almost any starting point in the interior of the feasible set, existence and convergence of a smooth homotopy path are proven. Without the normal cone condition for the feasible set, but if the feasible set can be regularly deformed into a convex set or a region satisfying the normal cone condition, the global convergence of the flattened aggregate shifting constraint homotopy method can be proven. In addition, the starting point is not needed to be an interior point of feasible set, and can be chosen as almost any point. Since the flattened aggregate (shifting) constraint function is related to the constraints whose function value are closed to zero, or even is a constant, it only needed to evaluate the gradients and the Hessians of few constraints or even none, the proposed method has high efficiency.In Chapter 5, a discretization-flattened aggregate shifting constraint homotopy method for solving nonlinear semi-infinite programming is developed. A shifting semi-infinite con-straint function is constructed, and the original problem is discreted into a sequence of finite-dimensional discretized subproblem using an adaptive discretization strategy, simul-taneously, the shifting semi-infinite constraint is discreted, then, the flattened aggregate shifting constraint homotopy method is used to solve the discretized subproblem. Under the boundedness of the shifting feasible set, positive linear independent constraint qualifica-tion for the shifting constraint and the normal cone condition for the initial shifting feasible set, we prove that the similar conditions hold for the discreted shifting constraints if the mesh size is sufficient small, consequently, existence and convergence of a smooth homotopy path, and the convergence of the discretization homotopy method are proven. Preliminary numerical results show that the proposed method is robust and efficient.In Chapter 6, a feasible set swelling homotopy method for solving nonlinear program-ming problems with general equality and inequality constraints is proposed. The homotopy map is constructed by transforming each equality constraint into two inequality constraints and using special shifting constraints. It is proven to be globally convergent under some relatively weak conditions, and can solve problems that can not be solved by other existing homotopy methods.