ECC20: Determining the Exact Local Convergence Rate of Sequential Convex Programming

Florian Messerer

University of Freiburg

Thursday, May 14, 2020, 15:20

virtual

This talk was recorded for the European Control Conference 2020, which is held virtually. The talk is a presentation of this paper.

* Link to recording *

Sequential Convex Programming (SCP) is an iterative algorithm for solving Nonlinear Programs (NLP) with "convex-over-nonlinear" substructure. At every iteration it solves a convex, but generally nonlinear, approximation to the original NLP, exploiting its outer convexities. It is already known that SCP has linear local convergence, though without a tight characterization of the rate. Sequential Convex Quadratic Programming (SCQP) is another "convex-over-nonlinear" substructure exploiting algorithm, for which a tight characterization of the convergence rate has already been obtained. In this paper we show under mild assumptions that in fact both methods have the same local linear convergence - or divergence - rate.
We can therefore determine the convergence rate of SCP, which is tightly characterized by two simple matrix inequalities evaluated at the solution. We further reason why - as a heuristic - SCP should in general show more robust global convergence than SCQP. We illustrate this, as well as the local convergence rate, with a numerical example.