Validated Linear Relaxations and Preprocessing: Some Experiments
| Autor: | R. Baker Kearfott, Siriporn Hongthong |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Mathematical optimization
Computational complexity theory Unary operation Automatic differentiation MathematicsofComputing_NUMERICALANALYSIS Symbolic computation Measure (mathematics) Theoretical Computer Science Nonlinear system Binary operation TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Global optimization Software Mathematics |
| Zdroj: | SIAM Journal on Optimization. 16:418-433 |
| ISSN: | 1095-7189 1052-6234 |
| DOI: | 10.1137/030602186 |
| Popis: | Based on work originating in the early 1970s, a number of recent global optimization algorithms have relied on replacing an original nonconvex nonlinear program by convex or linear relaxations. Such linear relaxations can be generated automatically through an automatic differentiation process. This process decomposes the objective and constraints (if any) into convex and nonconvex unary and binary operations. The convex operations can be approximated arbitrarily well by appending additional constraints, while the domain must somehow be subdivided (in an overall branch-and-bound process or in some other local process) to handle nonconvex constraints. In general, a problem can be hard if even a single nonconvex term appears. However, certain nonconvex terms lead to easier-to-solve problems than others. Recently, Neumaier, Lebbah, Michel, ourselves, and others have paved the way to utilizing such techniques in a validated context.In this paper, we present a symbolic preprocessing step that provides a measure... |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|