Nonconvex constrained optimization by a filtering branch and bound
- PDF / 1,050,550 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 247 Views
Nonconvex constrained optimization by a filtering branch and bound Gabriele Eichfelder1
· Kathrin Klamroth2
· Julia Niebling1
Received: 5 January 2020 / Accepted: 27 September 2020 © The Author(s) 2020
Abstract A major difficulty in optimization with nonconvex constraints is to find feasible solutions. As simple examples show, the αBB-algorithm for single-objective optimization may fail to compute feasible solutions even though this algorithm is a popular method in global optimization. In this work, we introduce a filtering approach motivated by a multiobjective reformulation of the constrained optimization problem. Moreover, the multiobjective reformulation enables to identify the trade-off between constraint satisfaction and objective value which is also reflected in the quality guarantee. Numerical tests validate that we indeed can find feasible and often optimal solutions where the classical single-objective αBB method fails, i.e., it terminates without ever finding a feasible solution. Keywords Constrained optimization · Nonconvex optimization · Global optimization · Branch and bound · Multiobjective optimization Mathematics Subject Classification 90C26 · 90C29 · 90C30
1 Introduction and motivation Numerical methods for constrained optimization problems have a multitude of applications in a large range of technical and economical applications. To give a concrete example, we consider an engineering design problem where the overall aim is to minimize the building costs while certain requirements on the quality have to be met. Depending on the structure
B
Julia Niebling [email protected] Gabriele Eichfelder [email protected] Kathrin Klamroth [email protected]
1
Institute for Mathematics, Technische Universität Ilmenau, P.O. Box 10 05 65, 98684 Ilmenau, Germany
2
Department of Mathematics and Computer Science, University of Wuppertal, Gaußstr. 20, 42119 Wuppertal, Germany
123
Journal of Global Optimization
of the problem at hand, it may already be a challenging task to find feasible solutions, and even more so to find feasible solutions that are provably optimal.
1.1 Constraint handling and multiobjective counterparts In this paper, we focus on constrained optimization problems where the objective function as well as the constraints are given by twice continuously differentiable functions. Noting that feasibility constraints are a prevalent difficulty in constrained optimization, we take a multiobjective perspective and suggest to relax all complicating constraints and re-interprete them as additional and independent objective functions. From a practical point of view, such multiobjective counterpart models account for the fact that the right-hand-side values of constraints are often based on individual preferences and/or estimations (consider, for example, quality constraints in an engineering design problem). Indeed, slight constraint violations may be acceptable if this allows for a significant improvement of the primary (cost) objective function. Converse
Data Loading...
