Treffer: An efficient and safe framework for solving optimization problems

Title:
An efficient and safe framework for solving optimization problems
Authors:
LEBBAH, Yahia, MICHEL, Claude, RUEHER, Michel
Source:
Scientific Computing, Computer arithmetic, and Validated Numerics (SCAN 2004)Journal of computational and applied mathematics. 199(2):372-377
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 14 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Analyse mathématique, Mathematical analysis, Calcul des variations et contrôle optimal, Calculus of variations and optimal control, Analyse numérique. Calcul scientifique, Numerical analysis. Scientific computation, Analyse numérique, Numerical analysis, Méthodes numériques en programmation mathématique, optimisation et calcul variationnel, Numerical methods in mathematical programming, optimization and calculus of variations, Algèbre linéaire numérique, Numerical linear algebra, Algebra lineal numérica, Analyse numérique, Numerical analysis, Análisis numérico, Borne inférieure, Lower bound, Cota inferior, Inversion matrice, Matrix inversion, Inversión matriz, Mathématiques appliquées, Applied mathematics, Matemáticas aplicadas, Méthode directe, Direct method, Método directo, Méthode optimisation, Optimization method, Método optimización, Optimisation sous contrainte, Constrained optimization, Optimización con restricción, Programmation linéaire, Linear programming, Programación lineal, Programmation mathématique, Mathematical programming, Programación matemática, Vitesse convergence, Convergence speed, Velocidad convergencia, Optimisation globale, Programmation contrainte, Relaxation linéaire sûre, Safe linear relaxation, Constraint programming, Global optimization, Safe linear relaxations
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Université de Nice-Sophia Antipolis, COPRIN (13S-CNRS/INRIA/CERTIS), 930 route des Colles, B.P. 145, 06903 Sophia Antipolis, France
Université d'Oran, Département d'Informatique, 31000 Oran, Algeria
ISSN:
0377-0427
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18411500
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Mathematics
Accession Number:
edscal.18411500
Database:
PASCAL Archive

Weitere Informationen

Interval methods have shown their ability to locate and prove the existence of a global optima in a safe and rigorous way. Unfortunately, these methods are rather slow. Efficient solvers for optimization problems are based on linear relaxations. However, the latter are unsafe, and thus may overestimate, or, worst, underestimate the very global minima. This paper introduces QuadOpt, an efficient and safe framework to rigorously bound the global optima as well as its location. QuadOpt uses consistency techniques to speed up the initial convergence of the interval narrowing algorithms. A lower bound is computed on a linear relaxation of the constraint system and the objective function. All these computations are based on a safe and rigorous implementation of linear programming techniques. First experimental results are very promising.