为何需要障碍法
罚函数法与增广拉格朗日(Lagrange)法以惩罚违反约束的程度来处理约束,其迭代点一般不可行。内点法则相反:每个迭代点都严格可行,并以一个在边界处趋向 的障碍项使迭代点远离边界。参数 逐步减弱障碍的影响,所得的极小点曲线(中心路径)收敛到解。借助拉格朗日与 KKT 单元中的拉格朗日函数及弱对偶,一个简短的论证便把路径上每一点变成目标值离最优有多远的可验证界。计算这些点则使用线搜索与牛顿(Newton)法单元中的带线搜索牛顿法。
定义
考虑问题
其中 为凸且连续可微。以 记最优值。
定义 12.1.1
(严格可行与对数障碍函数)
若集合
非空,则称问题严格可行。在 上,对数障碍函数为
障碍函数在 上为凸: 为凸且递减, 为凹且为正,故每一项都是凸的。它可微,;当 内的点趋近某个 的点时,。注意 取决于函数 本身,而不只是它们所描述的可行集;这一点在下文很重要。
定义 12.1.2
(中心化问题、中心路径与中心乘子)
对 ,中心化问题为
若对每个 它都有极小点 ,则集合 称为中心路径,而中心乘子为 ,。
我们假设对每个 极小点都存在。例如可行集有界时就成立,因为目标函数在 上连续,并在 的边界处趋向 。由于 为开集且目标函数可微, 由驻点条件刻画:
因中心化目标为凸,此条件也是极小点的充分条件。因 ,中心乘子严格为正。
概念视角代数
中心路径即扰动的 KKT 方程组
恰好是把互补松弛条件放宽到同一正数水平后的 KKT 方程组的解:
把驻点条件除以 ,即知 满足这些方程。反之,若 满足它们,则 ,把第一个方程乘以 便得中心化驻点条件,所以 是中心化问题的极小点。当 时,乘积 被推向零,这正是 KKT 互补条件。牛顿型原始–对偶方法线性化的正是这个描述。
中心路径上的对偶间隙
扰动的互补条件 正是可计算间隙的来源。
定理 12.1.3
(中心路径上的对偶间隙)
在上述假设下,对每个 ,
证明
(在中心乘子处计算对偶函数)
可行,故 。把驻点条件除以 ,得
即 是拉格朗日函数 在 时的驻点。对固定的 ,拉格朗日函数关于 为凸,故驻点是 上的全局极小点。因此对偶函数满足
因为 个约束中每个都有 。弱对偶给出对每个 有 。
证明透视
三个假设,三项不同的工作
的可行性只提供上界。严格可行性使中心乘子有定义且为正,所以 是容许的对偶点。凸性只有一项工作:把 的驻点提升为全局极小点,从而把 认定为对偶值 。数量 则来自一个记账恒等式:每个约束恰好贡献 ;论证最后以弱对偶收尾。证明没有用到 或原问题解的唯一性,也不需要知道 的值。
因此 是 -次优的,无须知道 即有停止准则。凸性要求针对函数 ,不能减弱为可行集的凸性。
反例模式
凸集的非凸描述
断言:只要可行集是凸的,任何光滑描述都使间隙界成立。用 描述 (它在 上不是凸函数),并极小化 ,故 、。此时 ,中心化目标 的驻点条件为 ,所以 。间隙界会给出 ,这是错的。证明在凸性一步失效:,而 无下界,其驻点不是极小点。若改用凸描述 ,同一问题给出 ,间隙恰为 。修正后的表述保留每个 为凸的假设。
量 也随 不增,其论证只用到极小性。
命题 12.1.4
(目标值沿中心路径下降)
若 ,则 。
证明
(把两个极小性不等式相加)
记 ,。由极小性, 及 。两式相加, 抵消,剩下 。因 ,故 。
算法
给定严格可行的 、初始 、因子 及容差 :
- 令 。
- 中心化。 由当前点出发,用带回溯线搜索的牛顿法在 上极小化 。线搜索须保持在 内:试探步长不断缩减,直至严格可行并达到充分下降。令 为(近似)中心化点 。
- 若 则停止;由对偶间隙定理,。
- 令 ,,回到步骤 2。
不变量。 每个迭代点都在 内,故 有限,每个中心化阶段的驻点条件都有意义。外层循环的终止。 由于 ,检验 首次成立于
(若括号内的量非正则取 ),故恰好求解 个中心化问题。此公式不计内层牛顿迭代的次数。对一般凸数据,若无障碍函数的进一步结构(自和谐性,此处不展开),无法用此类公式界定其次数; 的选取是在较少的外层步数与较难的中心化问题之间权衡。
例题
例题 12.1.5
(一个约束:间隙界取等号)
在 (即 ,,)下极小化 。此时 ,。中心化问题是极小化 。驻点条件为 ,故 。于是 :对偶间隙定理的界取等号。中心乘子为 ,正是该约束的真实乘子。例如要证明间隙不超过 ,取 即可,此时 。
例题 12.1.6
(两个约束,其中一个不活跃)
在 下极小化 ,取 ,,,。此时在 上 。令 ,驻点条件为
乘以 得 ,即 ,其根为 。取正号的根大于 (至少为 ),在 之外,故
时:,。驻点验算:,,故 。乘子为 ,,而 即拉格朗日函数的驻点条件。可验证的界为
与 一致。 时:,故 ,界为 ;真实间隙 小于 。不活跃的约束在界中仍占 。间隙定理与单调性命题都可见:。
例题 12.1.7
(热启动的牛顿步离开定义域)
在一个约束的问题中,设 的中心化已得 ,参数升至 。新目标 有 、,故在 的牛顿方向为 。完整一步到达 。把步长逐次减半,试探点依次为 、、,都在 之外,然后是 。此处 ,低于 ;取 的 Armijo 测试只要求 。于是接受此步,继续趋向 。这个边界情形说明线搜索为何必须先检查是否属于 再计算 :牛顿公式本身提出了一个障碍函数无定义的点。
常见错误与细节
常见错误
(从并非严格可行的点出发)
方法需要严格可行的起点。内部为空的问题(例如把等式写成两个不等式)有 ;等式约束应作为仿射约束放进中心化问题,而不是障碍项。找出 中的第一个点是另一个独立的第一阶段问题。
常见错误
(在未中心化的点引用 m/t)
界 针对精确中心化的点。在一个约束的问题中取 ,严格可行点 会给出错误的界 。只是近似在路径上的点,其间隙界还要加上一项,视驻点条件的偏差而定。
常见错误
(让线搜索离开内部)
线搜索必须拒绝离开 的步长:障碍函数在该处为 (无定义),而牛顿步的公式并不知道定义域,热启动例题正好说明这一点。
另有三点容易忽略。
- 中心路径是一条随参数变化的问题的极小点曲线,并不是迭代点的路径;迭代点只是近似地沿它前进。
- 增大 使中心化问题更病态:其 Hessian 含有大小为 的项,在边界附近急剧增大。因此采用适中的 及热启动,而不是一次用极大的 求解。
- 对偶间隙定理并不要求 或原问题的解唯一;它只用到 是中心化问题的极小点。
练习
快速检查
(在 下极小化 。求 ,并求使对偶间隙定理能证明 的最小 。)
取 ,解中心化驻点条件。
解答
取 ,中心化目标为 ,驻点条件为 ,故 ,,其中 。对 ,定理证明的间隙为 ,故需 ,即 ;最小的 为 。
快速检查
(取 ,,,。障碍法要求解多少个中心化问题?分别在哪些 值?)
找出首个满足 的 。
解答
检验 要求 。因 ,首个满足的 为 。公式给出 。故共求解 个中心化问题,在 。
快速检查
(在 下极小化 。计算 、 时的中心乘子,以及所得的 的可验证下界。)
消去驻点条件的分母,并取 内的根。
解答
此时 ,,,。 时驻点条件为 。乘以 得 ,即 ,在 内的根为 。乘子为 ,,满足 。下界为 ,等于对偶值 ,且不超过 。(真实间隙为 。)
快速检查
(在 、 下极小化 。求 、中心乘子,以及精确间隙 。)
中心化目标可拆分为单变量问题。
解答
中心化目标为 ,故 、。取 、,中心乘子为 、,满足 。因 ,间隙为 ,恰好取等:线性问题的每个约束在解处都活跃时,界可以取到。
快速检查
(在两个约束的例题中,给出由 得到的 的可验证区间,并验证它包含 。)
用 ,其中 。
解答 · 答案
时,,,其中 (取 )。区间为 ,包含 。