非线性规划的罚函数算法
摘要：最优化理论和方法是一门十分活跃的学科，罚函数法是将约束问题无约束化的一种主要方法。本文简要介绍了最优化问题的优化算法，主要介绍了非线性规划的罚函数算法的基本理论和相应的发展过程。
关键词：最优化理论；非线性规划；惩罚函数法
1 前言
最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一门独立的学科还是在上世纪40年代末．Dantzing在1947年提出求解一般线性规划问题的单纯形算法之后，随着工业革命、信息革命的不断深化，以及计算机技术的巨大发展，至今短短的几十年，它得到了迅猛的发展．现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学技术等方面得到了广泛的应用，成为一门十分活跃的学科．
约束非线性规划问题广泛见于工程、国防、经济等许多重要领域．求解约束非线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方法和拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法．罚函数方法通过求解一个或多个罚问题来得到约束规划问题的解，如果当罚参数充分大时，求单个罚问题的极小点是原约束规划问题的极小点，则称此罚问题中的罚函数为精确罚函数，否则称为序列罚函数．针对传统罚函数的定义而言，若罚函数是简单的、光滑的，则它一定是不精确的；若罚函数是简单的、精确的，则它一定是不光滑的；若罚函数是精确的、光滑的，则它一定是复杂的．因此我们的工作是对传统罚函数进行了改造，主要是引入了指数型罚函数和对数型罚函数，并在改造后的罚函数中增添了乘子参数，使之成为既是简单的、光滑的，又是精确的结
果．我们把这类罚函数称为简单光滑乘子精确罚函数．所谓简单的，即罚函数中包含原问题中的目标函数和约束函数而不包含它们的梯度，若罚函数中包含有原问题中目标函数和约束函数的梯度，则称为是复杂的．
2求解最优化问题的介绍和方法分类
2.1最优化问题及分类
优化技术是一种以数学为基础的，用于求解各种工程问题优化解的应用技术，作为一个重要的科学分支一直受到人们的广泛注视，并在诸多工程领域得到迅速的推广和应用，如系统控制、人工智能、模式识别、生产调度、计算机工程等等。实现生产过程的最优化，对提高生产效率和生产效益、节约资源具有重要的作用。同时优化方法的理论研究对改进算法的性能、拓宽算法应用领域、完善算法体系同样具有重要作用。因此，优化理论与算法的研究时一个同时具有理论意义和应用价值的重要课题。最优化分为最小化和最大化，本文是求解最大化[10]。
优化方法涉及的工程领域很广，问题种类与性质繁多。归纳而言，最优化问题可以分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间内连续变量，而组合优化的对象则是解空间中的离散状态。
对于求解函数受约束问题的最优化，除了局部极大值的存在，影响最优化性能的因素主要包括：
（1）目标函数所对应曲面的拓扑性质，譬如在相同约束下，线性或凸函数比无规律的函数要容易求解。
（2）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量；同事，约束在可行区域边界上的变化强度与惩罚项的确定也有较大关系。
（3）目标函数在整个搜索空间中整体优化解与可行区域中最优解之比，特别当整体最优解离可行区域很近时将使其对惩罚项非常敏感。
（4）在最优解处活跃约束的数目，活跃约束数目越多，则最优解离可行区域的边界越近。
许多场合将受约束问题转化为无约束问题来处理，常用的途径有：
（1）把问题的约束在状态的表达形式中体现出来，并设计专门的算子，使状态所表示的解在搜索过程中始终保持可行性。这种方法最直接，但适用领域有限，算子的设计也较困难。
（2）在编码过程中不考虑约束，而在搜索过程汇总通过检验解的可行性来
决定接的弃用。这种方法一般只适用于简单的约束问题。
（3）采用惩罚的方法来处理约束的束越界问题。这种方法比较通用，适当选择惩罚函数的形式可得到较好的效果。
2.2 优化算法及分类
所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定得途径或规则来得到满足用户要求的问题的解。
就优化机制与行为分析而分，目前工程中常用的优化算法分为：经典算法、构造性算法、改进型算法、基于系统动态眼花的算法和混合算法等。
（1）经典算法。包括线性规划、动态规划、整数规划和分支定界等运筹学中的传统算法，其算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用。
（2）构造型算法。用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要。譬如，调度问题中的典型构造型方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、NEH法。
（3）改进型算法，或称领域搜索算法。从任一解出发，对其领域的不断搜索和当前解得替换来实现优化。根据搜索行为，它又可以分为局部搜索法和指导性搜索法。
局部搜索法。以局部优化策略在当前解的领域中贪婪搜索，如只接受优于当前解的状态作为下一当前的爬山法；接受当前解领域中的最好解作为下一当前解得罪陡下降法等。
指导性搜索法。利用一些指导规则来指导整个解空间中优良解得探索，如SA、GA、EP、ES和TS等。
（4）基于系统动态演化的方法。将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等。
（5）混合性算法。值上述各种算法从结构会操作上相混合而产生的各类算法。
优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法，局部优化算法和全局优化算法等。
3 罚函数算法的基本理论
3.1 简单罚函数法
罚函数方法的基本思想就是把约束问题变换成无约束问题来求解，采用的方法是在目标函数上加上一个或多个与约束函数有关的函数，而删去约束条件。 考虑问题
min ()f x
(P) ..()0,1,2,,i s t g x i m ≤=
()0,1,2,,j h x j r ==
x X ∈
其中 m X R ?。
罚函数法就是将问题P 换成如下形式：
[]11(,,)()()()m r k k k i k j j j Q x f x g x h x λμλφμψ==??=++??∑∑
其中，()y φ，()y ψ为连续函数，且满足()0,0y y φ=≤且()0,0y y φ>>；且
(()0,0y y ψ==且()0,0y y ψ>≠，而k λ，k μ为罚因子，(,,)k k Q x λμ称为罚函数．
若,k k k λλμ==，则是一个无约束问题；若出现一列,k k λμ，1,2,k k λ= ，k μ↑+∞则是一系列无约束问题．
罚函数法主要分SUMT(Sequential Unconstrained Minimization Techniques)法，增广Lagrange 罚函数法和精确罚函数法三类．它们有一点共同点就是对不可行点要予以惩罚其惩罚大小体现在罚参数,k k λμ及(),()y y ψφ上．用罚函数方法来解约束最优化问题通常认为最早由Courant 在求解线性规划时提出。后来，Camp[48]和Pietrgykowski[47]讨论了罚函数方法在解非线性规划问题中的应用。Fiacco 和McCormick[1]一[6]在利用罚函数方法，即序列无约束极小化方法上作了不少工作，并总结为SUMT 方法．
3.2 内点罚函数法
内点罚函数法是利用内点罚函数求解仅含不等式约束的非线性规划问题
（P1） min ()f x
..()0,1,2,,i s t g x i m ≤=
的方法，其中(),(),1,2,,i f x g x i m = 是连续函数。记1()((),,())T m g x g x g x = ，则（P1）
的可行域{}
|()0n S x R g x =∈≤。内点罚函数法是在S 的边界上建造一个“围墙”，使迭代点在S 的内部，因此内点罚函数法由称为SUMT 内点法。
设(P1)的可行域S 内部非空，即{}
int |()0n S x R g x =∈<≠?，在int S 内构造关于()g x 单调增连续函数
0,()0()(()),int ,()0
i g x B x B g x x S g x ->为罚因子。
为求解(P1)，我们考虑无约束优化问题：
min (,)F x r
记其最优解为x(r)。当r 0→时，x(r)趋于(P1)的最优解。
3.3 乘子法
乘子法是将增广 Lagrange 函数作为罚函数求解约束优化问题的方法。本文仅对Hestenes-Powell 乘子法做一简介。
首先考虑仅含等式约束的非线性规划问题（P2）
min ()f x
..()0,1,2,,j s t h x j p ==
其中()f x ，()0,1,2,,j h x j p == 是连续函数。记1()((),,())T p h x h x h x = ，则
（P2）的可行域为{}
|()0n S x R h x =∈=。 先分析用简单罚函数求解（P2）的弊端。当α取2时，
2
1(,)()()p j j F x M f x M h x ==+∑，1(,)()2()()p
x j j j F x M f x M h x h x =?=?+?∑ min (,)F x M 的最优解k x 满足(,)0k x F x M ?=，即
1
1()()()2p k k k j j j k h x h x f x M =?=-
?∑ 由于一般()k f x ?不趋于零，因此若要求k x 趋于(P2)的最优解，则要求()k
j h x 趋于零，也
就要求k M 趋于无穷。因此，k M 必须充分大才可能使k x 接近(P2)的最优解。为此，我们用一个梯度趋于零的函数——Lagrange 函数(,)L x v 代替()f x ，其中
1(,)()()p
j j j L x v f x v h x ==+∑。令
2
11(,,)()()()2p p j j j j j j M x v M f x v h x h x φ===++∑∑
(,,)x v M φ称为增广Lagrange 函数，v 称为Lagrange 乘子，1(,,)0)T p M M M => 称为罚因子。对给的的,k k v M 求解无约束优化问题
min (,,)x v M φ (2)k P
得最有解k x 。下面考虑如何修正成子和罚因子
由于k x 是(2)k P 的最优解，所以有
10(,,)()(())()m k k k k k k k k x j j j j j x v M f x v M h x h x φ==?=?+
+?∑ 由K-T 条件，我们取
1(),1
,,k k k k j j j j v v M h x j m +=+= {}11211,()()41,,1max ,,()()4k k k j j j K j k k k j j j M h x h x M j m cM k h x h x -+-?
3.4 精确罚函数法
考虑问题
min ()f x
（P3） ..()0,1,2,i s t g x i m
≤= n x X R ∈?
精确罚函数是用形如min[()()]f x E x ν+的无约束问题()P μ来替代问题（P ），其中μ为参数，()E x 为X R →上的函数且满足：
1 . ()0E x x X ≥??，
2. ()0E x =的充要条件是x S ∈
这里{},()0,1,2,,,i S x g x i m x X =≤=∈
若存在0o μ>，则当o μμ>时，使得问题()P μ的解是问题（P ）的解，或问题（P ）的解是()P μ的解，则称()()f x E x μμμ+为问题(P)的精确罚函数。这里解可以是局部最优解，也可以是全局最优解。
精确罚函数概念首先由Eremin[42]和Zangwill[107]于上世纪六十年代后期提出。这是线性规划中大M法在非线性规划中的自然推广。从那时起，精确罚函数一直在数学规划理论与方法中扮演很重要的角色。
最优化方法大作业 ---------用优化算法求解函数最值问题
摘要 最优化(optimization) 是应用数学的重要研究领域.它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。最优化问题一般包括最小化问题和最大化问题，而最大化问题可以通过简单的转化使之成最最小化问题。最小化问题分为两类，即约束最小化和无约束最小化问题。在此报告中，前两个问题属于无约束最小化问题的求解，报告中分别使用了“牛顿法”和“共轭梯度法”。后两个问题属于有约束最小化问题的求解，报告中分别用“外点法”和“内点法”求解。虽然命名不一样，其实质都是构造“惩罚函数”或者“障碍函数”，通过拉格朗日乘子法将有约束问题转化为无约束问题进行求解。再此报告中，“外点法”和“内点法”分别用了直接求导和调用“牛顿法”来求解无约束优化问题。 在此实验中，用“共轭梯度法”对“牛顿法”所解函数进行求解时出现错误，报告中另取一函数用“共轭梯度法”求解得到正确的结果。此实验中所有的函数其理论值都是显见的，分析计算结果可知程序正确，所求结果误差处于可接受范围内。 报告中对所用到的四种方法在其使用以前都有理论说明，对“外点法”中惩罚函数和“内点法”中障碍函数的选择也有相应的说明，另外，对此次试验中的收获也在报告的三部分给出。 本报告中所用程序代码一律用MATLAB编写。 【关键字】函数最优化牛顿法共轭梯度法内点法外点法 MATLAB
一，问题描述 1， 分别用共轭梯度发法和牛顿法来求解一下优化问题 ()()()()()4 41432243221102510min x x x x x x x x x f -+-+-++= 2， 分别用外点法和内点发求解一下优化问题 ?? ?≥-++0 1.min 212 231x x t s x x 二、问题求解 1.1 用牛顿法求解 ()()()()()4 414 322 432 21102510min x x x x x x x x x f -+-+-++= 1.1.1问题分析： 取步长为1而沿着牛顿方向迭代的方法称为牛顿法，在牛顿法中，初始点的取值随意，在以后的每次迭代中，()[] ()k k k k x f x f x x ??-=-+1 21，直到终止条件成立时停止。 1.1.2 问题求解 注：本程序编程语言为MATLAB ，终止条件为()162 110-≤?x f ，初始取值 为[10 10 10 10] M 文件（求解函数）如下： function s=newton1(f,c,eps) %c 是初值，eps 为允许误差值 if nargin==2 eps=1.0e-16; elseif nargin<1 error('') % return end syms x1 x2 x3 x4
北航最优化方法大作业参考
1 流量工程问题 1.1 问题重述 定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1，其余元素为0。再令b m=(b m1,…,b mN)T，f m=(f m1,…,f mE)T，则可将等式约束表示成： Af m=b m 本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5…,5)1 )T， ×13 根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1× )。 13 图 1 网络拓扑和流量需求
1.2 7节点算例求解 1.2.1 算例1（b1=[4;-4;0;0;0;0;0]T） 转化为线性规划问题： Minimize c T x1 Subject to Ax1=b1 x1>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x1=20 1.2.2 算例2（b2=[4;0;-4;0;0;0;0]T） Minimize c T x2 Subject to Ax2=b2 X2>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x2=20 1.2.3 算例3（b3=[0;-4;4;0;0;0;0]T） Minimize c T x3 Subject to Ax3=b3 X3>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T 对应的最优值c T x3=40
1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。 解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x 列成表格：
1 2 1 610011460105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 1 2 1 2102310401162010021212 11-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 2 12 32 30 210231040116201002121211- ------ 再从底行中选元素-3，和第二列正元素2，迭代一次得 4 2 3 3 410120280114042001112--- 再迭代一次得 10 2 30 2 10 6 221023 1010213000421021013-- 选取最优解：
基于粒子群算法的神经网络在电液伺服系统中的应用 摘要：由于人工神经网络在解决具有非线性、不确定性等系统的控制问题上具有极大的潜力，因而在控制领域正引起人们的极大关注，并且已在一些响应较慢的过程控制中获得成功应用。由于电液伺服系统属 于非线性系统，因此本文利用神经网络控制电液伺服系统，并利用粒子群优化算法训练该神经网络的 权值。通过对神经网络的优化实现对电液伺服系统的控制。 关键词：神经网络电液伺服系统粒子群算法优化 近年来，由于神经网络具有大规模并行性、冗余性、容错性、本质的非线性及自组织自学习自适应能力，所以已成功地应用于众多领域。但在具有复杂非线性特性的机电设备的实时控制方面，虽然也有一些神经网络技术的应用研究，但距实用仍有一段距离。电液伺服系统就属于这类设备[1]。 神经网路在用于实时控制时，主要是利用了网络所具有的其输人——输出间的非线性映射能力。它实际上是通过学习来逼近控制对象的动、静态特性。也就是构造实际系统的神经网络模型[2]。本文利用神经网络控制一电液伺服系统，并利用粒子群优化算法训练该神经网络的权值，将结果与BP神经网络控制该系统的结果进行比较。从而得在电液伺服系统中引入神经网络是可行的。 1、粒子群算法 粒子群优化算法(Particle Swarm optimization, PSO)是一种进化计算技术, 由Eberhart博士和kennedy博士发明, 源于对鸟群捕食的行为研究, 粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解[3]。算法最初受到飞鸟和鱼类集群活动的规律性启发，利用群体智能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间个体协作来实现对问题最优解的搜索[4]。 在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置 v[]=v[]+c1*rand()*(pbest[]-present[]) + c2*rand()*(gbest[]-present[]) present[]=persent[]+v[] 式中ω为惯性权重，ω取大值可使算法具有较强的全局搜索能力，ω取小值则算法倾向于局部搜索。一般的做法是将ω初始取0.9并使其随迭代次数的增加而线性递减至0.4，这样就可以先侧重于全局搜索，使搜索空间快速收敛于某一区域，然后采用局部精细搜索以获得高精度的解；c1、c2为两个学习因子，一般取为2；randl和rand2为两个均匀分布在(0，l)之间的随机数；i=1，2，?，m；k=1，2，?，d。另外，粒子在每一维的速度Vi都被一个最大速度Vmax所限制。如果当前粒子的加速度导致它在某一维的速度 超过该维上的最大速度Vmax，则该维的速度被限制为最大速度[5]。 粒子群算法流程如下： (一)初始化粒子群。设群体规模为m，在允许的范围内随机设置粒子的初始位置和速 度。 (二)评价每个粒子的适应值。 (三)调整每一个粒子的位置和速度。 (四)如果达到最大迭代次数genmax或误差达到最初设定数值终止迭代，否则返回(2)。 2、神经网络 神经网络一般由输入层、隐含层、输出层组成。对于输入信号，先向前传播到隐节点，经过节点作用函数后，再把隐节点的输出信息传播到输出节点，最后输出结果。节点的作用函数通常选取S 型函数f（x）=1/（1+e-x）。神经网络算法的学习过程分为正
武工院你们懂的 1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。 解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x
列成表格： 00001216 100114 60105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 0000 1 2 121023 10 40116201002 1 21 211-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 002 1232 30210231 040116201002121211-- ----- 再从底行中选元素-3，和第二列正元素2，迭代一次得 4002 3 03410120280114042001112--- 再迭代一次得
10 23021 062 21023 1010 213 000421 2 10 13- - 选取最优解： 01=x 42=x 23=x 3. 试用DFP 变尺度法求解下列无约束优化问题。 min f （X ）=4（x 1-5）2+（x 2-6）2 取初始点X=（8，9）T ，梯度精度ε=0.01。 解：取I H =0,初始点()T X 9,8= 2221)6()5(4)(-+-=x x x f ??????--=?122408)(21x x x f ???? ??=?624)() 0(x f T x f d )6,24()()0()0(--=-?= )0(0)0()1(d x x α+= T )69,248(00αα--= ])669()5248(4min[)(min 2020)0(0)0(--+--?=+αααd x f )6()63(2)24()2458(8) (00)0(0)0(=-?-+-?--=+ααααd d x df 13077.013017 0≈= α ???? ??=???? ??--?+???? ??=21538.886153.462413077.098)1(x
发动机空燃比控制器 引言：我主要从事自动化相关研究。这里介绍我曾经接触过的发动机空燃比控制器设计中的优化问题。 发动机空燃比控制器设计中的最优化问题 AFR =a f m m && (1) 空燃比由方程（1）定义，在发动机运行过程中如果控制AFR 稳定在14.7可以获 得最好的动力性能和排放性能。如果假设进入气缸的空气流量a m &可以由相关单元检测得到，则可以通过控制进入气缸的燃油流量f m &来实现空燃比的精确控制。由于实际发动机的燃油喷嘴并不是直接对气缸喷燃油，而是通过进气歧管喷燃油，这么做会在进 气歧管壁上液化形成油膜，因此不仅是喷嘴喷出的未液化部分燃油会进入气缸，油膜 蒸发部分燃油也会进入气缸，如方程（2）。这样如何更好的喷射燃油成为了一个问题。 1110101122211ττττ?? ?? -?? ??????????=+????????-????????????-???? ? ??? ?? ????????? ?f f f v X x x u x x X x y =x && (2) 其中12、,==ff fv x m x m &&=f y m &,=fi u m &这里面，表示油膜蒸发量ff m &、fv m &表示为液化部分燃油、fi m &表示喷嘴喷射的燃油，在τf 、τv 、X 都已知的情况下，由现代控制理论知识，根据系统的增广状态空间模型方程（3） 0000001 1 011011114.70ττττ????-?? ??????????=-+-??????????????? ??????????????? ?? ??=?????? f f v v a X X u +q q m y q x x x &&& (3) 其中()0 14.7?t a q = y -m &。由极点配置方法，只要设计控制器方程（4），就可以 使得y 无差的跟踪阶跃输入，那么y 也能较好的跟踪AFR *a m /&。 12-- u =K q K x (4) 这里面的12、K K 确定，可由主导极点概念降维成两个参数12C ,C ，虽然都是最终稳态无差，但是目标是使得瞬态过程中y 和阶跃输入y r 的差异尽可能的小。所以原问
最优化方法程序作业 专业：油气储运工程 班级： 姓名： 学号：
一、开发工具 该应用程序采用的开发工具是Visual studio 2005，编程语言使用的是C#。 二、程序代码 （1）0.618法和抛物线法求ψ(t)=sint，初始点t0=1 ①主程序： using System; using System.Data; using System.Configuration; using System.Web; using System.Web.Security; using System.Web.UI; using System.Web.UI.WebControls; using System.Web.UI.WebControls.WebParts; using System.Web.UI.HtmlControls; using System.Collections; public partial class_Default : System.Web.UI.Page { JiSuan JS = new JiSuan(); protected void Button1_Click(object sender, EventArgs e) { double xx0 = 0.01;//步长 double tt0 = 1, pp = 2, qq = 0.5; ArrayList list1 = new ArrayList(); list1 = (ArrayList)JS.SuoJian(xx0, tt0, pp, qq);//调用倍增半减函数double aa = double.Parse(list1[0].ToString()); double bb = double.Parse(list1[1].ToString()); txtShangxian.Text = bb.ToString();//在页面上显示极小区间 txtXiaxian.Text = aa.ToString(); ArrayList list2 = new ArrayList(); list2 = (ArrayList)JS.JiXiao1(aa, bb);//调用0.618法函数 double jixiao1 = double.Parse(list2[0].ToString()); double fjixiao1 = double.Parse(list2[1].ToString()); txtJixiao1.Text = jixiao1.ToString();//在页面上显示极小点 txtFjixiao1.Text = fjixiao1.ToString();//在页面上显示极小点处的函数值 ArrayList list3 = new ArrayList(); list3 = (ArrayList)JS.JiXiao2(aa, bb);//调用抛物线法函数 double jixiao2 = double.Parse(list3[0].ToString()); double fjixiao2 = double.Parse(list3[1].ToString()); txtJixiao2.Text = jixiao2.ToString();//在页面上显示极小点
1流量工程问题 1.1问题重述 定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1， 其余元素为0。再令b m =(b m1 ,…,b mN )T，f m =(f m1 ,…,f mE )T，则可将等式约束表示成： Af m=b m 本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5 (5) 1×13 )T， 根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x 12,x 13 ,…,x 75 ) 1×13 )。 图 1 网络拓扑和流量需求
1.27节点算例求解 1.2.1\ T） 1.2.2算例1（b1=[4;-4;0;0;0;0;0] 转化为线性规划问题： Minimize c T x1 Subject to Ax1=b1 x1>=0利用Matlab编写对偶单纯形法程序，可求得: 最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x1=20 1.2.3算例2（b2=[4;0;-4;0;0;0;0]T） Minimize c T x2 Subject to Ax2=b2 \ X2>=0利用Matlab编写对偶单纯形法程序，可求得: 最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x2=20 1.2.4算例3（b3=[0;-4;4;0;0;0;0]T） Minimize c T x3 Subject to Ax3=b3 X3>=0利用Matlab编写对偶单纯形法程序，可求得: 最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T
function [x,dk,k]=fjqx(x,s) flag=0; a=0; b=0; k=0; d=1; while(flag==0) [p,q]=getpq(x,d,s); if (p<0) b=d; d=(d+a)/2; end if(p>=0)&&(q>=0) dk=d; x=x+d*s; flag=1; end k=k+1;
if(p>=0)&&(q<0) a=d; d=min{2*d,(d+b)/2}; end end %定义求函数值的函数fun，当输入为x0=（x1，x2）时，输出为f function f=fun(x) f=(x(2)-x(1)^2)^2+(1-x(1))^2; function gf=gfun(x) gf=[-4*x(1)*(x(2)-x(1)^2)+2*(x(1)-1),2*(x(2)-x(1)^2)]; function [p,q]=getpq(x,d,s) p=fun(x)-fun(x+d*s)+0.20*d*gfun(x)*s'; q=gfun(x+d*s)*s'-0.60*gfun(x)*s'; 结果： x=[0,1]; s=[-1,1]; [x,dk,k]=fjqx(x,s) x =-0.0000 1.0000 dk =1.1102e-016 k =54
function f= fun( X ) %所求问题目标函数 f=X(1)^2-2*X(1)*X(2)+2*X(2)^2+X(3)^2+ X(4)^2- X(2)*X(3)+2*X(1)+3*X(2)-X(3); end function g= gfun( X ) %所求问题目标函数梯度 g=[2*X(1)-2*X(2)+2,-2*X(1)+4*X(2)-X(3)+3,2*X(3)-X(2)-1,2*X(4)]; end function [ x,val,k ] = frcg( fun,gfun,x0 ) %功能：用FR共轭梯度法求无约束问题最小值 %输入：x0是初始点，fun和gfun分别是目标函数和梯度 %输出：x、val分别是最优点和最优值，k是迭代次数 maxk=5000;%最大迭代次数 rho=0.5;sigma=0.4;
非线性规划的罚函数算法 摘要：最优化理论和方法是一门十分活跃的学科，罚函数法是将约束问题无约束化的一种主要方法。本文简要介绍了最优化问题的优化算法，主要介绍了非线性规划的罚函数算法的基本理论和相应的发展过程。 关键词：最优化理论；非线性规划；惩罚函数法 1 前言 最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一门独立的学科还是在上世纪40年代末．Dantzing在1947年提出求解一般线性规划问题的单纯形算法之后，随着工业革命、信息革命的不断深化，以及计算机技术的巨大发展，至今短短的几十年，它得到了迅猛的发展．现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学技术等方面得到了广泛的应用，成为一门十分活跃的学科． 约束非线性规划问题广泛见于工程、国防、经济等许多重要领域．求解约束非线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方法和拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法．罚函数方法通过求解一个或多个罚问题来得到约束规划问题的解，如果当罚参数充分大时，求单个罚问题的极小点是原约束规划问题的极小点，则称此罚问题中的罚函数为精确罚函数，否则称为序列罚函数．针对传统罚函数的定义而言，若罚函数是简单的、光滑的，则它一定是不精确的；若罚函数是简单的、精确的，则它一定是不光滑的；若罚函数是精确的、光滑的，则它一定是复杂的．因此我们的工作是对传统罚函数进行了改造，主要是引入了指数型罚函数和对数型罚函数，并在改造后的罚函数中增添了乘子参数，使之成为既是简单的、光滑的，又是精确的结
天津大学《最优化方法》复习题（含答案） 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg min max x f x f n n R x R x -=∈∈ √ 2 {}{} .:)(m in :)(m ax n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题)(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的 严格局部最优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍
属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法 A 为下降算法，则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ . 13 算法迭代时的终止准则（写出三种）：_____________________________________。 14 凸规划的全体极小点组成的集合是凸集。 √ 15 函数R R D f n →?:在点k x 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k α，则其搜索公式
最优化马昌凤第五章作业-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
最优化方法及其Matlab程序设计习题作业暨实验报告 学院：数学与信息科学学院 班级：12级信计一班 姓名：李明 学号：1201214049
第四章 共轭梯度法 一、上机问题与求解过程 1、用DFP 算法求解,3)(m in 22 21x x x f +=取初始点和初始矩阵为 .1112,1100??????=??????-=H x 。 解： 仿照书上编写DFP 程序，将程序HESS 矩阵变为0H 具体如下： function [x,val,k]=dfp(fun,gfun,x0) %功能：用DFP 算法求解吴宇舒问题：min f(x) %输入：x0是初始点，fun,gfun 分别是目标函数及其梯度 %输出：x,val 分别是近似最优点和最优值，k 是迭代次数 maxk=1e5;%给出最大迭代次数 rho=0.55;sigma=0.4;epsilon=1e-5; k=0; n=length(x0); Hk=[2 1;1 1]; while (k
2016年大连理工大学优化 方法上机大作业 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
2016年大连理工大学优化方法上机大作业学院： 专业： 班级： 学号： 姓名： 上机大作业1： 1.最速下降法：
function f = fun(x) f = (1-x(1))^2 + 100*(x(2)-x(1)^2)^2; end function g = grad(x) g = zeros(2,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)^2-x(2)); g(2) = 200*(x(2)-x(1)^2); end function x_star = steepest(x0,eps) gk = grad(x0); res = norm(gk); k = 0; while res > eps && k<=1000 dk = -gk;
ak =1; f0 = fun(x0); f1 = fun(x0+ak*dk); slope = dot(gk,dk); while f1 > f0 + 0.1*ak*slope ak = ak/4; xk = x0 + ak*dk; f1 = fun(xk); end k = k+1; x0 = xk; gk = grad(xk); res = norm(gk); fprintf('--The %d-th iter, the residual is %f\n',k,res); end x_star = xk; end >> clear >> x0=[0,0]'; >> eps=1e-4; >> x=steepest(x0,eps)
最优化大作业 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
最优化方法大作业 ---------用优化算法求解函数最值问题
摘要 最优化(optimization) 是应用数学的重要研究领域.它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。最优化问题一般包括最小化问题和最大化问题，而最大化问题可以通过简单的转化使之成最最小化问题。最小化问题分为两类，即约束最小化和无约束最小化问题。在此报告中，前两个问题属于无约束最小化问题的求解，报告中分别使用了“牛顿法”和“共轭梯度法”。后两个问题属于有约束最小化问题的求解，报告中分别用“外点法”和“内点法”求解。虽然命名不一样，其实质都是构造“惩罚函数”或者“障碍函数”，通过拉格朗日乘子法将有约束问题转化为无约束问题进行求解。再此报告中，“外点法”和“内点法”分别用了直接求导和调用“牛顿法”来求解无约束优化问题。 在此实验中，用“共轭梯度法”对“牛顿法”所解函数进行求解时出现错误，报告中另取一函数用“共轭梯度法”求解得到正确的结果。此实验中所有的函数其理论值都是显见的，分析计算结果可知程序正确，所求结果误差处于可接受范围内。 报告中对所用到的四种方法在其使用以前都有理论说明，对“外点法”中惩罚函数和“内点法”中障碍函数的选择也有相应的说明，另外，对此次试验中的收获也在报告的三部分给出。 本报告中所用程序代码一律用MATLAB编写。 【关键字】函数最优化牛顿法共轭梯度法内点法外点法 MATLAB
一，问题描述 1， 分别用共轭梯度发法和牛顿法来求解一下优化问题 ()()()()()4 41432243221102510min x x x x x x x x x f -+-+-++= 2， 分别用外点法和内点发求解一下优化问题 ?? ?≥-++0 1.min 212 231x x t s x x 二、问题求解 1.1 用牛顿法求解 ()()()()()4 414 322 432 21102510min x x x x x x x x x f -+-+-++= 1.1.1问题分析： 取步长为1而沿着牛顿方向迭代的方法称为牛顿法，在牛顿法中，初始点的取值随意，在以后的每次迭代中，()[] ()k k k k x f x f x x ??-=-+1 21，直到终止条件成立时停止。 1.1.2 问题求解 注：本程序编程语言为MATLAB ，终止条件为()162 110-≤?x f ，初始取值为[10 10 10 10] M 文件（求解函数）如下： function s=newton1(f,c,eps) %c 是初值，eps 为允许误差值 if nargin==2 eps=1.0e-16; elseif nargin<1 error('')
《最优化方法课程设计》——关于存贮论的 操作实践 存贮论(inventory theory)又称库存理论，是运筹学中发展较早的分支。现代化的生产和经营活动都离不开存贮，为了使生产和经营活动有条不紊地进行，一般的工商企业总需要一定数量的贮备物资来支持。在企业的生产经营或人们的日常生活中，通常需要把一定数量的物质，用品或食品暂时储存起来，以备将来使用和消费，这就是所谓的存贮现象。存贮的存在主要基于社会经济现象的不确定性。 一、存贮论的基本理论 存贮系统是由存贮、补充和需求三个基本要素所构成的资源动态系统，其基本形态如图所示。 以下就上述结构图的三个环节分别加以说明： 1．存贮（inventory） 企业的生产经营活动总是要消耗一定的资源，由于资源供给与需求在时间和空间上的矛盾，使企业贮存—定数量的资源成为必然，这些为满足后续生产经营需要而贮存下来的资源就称为存贮。 2．补充（replenishment） 补充即存贮的输入。由于后续生产经营活动的不断进行，原来建立起来的存贮逐步减少，为确保生产经营活动不间断，存贮必须得到及时的补充。补充的办法可以是企业外采购，也可以是企业内生产。若是企业外采购，从订货到货物进入“存贮”往往需要一定的时间，这一滞后时间称为采购时间。从另一个角度看，为了使存贮在某一时刻能得到补充，由于滞后时间的存在必须提前订货，那么这段提前的时间称为提前期。存贮论主要解决的问题就是“存贮系统多长时间补充一次和每次补充的数量是多少？”，对于这一问题的回答便构成了所谓的存贮策略。 3．需求（demand）
需求即存贮的输出，它反映生产经营活动对资源的需要，即从存贮中提取的资源量。需求可以是间断式的，也可以是连续式的。 存贮系统所发生的费用包括存贮费用、采购费用和缺货费用。存贮费用（holding cost ）是指贮存资源占用资本应付的利息，以及使用仓库、保管物、保管人力、货物损坏变质等支出的费用。采购费用（order cost ）是指每次采购所需要的手续费、电信费、差旅费等，它的大小与采购次数有关而与每次采购的数量无关。存贮系统所发生的费用除存贮费用和采购费用之外，有时还会涉及缺货费用，缺货费用（stock-out cost ）是指当存贮供不应求时所引起的损失，如机会损失、停工待料损失，以及不能履行合同而缴纳的罚款等。 确定性存贮模型 在讨论确定性模型前，首先对一些常用符号的含义作必要的说明。 C ：单位时间平均运营费用（或称单位时间平均总费用）， R ：单位时间物品需求量（或称需求速度）， P ：单位时间物品生产量（或称生产速度）， K ：物品单价（外部订购）或单位物品成本费用（内部生产）， Q ：订货量（外部订购）或生产量（内部生产）， C1：单位物品单位时间保管费用（简称单位保管费用）， C2：单位物品单位时间缺货损失（简称单位缺货损失）， C3：订购费用（外部订购）或生产准备费用（内部生产）， 以上定货量（生产量）Q 和订购费用（生产准备费用）C3，都是对应于一次 订购（一次生产）而言的。 模型1，不允许缺货，且一次到货。 建立模型前，需要作一些假设： ① 缺货损失无穷大（即不允许缺货）， ② 当存贮量降至零时，可以瞬间得到补充（即一次到货）， ③ 需求是连续和均匀的，需求速度R 是固定的常数， ④ 每次订货量（生产量）Q 不变，订购费用（生产准备费用）C3不变。 存贮状态的变化情况可用图7—4表示： 易知：平均保管费用=平均存贮量×单位保管费用111122QC RtC = =， 平均订购费用3C t =， 平均物品成本费用QK RK t t ?= ==订购量单价。 由此可以推得模型1的单位时间平均运营费用函数：
实用最优化方法 ——matlab编程作业
题一、 初值为[-1;1] 其中g0、g1分别为不同x值下得导数，f0、f1为函数值 MATLAB程序： x0=[-1;1]; s0=[1;1]; c1=0.1;c2=0.5;a=0;b=inf;d=1;n=0; x1=x0+d*s0; g0=[-400*(x0(2)-x0(1)^2)*x0(1)-2*(1-x0(1));200*(x0(2)-x0(1) ^2)]; g1=[-400*(x1(2)-x1(1)^2)*x1(1)-2*(1-x1(1));200*(x1(2)-x1(1) ^2)]; f1=100*(x1(2)-x1(1)^2)^2+(1-x1(1))^2; f0=100*(x0(2)-x0(1)^2)^2+(1-x0(1))^2; while((f0-f1<-c1*d*g0'*s0)||(g1'*s0 《最优化理论与方法》复习内容要求和题型 一、复习内容要求 1、最优化问题及其分类，最优解的相关概念，最优化问题的算法的一般迭代格式及其收敛性和停止准则。 2、建立一个实际最优化问题的数学模型的思想和方法，包括线性规划、非线性规划、动态规划及多目标规划模型。 3、掌握单纯形法的理论依据、基本思想和最优性检验定理，熟练用大M法和两阶段求解线性规划问题，特别是构造的新问题与原问题的解的关系。 4、了解内点法的基本思想，掌握线性规划和0-1规划问题的计算机求解方法。 5、知道解决特殊线性规划问题的解法（含分支定界法、隐枚举法、表上作业法和匈牙利法）的思想方法。 6、了解非线性规划问题及数学模型，了解非线性规划的相关概念及理论，知道非线性规划的最优性条件。 7、掌握一维搜索的黄金分割法（0.618法）与Fibonacci法，知道二分法，特别注意这些算法的适用条件。 8、掌握最速下降法、牛顿类算法、FR共轭梯度法的算法步骤，并熟练使用它们求解多维无约束非线性规划，特别注意这些算法的异同点及它们与一维优化的关系。 9、了解惩罚函数法的算法思想，熟练掌握用内、外点法求解多维约束非线性规划问题，特别注意它们的异同点及适用条件。 10、了解乘子法的算法思想，熟练掌握乘子法求解多维约束非线性规划问题，特别注意它与惩罚函数法的异同。 11、了解动态规划的基本概念、最优性原理与基本方程，特别注意动态规划问题与静态规划问题（线性和非线性规划）的异同及一些静态规划问题如何化为动态规划问题。 12、掌握动态规划的建模步骤，了解逆推解法和顺推解法的异同。 13、了解有效解、弱有效解等多目标规划问题的重要概念，注意与单目标规划问题解概念的区别。 14、掌握多目标规划的几种评价函数法：理想点法、线性加权法和极大极小法，了解分层排序法求解层次多目标规划的求解思路，会用这种方法解简单的层次多目标问题。 15、掌握多目标规划计算机求解方法。 二、题型 填空题、简答题、计算题、建模和求解题 三、成绩评定办法 闭卷笔试（50%）+平时出勤、作业、参与课堂练习或讨论（30%）+讨论报告或大作业（小论文）或自主学习（20%） 最优化大作业 所在院系：电子工程学院 学号：02115088 姓名: 张赛捷 第一题 问题描述 分别用最速下降法和共轭梯度法求优化问题2212112min ()242f x x x x x x =+-- 一、 最速下降法 1、 算法简介 在基本迭代公式k k k k p t x x +=+1中，每次迭代搜索方向k p 取为目标函数)(x f 的负梯度方向，即)(k k x f p -?=，而每次迭代的步长k t 取为最优步长，由此确定的算法为最速下降法 2、 迭代步骤 给定控制误差0ε> 步骤1：取初始点)0(x ，令k=0； 步骤2：计算)(k p =)()(k x f ?-； 步骤3：若ε≤)(k p ,取)(*k x x ≈，停止计算；否则，转下一步； 步骤4：求0>k α，使得)(min )()()(0 )()(k p x f p x f k k k k ααα+=+≥，转步骤2； 3、 实验结果 初始点为（1,1），运行结果为)9980.1,9941.3(*=x 。 4、 总结 最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小值点。但从全局来看，由于锯齿现象的影响，即使向着极小点移近不太大的距离，也要经历不小的“弯路”，因此收敛速度大为减慢。 二、 共轭梯度法 1、 算法简介 在共轭方向法中初始的共轭向量0P 恰好取为初始点0X 处的负梯度00(X )g f -=-?，而以下各共轭方向k P 由第k 迭代点k X 处的负梯度k g -与已经得到的共轭向量1k P -的线性组合来确定，那么就构成了一种具体的共轭方向法。因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。 2、 迭代步骤最优化理论与方法复习要求2015
最优化大作业
相关主题
文本预览