-

 

 

 




Optimization Online





 

Optimal Deterministic Algorithm Generation

Alexander Mitsos (amitsos***at***alum.mit.edu)
Jaromił Najman (jaromil.najman***at***avt.rwth-aachen.de)
Ioannis G. Kevrekidis (yannis***at***princeton.edu)

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 consists. 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 non- linear 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 developed along with illustrative results demonstrating cases for which well-known algorithms are shown to be optimal. The formulation is a mixed-integer non-linear program (MINLP). 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.

Keywords: Optimization, Nonlinear Equations, Algorithms, Optimal Control

Category 1: Global Optimization

Category 2: Applications -- Science and Engineering

Category 3: Other Topics

Citation:

Download: [PDF]

Entry Submitted: 09/22/2016
Entry Accepted: 09/22/2016
Entry Last Modified: 12/06/2016

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society