最优化理论在信息论中的应用_(6)

最优化课程的具体应用,结合具体的专业。

113 Zoutendijk可行方向法 6

C max p(xi)p(yj/xi)log

i 0j 0p(yj/xi) p(x)p(y/x)iji

i 01

p(x0) p(x1) 1

p(xi) 0(i 0,1) （9）

3 Zoutendijk可行方向法

可行方向法是约束最优化方法中的一类算法，这种方法可以看作是无约束下降算法的自然推广，它的典型策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点。算法的主要步骤是在确定初始搜索点x(k)的基础上，选择可行的搜索方向d(k)并确定沿着此方向移动的步长 (k)，依次进行迭代，满足一定规则后停止迭代并得到最终的结果。可行下降的搜索方向的选择有多种方式，不同的方法就形成了不同的可行方向算法，这里主要对Zoutendijk可行方向法和Frank-Wolfe可行方向法进行详细介绍。

Zoutendijk可行方向法于1960提出的求解约束问题的一种算法。考虑非线性规划问题：

minf(x)

s..tAx b （10）

Ex e

其中是f(x)可微函数，A为m n阶矩阵，E为l n阶矩阵，x Rn，b和e分别为m维和l维列向量。

针对上述问题，Zoutendijk可行方向法的计算步骤如下：

（1）给定初始可行点x(1)，令k=1。

如果原问题容易观察得到一个可行点，则可以将其作为初始可行点进行迭代计算，若原问题较为复杂，难以直接观察到可行点，可通过引入人工变量的方法求得。例如针对最优化问题（10），引入人工变量 和 ，求解辅助线性规划：

l m min i i i 1 i 1

（11） s..tAx b

Ex e

0, 0

如果优化问题（11）的最优解(x,,) (x,0,0)，那么x就是优化问题（10）的一个可行解。

（2）在点x(k)处把A和b分解成