文档介绍：§ 内点算法
算法复杂性
计算模型
假设基本运算(﹢、﹣、×、÷、比较、转移)均可在
单位时间内完成.
算法执行时间可用算法所需执行基本运算的总次数.
输入长度
字符串(二进制或某大于1进制的代码序列)
对于优化问题: 问题维数、约束个数、n、m
时间复杂性函数
算法分类: 多项式时间算法
指数时间算法
大量计算实践表明, 单纯形法及其变形是求解LP问题
的一类收敛很快、相当成功的算法.
例如, 对形如:
的典型LP问题, 在假设问题中的数据按某种合理的分布取值
时, 理论上可以证明单纯形法平均经
次迭代即可确定问题的最优解. 因此, 在一般情况或平均意义
下, 单纯形法是很有效的.
但是, 当把单纯形法应用于下列LP问题
时, 则它需经次迭代方能确定问题的最优解.
指数时间算法
(1979)
LP与严格线性不等式组的关系
以下都假定A、b、c均为整数
( 1 )
Proof:
Th. : 存在求解LP问题的多项式时间算法的充分必要条件
是存在求解形如
的线性不等式组的多项式时间算法。
令, 写出与(1)有关的LP :
行向量c可任意给定, 如取 c=0
( 2 )
若有多项式时间的LP算法, 则可判定:
问题(2)不可行→这时不等式组(1)无解.
得到(2)的最优解
或判定(2)无界
→这时必可得(1)的一个解
在多项式
时间内求解
了问题(1)
反之, 若有一多项式时间方法求解闭(弱)的线性不等式组(1)
考虑问题(2)的对偶:
对偶Th
求解问题(2)可归结为求解关于
变量的下述弱不等式组
否则, 再考虑另一个弱不等式组:
若它有解→则问题(2)无界
否则→问题(2)不可行
总之, 最多求解两个弱不等式组就完全解决了LP问题(2)
从而得到求解LP问题的一个多项式时间算法
若该联立不等式组有解
则为问题(2)的最优解, 为其对偶最优解.
(1)与严格(强)线性不等式组的关系:
( 3 )
令
则由线代行列式理论易证
设, 且(否则LP问题很容易求解)
引理: 设B是矩阵的任一子方阵, 则
记为A的第i个行向量, . 代替(3), 考察不等式组
其中
令
显然, x为弱不等式组(1)的解
引理: 对中任一点, 必定存在一个,使得:
1.
2. A的每个行向量均可表示为向量集
满足的线性组合.
推论: 若有一个求解严格线性不等式组的多项式时间算法,
则就有一个求解弱线性不等式组的多项式时间算法.
Th. : 弱不等式组(1)可行
严格不等式组(3)可行