我正在阅读网络流-理论,算法和应用,并且我被困在证明以下定理(Ch。第3页,67页):
定理。假设在算法的??ℎ迭代中,?^?是最小化问题某解的目标函数值,?^∗是最小目标函数值。此外,假设该算法保证对于每个迭代?,
(1) (?^?−?^(?+1))≥?(?^?−?^∗)
(即,对于0<?<1(与问题数据无关)的某个常数?,迭代?+1的改进至少是总可能改进的?倍)。然后,该算法在/?)迭代中终止,其中?是最大和最小目标函数值之间的差。
证据。数量(?^?−?^∗)表示在??ℎ迭代之后目标函数值的总可能改进。考虑从迭代?开始的2/?迭代的连续序列。如果算法的每次迭代都将目标函数值提高至少?(?^?−?^∗(/2)个单位,则算法将在这些2/?迭代中确定最优解。相反,假设在某个迭代/2+ 1处,该算法将目标函数值改进了小于?(?^?−?^∗)个单位。换句话说,
(2) /2(?^?−?^(?+1)≤?(?^?−?^∗)。
不等式(1)意味着
(3)?+1(?(?^?−?^∗)≤?^?−?^)
不等式(2)和(3)意味着
(?^?−?^∗)≤(?^?−?^∗)/2,
因此,该算法将总可能改进(?^?−?^∗)减少了至少2倍。因此,我们已经证明,在2/?连续迭代内,该算法要么获得最优解,要么将总可能改进减少至少2倍。由于?是最大可能的改进,并且每个目标函数值都是整数,因此该算法必须在?((????)迭代内终止。
为什么作者关注2/a迭代?
发布于 2020-09-11 09:03:09
我认为这样写是为了让计算机科学家更容易理解,我们每2/α轮将整数减半,因此2/α轮超级轮次的数量将是O(对数)。没有特别的理由我们不能更直接地做数学计算:
T(n) is the gap between the nth solution and an optimal solution.
T(n) ≤ (1 - α) T(n-1) [assumption]
n
T(n) ≤ T(0) (1 - α) [by induction]
-α n x
< T(0) (e ) [by 1 + x < e for x ≠ 0]
-α (ln T(0))/α
T((ln T(0))/α) < T(0) e
= 1,所以(ln T(0))/α循环就足够了。
https://stackoverflow.com/questions/63839341
复制相似问题