区间约束下的多元最值：逐变量线性与顶点法

逐变量线性与端点原理

设 $x_i\in[l_i,u_i]$，且 $l_i<u_i$。若固定其余变量后，$F(x_1,\ldots,x_n)$ 关于每一个 $x_i$ 都是一次函数或常数，则其最大值、最小值均可在长方体的顶点取得。

证明时固定 $x_2,\ldots,x_n$，把 $x_1$ 移到不使函数值减小的端点，再依次处理其余变量。有限次移动后达到某个顶点，故任何函数值都不大于某个顶点值；反向选择给出最小值。只需比较 $2^n$ 个顶点。

例如 $xy+yz+zx-xyz$ 符合条件；$x^2+y$ 不符合。变量的可行范围必须彼此独立，若有 $x+y=1$，不能任意移动一个变量而固定另一个。

插值表示与开区间的严格性

令 $t_i=(x_i-l_i)/(u_i-l_i)\in[0,1]$。反复使用一次插值，可把 $F$ 写成全部顶点值的加权和；某顶点在第 $i$ 个坐标取下端点时贡献因子 $1-t_i$，取上端点时贡献 $t_i$。所有权重非负，和为 $\prod_i[(1-t_i)+t_i]=1$。

若各坐标都严格位于区间内部，所有权重均为正。因此只要顶点值不全相等，内部函数值严格介于顶点最小值与最大值之间。开长方体内可以无限接近边界的最优值，却不能据此说存在最大值或最小值。若所有顶点值相同，插值式说明函数在整个长方体上恒定。