搜索
最优化理论在信息论中的应用最优化理论在信息论中的应用摘要最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎么找出最优方案。这类问题普遍的存在于各类的工程计算和方案设计领域，最优化这一数学分支为这些问题的解决提供了有力的理论基础和可靠的求解方法，在实际中应用中发挥了巨大的作用。信息论以香农的三大定理为学科的支撑和架构，其中涉及到了诸多有关信息量和信道容量等的最优值求解问题。本文结合所学的信息与通信领域的专业知识，讨论最优化理论与算法在信息论中的应用：使用最优化课程中解决非线性目标函数、线性约束函数极值问题的可行方向法中的Zoutendijk方法，结合Matlab软件中的数值计算工具箱对信息论中的问题进行编程分析和求解。最优化方法的引入，能够从数值计算的角度给出相关定理的解释，有助于加深对信息论中香农定理的理解；同时两门学科的交叉融合也能够将学到的最优化理论加以实践，从而更好的掌握并解决实际问题。关键词：最优化信息论香农定理可行方向法ZoutendijkABSTRACTABSTRACTOptimizationtheoryandalgorithmisanimportantbranchofmathmatics,whichfocusonhowtomeasurevariouskindsofplanstopickoutthebestoneaswellashowtocomingupwiththemostexcellentplan.Suchproblemsgenerallyexistinmosttypesofengineeringcalculationanddesignfield,andtheoptimizationprovidesastrongtheoreticalfoundationandreliablealgorithmforthesesolutions,whichhasplayedahugeroleintheactualapplication.TheinformationtheoryisbasedontheShannon'stheoremsandreferstoaproportionofoptimizationproblemsontheinformationcontentandinformationcapacity.Inthispaper,theapplicationofoptimizationintheinformationtheoryfieldwillbestudiedandanalysedinthecombinationofpartoftheprofessionalknowledgeontheinformationandcommunication.WiththehelpofMatlabnumericalcomputationtoolbox,theZoutendijkfeasibledirectionmethodintheoptimizationtextconceringontheproblemwithnon-linearobjectivefunctionandlinearconstraintedfunctionswillbeprogrammedtosolvethecorrespondingproblemofimformationtheory.Throughthisprocess,theShannon'stheoremscanbeexplainedintheaspectofnumericalcomputation,whichmaygaintheunderstandingofthetheorems;andtheoptimizationtheorycanbebettergraspedduringthepracticalapplication.Keywords:optimizationinformationtheoryShannon'stheoremsFeasibleDirectionMethodZoutendijk1引言31引言最优化方法是在给定约束之下，从问题的许多可能解答中，寻求使某一或某些指标达到最优解答，或者对于给定的问题通过何种途径去寻找最优解答的方法，它是一个重要的数学分支。最优化是个古老的方法，早在17世纪从英国科学家牛顿提出极值问题开始，就已经出现了最优化研究的雏形。至20世纪40年代，由于生产和科学研究迅猛发展，尤其是电子计算机的广泛应用，一方面对最优化的研究有力空前的迫切需求，另一方面也为最优化研究提供了新型的有力的工具。最优化问题与现代电子技术结合，步入了全新发展的快车道，形成了一个新的学科，出现了线性规划、非线性规划、整数规划等众多的分支。最优化问题普遍存在于各类工程设计和方案规划问题中，例如在工程设计中怎样选择设计参数，使设计方案既满足设计要求又能降低成本；在资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益。随着最优化学科的发展，及其与社会各领域的紧密结合，最优化理论和算法在实际中正发挥着越来越大的作用。信息论是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。狭义的信息论以香农信息论为基础，核心内容是香农三大定理，涉及最大熵、信道容量、最佳信源编码以及最佳信道编码等最优化问题。这些问题在教科书中一般以定理形式给出，并未给出具体的求解形式，不利于对定理的理解。本文结合信息论的部分专业知识以及最优化理论中所学习的求解方法，对信息论中的最大熵和信道容量的最优化问题进行编程分析和求解，主要使用的算法为求解非线性目标函数、线性约束函数极值问题的Zoutendijk可行方向法，用到的编程软件为Matlab2012b。通过数值分析，对香农定理深入理解并更好的掌握所学习的最优化理论算法。2最大熵原理和信道容量2.1最大熵原理在信息论中，信息是对于事件随机性的一种描述，一个事件所包含的信息量与该事件出现的概率有关，两者之间的关系有如下定义：()log()Ixpx（1）2最大熵原理和信道容量4公式（1）中()px表示时间x发生的概率，是介于0和1之间的数。由公式可以看出，事件发生的概率越大，所包含的信息量就越小，当事件发生的概率为1——即确知该事件会发生时，它所包含的信息量为0，对于确知事件，不再有研究意义。对于通信系统的信号在信道的传输问题，信源可能产生n个不同的消息0121,,,nxxxx，各自对应于不同的事件，并且产生每个消息的概率不同，假设每个消息ix产生的概率为()ipx，因此根据公式（1）可以得到每个消息包含的信息量。而由于信源是按照不同的概率来产生这些消息的，因此从信源的角度综合考虑发送信号所包含的总的信息量，则有信源的平均信息量()Hx，定义如下：10()()log()niiiHxpxpx（2）该信源的平均信息量通常也称为信源的熵，可以理解为信源的平均不确定度。在很多情况下，对一些随机事件，我们并不了解其概率分布，所掌握的只是与随机事件有关的一个或几个随机变量的平均值。按最大信息熵原理，如果我们从全部相容的分布中挑选这样的分布，它是在某些约束条件下（通常是给定的某些随机变量的平均值）使信息熵达到极大值的分布，这是因为信息熵取得极大值时对应的一组概率分布出现的概率占绝对优势。可以看出，在给定的等式和不等式约束条件下，由最大信息熵原理求消息发生的“最佳”概率分布，就是一个求解条件极值的最优化问题，可表示如下：1010max()()log()()1()0(0,11)niiiniiiHxpxpxpxpxin（3）2.2信道容量信息论中的另外一个重要的问题是求解信道的容量。信道容量是指信道上没传送一个符号所能携带的信息量，可以用信道接收端和发送端互信息量的最大值来表征。假设一个信道输入的字符集为0121,,,nXxxxx，信道接收端接收到的字符集为0121,,,mYyyyy，信道的转移概率(/)(0,1;0,1)ijjiPpyxinjm，则信道发送端和接收端之间的平均互信息量(,)IXY可以表示为：2最大熵原理和信道容量5111000(/)(,)()(/)log()(/)nmjiijinijijiipyxIxypxpyxpxpyx（4）根据定义，信道容量的表达式为：max(,)CIXY（5）对于一个给定的信道，它的特性是固定的，不随信源的不同而改变，因此信道的转移概率(/)jipyx是确定的，则可以从公式（3）和（4）中看出，信道容量是关于变量()ipx的一个极值问题，也就是关于信源产生消息的概率分布的一个最优化问题。这里我们主要讨论离散无记忆的对称二进制信道的最大熵和信道容量，这种信道在某个时刻的输出符号只与当前时刻的输入符号有关，而与之前的输入符号无关，所以称为无记忆的。同时离散无记忆的对称二进制信道的输入和输出都是序列0,1，而且信道噪声和其它干扰导致的信道传输发生的差错统计独立，信道的转移概率相互对称，即(1/0)(0/1)(0/0)(1/1)1pYXPYXpYXPYX（6）信道模型可以用简化图表示如下：根据离散无记忆对称二进制信道的定义，对应的信源的熵可以表示为：0111()()log()()log()Hxpxpxpxpx（7）最大熵的极值表达式为：011101max()()log()()log()()()1()0(0,1)iHxpxpxpxpxpxpxpxi（8）同样的，信道容量在离散无记忆对称二进制信道中可以表示为如下的最优化问题：1100x00y11x11y3Zoutendijk可行方向法611100001(/)max()(/)log()(/)()()1()0(0,1)jiijiijijiiipyxCpxpyxpxpyxpxpxpxi（9）3Zoutendijk可行方向法可行方向法是约束最优化方法中的一类算法，这种方法可以看作是无约束下降算法的自然推广，它的典型策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点。算法的主要步骤是在确定初始搜索点()kx的基础上，选择可行的搜索方向()kd并确定沿着此方向移动的步长()k，依次进行迭代，满足一定规则后停止迭代并得到最终的结果。可行下降的搜索方向的选择有多种方式，不同的方法就形成了不同的可行方向算法，这里主要对Zoutendijk可行方向法和Frank-Wolfe可行方向法进行详细介绍。Zoutendijk可行方向法于1960提出的求解约束问题的一种算法。考虑非线性规划问题：min()..fxstAxbExe（10）其中是()fx可微函数，A为mn阶矩阵，E为ln阶矩阵，nxR，b和e分别为m维和l维列向量。针对上述问题，Zoutendijk可行方向法的计算步骤如下：（1）给定初始可行点(1)x，令k=1。如果原问题容易观察得到一个可行点，则可以将其作为初始可行点进行迭代计算，若原问题较为复杂，难以直接观察到可行点，可通过引入人工变量的方法求得。例如针对最优化问题（10），引入人工变量和，求解辅助线性规划：11min..0,0mliiiistAxbExe（11）如果优化问题（11）的最优解(,,)(,0,0)xx，那么x就是优化问题（10）的一个可行解。（2）在点()kx处把A和b分解成4Zoutendijk可行方向法在信息论中的应用712AA和12bb，使得()()1122,kkAxbAxb，计算()()kfx。（3）求解线性规划问题()1min()..0011,1,kTjfxdstAdEddjn（12）从而得到最优解()kd。（4）如果()()()0kTkfxd，则停止计