A BFGS-SQP method for nonsmooth, nonconvex, constrained optimization and its evaluation using relative minimization profiles

Frank E. Curtis, Tim Mitchell, Michael L. Overton

Research output: Contribution to journalArticle

Abstract

We propose an algorithm for solving nonsmooth, nonconvex, constrained optimization problems as well as a new set of visualization tools for comparing the performance of optimization algorithms. Our algorithm is a sequential quadratic optimization method that employs Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton Hessian approximations and an exact penalty function whose parameter is controlled using a steering strategy. While our method has no convergence guarantees, we have found it to perform very well in practice on challenging test problems in controller design involving both locally Lipschitz and non-locally-Lipschitz objective and constraint functions with constraints that are typically active at local minimizers. In order to empirically validate and compare our method with available alternatives—on a new test set of 200 problems of varying sizes—we employ new visualization tools which we call relative minimization profiles. Such profiles are designed to simultaneously assess the relative performance of several algorithms with respect to objective quality, feasibility, and speed of progress, highlighting the trade-offs between these measures when comparing algorithm performance.

Original languageEnglish (US)
Pages (from-to)148-181
Number of pages34
JournalOptimization Methods and Software
Volume32
Issue number1
DOIs
StatePublished - Jan 2 2017

    Fingerprint

Keywords

  • benchmarking
  • computational budget
  • constrained optimization
  • exact penalty methods
  • nonconvex optimization
  • nonsmooth optimization
  • performance profiles
  • sequential quadratic optimization

ASJC Scopus subject areas

  • Software
  • Control and Optimization
  • Applied Mathematics

Cite this