Evaluating Methods for Solving Mathematical Programs With Complementarity Constraints Arising From Nonsmooth Optimal Control

Anton Pozharskiy

University of Freiburg

Tuesday, November 07, 2023, 11:00 - 12:30

SR 01-012

The recently introduced Finite Elements with Switch Detection (FESD) discretization for nonsmooth dynamical systems provides a new source of Mathematical Programs with Complementarity Constraints (MPCCs), which are a particularly difficult form of nonlinear program. This approach has multiple powerful properties that are particularly useful when applied to Optimal Control Problems (OCPs). However, in order to be used in this context effectively, fast, robust solvers for MPCCs must exist. This thesis evaluates the performance of various solution methods for MPCCs that arise from the application of FESD to OCPs. The approach of interest is a generally successful class of solution methods which solves MPCCs via a sequence of relaxed nonlinear programs in a homotopy procedure where the relaxation is governed by a parameter that is driven to zero. This thesis introduces a novel benchmark suite, NOSBENCH, with a total set of 603 MPCCs, and uses it to evaluate the performance of various relaxations and other reformulation parameters. It is observed that only 73.8% of problems in the benchmark are solved by the best approaches, often requiring minutes to tens of minutes to converge even for relatively small OCPs. These results highlight the need for further work to be done to improve the state of the art for MPCC solvers. Finally, this thesis evaluates several sparsities of the complementarity constraints generated by FESD and proves that the sparsest form violates certain constraint qualifications at all feasible points. This fact is then augmented by empirically showing that the degeneracy of the sparsest mode indeed affects practical performance.