Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Computational Math

Jane Ye

University of Victoria, Canada

On solving bilevel programs with a nonconvex lower level program by smoothing techniques

Abstract:

A bilevel program is a sequence of two optimization problems where the constraint region of the upper level problem is determined implicitly by the solution set to the lower level problem. The classical approach to solve a bilevel program is to replace the lower level program by its first order optimality condition. This approach, however, is not valid for the case where the lower level program is nonconvex. The reformulation based on the value function of the lower level program, on the other hand, is completely equivalent to the original bilevel program but may not have the optimal solution of the bilevel program as a stationary point. The combined program with both the value function constraint and the first order condition is much more likely to have the optimal solution as a stationary point. Since the value function is in general a nonsmooth function, we propose to solve the problem by smoothing techniques. Using smoothing technique, we approximate each nonsmooth Lipschitz continuous function by a family of smoothing functions. We use certain penalty based methods to solve the smooth problem and drive the smoothing parameter to infinity. Based on the sequence of iteration points and the family of smoothing functions we introduce the weak extended generalized Mangasarian-Fromovitz constraint qualification (WEGMFCQ). We show that if the WEGMFCQ holds at the accumulation point of the iteration points, then the accumulation point is a stationary point of the nonsmooth optimization problem. Numerical experiments show that while the EGMFCQ never hold for bilevel programs, the WEGMFCQ may hold for bilevel programs easily.

Host: Jiawang Nie

September 24, 2013

11:00 AM

AP&M 2402

****************************