On intrinsic complexity of bilevel optimization

Abstract:

We examine bilevel optimization from the parametric perspective. Observing the intrinsic complexity of bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity we understand the involved geometrical complexity of bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation eects. By taking the study of singularities in parametric optimization into account, the structural analysis of bilevel feasible sets is performed. We describe the global structure of the bilevel feasible set in case of a one-dimensional leaders variable. We point out that the typical discontinuities of the leaders objective function will be caused by followers singularities. The latter phenomenon occurs independently from the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are till then.

Posted on Aug 13, 2013 in Optimization and Equilibrium, Seminars