Study On Numerical Algorithms For A Class Of Bilevel Programming Problems

Bilevel programming problems have numerous applications in economic equilibrium, engineering design and transportation. In the case where the lower level program is a convex program, the general practice to solve a bilevel program is to replace the solution set of the lower level program by it’s KKT points and solve a mathematical program with equilibrium constraints (MPEC). However, for the case where the lower level program is not convex, it seems very difficult to solve the bilevel program. While most of the works assume that the lower level program is convex with few exceptions. In this paper, we propose some algorithms to solve bilevel programs with nonconvex lower level program. Furthermore, we apply the algorithm to the semi-infinite programs.In chapter3, by using the value function of the lower level program, we reformulate the bilevel program as a single level optimization problem with a nonsmooth inequality constraint and a convex set constraint. To deal with such a nonsmooth and nonconvex optimization problem, we design a smoothing projected gradient algorithm for a general optimization problem with a nonsmooth inequality constraint and a convex set constraint. We show that, if the sequence of penalty parameters is bounded then any accumulation point is a stationary point of the nonsmooth optimization problem and, if the generalized sequence is convergent and the extended Mangasarian-Fromovitz constraint qualification holds at the limit then the limit point is a stationary point of the nonsmooth optimization problem. We apply the smoothing projected gradient algorithm to the bilevel program if a calmness condition holds and to an approximate bilevel program otherwise.In chapter4, we propose to solve a combined problem where the first order condition and the value function are both present in the constraints. Since the value function is in general nonsmooth, the combined problem is in general a nonsmooth and nonconvex optimization problem. We propose a smoothing augmented Lagrangian method for solving a general class of nonsmooth and nonconvex constrained optimization problems. We show that, if the sequence of penalty parameters is bounded, then any accumulation point is a stationary point of the nonsmooth optimization problem. The smoothing augmented Lagrangian method is used to solve the bilevel problem.In chapter5, we consider an optimization problem with both the objective function and the constraint functions possibly nonsmooth and nonconvex. We use smoothing functions with the gradient consistency property to approximate the nonsmooth functions and introduce a robust sequential quadratic programming (SQP) algorithm. We show that any accumulation point of the iteration sequence generated by the smoothing SQP algorithm is a Clarke stationary point, provided that the sequence of multipliers and the sequence of exact penalty parameters are bounded. Furthermore, we propose a new condition called the weakly generalized Mangasarian Fromovitz constraint qualification (WGMFCQ) that is weaker than the GMFCQ. We show that the extended version of the WGMFCQ guarantees the boundedness of the sequence of multipliers and the sequence of exact penalty parameters and thus guarantees the global convergence of the smoothing SQP algorithm. We demonstrate that the WGMFCQ can be satisfied by bilevel programs for which the GMFCQ never holds. Preliminary numerical experiments show that the algorithm is efficient for solving the simple bilevel program.In chapter6, we propose to solve a nonsmooth and nonconvex optimization problem by a smoothing augmented Lagrangian method. We show that any accumulation point of the iteration sequence generated by the algorithm is a stationary point provided that the penalization parameters are bounded. Furthermore, we show that the extended weakly generalized Mangasarian Fromovitz constraint qualification (EWGMFCQ) guarantees the boundedness of the penalization parameters and thus the global convergence of the algo-rithm. Since the WGMFCQ may hold even when GMFCQ does not hold, our algorithm is applicable for solving a degenerated optimization problem where the GMFCQ does not hold, including the bilevel programs.In chapter7, we study a semi-infinite programming (SIP) problem with a convex set constraint. Using the value function of the lower level problem, we reformulate SIP problem as a nonsmooth optimization problem. Using the theory of nonsmooth Lagrange multiplier rules and Danskin’s theorem, we present constraint qualifications and necessary optimality conditions. We propose a new numerical method for solving the problem. The novelty of our numerical method is to use the integral entropy function to approximate the value function and then solve SIP by the smoothing projected gradient method. Moreover we study the relationships between the approximating problems and the original SIP problem. We derive error bounds between the integral entropy function and the value function, and between locally optimal solutions of the smoothing problem and those for the original problem. Using certain second order sufficient conditions, we derive some estimates for locally optimal solutions of SIP.