最优化应用(数据处理)

最优化问题的数据处理以及Matlab求解摘要数学问题是科学研究领域经常需要解决的问题. 研究者通常将自己研究的问题用于数学建模的方法建立起数学模型, 然后通过求解数学模型的方法获得所研究问题的解.基于Matlab语言的应用数学问题的求解方法, 有着优于其他两种计算机数学语言Mathematica和Maple无法比拟的优势和适用面. 本文主要介绍的是有约束的线性规划和二次型规划的Matlab求解过程.关键词: 数学模型线性规划二次型规划无约束问题约束问题1．最优化方法应用背景在生活和工作中, 人们对于同一问题往往会提出多种解决方案,并通过各方面的论证从中提取最佳方案. 最优化方法就是专门研究如何从多个方案中科学合理的提取出最佳方案的科学. 由于优化问题无处不在, 目前最优化方法的应用和研究已经深入到了生产和科研的各个领域, 如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等, 并取得了显著地经济效益和社会效益.用最优化方法求最优化问题的技术称为最优化技术, 它包含两个方面的内容:1) 建立数学模型即用数学语言来描述最优化问题. 模型中的数学关系式反映了最优化问题所要达到的的目标和各种约束条件.2) 数学求解数学模型建好以后, 选择合适的最优化方法来进行求解.最优化方法的发展很快, 现在已经包含有多个分支, 如线性规划、非线性规划、整数规划、动态规划、多目标规划等.利用MATLAB优化工具箱可以求解线性规划、非线性规划和多目标规划问题. 具体而言, 包括线性、非线性最小化, 最大最小化, 二次规划, 半无限问题, 线性、非线性方程(组)的求解, 线性、非线性的最小二乘问题. 另外, 该工具箱还提供了线性、非线性最小化, 方程求解, 曲线拟合, 二次规划等问题中大型课题的求解方法. 为优化方法在工程中的实际应用提供了更方便快捷的途径.关于最优化方法以及支持向量机的理论知识可参考文献[1][2].2.主要的数据处理方法本学期学习的数据处理方法主要有矩阵分解、线性判别分析和局部降维方法.2.1. 矩阵分解矩阵分解[3]是将矩阵拆解为数个矩阵的乘积, 可分为三角分解、满秩分解、QR分解、Jordan 分解和奇异值分解等, 常见的有三种: 三角分解法(Triangular Factorization), QR分解法(QR Factorization), 奇异值分解法(Sigular Value Decomposition, SVD).三角分解法是将原正方矩阵分解成一个上三角形矩阵或是排列的上三角形矩阵和一个下三角形矩阵, 这样的分解法又称为LU分解法. 它的用途主要在简化一个大矩阵的行列式值的计算过程, 求反矩阵, 和求解联立方程组. 不过要注意这种分解法所得到的上下三角形矩阵并非唯一, 还可找到数个不同的一对上下三角形矩阵, 此两三角形矩阵相乘也会得到原矩阵. 在MATLAB 中是以lu 函数来执行lu 分解法, 其语法为[L, U]=lu(A).QR 分解法是将矩阵分解成一个正规正交矩阵与上三角形矩阵, 所以称为QR 分解法, 与此正规正交矩阵的通用符号Q 有关. 在MATLAB 中是以qr 函数来执行QR 分解法, 其语法为[Q, R]=qr(A).奇异值分解(sigular value decomposition, SVD) 是另一种正交矩阵分解法. SVD 是最可靠的分解法, 但是它比QR 分解法要花上近十倍的计算时间. [U, S, V]=svd(A), 其中U 和V 代表二个相互正交矩阵, 而S 代表一对角矩阵. 和QR 分解法相同者, 原矩阵A 不必为正方矩阵. 使用SVD 分解法的用途是解最小平方误差法和数据压缩. 在MATLAB 中是以svd 函数来执行svd 分解法, 其语法为[S, V , D]=svd(A).特征值分解(Eigen-Value Decomposition,简称EVD)[4]被应用于科研和工程的很多领域,如主成分分析算法、人工视觉等.其理论知识如下.设n n A R ⨯∈, 则A 是正规阵当且仅当存在正交阵n n U R ⨯∈使得T A U U =∑, 其中12(,,,)n diag λλλ=∑L . 其中12,,,nλλλL 都是A 的特征值. 设n n A R ⨯∈是对称非负定矩阵, 且秩A r =. 则存在正交阵n n U R ⨯∈, 使得0, 0 0T A U U ⎡⎤=⎢⎥⎣⎦∑其中121(,,,), 0r r diag λλλλλ=≥≥>∑L L 是A 的全部非零特征值.奇异值分解(Singular Value Decomposition,简称SVD)是线性代数中一种重要的矩阵分解, 是矩阵分析中正规矩阵酉对角化的推广. 在信号处理、统计学等领域有重要应用.设n n A R ⨯∈,且秩A r =.则存在两个正交阵, m m n n U R V R ⨯⨯∈∈, 使得0, 0 0T A U V ⎡⎤=⎢⎥⎣⎦∑其中∑是一个r 阶对角阵, 121(,,,), 0r r diag λλλλλ=≥≥>∑L L , i λ是A 的全部非零奇异值. 所有的矩阵都可以进行奇异值分解, 而只有方阵才可以进行特征值分解.2.2．线性判别分析线性判别式分析(Linear Discriminant Analysis, LDA)[5], 也叫做Fisher 线性判别(Fisher Linear Discriminant , FLD), 是模式识别的经典算法, 它是在1996年由Belhumeur[6]引入模式识别和人工智能领域的. 线性判别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间, 以达到抽取分类信息和压缩特征空间维数的效果, 投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离, 即模式在该空间中有最佳的可分离性. 因此, 它是一种有效的特征抽取方法. 使用这种方法能够使投影后模式样本的类间散布矩阵最大, 并且同时类内散布矩阵最小. 就是说, 它能够保证投影后模式样本在新的空间中有最小的类内距离和最大的类间距离, 即模式在该空间中有最佳的可分离性.设1{(,)}{1,,}n m i i i x y R r =⊂⨯L 是样本集. ()()11[,,], [,,]i im n m n i i n i n X x x R X x x R ⨯⨯=∈=∈L L . 其中1r n n n ++=L . 11n i i c x n ==∑表示总体均值, 1i i x x i c x n ∈=∑表示类均值. 称1()()r T m m b i i i i S n c c c c R ⨯==--∈∑为类间散布阵. 称1()()i rT m m w i i i x x S x c x c R ⨯=∈=--∈∑∑为类内散布阵, 1()()r T m m t j j j S x c x c R ⨯==--∈∑为总体散布阵. 21()n b i i i tr S n c c ==-∑,21()i n w i i x x tr S x c =∈=-∑∑, 21()n t i j i tr S n x c ==-∑. LDA 的基本思想是利用Fisher 准则(()b tr S 越大越好, ()w tr S 越小越好)寻找最优变换阵m l G ⨯. 即()max .()T b T G wtr G S G tr G S G 2.3. 局部降维方法当今, 很多领域所涌现出的数据多为海量数据, 其特点往往是高维的、非线性的、非结构性的. 高维数据给现实世界中事物的描述带来了更加准确的信息. 然而, 高维特性存在着大量的冗余信息, 对数据处理问题带来了极大的复杂性. 于是高维数据降维[7]成为了近年来新兴的热门技术.高维数据降维方法已经被广泛应用在信息检索、模式识别、数据挖掘和人工智能等领域. 针对目前流形学习方法的嵌入效果非常敏感于局部邻域的选取方式, 提出一种自适应邻域选择的局部线性降维方法. 该方法评估真实数据的固有维数, 判断每一数据点的局部切方向, 以便自适应地选择每一数据点的邻域数, 使得不同数据集与邻域选取方式之间存在很好的自适应性, 实现更好的降维效果. 在人工生成数据集和医学数据上的仿真结果表明, 该方法起到了良好的降维效果.本节主要介绍以下几种局部降维方法: 局部保持投影(Locality Preserving Projection, 简称LPP), 判别局部保持投影(Discriminant LPP, 简称为DLPP), 间隔Fisher 分析(Marginal Fisher Analysis, 简称MFA), 极大间隔准则(Maximum Margin Criterion, 简称MMC).设1{(,)}{1,,}n m i i i x y R p =⊂⨯L 是样本集, 记1[,,]m n n X x x R ⨯=∈L ,()()1[,,]i i m n i i i n X x x R ⨯=∈L ,其中1r n n n ++=L . 11n i i c x n ==∑表示总体均值, 1ii x x i c x n ∈=∑表示类均值.其中LPP 的基本思想是寻找m l G ⨯使得在降维空间中保持类内的局部几何结构. 用()k i N x +表示i x 的同类k 近邻, ()k i N x -表示i x 的不同类k 近邻. 令2exp{},, ,1,, 0, i j i k j k ij x x x N x N i j n w σ+-⎧--∈∈=⎪=⎨⎪⎩L 或否则LPP 的准则是221,,1min min i j k n p T T T T i j ij i j ij k x x x G G i j G x G x w G x G x w =∈=-⇔-∑∑∑ 记1[], [,,]k k p ij w w w diag w w ==L , 11,, 1,,, (,,)k k i jk k k k k ii ij k n n x x D w i n D diag D D ===∑L L 11(,,), (,,)p p w diag w w D diag D D ==L L , L D w =-.经过变形与推导LPP 的准则变为()max .()T T T T G tr G XDX G tr G XLX G DLPP 的基本思想是在降维空间中, 对同类样本保持局部几何结构, 对不同类样本, 近的样本尽可能远离. 记2exp{},,1,,ij i j S c c t i j p =--=L .DLPP 对应的模型为1max p T T i j ij i G c G c S =-∑.记1[],,1,,pij p p ii ij i S S h S i p ⨯====∑L , 11(,,)p p pp H diag h h R ⨯=∈L . E H S =-. 经过一番变形后DLPP 的模型为 ()max .()T T T T G tr G CEC G tr G XLX G MFA 的基本思想是在降维空间中, 使得类内样本越紧凑越好, 类间原来近的越远越好.定义L D w =-. 用与LPP 同样的手法可得到MFA 的判别准则:()max .()T p T T T G tr G XL X G tr G XLX G MMC 的判别准则为max ()T T b w Gtr G S G G S G -. 3. Matlab 语言及最优化问题Matlab 语言[8]变量名应该由一个字母引导, 后面可以跟字母、数字、下划线等. 强大方便的运算功能是Matlab 语言最显著的特色. 为保证较高的计算精度, Matlab 语言中最常用的数值量为双精度浮点数, 占8字节(64位), 遵从IEEE 计数法, 有11个指数位, 53位尾数及一个符号位, 值域的近似范围为3083081.710~1.710-⨯⨯, 其Matlab 表示为double(). 考虑到一些特殊作用, 比如图像处理, Matlab 语言还引入了无符号的8位整形数据类型, 其Matlab 表示为uint8(), 其值域为0~255, 这样可以大大的节省Matlab 的存储空间, 提高了处理速度. 此外, 在Matlab 中还可以使用其他的数据类型, 如int8(), int16(), int32(), unit16(), unit32()等, 每一个类型后面的数字表示其位数, 其含义不难理解.除了用于数学运算的数值结构外, Matlab 还支持下面的数据结构:1)字符串型数据 Matlab 支持字符串变量, 可以用它来存储相关的信息. 和C 语言等程序设计语言不同, Matlab 字符串是用单引号括起来的, 而不是双引号. 2) 多维数组 三维数组是一般矩阵的直接拓展, 可以这样理解, 三维数组可以直接用于彩色数字图像的描述, 在控制系统的分析上也可以直接用于多变量系统的表示上. 在实际编程中还可以使用维数更高的数组.3) 单元数组 单元数组是矩阵的直接扩展, 其存储格式类似于普通的矩阵, 而矩阵的每个元素不是数值, 可以认为能存储任意类型的信息, 这样每个元素称为”单元”(cell), 例如, {,}A i j 可以表示单元数组A 的第i 行, 第j 列的内容.4) 类与对象 Matlab 允许用户自己编写包含各种复杂信息的变量, 亦即类变量,该变量可以包含各种下级信息, 还可以重新对类定义其计算, 这在控制系统描述中特别有用. 例如, 在Matlab 的控制系统工具中还定义了传递函数类, 可以用一个变量来表示整个传递函数, 还重新定义了该类的运算, 如加法运算可以直接求取多个模块的并联连接, 乘法运算可以求取若干模块的串联.Matlab 语句有两种结构.1) 直接赋值语句 直接赋值语句的基本结构为: 赋值变量=赋值表达式, 这一过程把等号右边的表达式直接赋给左边的赋值变量, 并返回到Matlab 的工具空间.2) 函数调用语句 函数调用语句的基本结构为: [返回变量列表]=函数名(输入变量列表), 其中, 函数名要求和变量名的要求是一致的, 一般函数名应该对应在Matlab 路径下的一个文件.接下来简单介绍下最优化技术.所谓最优化技术就是找出使得目标函数值达到最小或最大的自变量值的方法. 最优化问题从其分类看有经典无约束最优化问题和有约束最优化问题.无约束极值问题的数学模型为min ()xf x 其中12[,,]T n x x x x =L 称为优化变量,()f ⋅函数称为目标函数, 该数学表示的含义亦即求取一组x 向量, 使得最优化目标函数()f x 为最小, 故这样的问题又称为最小化问题, 那么只需给目标函数()f x 乘以一个负号就能立即将最大化问题转换成最小化问题. 所以最优化问题研究的一般全是最小化问题.有约束最优化问题的数学模型为min ().. ()0,xf x s t G x ≤其中12[,,]T n x x x x =L . 该数学表达式的含义为求取一组x 向量, 使得在满足约束条件()0G x ≤的前提下能够使目标函数()f x 最小化. 在实际遇到的最优化问题中, 有时约束条件可能是很复杂的, 它既可以是等式约束, 也可以是不等式约束; 既可以是线性的, 也可以是非线性的, 有时甚至不能用纯数学函数来描述.我们平时遇到的问题大多数是有约束条件的线性规划问题或二次规划问题, 接下来介绍线性规划问题和二次规划问题的计算机求解过程.3. Matlab 语言的问题求解3.1. 线性规划问题的计算机求解线性规划问题是一类特殊的问题, 也是最简单的有约束最优化问题. 在线性规划中, 目标函数和约束函数都是线性的, 其整个问题的数学描述为min .. , ,.T m M f xs t Ax B Aeqx Beq x x x ≤=≤≤ 求解线性规划问题有多种算法. 其中, 单纯形法是最有效的一种方法, Matlab 的最优化工具箱中实现了该算法, 提供了求解线性规划问题的linprog()函数. 该函数的调用格式为opt 012[,,flag,]linprog(,,,eq,eq,,,,OPT,,,)m M x f c f A B A B x x x p p =L其中如果各个矩阵的约束不存在, 则应该用空矩阵来占位.OPT 为控制选项, 该函数还允许使用附加参数12,,p p L .最优化运算完成后, 结果将在变量x 中返回, 最优化的目标函数将在opt f 变量中返回. 我们将通过下面的例子来演示线性规划的求解问题.例 试求解下面的线性规划问题.1234523451234512345min 243.. 24254,34562,,0, 3.32,0.678, 2.57.x x x x x s t x x x x x x x x x x x x x x -----+++≤++--≤≥≥≥≥求解 从给出的数学式子可以看出, 其目标函数可以用其系数向量[2,1,4,3,1]T f =-----表示, 不等式约束有两个, 即 0 2 1 4 254, 3 4 5 1 162A B ⎡⎤⎡⎤==⎢⎥⎢⎥--⎣⎦⎣⎦另外, 由于没有等式约束, 故可以定义eq A 和eq B 为空矩阵, x 的下界可以定义为[0,0,3.32,0.678,2.57]T m x =, 对上界没有限制, 故可以将其写成空矩阵. 由前面的分析, 可以给出如下的Matlab 命令来求解线性规划问题, 并立即得出结果为opt [19.785, 0, 3.32, 11.385, 2.57], 89.5750.T x f ==-[2 1 4 3 1]; [0 2 1 4 2; 3 4 5 -1 -1];[54; 62]; []; []; [0, 0, 3.32 0.678, 2.57];ff optimset; rgeScale 'off ';ff.TolX=1-15; ff.TolFun=1-20; ff.TolCon=1-20;T m f A B Aeq Beq x e e e >>=-=======， [,_opt,key,]linprog(,,,,,,[],[],ff )x f c f A B Aeq Beq xm =从列出的结果看, 由于key 值为1, 故求解是成功的. 以上只用了5步就得出了线性规划问题的解, 可见求解程序功能是很强大的, 可以很容易得出线性规划问题的解.3.2. 二次型规划的求解二次型规划问题是一种简单的有约束最优化问题, 其目标函数为x 的二次型形式, 约束条件为线性不定式约束. 一般二次型规划问题的数学表达式为1min 2.. , ,.T T m M x Hx f x s t Ax B Aeqx Beq x x x +≤=≤≤和线性规划相比, 二次型规划目标函数中多了一个二次项T x Hx 来描述2i x 和i j x x 项. Matlab 优化工具箱提供了求解二次型规划问题的quadprog()函数, 该函数的调用格式为opt 012[,,flag,]quadprog(,,,,eq,eq,,,,OPT,,,)m M x f c H f A B A B x x x p p =L其中, 函数调用时, H 为二次型规划目标函数中的H 矩阵, 其余各个变量与线性规划函数调用的完全一致. 我们将通过下面的例子来演示线性规划的求解问题.例 试求解下面的四元二次型规划问题.22221234123412341234min (1)(2)(3)(4).. 5,33210,,,,0x x x x s t x x x x x x x x x x x x -+-+-+-+++≤+++≤≥求解 首先应该将原始问题写成二次规划模型的模式. 展开目标函数得221122223344222212341234()214469816246830f x x x x x x x x x x x x x x x x x =-++-++-++-+=+++----+因为目标函数中的常数对最优化结果没有影响, 所以可以放心地略去. 这样就可以将二次型规划标准型中的H 矩阵和T f 向量写成([2, 2, 2, 2]), [2, 4, 6, 8]T H diag f ==----从而可以给出下列Matlab 命令来求解二次型最优化问题.[2,4,6,8]; ([2,2,2,2]);OPT=optimset; rgeScale='off';=[1,1,1,1;3,3,2,1]; =[5;10]; [];[];(4,1);[,_opt]=quadprog(, , , , , , , [], [], f H diag A B Aeq Beq LB zeros x f H f A B Aeq Beq LB >>=----====OPT)这样得出的最优解为[0, 0.6667, 1.6667, 2.6667]T x =, 目标函数的值为23.6667-. 4. 总结无论做任何一件事, 人们总是希望以最少的代价取的最大的效益, 也就是力求最好, 这就是优化问题. 最优化就是在一切可能的方案中选取一个最好的方案以达到最优目标的学科. 最优化方法, 顾名思义是为了达到最优化目的所提出的各种求解方法. 从数学意义上说, 最优化方法是一种求极值的方法, 即在一组约束为等式或不等式的条件下, 使系统的目标函数达到极值, 即最大值或最小值. 从经济意义上说, 是在一定的人力、物力和财力资源条件下, 使经济效果达到最大(如产值、利润), 或者在完成规定的生产或经济任务下, 使投入的人力、物力和财力等资源为最少.数据处理这门课程给我们的是一个工具的作用, 在学习的过程中还需要结合实际问题尤其是自己的专业方向来想问题.参考文献[1] 唐焕文, 秦学志. 实用最优化方法. 大连理工大学出版社, 2000.[2] 邓乃扬, 田英杰. 数据挖掘中的新方法: 支持向量机[M]. 北京科学出版社, 2006.[3] 李宇光,朱志德. 矩阵分解法分析及其应用研究. 哈尔滨工程大学学报, 1989年04期.[4] 袁生光. 对称矩阵特征值分解的硬件实现研究. 浙江大学, 2008.[5] Cheong Hee Park, Haesun Park. A comparison of generalized linear discriminant analysis algorithms[J]. Pattern Recongonition, 2008, 41:1083-1097.[6] Belhumeur, P.N., Kriegman, D. What is the set of images of an object under all possible lighting conditions. Computer Vision and Pattern Recognition, 1996.[7] 蒲玲. 自适应局部线性降维方法. 计算机应用与软件. 2013年04期.[8] 薛定宇, 陈阳泉. 高等应用数学问题的Matlab 求解. 清华大学出版社.2010:14-16.。