Approximation theory for two-level value functions with applications

点击翻译按钮获取中文摘要

A two-level value function is an optimal value function of a parametric optimization problem where the feasible set is described by the optimal solution set of another optimization problem. The primary goal of this project is to develop, for the first time ever in the literature, explicit approximations of two-level value functions. Being able to approximate these functions will enable the design of simple and efficient algorithms for unsolved problems in various areas of optimization, including multilevel, robust, and stochastic optimization. As pessimistic bilevel optimization represents the most prominent application of two-level value functions, the efficiency of the approximations developed in this project will be evaluated though algorithms to be constructed to solve the pessimistic bilevel program. This is one of the most challenging problems in the field of optimization, as the objective function does not have an explicit analytical expression and is typically only upper semicontinuous. These features of pessimistic bilevel optimizaion place the problem out of the framework of standard optimization, where the objective function to be minimized is usually given explicitly and required to be at least lower semicontinuous. Solving the pessimistic bilevel program will unlock the potential of bilevel optimization as a powerful tool for optimal decision-making. To see this, note that the most basic rule in a bilevel optimization problem (also known as Stackelberg game) is that the leader (upper-level player) plays first by selecting a decision value that optimizes his/her utility function. Subsequently, the follower (lower-level player) selfishly reacts to this choice from the leader by choosing his/her own decision value that optimizes his/her utility function. This generally gives rise to two scenarios: the optimistic and pessimistic bilevel programs. In the optimistic case, one assumes that the follower will cooperate to make decisions that are in favour of the leader. However, if the leader is uncertain about the cooperation of the follower, as a risk-averse player, he/she will solve the pessimistic bilevel program to minimize any potential damage that might result from unfavorable choices from the follower. It is therefore clear that most practical applications of bilevel optimization will only fit into the pessimistic model, as it is more realistic for the leader to assume that the follower will not play in his/her favour. However, because solving the pessimistic bilevel program is very difficult, the literature on bilevel optimization has almost ignored the problem, and is therefore essentially concentrated around the optimistic model of the problem. This project will shift focus from optimistic to pessimistic bilevel optimization, while creating the first framework to efficiently solve the problem. More broadly, bilevel optimization represents one of the most popular problems in the field of optimization thanks to its inherent mathematical challenges, as well as the wide range of applications which have been growing exponentially in the last 40 years. The results from this project can help to solve problems of major importance in the UK and internationally. For instance, for the large transportation projects currently planned or ongoing in the UK (e.g., Crossrail, HS2, and Heathrow 3rd Runway), bilevel optimization offers a framework for the government (as upper-level player) to maximize their outputs while ensuring that taxpayers (as lower-level player) are also able to achieve their expected objectives. Suitable bilevel optimization models in this context can be constructed around the optimal network design, establishing optimal toll policies where necessary or the optimal estimation of the demand for these facilities.