Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Safe and tight linear estimators for global optimization

Published: 01 April 2005 Publication History

Abstract

Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This paper studies how to derive safe linear relaxations to account for numerical errors arising when computing the linear coefficients. It first proposes two classes of safe linear estimators for univariate functions. Class-1 estimators generalize previously suggested estimators from quadratic to arbitrary functions, while class-2 estimators are novel. When they apply, class-2 estimators are shown to be tighter theoretically (in a certain sense) and almost always tighter numerically. The paper then generalizes these results to multivariate functions. It shows how to derive estimators for multivariate functions by combining univariate estimators derived for each variable independently. Moreover, the combination of tight class-1 safe univariate estimators is shown to be a tight class-1 safe multivariate estimator. Finally, multivariate class-2 estimators are shown to be theoretically tighter (in a certain sense) than multivariate class-1 estimators.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B
Mathematical Programming: Series A and B  Volume 102, Issue 3
April 2005
203 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2005

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2017)Domain reduction techniques for global NLP and MINLP optimizationConstraints10.1007/s10601-016-9267-522:3(338-376)Online publication date: 1-Jul-2017
  • (2012)Boosting Local Consistency Algorithms over Floating-Point NumbersProceedings of the 18th International Conference on Principles and Practice of Constraint Programming - Volume 751410.5555/2969951.2969968(127-140)Online publication date: 8-Oct-2012
  • (2009)A review of recent advances in global optimizationJournal of Global Optimization10.1007/s10898-008-9332-845:1(3-38)Online publication date: 1-Sep-2009
  • (2009)Fast construction of constant bound functions for sparse polynomialsJournal of Global Optimization10.1007/s10898-007-9195-443:2-3(445-458)Online publication date: 1-Mar-2009
  • (2007)Using constraint techniques for a safe and fast implementation of optimality-based reductionProceedings of the 2007 ACM symposium on Applied computing10.1145/1244002.1244079(326-331)Online publication date: 11-Mar-2007
  • (2007)An efficient and safe framework for solving optimization problemsJournal of Computational and Applied Mathematics10.1016/j.cam.2005.08.037199:2(372-377)Online publication date: 15-Feb-2007
  • (2003)A comparison of methods for the computation of affine lower bound functions for polynomialsProceedings of the Second international conference on Global Optimization and Constraint Satisfaction10.1007/11425076_6(71-85)Online publication date: 18-Nov-2003

View Options

View options

Get Access

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media