A successive linear relaxation method for MINLPs with multivariate Lipschitz continuous nonlinearities
From MaRDI portal
Abstract: We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt et al. (2018, 2021) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems.
Recommendations
- A decomposition method for MINLPs with Lipschitz continuous nonlinearities
- The cost of not knowing enough: mixed-integer optimization with implicit Lipschitz nonlinearities
- Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes
- Linearization-based algorithms for mixed-integer nonlinear programs with convex continuous relaxation
- Solving mixed-integer nonlinear optimization problems using simultaneous convexification: a case study for gas networks
Cites work
- A decomposition method for MINLPs with Lipschitz continuous nonlinearities
- A survey on bilevel optimization under uncertainty
- A survey on mixed-integer programming techniques in bilevel optimization
- An algorithmic framework for convex mixed integer nonlinear programs
- An outer-approximation algorithm for a class of mixed-integer nonlinear programs
- Bilevel optimization: theory, algorithms, applications and a bibliography
- Bilevel programming problems. Theory, algorithms and applications to energy networks
- Black-Box Optimization: Methods and Applications
- Branch- and bound algorithms for solving global optimization problems with Lipschitzian structure
- Branch-and-bound methods for solving systems of Lipschitzian equations and inequalities
- Combinatorial optimal control of semilinear elliptic PDEs
- Computational optimization of gas compressor stations: MINLP models versus continuous reformulations
- Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems
- Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
- Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reserve convex constraints, DC-programming and Lipschitzian optimization
- Efficient numerical solution of parabolic optimization problems by finite element methods
- Evaluating Gas Network Capacities
- Foundations of bilevel programming
- Global optimization in action. Continuous and Lipschitz optimization: algorithms, implementations and applications
- Globally convergent methods for n-dimensional multiextremal optimization
- scientific article; zbMATH DE number 5703572 (Why is no real title available?)
- scientific article; zbMATH DE number 193808 (Why is no real title available?)
- scientific article; zbMATH DE number 3637601 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 914364 (Why is no real title available?)
- Introduction to Derivative-Free Optimization
- Mixed-integer nonlinear optimization
- Networks of pipelines for gas with nonconstant compressibility factor: stationary states
- On a computationally ill-behaved bilevel problem with a continuous and nonconvex lower level
- On Finitely Terminating Branch-and-Bound Algorithms for Some Global Optimization Problems
- On the convergence of global methods in multiextremal optimization
- Optimization with PDE Constraints
- Outer approximation for global optimization of mixed-integer quadratic bilevel problems
- Pyomo -- optimization modeling in Python
- SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
- Solving mixed integer nonlinear programs by outer approximation
- The cost of not knowing enough: mixed-integer optimization with implicit Lipschitz nonlinearities
- The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program
- Towards simulation based mixed‐integer optimization with differential equations
- Validation of nominations in gas network optimization: models, methods, and solutions
Cited in
(3)
This page was built for publication: A successive linear relaxation method for MINLPs with multivariate Lipschitz continuous nonlinearities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6050153)
