Optimal deterministic algorithm generation

Alexander Mitsos, Jaromił Najman, Ioannis G. Kevrekidis

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

A formulation for the automated generation of algorithms via mathematical programming (optimization) is proposed. The formulation is based on the concept of optimizing within a parameterized family of algorithms, or equivalently a family of functions describing the algorithmic steps. The optimization variables are the parameters—within this family of algorithms—that encode algorithm design: the computational steps of which the selected algorithms consist. The objective function of the optimization problem encodes the merit function of the algorithm, e.g., the computational cost (possibly also including a cost component for memory requirements) of the algorithm execution. The constraints of the optimization problem ensure convergence of the algorithm, i.e., solution of the problem at hand. The formulation is described prototypically for algorithms used in solving nonlinear equations and in performing unconstrained optimization; the parametrized algorithm family considered is that of monomials in function and derivative evaluation (including negative powers). A prototype implementation in GAMS is provided along with illustrative results demonstrating cases for which well-known algorithms are shown to be optimal. The formulation is a mixed-integer nonlinear program. To overcome the multimodality arising from nonconvexity in the optimization problem, a combination of brute force and general-purpose deterministic global algorithms is employed to guarantee the optimality of the algorithm devised. We then discuss several directions towards which this methodology can be extended, their scope and limitations.

Original languageEnglish (US)
Pages (from-to)891-913
Number of pages23
JournalJournal of Global Optimization
Volume71
Issue number4
DOIs
StatePublished - Aug 1 2018

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Algorithms
  • Nonlinear equations
  • Optimal control
  • Optimization

Fingerprint Dive into the research topics of 'Optimal deterministic algorithm generation'. Together they form a unique fingerprint.

  • Cite this