EPSRC logo

Details of Grant 

EPSRC Reference: EP/P022553/1
Title: Newton-type methods for bilevel optimization
Principal Investigator: Zemkoho, Dr A
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: School of Mathematics
Organisation: University of Southampton
Scheme: First Grant - Revised 2009
Starts: 03 July 2017 Ends: 02 January 2019 Value (£): 100,929
EPSRC Research Topic Classifications:
Mathematical Aspects of OR
EPSRC Industrial Sector Classifications:
Healthcare Transport Systems and Vehicles
Related Grants:
Panel History:
Panel DatePanel NameOutcome
28 Feb 2017 EPSRC Mathematical Sciences Prioritisation Panel March 2017 Announced
Summary on Grant Application Form
A bilevel optimization problem is an optimization problem with a hierarchical structure featuring a leader (upper-level player) and a follower (lower-level player). The problem is very attractive in modeling real-world problems involving two levels of decision-making. Problems in economics, engineering, health, environmental sciences and other areas of mathematics have been successfully modeled using the bilevel paradigm. Mathematically, the main issue with the structure of the problem is that part of the feasible set of the upper-level problem is defined by the solution map of the lower-level problem. Because of this, the standard optimization theory and the corresponding numerical methods are not applicable. For instance, in the process of constructing a Newton method in standard nonlinear optimization, constraint qualifications are needed to ensure that the method is well-defined. Standard constraint qualifications systematically fail for bilevel optimization problems.

The Newton method is one of the most powerful techniques to solve nonlinear system of equations. Over the years, it has been successfully extended to various classes of optimization and closely related problems. The method is the base of a large number of commercial and open source optimization software, and is crucial in solving subproblems in popular algorithms such as augmented Lagrangian and interior point methods. Considering this success in other areas of optimization, we will be proposing cutting-edge techniques, which once combined with the Newton scheme, will lead to efficient algorithms for the bilevel optimization problem.

Precisely, we will develop a semismooth Gauss-Newton method and a semismooth Newton-type method to compute the weak and strong stationary points, respectively. We will also construct a general purpose solver based on these two methods. In the process, important gaps in the literature on bilevel optimization will be filled, including the development of second order sufficient conditions and approximation schemes allowing constraint qualifications to be fulfilled. The continuous optimization community will benefit from the Hessian consistency property that will be introduced and studied in the context of the approximation of the lower-level value function, in the process of constructing the semismooth Newton-type method. The Hessian consistency property will be crucial for the construction of (general) nonsmooth optimization Newton-type methods, for which work is still at an early stage. The development of the Gauss-Newton-type method will provide the optimization and numerical analysis communities with new paths for solving non-square nonsmooth systems of equations.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.soton.ac.uk