INFORMS Journal on Computing
HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH
QUICK SEARCH:   [advanced]


     

INFORMS JOURNAL ON COMPUTING,
Published online in Articles in Advance, July 29, 2009
DOI: 10.1287/ijoc.1090.0321
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Download to citation manager
Right arrow reprints & permissions
Google Scholar
Right arrow Articles by Fourer, R.
Right arrow Articles by Schichl, H.

Convexity and Concavity Detection in Computational Graphs: Tree Walks for Convexity Assessment

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

Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208
Department of Mechanical Engineering, India Institute of Technology Guwahati, Guwahati 781039, India
Department of Mathematics, University of Vienna, A-1090 Vienna, Austria
GERAD and Département de Mathématiques et Génie Industriel, École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada
Department of Mathematics, University of Vienna, A-1090 Vienna, Austria
4er{at}iems.northwestern.edu
chandrakant721{at}yahoo.com
arnold.neumaier{at}univie.ac.at
dominique.orban{at}gerad.ca
hermann.schichl{at}esi.ac.at

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. The DrAMPL 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.

Key words: convexity proving; convexity disproving; directed acyclic graph; constrained optimization
History: received November 2007; revised December 2008; accepted February 2009.






HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH
Copyright © 2009 by INFORMS.