Forrest Laine

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2021-182

August 12, 2021

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-182.pdf

This dissertation describes the work I have done on the subject of computing equilibrium solutions of connected quadratic programs (QPs), particularly for the connected programs arising in the context of autonomous system design. Reasoning about the interaction between multiple mathematical programs enables the analysis and solution to a wealth of problems inaccessible by standard optimization formulations.

One of the most commonly arising examples of connected optimization problems is the bilevel program, comprised of an outer-level and inner-level program. The outer-level problem is subject to a constraint that a subset of decision variables solve the inner-level problem. Another class of connected optimization problems are those of Nash equilibrium problems, in which optimization problems are solved simultaneously.

Beyond these and some other simple organizations of problem, general interactions among optimization problems are not well studied, despite the potential for modeling many interesting real-world problems. Presumably this is because with generalization in problem organization comes increased complexity, both from an analysis and computation perspective.

To address this, it is claimed in this work that it is possible to compute equilibrium solutions to a broad range of connected optimization problems, assuming those problems take the form of convex quadratic programs. This claim is based off a result that equilibrium solutions to a collection of QPs with piecewise linear constraints can be represented as a piecewise linear mapping. Recursive application of this result leads to the results for generally nested equilibrium problems. Theoretical results and computational approaches for this class of problem are developed. The efficacy of the presented methodologies is demonstrated on various problems faced by autonomous vehicles.

Advisors: Claire Tomlin

---

BibTeX citation:

@phdthesis{Laine:EECS-2021-182,
    Author= {Laine, Forrest},
    Title= {Connected Quadratic Programs for Autonomy},
    School= {EECS Department, University of California, Berkeley},
    Year= {2021},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-182.html},
    Number= {UCB/EECS-2021-182},
    Abstract= {This dissertation describes the work I have done on the subject of computing equilibrium solutions of connected quadratic programs (QPs), particularly for the connected programs arising in the context of autonomous system design. Reasoning about the interaction between multiple mathematical programs enables the analysis and solution to a wealth of problems inaccessible by standard optimization formulations. 

One of the most commonly arising examples of connected optimization problems is the bilevel program, comprised of an outer-level and inner-level program. The outer-level problem is subject to a constraint that a subset of decision variables solve the inner-level problem. Another class of connected optimization problems are those of Nash equilibrium problems, in which optimization problems are solved simultaneously. 

Beyond these and some other simple organizations of  problem, general interactions among optimization problems are not well studied, despite the potential for modeling many interesting real-world problems. Presumably this is because with generalization in problem organization comes increased complexity, both from an analysis and computation perspective.  

To address this, it is claimed in this work that it is possible to compute equilibrium solutions to a broad range of connected optimization problems, assuming those problems take the form of convex quadratic programs. This claim is based off a result that equilibrium solutions to a collection of QPs with piecewise linear constraints can be represented as a piecewise linear mapping. Recursive application of this result leads to the results for generally nested equilibrium problems. Theoretical results and computational approaches for this class of problem are developed. The efficacy of the presented methodologies is demonstrated on various problems faced by autonomous vehicles.},
}

EndNote citation:

%0 Thesis
%A Laine, Forrest 
%T Connected Quadratic Programs for Autonomy
%I EECS Department, University of California, Berkeley
%D 2021
%8 August 12
%@ UCB/EECS-2021-182
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-182.html
%F Laine:EECS-2021-182