本节讲解线性规划的一项基础建模技巧:绝对偏差与极小极大目标的精确线性表述。
动机
求解器只能优化交给它的模型。在选择换基规则之前,先要弄清每个变量的意思,以及不等式是否真的表达决策者的要求。假设我们要用一个设定值近似多个测量值:最小化最大误差会保护最差的一个观测值;最小化误差总和则衡量另一种取舍。由于误差涉及绝对值与最大值,两个目标看似都不是线性的。只要不等式方向正确,引入辅助变量便可把它们化为线性规划(LP)。
建模的关键是等价。同一个原决策可能对应多个可行的辅助变量值,因此不能要求两个可行集逐点相等。我们应检查:每个原决策能否扩展为新模型的可行解?对固定原决策优化辅助变量后,是否得到原本的目标值?
定义
定义 20.1.1
(残差与上图集)
设 是非空多面体;模型也可包含仿射等式和变量界。对有限个()仿射残差 及权重 ,考虑加权绝对偏差问题
函数 在 上的上图集是满足 、 的点对 的集合。对有限多个仿射函数 ,条件 等价于对每个 都有 。
此处目标以下界零为界;由线性规划的最优值存在定理,非空可行 LP 会取到有限最优值。保留下确界符号是为了清楚比较两个问题的值。除非另有界限, 的分量可以为负。在转换后的 LP 中,对每个残差引入 ,要求 及 。这两个不等式已经推出 ;额外写出非负约束虽无妨,却是多余的。
定理/命题
定理 20.1.2
(精确表述与原解的还原)
当所有权重 时,原偏差问题与以下 LP 有相同的下确界:
只要其中一个问题取到下确界,另一个也会取到。任何 LP 最优解的 部分都是原问题的最优解。若 ,每个 LP 最优解均满足 ;若 ,此等式未必成立,但可以选择使它成立。
同样,要最小化 ,可在 及所有 的限制下最小化 。即使 没有界或是自由变量,这仍是有限条约束的 LP;可行集本身不必有界。
证明思路
固定任意 。关于 的两个不等式恰好等价于 。因此取 不但可行,而且对固定的 使 最小。由于权重非负,任何扩展解的目标值都不小于原偏差目标,而上述选择恰好达到它。再对 取下确界,两个最优值相同。
若原问题有最优解,把它用绝对值扩展便得 LP 最优解。反过来,将 LP 最优解与每个原决策的这种扩展比较,可知其 部分必定原本已最优。若某权重严格为正,最优解中该 一旦有多余值,就可减至其下界并严格改善目标,造成矛盾;权重为零时则没有这个严格改善。
最坏情况模型亦然: 大于等于全部 个带符号残差,等价于它大于等于这些数的最大值,也就是 。固定 作同样比较,便得到最优值与解的等价;证明不需要可微性或唯一解。
证明透视
为何不等式在最优时可以取等号?
对一般可行点,这些不等式只给 的下界。最小化含正系数的 才是最优时下界取等号的另一个理由。证明是在固定 后比较可行扩展,并不是说每个可行辅助变量都等于绝对值。套用前必须检查系数符号和这变量是否受到其他约束。
例题
例题 20.1.3
(用一个设定值配合三个目标)
对目标 ,选择实数设定 ,最小化绝对误差总和。LP 是
消去辅助变量后,在 、、、 四段上,目标值分别为 、、、。各分段在端点相接。最小值在 取得,等于 ;对应 。这个设定是中位数,不是平均数 。
若改为最小化最大误差,令 且 ,并最小化 。仅看两端目标可得 。取 时,三个误差都不超过 ,所以达到此下界。故最小的最大误差为 ,设定值为 。中间目标影响误差总和,却没有改变此例的最坏情况解。
例题 20.1.4
(共享资源与最优性证书)
设 、,两项目标均为 。若超出目标也算偏差,最小化最大偏差的模型为
把两条 相加,得 ,所以 。可行选择 达到这下界,因而是全局最优;我们无须预先猜测哪条约束在未知最优解处取等号。若只惩罚不足而不惩罚超额,应使用不足量 ;那是另一个模型,需包括 及不足量不等式。
常见错误与细节
反例模式
负权重会颠倒诱因
考虑固定 时最小化 ,其值为零。若以 、 取代绝对值,却得到在 下最小化 ,目标无下界。这些不等式确实描述上图集,但最小化负倍数会奖励人为增大的 。同理,在这些下界下最大化 也不能表示最大化 ;其他情况可能需要非凸等式或离散模型。
固定 时, 恰好等价于 。相反,若 , 是“ 或 ”的析取;同时要求两者是不可能的。若只写 及 ,又完全不能限制 ,因为总可把 选得够大。上图集表述必须连同其使用方式一起检查。
快速检查
若零权重残差的值是 ,最优 LP 解的辅助变量可以是 吗?可以,只要其他约束与目标项都得到满足:它的上图集约束只要求 。在本模型中,把它改为 不会改变目标值。
练习
快速检查
(在实数上最小化 ,写出 LP 并求最优解及最小值。)
解答 · 答案
令 、、、,最小化 。原目标在 、、 分别为 、、。它在 之前递减,其后递增;故唯一最优解为 ,最小值为 。
快速检查
(在 下最小化 。以一个下界和一个可行点证明答案。)
解答 · 答案
因 ,第二个误差为 。取 时两个误差是 和 ,故最小值为 。下界与可行点共同证明最优性,无须依赖图形。
快速检查
(有人为 建立模型:最小化 ,但只加 。求其值并说明如何修正。)
解答 · 答案
所建 LP 在最优时取 ,在 得值 ;真正的最小值却是 时的 。加上 ;两个符号都不可缺。修正后,在给定区间内最小可行 是 。