Convexity and concavity detection in computational graphs: Tree walks for convexity assessment

Robert Fourer*, Chandrakant Maheshwari, Arnold Neumaier, Dominique Orban, Hermann Schichl

*Corresponding author for this work

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

We examine symbolic tools associated with two modeling systems for mathematical programming, which can be used to automatically detect the presence or absence of convexity and concavity in the objective and constraint functions, as well as convexity of the feasible set in some cases. The coconut solver system [Schichl, H. 2004a. COCONUT: COntinuous CONstraints-Updating the technology] focuses on nonlinear global continuous optimization and possesses its own modeling language and data structures. The Dr. Ampl meta-solver [Fourer, R., D. Orban. 2007. Dr. Ampl-A meta solver for optimization. Technical Report G-2007-10, GERAD, Montréal] aims to analyze nonlinear differentiable optimization models and hooks into the ampl Solver Library [Gay, D. M. 2002. Hooking your solver to AMPL]. Our symbolic convexity analysis may be supplemented, when it returns inconclusive results, with a numerical phase that may detect nonconvexity. We report numerical results using these tools on sets of test problems for both global and local optimization.

Original languageEnglish (US)
Pages (from-to)26-43
Number of pages18
JournalINFORMS Journal on Computing
Volume22
Issue number1
DOIs
StatePublished - Dec 1 2010

Keywords

  • Constrained optimization
  • Convexity disproving
  • Convexity proving
  • Directed acyclic graph

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Convexity and concavity detection in computational graphs: Tree walks for convexity assessment'. Together they form a unique fingerprint.

  • Cite this