新版线性判别函数省公共课一等奖全国赛课获奖课件.pptx

第四章第四章 线性判别函数线性判别函数nBayesian分类器设计方法，已知n类条件概率密度 p(x|i)参数表示式n先验概率 P(i)n利用样本预计 p(x|i)未知参数n用贝叶斯规则将其转换成后验概率 P(i|x)，并依据后验概率大小进行分类决议。第1页处理实际问题方法处理实际问题方法n在实际中存在问题n样本特征空间类条件概率密度形式经常极难确定n利用 Parzen 窗等非参数方法恢复分布往往需要大量样本，而且伴随特征空间维数增加所需样本数急剧增加。n所以，在处理实际问题时，往往是利用样本集直接设计分类器，而不恢复类条件概率密度。n即采取判别函数，首先给定某个判别函数类，然后利用样本集确定出判别函数中未知参数。第2页线性判别函数线性判别函数n线性判别函数法是一类较为简单判别函数。是统计模式识别基本方法之一。n它首先假定判别函数 g(x)是 x 线性函数，即 g(x)=wTx+w0，对于 c 类问题，能够定义 c 个判别函数，gi(x)=wiTx+wi0，i=1,2，c。n用样本去预计各 wi 和 wi0，并把未知样本 x 归到含有最大判别函数值类别中去。n关键是怎样利用样本集求得 wi 和 wi0。第3页训练和学习训练和学习n“训练”和“学习”n在待识别模式中，挑选一批有代表性样本，经过人工判读，成为已知分类样本，把这批样本逐一输入到计算机中“训练”程序或算法中，经过一次次迭代，最终得到正确线性判别函数。n这么迭代过程称之为训练过程，所组成分类器称为有些人监督或有教师分类器。第4页4.1.1 线性判别函数基本概念线性判别函数基本概念n在正态分布Bayesian判别中，已经碰到过在两类情况下判别函数为线性情况。n假设有1 和2 两类模式，在二维模式特征空间可用一直线把这两类模式划分开，如图 4.1 所表示。第5页x1x2g(x)=w2x2+w1x1+w0 图4.1两类模式一个简单判别函数+划分直线方程参数坐标变量4.1.1 线性判别函数基本概念线性判别函数基本概念第6页判别规则判别规则n若给定一个未知类别模式xn当g(x)0 时，则决议 x 属于1；n当 g(x)0，所以决议面法向量是指向 R1。n所以，有时称 R1 中任何 x 在 H 正侧，对应地，称 R2 中任何 x 在 H 负侧。4.1.1 线性判别函数基本概念线性判别函数基本概念第12页判别函数判别函数 g(x)是特征空间中某点是特征空间中某点 x 到超平到超平面距离一个代数量度。面距离一个代数量度。n若把 x 表示成式中 xp：是 x 在 H 上投影向量；r：是 x 到 H 垂直距离；：是w方向上单位向量。4.1.1 线性判别函数基本概念线性判别函数基本概念第13页若 x 为原点，则 g(x)=w0 (4-7)将(4-7)代入(4-6)，就得到从原点到超平面 H 距离 (4-6)判别函数判别函数 g(x)是特征空间中某点是特征空间中某点 x 到超平到超平面距离一个代数量度。面距离一个代数量度。4.1.1 线性判别函数基本概念线性判别函数基本概念第14页假如 w00，则原点在 H 正侧；若 w00，则原点在 H 负侧。若w0=0，则 g(x)含有齐次形式 wTx，说明超平面 H 经过原点。判别函数判别函数 g(x)是特征空间中某点是特征空间中某点 x 到超平到超平面距离一个代数量度。面距离一个代数量度。4.1.1 线性判别函数基本概念线性判别函数基本概念第15页图 4.2 对这些结果作了几何解释。4.1.1 线性判别函数基本概念线性判别函数基本概念第16页结论结论n利用线性判别函数进行决议，就是用一个超平面把特征空间分割成两个决议区域。n超平面方向由权向量 w 确定，它位置由阈值权 w0 确定。n判别函数 g(x)正比于 x 点到超平面代数距离（带正负号）当 x 在 H 正侧时，g(x)0，在负侧时，g(x)0。4.1.1 线性判别函数基本概念线性判别函数基本概念第17页4.1.2 广义线性判别函数广义线性判别函数n如图 4.3 所表示二类问题。n设有一维样本空间 X，所希望划分是：n假如 xa，则 x 属于1 类；n假如 b x0，则决议 x1g(x)0，则决议 x2二次判别函数可写成以下普通形式g(x)=c0+c1x+c2x2(4-10)假如适当选择 x y 映射，则可把二次判别函数化为 y 线性函数4.1.2 广义线性判别函数广义线性判别函数第20页式中式中称为广义判别函数，a叫做广义权向量。普通地，对于任意高次判别函数 g(x)(这时 g(x)可看作对任意判别函数作级数展开，然后取其截尾部分迫近)，都能够经过适当变换，化为广义线性判别函数来处理。4.1.2 广义线性判别函数广义线性判别函数第21页存在问题存在问题n经过变换后，维数大大增加了，这将使问题很快陷入所谓“维数灾难”。n在统计学习理论中，对广义线性分类器进行研究，克服了“维数灾难”问题，进而发展出了最新模式识别方法支持向量机，成为处理有限样本情况下非线性分类问题有效伎俩。4.1.2 广义线性判别函数广义线性判别函数第22页n把(4-1)式定义线性判别函数写成下面形式(4-12)增广特征向量Augmented feature vector增广权向量(广义权向量)Augmented weight vector4.1.2 广义线性判别函数广义线性判别函数第23页结论结论ny 与 x 相比，即使增加了一维，但保持了样本间欧氏距离不变，变换后样本向量依然全部位于 d 维子空间，即原 X 空间中，方程(4-13)在Y空间确定了一个经过原点超平面 。它对 d 维子空间划分与原决议面 wTx+w0=0 对原 X 空间划分完全相同。4.1.2 广义线性判别函数广义线性判别函数第24页例子例子n这种方法优缺点可经过例子来说明。考虑二次判别函数得到三维向量y从x到y映射如图所表示。4.1.2 广义线性判别函数广义线性判别函数第25页例子例子4.1.2 广义线性判别函数广义线性判别函数数据仍保持固有一维，因为改变x将造成y沿着一个三维曲线运动。假如x服从某一个概率分布时，得到密度函数是退化，即曲线之外是0，在曲线上是无穷大，这是从低维空间到高维空间映射普遍问题。第26页例子例子4.1.2 广义线性判别函数广义线性判别函数图中映射y=(1,x,x2)T把一条直线映射为三维空间中一条抛物线。因为两类问题，在三维空间中，一个平面就是一个分隔面。所以，由图可见，这产生了原始一维x空间不连通性第27页例子例子g(x)=1+x+2x2x0.5时g(x)0a=(-1,1,2)T4.1.2 广义线性判别函数广义线性判别函数由aTy=0定义平面将y空间分成两个判别区域，如图给出当a=(-1,1,2)T时分类平面和x空间对应判别区域。第28页结论结论aTy=0在2维空间不穿过原点4.1.2 广义线性判别函数广义线性判别函数一个三维增广特征空间y和增广权向量a(在原点)。满足aTy=0点集是一个穿过y空间原点超平面(用红色表示)，这个平面垂直于a。这个平面在其原来二维空间中不一定穿过原点(即立方体顶部虚线所表示判决边界)。所以存在一个增广权向量a，能够取得x空间中任意判定线。第29页4.1.3 设计线性分类器主要步骤设计线性分类器主要步骤设计线性分类器，就是建立线性判别函数(4-l)式g(x)=wTx+w0或广义线性判别函数(4-12)式这么，设计线性分类器就转化为，利用训练样本集寻找准则函数极值点 和 或 。第30页设计线性分类器主要步骤以下：设计线性分类器主要步骤以下：n 要有一组含有类别标志样本集X=x1，x2，xN。n假如在样本 xn 抽出后，把它看作一个确定观察值，则这组样本集称为确定性样本集；n若把 xn 看作一个随机变量，则这组样本集称为随机样本集。n有时也将样本集 X 转换成增广样本集 Y 来处理。4.1.3 设计线性分类器主要步骤设计线性分类器主要步骤第31页n 要依据实际情况确定一个准则函数 J 它必须满足：J 值反应分类器性能，它极值解则对应于 最好 决议。J是样本集X和w、w0或 a 函数；设计线性分类器主要步骤以下：设计线性分类器主要步骤以下：4.1.3 设计线性分类器主要步骤设计线性分类器主要步骤第32页用最优化技术求出准则函数极值解 和 w*或a*。这么就能够得到线性判别函数或设计线性分类器主要步骤以下：设计线性分类器主要步骤以下：4.1.3 设计线性分类器主要步骤设计线性分类器主要步骤第33页4.2 Fisher线性判别线性判别nFisher线性判别函数是经典判别方法之一，应用非常广泛。n应用统计方法处理模式识别问题时，困难之一是维数问题。n在低维空间里行得通方法，在高维空间里往往行不通。n所以，降低维数有时就成为处理实际问题关键。第34页n在数学上通常能够把 d 维空间样本投影到一条直线上，形成一维空间，即把维数压缩到一维。n在普通情况下，总能够找到某个方向，使在这个方向直线上，样本投影能分开得最好。n问题是怎样依据实际情况找到这条最好、使最易于分类投影线。这就是Fisher法所要处理基本问题(见图 4.4)。4.2 Fisher线性判别线性判别第35页4.2 Fisher线性判别线性判别第36页从从 d 维空间到一维空间数学变换方法维空间到一维空间数学变换方法n假设有一集合 X 包含 N 个 d 维样本 x1，x2，xN，其中 N1 个属于1 类样本记为子集 X1，N2 个属于2 类样本记为 X2，若对 xn 分量作线性组合可得标量yn=wTxn,n=1，2，Nin这么便得到 N 个一维样本 yn 组成集合，并可分为两个子集 Y1 和 Y2。4.2 Fisher线性判别线性判别第37页w*就是最好投影方向n从几何上看，假如|w|=1，则每个 yn 就是相对应 xn 到方向为 w 直线上投影，实际上，w 绝对值是无关紧要，它仅使 yn 乘上一个百分比因子，主要是选择 w 方向。nw 方向不一样，将使样本投影后可分离程度不一样，从而直接影响识别效果。n所以，前述所谓寻找最好投影方向问题，在数学上就是寻找最好变换向量 w*问题。4.2 Fisher线性判别线性判别第38页定义几个基本参量定义几个基本参量n在 d 维 X 空间n各类样本均值向量mi，i=1，2 n样本类内离散度矩阵 Si 和总类内离散度矩阵 Sw，i=1，2 Sw=S1+S24.2 Fisher线性判别线性判别第39页n样本类间离散度矩阵SbSb=(m1 m2)(m1 m2)Tn其中 Sw 是对称半正定矩阵，而且当 Nd 时通常是非奇异。nSb 也是对称半正定矩阵，在两类条件下，它秩最大等于 1。定义几个基本参量定义几个基本参量4.2 Fisher线性判别线性判别第40页在一维在一维 Y Y 空间空间n各类样本均值，i=1，2 样本类内离散度 和总类内离散度4.2 Fisher线性判别线性判别第41页定义定义Fisher准则函数准则函数n希望投影后，在一维 Y 空间里各类样本尽可能分得开些，即希望两类均值之差越大越好；n希望各类样本内部尽可能密集，即希望类内离散度越小越好。所以，能够定义Fisher准则函数为：4.2 Fisher线性判别线性判别第42页n寻找使JF(w)尽可能大 w 作为投影方向。但 JF(w)式并不显含w，所以必须设法JF(w)将变成w显函数。尽可能大尽可能小Fisher准则函数准则函数4.2 Fisher线性判别线性判别第43页Fisher准则函数准则函数4.2 Fisher线性判别线性判别第44页Fisher准则函数准则函数4.2 Fisher线性判别线性判别第45页Fisher准则合理性：准则合理性：nJF(w)只与投影方向相关，与大小无关若w是一个最优解，kw也是最优解，k是任何不为零常数。4.2 Fisher线性判别线性判别第46页Fisher最正确投影方向求解：最正确投影方向求解：n要求：Sw=S1+S2正定。不然，存在投影方向w，使得wTSww=0，全部数据被投影到一点上。JF(w)没有极大值。n求出最正确投影方向上任何一个w即可。nJF(w)有上界，最正确投影方向一定存在！(Sb)max，(Sw)min分别是Sb，Sw矩阵最大、最小特征根。4.2 Fisher线性判别线性判别第47页Fisher最正确投影方向求解：最正确投影方向求解：n一定存在一个最优w，满足wTSww=1，因为Sw 正定。无约束最优化：等价于带约束最优化：max wTSbw wTSww=14.2 Fisher线性判别线性判别第48页n因为分母等于1是非零常数，wTSww=10n定义 Lagrange 函数为JF(w)是广义Rayleigh商，带等式约束最优化，能够用Lagrange乘子法求解。Fisher最正确投影方向求解：最正确投影方向求解：4.2 Fisher线性判别线性判别第49页式中 为Lagrange乘子，将上式对w求偏导数，得Fisher最正确投影方向求解：最正确投影方向求解：4.2 Fisher线性判别线性判别第50页最优解满足：最优解满足：n其中 w*就是 JF(w)极值解。因为Sw非奇异，上式两边左乘 ，可得 Fisher最正确投影方向求解：最正确投影方向求解：4.2 Fisher线性判别线性判别第51页解上式是求普通矩阵 本征值问题。依据类间离散度Sb 定义，上式左边 Sbw*能够写成Fisher最正确投影方向求解：最正确投影方向求解：注意 是一个数，所以 总是在向量(m1m2)方向上。4.2 Fisher线性判别线性判别第52页n只关心投影方向：w*就是使Fisher准则函数JF(w)取极大值时解，也就是d维X空间到一维Y空间最好投影方向。Fisher最正确投影方向求解：最正确投影方向求解：4.2 Fisher线性判别线性判别第53页几种分类阈值确定几种分类阈值确定n均值中点法类样本数加权法4.2 Fisher线性判别线性判别第54页n依据决议规则先验概率加权法就可判断x属于什么类别。y y0 x120，n=1，2，N权向量a即可。a被称作分离向量(separating vector)或解向量(solution vector)。样本规范化样本规范化 4.3.1 几个基本概念几个基本概念 线性可分性线性可分性第63页 解向量和解区解向量和解区解向量假如存在，则必在 正侧，因为只有在正侧才能满足 。4.3.1 几个基本概念几个基本概念 线性可分性线性可分性第64页 解向量和解区解向量和解区4.3.1 几个基本概念几个基本概念 线性可分性线性可分性第65页4.3.2 梯度下降算法梯度下降算法，n=1,2，N，设有一组样本y1，y2，yN，其中yn是规范化增广样本向量，目是找一个解向量 a，使n采取方法是：定义一个准则函数J(a)，当a是解向量时，J(a)最小。标量函数最小化问题用梯度下降法。第66页4.3.2 梯度下降算法梯度下降算法 n梯度下降法原理：从随意选择权向量a(1)开始，计算其梯度向量 J(a(1)，a(2)由自a(1)向下降最陡方向移一段距离得到。设定步长学习率(learn rate)或正百分比因子。取得权向量序列，使J(a)极小第67页Algorithm 1(Basic gradient descent)：1 begin initialize a;criterion,(),k 02 do k k+13 a a (k)J(a)4 until|(k)J(a)|5 return a6 end4.3.2 梯度下降算法梯度下降算法 第68页n其中H是赫森矩阵，是J(a)在a(k)二阶偏导：4.3.2 梯度下降算法梯度下降算法 n梯度下降法存在问题：怎样选择学习率(k)？假如(k)太小，收敛将非常慢；而假如(k)太大话可能会过冲(overshoot)，甚至发散。n牛顿下降法：第69页n牛顿下降法：Algorithm 2(Newton descent)1 begin initialize a;criterion 2 do3 a aH1J(a)4 until|H1J(a)|5 return a6 end4.3.2 梯度下降算法梯度下降算法 第70页n简单梯度下降法和牛顿下降法比较:简单梯度下降法牛顿(二阶)算法每一步都给出更加好步长但求赫森逆矩阵计算量很大4.3.2 梯度下降算法梯度下降算法 第71页4.3.3 感知器准则函数感知器准则函数(perceptron criterion function)n结构这么一个准则函数n式中Yk是被权向量a错分类样本集合。n当y被错分类时n也就是说，当且仅当不存在错分样本，即Yk为空集时第72页4.3.3 感知器准则函数感知器准则函数n求准则函数梯度第73页n感知器准则函数算法(批处理)：Algorithm 3(Batch Perceptron)1 begin initialize a;(),criterion,k 02 do k k+13 a a+(k)yYky4 until|(k)yYky|0所表示不等式组，4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第95页n为使解更可靠，引入余量b 0，那么规范化增广样本矩阵4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第96页对于(4-47)式能够定义准则函数(4-47)N维向量4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第97页假如 则 和 同号，所以，反之，假如有一些yi不满足 ，则 和 异号，所以，。不满足yi越多，越大。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第98页显然，取极小值时a为最优解a*。而且在不等式组一致情况下，在不等式组不一致情况下，。称为最小错分样本数准则1。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第99页共轭梯度算法基本概念共轭梯度算法基本概念n设B是一个dd阶对称正定矩阵，若有两个d维向量u和v使(u，Bv)=0，则称u和v对于矩阵B互为共轭。n显然，若u和v对于单位阵I互为共轭，则u和v正交，当x和y是B本征向量时，有 (y，Bx)=(y,x)=(y，x)=0n所以，一个正定矩阵B本征向量对于B互为共轭。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第100页n共轭梯度算法就是以Ed空间中一组对于B互为共轭向量作为一维搜索方向，使二次正定函数f(x)=b0+bTx+xTBx n到达极小值最优化算法。n用共轭梯度法能够求得序列x0，x1，x2，使得f(x0)f(x1)f(x2)n能够证实，对于二次正定函数f(x)，最多用d步，就能够使序列x收敛于f(x)极值解x*。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第101页n所以，在沿d个(对于增广空间则为d+1个)互为共轭向量进行一维搜索后，有可能达不到准则函数最小值，即算法经过d(或d+1)步可能不收敛，这时就要重新开始计算，若用r表示重新开始周期，则r=d(或d+1)。因为 式定义准则函数不是一个二次正定函数，而是一个分段二次正定函数，4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第102页在任意点 ，负梯度方向可表示为4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 令第103页n这种算法详细步骤以下：用k表示迭代步数，用 表示满足于 不等式数目，表示最优解。置k=0，并任意给定初始权向量 ，计算 和 。假如 ，则令然后继续。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 假如 ，则令 ，停顿；假如 ，则令 ，停顿；不然继续。第104页计算gk。假如gk=0，则停顿；不然计算 ，然后继续。求k。假如k为r整数倍，则令k=0；不然令k=1，并计算Sk表示第k次搜索时梯度下降方向。若 表示对 第一次迫近，则 。能够证实，由上述表示式所产生S1，S2，对于二次函数中正定矩阵是互为共轭。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第105页寻找最正确步长vk，即计算使 取极小值时v。令 ，并计算 。令k=k+1，转向步骤2。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第106页Nagaraja和Krishna证实，对于 表示分段二次函数，在 一致条件下，上述算法能够在有限步内使序列收敛于最优解。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 而在 不一致条件下，只要适当选择b，使在 唯一极小点 上，有，i=1，2，N第107页则该算法产生序列a也在有限步内收敛于 a*。对于 表示准则函数，在不等式组不一致情况下，对一些样本，可能存在 所以就产生了一个阈值问题。这时，因为 aTyi0，yi应被正确分类；但又因为 aTyi0收敛于解a*。在不一致情况下，因为Jq1(a)是严格凸函数，其唯一极小点是a=0，而且有4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第109页所以，aTyi bi(i=1，2，N)条件不成立，所以得不到解向量a*。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 作为准则函数来处理上述问题。显然，这时存在以下关系：第110页也就是说，使 最小，同在终止条件和 下使 最小是等价。这时需要将上述算法步骤1和4改变以下：4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 经过原有算法得到一个收敛点，记为 ，并以此作为补充算法起点。计算 和 ，而且继续。第111页能够证实，这么得到Sk依然是 下降方向。同时能够证实，假使Ya0是不一致，且在求Jq1(a)最小值过程中用步骤代替原算法步骤4，若所得序列a是有限，则序列最终一个元素就相当于F(a)一个局部最小值解。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第112页若序列是无限，则它趋向于F(a)一个局部最小值解。在进行上述计算时，因为我们使用原算法收敛点as 作为起始点，它经常是全局最优解F(a)一个很好迫近，故能够得到全局最优解。4.4.1解线性不等式组共轭梯度法解线性不等式组共轭梯度法 第113页4.4.2解线性不等式组搜索法解线性不等式组搜索法 n考虑齐次线性不等式组n其中 矩阵 n为规范化增广样本矩阵，每 一 行 yi代表一个样本，N为样本数，为yi维数。n且有第114页式中 实际上是 所满足不等式数目。称之为最小错分样本数准则2。使Jq2(a)取最大值a就是要求解 a*。n现在定义另一个形式最小错分样本数准则以下：4.4.2解线性不等式组搜索法解线性不等式组搜索法 第115页n所以，N个样本向量所建立超平面把权空间划分成为凸多棱锥有限集合，每个锥C都由有限个支撑超平面所组成。对于每个yi，方程yia=0在权空间中建立了一个超平面Hi，而且全部超平面都经过原点。n组成锥一部分超平面，或超平面截取部分，称为锥“前沿”，欧氏空间Ed中 个超平面交叫做锥棱。4.4.2解线性不等式组搜索法解线性不等式组搜索法 第116页n图4.10示出三维凸多棱锥及其前沿和棱一个例子。C+C+C+C原点前沿棱图 4.10而且某个锥C中任何权向量对样本集划分都是相同，或者说，某个锥中全部权向量所满足不等式数目是相同。锥C中每一个点，都对应一个权向量a4.4.2解线性不等式组搜索法解线性不等式组搜索法 第117页n假如某个锥C中任何权向量都能使上式准则函数为最大，那么就称这个锥为最小错误锥，记为C*。n这么，求使最多数目标不等式得到满足权向量 问题，就转化为寻找一个或多个最小错误锥C*问题了。n因为对于每个CEd，存在着对称反射，即 维权向量 和 所产生分类情况恰好相反，所以，假如对于某个存在4.4.2解线性不等式组搜索法解线性不等式组搜索法 第118页n其中n则必有 。n因为我们只关心最小错误锥，所以，我们只限于研究使锥就能够了。假如碰到情况，则用 代替 。那些4.4.2解线性不等式组搜索法解线性不等式组搜索法 第119页寻找最小错误锥寻找最小错误锥C*搜索算法。搜索算法。n定理 假设Y满足Haar(Y每个 子阵秩都是 )条件，令 是Ed中任何一条棱上权向量，不失普通性，初始棱选作前 个样本yi确定 个超平面交，即令：n那么，最优权向量 一定在下面定义搜索序列中，4.4.2解线性不等式组搜索法解线性不等式组搜索法 第120页上式中指标集Ik，k=1，2，是使 ，且那些样本yi下标i所组成集合。定理确定算法组成了一棵搜索树(见图4.11)。4.4.2解线性不等式组搜索法解线性不等式组搜索法 第121页35715148135图 4.114.4.2解线性不等式组搜索法解线性不等式组搜索法 第122页简单例子说明简单例子说明 n为清楚起见，用横截面来表示它们超平面，见图4.12。n假设有八个三维样本组成样本集，即4.4.2解线性不等式组搜索法解线性不等式组搜索法 第123页+H1H2H7H4H3H8H5H2H1H6H7H4H3H8H5H6C图 4.124.4.2解线性不等式组搜索法解线性不等式组搜索法 第124页+H1H2H7H4H3H8H5H2H1H6H7H4H3H8H5H6C图 4.12n设 n所以，nI1=3，5，7。n选I1中第一个 元素i1=3，n用H3代替中H1，得 n因为4.4.2解线性不等式组搜索法解线性不等式组搜索法 第125页n接接着着选选I2中中第第一一 个个 元元 素素 i2=1，用用H1代代替替中中H2，就得到，就得到n因为n ，所以I2=1，5因 n所以搜索序列到此就终止了。+H1H2H7H4H3H8H5H2H1H6H7H4H3H8H5H6C图 4.124.4.2解线性不等式组搜索法解线性不等式组搜索法 第126页+H1H2H7H4H3H8H5H2H1H6H7H4H3H8H5H6C图 4.12nI2中元素已全部考虑过，现在再考虑I1中第二个元素，令i1=5，用H5代替中H1，得n选I2中第二个元素，i2=5，用H5代替中H2，得到4.4.2解线性不等式组搜索法解线性不等式组搜索法 第127页+H1H2H7H4H3H8H5H2H1H6H7H4H3H8H5H6C图 4.12选i2=1，得 选i2=4，得 选i2=8，得 由此可得I2=1，4，84.4.2解线性不等式组搜索法解线性不等式组搜索法 第128页n最终考虑I1中得第三个元素，取i1=7，从而得+H1H2H7H4H3H8H5H2H1H6H7H4H3H8H5H6C图 4.12n由此可得I2=1，3，5，选i2=1，得 选i2=3，得 选i2=5，得 至此，搜索过程结束。至此，搜索过程结束。第129页n这是一个非穷举型搜索算法，它比E3中全部可能搜索数目 要小得多。n在上面12条棱搜索过程中，能够看到最优解出现在 和 上，由此便可求得最优权向量 。4.4.2解线性不等式组搜索法解线性不等式组搜索法 第130页