论文标题
非线性单变量功能的多面体松弛序列
Sequence of Polyhedral Relaxations for Nonlinear Univariate Functions
论文作者
论文摘要
给定一个非线性，单变量，有限和可区分的函数$ f（x）$，本文开发了一系列混合整数线性编程（MILP）和线性编程（LP）放松，分别收敛到$ f（x）$及其convex hull的图表。建立了弛豫序列及其凸壳的理论收敛。对于非线性非凸优化问题，本文中介绍的放松可用于构建紧密的MILP和LP松弛。这些MILP和LP松弛也可以分别与基于MILP的和空间分支和基于分支的全局优化算法一起使用。
Given a nonlinear, univariate, bounded, and differentiable function $f(x)$, this article develops a sequence of Mixed Integer Linear Programming (MILP) and Linear Programming (LP) relaxations that converge to the graph of $f(x)$ and its convex hull, respectively. Theoretical convergence of the sequence of relaxations to the graph of the function and its convex hull is established. For nonlinear non-convex optimization problems, the relaxations presented in this article can be used to construct tight MILP and LP relaxations. These MILP and the LP relaxations can also be used with MILP-based and spatial branch-and-bound based global optimization algorithms, respectively.
