《优化问题的求解.ppt》由会员分享，可在线阅读，更多相关《优化问题的求解.ppt（27页珍藏版）》请在三一办公上搜索。
1、第11章 优化问题的求解,11.1 线性规划11.2 无约束优化11.3 单目标约束优化11.4 多目标约束优化11.5 最小二乘优化11.6 混合整数规划11.7 动态规划11.8 实例解析,本章目标：求 或,11.1 线性规划,线性规划问题是目标函数和约束条件均为线性函数的问题，其整个问题的数学描述为：MATLAB的最优化工具箱中提供的线性规划求解函数是linprog()，该函数的调用格式为：x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,.),11.2 无约束优化,非线性规划是指目标函数
2、或约束函数（或两者）为设计变量的非线性函数的一种优化方法。其标准形式为：其中求解无约束优化问题的主要算法有单纯形法、拟牛顿法和最速下降法（或共轭梯度法）等，MATLAB提供了相应算法的实现函数fminsearch()和fminunc()。它们的调用格式分别如下：x,fval,exitflag,output=fminsearch(fun,x0,options,p1,p2,.)x,fval,exitflag,output,grad,hessian=fminunc(fun,x0,options,p1,p2,.),11.3 单目标约束优化,一、带有变量边界约束的优化带有变量边界约束的优化问题的一般描述
3、为：对于单变量目标函数f(x)，MATLAB提供了fminbnd()函数求解该目标函数在区间内的极小值，该函数的调用格式如下：x,fval,exitflag,output=fminbnd(fun,x1,x2,options,p1,p2,.)对于一般的多变量目标函数f(x)，MATLAB并未提供直接的函数求解。John DErrico开发的fminsearchbnd()函数扩展了现有函数的功能，能直接求解这样的问题，该函数可以从以下网址下载：。该函数的调用格式为：x,fval,exitflag,output=fminsearchbnd(fun,x0,LB,UB,options,p1,p2,.),
4、二、多变量约束优化多变量非线性约束优化问题的一般描述为：其中，。为求解方便，约束条件还可以进一步细化为线性等式约束，线性不等式约束，这时原规划问题可以改写成MATLAB最优化工具箱中提供了一个专门用于求解各种约束下的优化问题的函数fmincon()，该函数的调用格式为：x,fval,exitflag,output,lambda,grad,hessian=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,p1,p2,.),三、二次规划一般二次型规划问题的数学表示为：MATLAB最优化工具箱中提供了求解二次规划问题的函数quadprog()，该函数的
5、调用格式为：x,fval,exitflag,output,lambda=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,.),四、半无限约束优化半无限约束优化问题的标准形式为：其中 为向量x和 的连续函数，且向量 的长度最多为2。,MATLAB最优化工具箱中提供的函数fseminf()可以直接求解半无限约束优化问题，该函数的调用格式为：x,fval,exitflag,output,lambda=fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub,options,p1,p2,.)其中ntheta是半无
6、限约束条件的个数，seminfcon是一函数名，该函数定义了非线性约束条件和半无限约束条件，该函数的一般写法如下：function c,ceq,K1,K2,.,Kntheta,S=myinfcon(x,S)%S为向量w的采样值%初始化样本间距if isnan(S(1,1),S=.%S有ntheta行2列endw1=.%计算样本集w2=.%计算样本集.wntheta=.%计算样本集K1=.%在x和w处的第1个半无限约束值K2=.%在x和w处的第2个半无限约束值.Kntheta=.%在x和w处的第ntheta个半无限约束值c=.%在x处计算非线性不等式约束值ceq=.%在x处计算非线性不等式约束值
7、,11.4 多目标约束优化,多目标优化问题的一般表示为：其中，一、极小极大优化假设有一组n个目标函数，它们中的每一个均可以提取出一个最大值而这样得出的一组最大值仍然是x的函数。现在想对这些最大值进行比较进行最小化搜索，即 则这类问题称为极小极大问题。,考虑各类约束条件，极小极大问题可以更一般地改写成MATLAB最优化工具箱中的fminimax()函数可以直接求解极小极大问题，该函数的调用格式为x,fval,maxfval,exitflag,output,lambda=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,p1,p2,.)另外，基于f
8、minimax()函数，还可以求解相关的变形问题，如极小极小优化问题：,二、目标规划目标规划的标准形式如下：MATLAB最优化工具箱中提供了函数fgoalattain()来求解目标规划问题，该函数的调用格式为：x,fval,attainfactor,exitflag,output,lambda=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options,p1,p2,.),11.5 最小二乘优化,一、线性最小二乘优化线性最小二乘优化问题的一般数学描述为：MATLAB优化工具箱提供了函数lsqlin()来直接求解上述优化问题，该
9、函数的调用格式为：x,resnorm,residual,exitflag,output,lambda=lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,.),实际问题中经常会遇到下面的非负最小二乘优化问题：对于这种问题，MATLAB提供的lsqnonneg()函数可以用来轻松求解。lsqnonneg()函数的调用格式为：x,resnorm,residual,exitflag,output,lambda=lsqnonneg(C,d,x0,options),二、非线性最小二乘优化对于多目标规划问题其中，则可以按照下面的方式将其转换成单目标优化问题：这就是所
10、谓的非线性最小二乘优化。对于该问题固然可以利用前面介绍的函数求解，此外，MATLAB最优化工具箱还提供了lsqnonlin()函数直接求解这个问题，该函数的调用格式为：x,resnorm,residual,exitflag,output,lambda,jacobian=lsqnonlin(fun,x0,lb,ub,options,p1,p2,.),11.6 混合整数规划,一、线性整数规划（LIP）所谓线性整数规划，就是在线性规划的基础上，使得全部或部分自变量取整数。线性整数规划的一般数学描述为：MATLAB本身没有提供线性整数规划问题的求解函数，但如果已知自变量所在的区间，则理论上可以用穷举法
11、列出区间内所有的变量组合，逐个判定约束条件是否满足，从满足的组合中逐个求取函数的值并排序，由其最小值的对应关系可以简单地求解所需的自变量值。该方法看似简单直观，但它仅对于一些小规模问题可行。因此需要另外寻找比较好的算法求解线性整数规划问题，下面介绍常用的分支定界法。,分支定界法（分而治之）步骤：（为便于叙述，将要求解的整数规划问题称为LIP，将与它对应的线性规划问题称为LP）（1）求解问题LP，将得到以下情况之一：LP没有可行解，这时LIP也没有可行解，则停止；LP有最优解，并且解变量都是整数，则它也是LIP的最优解，则停止；LP有最优解，但不符合LIP中的整数条件，此时记它的目标函数值为，这
12、时若记 为LIP的最优目标函数值，则必有。（2）分支与定界首先在LP的最优解中任选一个不符合整数条件的变量x，设其值为l，构造两个约束条件：,将这两个约束条件分别加入问题LP，将问题LP分为两个后继问题LP1和LP2，不考虑整数条件要求，求解LP1和LP2，以每一个后继子问题为一分支并标明求解的结果，与其他问题的解的结果一道，找出最优目标函数值最小者作为新的下界，替换,从已符合整数条件的各分支中，找出目标数值为最小者作为新的上界,即有。（3）比较与剪支各分支的最优目标函数中若有大于 者，则剪掉这一支（即这一支所代表的子问题已无继续分解的必要）；若小于，且不符合整数条件，则重复第一步骤，一直到最
13、后得到的最优目标函数值 为止，从而得到最优整数解。,分支定界法的MATLAB实现因为MATLAB本身并没有提供求解线性整数规划问题的函数，所以我们有必要根据分支定界法的步骤自行设计其求解函数，但是幸运的是Thomas Trtscher编写了函数miprog()及几个附带函数，这几个函数可以从以下网址上下载：该函数的调用格式为：x_best=miprog(f,A,b,Aeq,beq,lb,ub,yidx,options)其中，参数yidx为整数变量指标列向量，1代表整数，0代表实数。注意：这里的yidx是一个逻辑向量，且它至少要含有一个逻辑1。,二、非线性整数规划（NLIP）一般非线性整数规划的
14、数学描述为：同样地，MATLAB最优化工具箱中没有提供求解一般非线性规划问题的函数。不过幸好荷兰Groningen大学的Koert Kuipers编写了函数bnb20()直接求解一般非线性整数规划的问题。该函数可以从以下网址下载：该函数也是基于分支定界的思想设计的，该函数的一般调用格式为：errmsg,f,x,t,c,fail=bnb20(fun,x0,xstatus,lb,ub,A,b,Aeq,beq,nonlcon,settings,options,p1,p2,.),三、0-1规划所谓0-1规划，即指自变量的值或者为0，或者为1。所以求解0-1规划看起来很简单，让每个自变量遍取0,1，在得
15、出的组合中选择既满足约束条件又使目标函数取最小值的项。但这种完全穷举法的思想也仅适用于小规模问题。故仍然需要考虑其他算法进行求解。自MATLAB 7.0版本起，MATLAB最优化工具箱中提供了一个新函数bintprog()专门用来求解0-1规划问题。该函数的调用格式为：x,fval,exitflag,output=bintprog(f,A,b,Aeq,beq,x0,options),一、动态规划的基本概念 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义：(一)阶段和阶段变量 为了便于求
16、解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目。,11.7 动态规划,（二）状态、状态变量和可能状态集 1.状态与状态变量：描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量包含在给定的阶段上确定全部允许决策所需要的信息。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终
17、止状态记为sk+1。通常定义阶段的状态即指其初始状态。2可能状态集 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定（三）决策、决策变量和允许决策集合 决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量。决策变量的值可以用数，向量、其它量，也可以是状态变量的函数，记以uk=uk(sk)，表示于阶段k状态sk时的决策变量。决策变量的取值往往
18、也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示,uk(sk)Uk(sk)允许决策集合实际是决策的约束条件。,（四）策略和允许策略集合 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分，全过程策略是指由依次进行的n个阶段决策构成的决策序列，简称策略，表示为p1,nu1,u2,un。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,nuk,uk+1,un，显然当k=1时的k部子策略就是全过程策略。在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它
19、们组成的集合，称之允许策略集合，记作P1,n，从允许策略集中，找出具有最优效果的策略称为最优策略。（五）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1。对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策 uk(sk)所确定，与系统过去的状态 s1,s2,sk-1及其决策u1(s1),u2(s2)，uk-1(sk-1)无关。系统状态的这种转移，用数学公式描述即有：通常称上式为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转
20、移，还是有一定规律可循的。,(六)指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。1)阶段指标函数（阶段效应）用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk2)过程指标函数（目标函数）用Rk(sk,uk)表示第k子过程的指标函数。Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:实际应用
21、中上式可表示为 Rk(sk,uk)或 Rk(sk)；过程指标函数 Rk(sk)通常是描述所实现的全过程或 k 后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数 gk(sk,uk)累积形成的。,适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式对于k部子过程的指标函数可以表示为：（表示某种运算）多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如总之，具体问题的目标函数表达形式需要视具体问题而定。,(七)最优解 用fk(sk)表示第k子过程指标函数，在状态sk下的最优
22、值,即 称fk(sk)为第k子过程上的最优指标函数；相应的子策略称为sk状态下的最优子策略，记为pk*(sk)；而构成该子策赂的各段决策称为该过程上的最优决策，记为故有 简记为：特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。但若取值不唯一,则问题的最优值记为f0，有最优策略即为s1=s1*状态下的最优策略：我们把最优策略和最优值统称为问题的最优解。,(八)多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:式中“OPT”表示最优化，视具体问题取max或min。上述数学模型说明
23、了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列，使之既满足上式给出的全部约束条件，又使上式所示的目标函数取得极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线。,二、动态规划逆序算法的MATLAB实现在编写程序之前，需要建立动态规划模型，这常归纳为以下几个步骤：将问题恰当划分为若干个阶段；正确选择状态变量，使它既能描述过程的演变，又满足无后效性；规定决策变量，确定每个阶段的允许决策集合；写出状态转移方程；确定各阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。根据上述步骤可以编写利用逆序算法求解动态规划问题的程序dynprog.m，程序的具体内容见书本。,
