论文标题
凸出单变量函数的分段线性估计器的估计值获得或失去观点
Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions
论文作者
论文摘要
我们研究了\ {0 \} \ cup [\ ell，u] $的分离$ x \ $ x \ $ x \的Minlo（混合企业非线性优化），其中$ z $是$ x \ in [\ ell，u，u] $的二进制指标（$ 0域$ [\ ell，u] $，但$ y = 0 $当$ x = 0 $。该模型在非线性组合优化中非常有用，在此，在操作范围$ [\ ell，u] $中以$ x $运营活动的固定成本，然后还有一个（凸）可变成本$ f（x）$。特别是，我们研究了与自然的分段线性低估$ f $的透视转换有关的放松，这是通过选择$ f $的线性化点获得的。我们使用3-D体积（在$（x，y，z）$中）作为凸出放松的紧密度的度量，我们调查了放松质量，该质量是$ f $，$ \ ell $，$ u $，以及所选的线性化点。我们对凸功率功能进行详细调查$ f（x）：= x^p $，$ p> 1 $。
We study MINLO (mixed-integer nonlinear optimization) formulations of the disjunction $x\in\{0\}\cup[\ell,u]$, where $z$ is a binary indicator of $x\in[\ell,u]$ ($0 \leq \ell <u$), and $y$ "captures" $f(x)$, which is assumed to be convex and positive on its domain $[\ell,u]$, but otherwise $y=0$ when $x=0$. This model is very useful in nonlinear combinatorial optimization, where there is a fixed cost of operating an activity at level $x$ in the operating range $[\ell,u]$, and then there is a further (convex) variable cost $f(x)$. In particular, we study relaxations related to the perspective transformation of a natural piecewise-linear under-estimator of $f$, obtained by choosing linearization points for $f$. Using 3-d volume (in $(x,y,z)$) as a measure of the tightness of a convex relaxation, we investigate relaxation quality as a function of $f$, $\ell$, $u$, and the linearization points chosen. We make a detailed investigation for convex power functions $f(x):=x^p$, $p>1$.
