论文标题
具有多元Lipschitz连续非线性的Minlps的连续线性松弛方法
A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities
论文作者
论文摘要
我们提出了一种新型方法，用于与多元和Lipschitz连续非线性的混合优化问题。特别是，我们不认为非线性约束是明确给出的，而是我们只能评估它们，并且我们知道他们的全球Lipschitz常数。该算法是一种连续的线性放松方法，在解决主问题之间我们交替进行交替，这是对原始问题的混合智能线性放松和一个子问题，该子问题旨在通过利用有关相应功能的Lipschitz信息来巩固下一个主问题的线性松弛。通过这样做，我们遵循Schmidt等人的思想。 （2018，2021）并改善了对多元限制的解决。尽管多元非线性显然提高了建模能力，但它们的掺入也显着增加了所提出算法的计算负担。我们证明了我们的方法的正确性，并得出了最坏的案例迭代结合。最后，我们通过说明非凸和二次较低级别的双光线优化问题以及非线性和混合构成天然气传输模型都可以通过我们的方法来解决，并显示了解决问题类别的通用性和提议的方法。我们为应用程序提供必要的理论，并在应用于这两个问题时简要说明新方法的结果。
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.
