161. Convexity detection in Hexaly
Invited abstract in session WB-9: What's New in Solvers I, stream Software for Operations Research.
Wednesday, 10:45-12:15Room: H15
Authors (first author is the speaker)
| 1. | Michael Feldmeier
|
| Hexaly |
Abstract
Hexaly is a mathematical optimization solver based on various operations research techniques, combining both exact and approximate methods such as linear programming, non-linear programming, constrained programming and primal heuristics. Knowing model features and recognizing special cases is imperative to selecting the right methods for solving the problem as fast as possible. One such model feature is convexity. Recognizing a convex model as such allows selecting more efficient algorithms under Hexaly's hood. In this talk we will present how Hexaly determines a user model's convexity. Convexity analysis typically examines the expression tree of the continuous relaxation of the model constraint by constraint. Combining knowledge of convexity-preserving operations with known properties of basic functions allows evaluating the curvature of complicated constraints and objectives. This can be straightforward to compute, e.g. positive sums of convex functions are convex. However, already for quadratic programmes convexity detection by this method can be ineffective: depending on the formulation of the functions as well as how they are translated into the expression tree it may not be possible to determine a convex problem as such. Of course, in the case of quadratic programming, spectral analysis can be applied. However, this is computationally expensive, and can sometimes be avoided, e.g. by application of Gershgorin's circle theorem. We will present data from numerical experiments about the reliability of our implementation of convexity detection in Hexaly.
Keywords
- Continuous Optimization
- Convex Optimization
- Nonlinear Programming
Status: accepted
Back to the list of papers