非线性优化问题
函数fmincon
使用格式：
[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
x0 为开始运算的初始值
x 为最优解时x的值
fval 为z 的最优值
exitflag 判断算法停止的原因
grad 梯度
m文件
function y=funn(x)
y=-x(1)-2*x(2)+0.5*(x(1).^2+x(2).^2)
主程序
A=[2 3;1 4];
b=[6;5];
vlb=[0;0];
x0=[0;0];
[x,fval,exitflag,output,lambda,grad,hession]=fmincon('funn',x0,A,b,[] ,[],vlb)
结果如下
Active inequalities (to within options.TolCon = 1e-006):
lower upper ineqlin ineqnonlin
2
x =
0.7647
1.0588
fval =
-2.0294
exitflag =
1
output =
iterations: 1
funcCount: 6
lssteplength: 1
stepsize: 1.3061
algorithm: 'medium-scale: SQP, Quasi-Newton, line-search' firstorderopt: 1.7969e-008
constrviolation: 0
message: [1x788 char]
lambda =
lower: [2x1 double]
upper: [2x1 double]
eqlin: [0x1 double]
eqnonlin: [0x1 double]
ineqlin: [2x1 double]
ineqnonlin: [0x1 double]
grad =
-0.2353
-0.9412
hession =
1 0
0 1
首先增加一个M文件
function y=nonline(x)
y=2*x(1)+3*x(2).^2-6
主程序
A=[2 3;1 4];
b=[6;5];
vlb=[0;0];
x0=[0;0];
[x,fval,exitflag,output,lambda,grad,hession]=fmincon('funn',x0,A,b,[] ,[],vlb,'nonline')
x =
0.7647
1.0588
fval =
-2.0294
exitflag =
1
output =
iterations: 1
funcCount: 6
lssteplength: 1
stepsize: 1.3061
algorithm: 'medium-scale: SQP, Quasi-Newton, line-search'
firstorderopt: 1.7969e-008
constrviolation: 0
message: [1x788 char]
lambda =
lower: [2x1 double]
upper: [2x1 double]
eqlin: [0x1 double]
eqnonlin: [0x1 double]
ineqlin: [2x1 double] ineqnonlin: [0x1 double]
grad =
-0.2353
-0.9412
hession =
1 0
0 1
线性和非线性最优化理论、方法、软件及应用 最优化在航空航天、生命科学、水利科学、地球科学、工程技术等自然科学领域和经济金融等社会科学领域有着广泛和重要的应用, 它的研究和发展一直得到广泛的关注. 最优化的研究包含理论、方法和应用.最优化理论主要研究问题解的最优性条件、灵敏度分析、解的存在性和一般复杂性等.而最优化方法研究包括构造新算法、证明解的收敛性、算法的比较和复杂性等.最优化的应用研究则包括算法的实现、算法的程序、软件包及商业化、在实际问题的应用. 这里简介一下线性和非线性最优化理论、方法及应用研究的发展状况. 1. 线性最优化 线性最优化, 又称线性规划, 是运筹学中应用最广泛的一个分支.这是因为自然科学和社会科学中许多问题都可以近似地化成线性规划问题. 线性规划理论和算法的研究及发展共经历了三个高潮, 每个高潮都引起了社会的极大关注. 线性规划研究的第一高潮是著名的单纯形法的研究. 这一方法是Dantzig在1947年提出的,它以成熟的算法理论和完善的算法及软件统治线性规划达三十多年. 随着60年代发展起来的计算复杂性理论的研究, 单纯形法在七十年代末受到了挑战. 1979年前苏联数学家Khachiyan提出了第一个理论上优于单纯形法的所谓多项式时间算法--椭球法, 曾成为轰动一时的新闻, 并掀起了研究线性规划的第二个高潮. 但遗憾的是广泛的数值试验表明, 椭球算法的计算比单纯形方法差. 1984年Karmarkar提出了求解线性规划的另一个多项式时间算法. 这个算法从理论和数值上都优于椭球法,因而引起学术界的极大关注, 并由此掀起了研究线性规划的第三个高潮. 从那以后, 许多学者致力于改进和完善这一算法,得到了许多改进算法.这些算法运用不同的思想方法均获得通过可行区域内部的迭代点列,因此统称为解线性规划问题的内点算法. 目前内点算法正以不可抗拒的趋势将超越和替代单纯形法. 线性规划的软件, 特别是由单纯形法所形成的软件比较成熟和完善.这些软件不仅可以解一般线性规划问题, 而且可以解整数线性规划问题、进行灵敏度分析, 同时可以解具有稀疏结构的大规模问题.CPLEX是Bi xby基于单纯形法研制的解线性和整数规划的软件, CPLEX的网址是https://www.doczj.com/doc/ad15167500.html,/. 此外,这个软件也可以用来解凸二次规划问题, 且特别适合解大规模问题. PROC LP是SAS软件公司研制的SAS商业软件中OR模块的一个程序. 这个程序是根据两阶段单纯形法研制的,可以用来解线性和整数规划问题并可进行灵敏度分析, 是一个比较完善的程序.用户可以根据需要选择不同的参数来满足不同的要求。关于内点法的软件也在研制之中.BPMP D是Cs.Mzos基于原始对偶内点法研制的解线性和整数规划的软件，其FTP地址是ftp://ftp.sztaki.hu/pub /oplab/SOFTWARE/BPMPD/ ，可以自由下载.此外,在互联网上能访问到的解线性和整数规划问题的软件还有:EQPS（线性，整数和非线性规划）,FMP（线性和混合整数规划），HS/LPLO（线性规划），KORBX（线性规划），LAMPS（线性和整数规划），LPBLP（线性规划），MILP（混合整数规划），MINTO（混合整数规划），MPSIII（线性和混合整数规划），OML（线性和混合整数规划），OSL（线性，二次和混合整数规划），PROCLP（线性和整数规划），WB（线性和混合整数规划），WHIZARD（线性和混合整数规划），XPRESSMP（线性和混合整数规划）等.
习题二包括题目：P36页5（1）（4） 5（4）
习题三 包括题目：P61页1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下
5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)1 1/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ?++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0) 1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-??=?-?= ?-?? 0110 111011101 T T T T H H H H H γγδδδγγγ=+-
Advances in Education教育进展, 2019, 9(4), 450-453 Published Online July 2019 in Hans. https://www.doczj.com/doc/ad15167500.html,/journal/ae https://https://www.doczj.com/doc/ad15167500.html,/10.12677/ae.2019.94076 A Good Textbook for Optimization —Review of Theory and Algorithms on Nonlinear Programming Naiyang Deng School of Science, China Agricultural University, Beijing Received: Jun. 30th, 2019; accepted: Jul. 12th, 2019; published: Jul. 22nd, 2019 Abstract This paper provides a review for the textbook written by Professors Yiju Wang and Naihua Xiu, named Theory and Method of Nonlinear Optimization published by Science Publishing House in 2012 by pointing out some highlights and features of the book, and giving some suggestions for improvement. Keywords Book Review, Highlights and Features, Suggestions 最优化课程的一本好教材 ——《非线性最优化理论与方法》书评 邓乃扬 中国农业大学理学院，北京 收稿日期：2019年6月30日；录用日期：2019年7月12日；发布日期：2019年7月22日 摘要 本文对王宜举教授和修乃华教授2012年在科学出版社出版的《非线性最优化理论与方法》进行了评述，指出了该书的一些亮点和特色，同时也给出了进一步提升的建议。 关键词 书评，亮点与特色，建议
最优化理论 一、最优化理论概述 优化是从处理各种事物的一切可能的方案中，寻求最优的方案。优化的原理与方法，在科学的、工程的和社会的实际问题中的应用，便是优化问题。优化一语来自英文Optimization，其本意是寻优的过程；优化过程：是寻找约束空间下给定函数取极大值（以max表示)或极小(以min表示)的过程。优化方法也称数学规划，是用科学方法和手段进行决策及确定最优解的数学。在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，获得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。 最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。 最优化理论与方法作为一个重要的数学分支，它所研究的就是在众多的方案中怎么能找到最优、最好的方案。由于科学技术与生产技术的迅速发展，尤其是计算机应用的不断扩大，使最优化问题的研究不仅成为了一种迫切的需要，而且有了求解的有力工具，因此，发展成了一种新的科学。最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：连续优化：包括线性规划、非线性规划、全局优化、锥优化等；离散优化：网络优化、组合优化等；和近年来发展迅速的智能优化等。 一般而言，最优化问题的求解方法大致可分为4类：1)解析法：对于目标函数及约束条件具有简单而明确的数学表达式的最优化问题，一般都可采用解析法。在解决实际问题时，由于描述实际问题的解析形式的数学表达式很难找到，因此，这种表达式则缺
非线性规划的罚函数算法 摘要：最优化理论和方法是一门十分活跃的学科，罚函数法是将约束问题无约束化的一种主要方法。本文简要介绍了最优化问题的优化算法，主要介绍了非线性规划的罚函数算法的基本理论和相应的发展过程。 关键词：最优化理论；非线性规划；惩罚函数法 1 前言 最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一门独立的学科还是在上世纪40年代末．Dantzing在1947年提出求解一般线性规划问题的单纯形算法之后，随着工业革命、信息革命的不断深化，以及计算机技术的巨大发展，至今短短的几十年，它得到了迅猛的发展．现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学技术等方面得到了广泛的应用，成为一门十分活跃的学科． 约束非线性规划问题广泛见于工程、国防、经济等许多重要领域．求解约束非线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方法和拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法．罚函数方法通过求解一个或多个罚问题来得到约束规划问题的解，如果当罚参数充分大时，求单个罚问题的极小点是原约束规划问题的极小点，则称此罚问题中的罚函数为精确罚函数，否则称为序列罚函数．针对传统罚函数的定义而言，若罚函数是简单的、光滑的，则它一定是不精确的；若罚函数是简单的、精确的，则它一定是不光滑的；若罚函数是精确的、光滑的，则它一定是复杂的．因此我们的工作是对传统罚函数进行了改造，主要是引入了指数型罚函数和对数型罚函数，并在改造后的罚函数中增添了乘子参数，使之成为既是简单的、光滑的，又是精确的结
统计学梯度下降法（SGDs）易于实现，然而它有两个主要的缺陷。第一个缺陷是它需要手动调谐大量的参数，比如学习速率和收敛准则。第二个缺陷是它本质上是序列方法，不利于并行计算或分布式计算。（然而，在计算资源如RAM受限的情况下，序列方法倒是一个不错的选择。） 这里介绍一些非线性优化算法：牛顿算法，伪牛顿算法和共轭梯度法。其中，伪牛顿算法包括DFP、BFGS和L-BFGS算法。 考虑如下的无约束最小化问题： min x f(x)（1） 其中x=(x1,…,x N)T∈?N. 为简便起见，这里假设f是凸函数，且二阶连续可导。记（1）的解为x?. 牛顿算法（Newton‘s Method） 基本思想：在现有的极小点估计值的附近对f(x)做二阶泰勒展开，进而找到下 其中g(k)=?f(x)| x(k)是梯度矩阵，H(k)=?2f(x)| x(k) 是海森矩阵。 牛顿算法是一种具有二次收敛性的算法。对于非二次函数，若函数的二次性态较强，或迭代点已进入极小点的领域，则其收敛速度也是很快的，这是牛顿算法的主要优点。但牛顿算法由于迭代公式中没有步长因子，而是定步长迭代，所以对于非二次函数，有时会出现f(x(k+1))>f(x(k))的情况，这表明牛顿算法不能保证函数值稳定地下降。由此，人们提出了阻尼牛顿算法，在原始牛顿算法的第4步中，采用一维搜索（line search）算法给d(k)加一个步长因子λ(k)，其中： λ(k)=arg minλ∈?f(x(k)+λd(k))（2）一维搜索算法将另作介绍。 拟牛顿算法（Quasi-Newton Methods） 基本思想：不直接计算二阶偏导数，而是构造出近似海森矩阵（或海森矩阵的逆）的正定对称阵，在拟牛顿条件下优化目标函数。 下文中，用B表示对H的近似，用D表示对H?1的近似，并令s(k)=x(k+1)?x(k)，y(k)=g(k+1)?g(k).
非线性约束最优化方法 ——乘子法 1.1 研究背景 最优化理论与方法是一门应用性相当广泛的学科，它的最优性主要表现在讨论决策问题的最佳选择性，讨论计算方法的理论性质，构造寻求最佳解的计算方法，以及实际计算能力。伴随着计算数学理论的发展、优化计算方法的进步以及计算机性能的迅速提高，规模越来越大的优化问题得到解决。因为最优化问题广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域，它已受到政府部门、科研机构和产业部门的高度重视。然而，随着人们对模型精度和最优性的要求所得到的优化命题往往具有方程数多、变量维数高、非线性性强等特点，使得相关变量的存储、计算及命题的求解都相当困难，从而导致大规模非线性优化很难实现。因此，寻求高效、可靠的大规模非线性优化算法成为近年来研究的热点。 本文讨论的问题属于非线性约束规划的范畴，讨论了其中的非线性等式约束最优化问题方面的一些问题。 1.2非线性约束规划问题的研究方法 非线性约束规划问题的一般形式为 （NPL ） {}{} m in (),, s.t. ()0,1,2,...,, ()0,1,2,...,n i i f x x R c x i E l c x i I l l l m ∈=∈=≤∈=+++ 其中，(),()i f x c x 是连续可微的. 在求解线性约束优化问题时，可以利用约束问题本身的性质，
但是对于非线性约束规划问题，由于约束的非线性使得求解这类问题比较复杂、困难。因此，我们将约束问题转化为一系列无约束优化问题，通过求解一系列无约束优化问题，来得到约束优化问题的最优解。我们用到的几类主要的方法有:罚函数法、乘子法以及变尺度法。 传统上我们所提出的非线性约束最优化方法一般都遵循下列三个基本思路之一 1 借助反复的线性逼近把线性方法扩展到非线性优化问题中来 2 采用罚函数把约束非线性问题变换到一系列无约束问题 3 采用可变容差法以便同时容纳可行的和不可行的X 矢量 其中源于思路2 的乘子罚函数法具有适合于等式及不等式约束不要求初始点为严格内点，甚至不要求其为可行点对自由度的大小无任何要求等特点。 1.3乘子法 罚函数法的主要缺点在于需要惩罚因子趋于无穷大，才能得到约束问题的极小点，这会使罚函数的Hesse矩阵变得病态，给无约束问题的数值求解带来很大问题，为克服这一缺点，Hestenes和Powell 于1964年各自独立地提出乘子法。所谓乘子法是：由问题的Lagrange 函数出发，考虑它的精确惩罚，从而将约束优化问题化为单个函数的无约束优化问题，它同精确罚函数法一样，具有较好的收敛速度和数值稳定性，且避免了寻求精确罚函数法中关于罚参数阈值的困难，它们一直是求解约束优化问题的主要而有效的算法。 考虑如下非线性等式约束优化问题：
五种最优化方法 1. 最优化方法概述 1.1最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3）线性优化与非线性优化（目标函数和约束条件是否线性）； 4）静态规划和动态规划（解是否随时间变化）。 1.2最优化问题的一般形式（有约束条件）： 式中f(X)称为目标函数(或求它的极小，或求它的极大)，si(X)称为不等式约束，hj(X)称为等式约束。化过程就是优选X，使目标函数达到最优值。 2.牛顿法 2.1简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）是一种函数逼近法。 2.2 原理和步骤
3. 最速下降法（梯度法） 3.1最速下降法简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）沿函数在该点处目标函数下降最快的方向作为搜索方向； 3.2 最速下降法算法原理和步骤
4. 模式搜索法(步长加速法) 4.1 简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的是探测有利的下降方向，而模式移动的目的则是沿着有利方向加速移动。 4.2模式搜索法步骤
5.评价函数法 5.1 简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下：min (f_1(x),f_2(x),...,f_k(x)) s.t. g(x)<=0 传统的多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有
毕业论文 题目非线性最优化计算方法与算法学院数学科学学院 专业信息与计算科学 班级计算1201 学生陶红 学号20120921104 指导教师邢顺来 二〇一六年五月二十五日
摘要 非线性规划问题是一般形式的非线性最优化问题。本文针对非线性规划的最优化问题进行方法和算法分析。传统的求解非线性规划的方法有最速下降法、牛顿法、可行方向法、函数逼近法、信赖域法，近来研究发现了更多的求解非线性规划问题的方法如遗传算法、粒子群算法。本文对非线性规划分别从约束规划和无约束规划两个方面进行理论分析。 利用最速下降法和牛顿法两种典型算法求解无约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。另外给出了阻尼牛顿法，探讨其算法的收敛性和稳定性，求解无约束非线性规划比牛顿法的精确度更高，收敛速度更快。惩罚函数是经典的求解约束非线性的方法，本文采用以惩罚函数法为核心的遗传算法求解有约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。并改进遗传算法，给出适应度函数，通过变换适应度函数，提高算法的收敛性和稳定性。 关键词：非线性规划；最速下降法；牛顿法；遗传算法
ABSTRACT Nonlinear programming problem is the general form of the nonlinear optimization problem. In this paper, we carry on the analysis of the method and algorithm aiming at the optimization problem of nonlinear programming. The traditional methods of solving nonlinear programming problems include steepest descent method, Newton method, the feasible direction method, function approximation method and trust region method. Recent studies found more method of solving nonlinear programming problems, such as genetic algorithm, particle swarm optimization (pso) algorithm. In this paper, the nonlinear programming is analyzed from two aspects: the constraint programming and the unconstrained programming. We solve unconstrained condition nonlinear programming problem by steepest descent method and Newton's method, and get the optimal value through MATLAB. Then the convergence and stability are discussed. Besides, the damped Newton method is furnished. By discussing the convergence and stability of the algorithm, the damped Newton method has higher accuracy and faster convergent speed than Newton's method in solving unconstrained nonlinear programming problems.Punishment function is a classical method for solving constrained nonlinear. This paper solves nonlinear programming problem with constraints by using genetic algorithm method, the core of which is SUMT. Get the optimal value through MATLAB, then the convergence and stability are discussed. Improve genetic algorithm, give the fitness function, and improve the convergence and stability of the algorithm through transforming the fitness function. Key words：Nonlinear Programming; Pteepest Descent Method; Newton Method; GeneticAlgorithm
五种最优化方法 1.最优化方法概述 1.1最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3）线性优化与非线性优化（目标函数和约束条件是否线性）； 4）静态规划和动态规划（解是否随时间变化）。 1.2最优化问题的一般形式（有约束条件）： 式中f(X)称为目标函数(或求它的极小，或求它的极大)，si(X)称为不等式约束，hj(X)称为等式约束。化过程就是优选X，使目标函数达到最优值。 2.牛顿法 2.1简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）是一种函数逼近法。 2.2原理和步骤 3.最速下降法（梯度法） 3.1最速下降法简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）沿函数在该点处目标函数下降最快的方向作为搜索方向； 3.2最速下降法算法原理和步骤 4.模式搜索法(步长加速法) 4.1简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的是探测有利的下降方向，而模式移动的目的则是沿着有利方向加速移动。 4.2模式搜索法步骤
5.评价函数法 5.1简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下： min(f_1(x),f_2(x),...,f_k(x)) s.t.g(x)<=0 传统的多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有“线性加权和法”、“极大极小法”、“理想点法”。选取其中一种线性加权求合法介绍。 5.2线性加权求合法 6.遗传算法 智能优化方法是通过计算机学习和存贮大量的输入-输出模式映射关系，进而达到优化的一种方法，主要有人工神经网络法，遗传算法和模拟退火法等。 6.1遗传算法基本概念 1.个体与种群 个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼。 种群就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。 2.适应度与适应度函数 适应度就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。 适应度函数就是问题中的全体个体与其适应度之间的一个对应关系。该函数就是遗传算法中指导搜索的评价函数。 6.2遗传算法基本流程 的就是对一定数量个体组成的生物种群进行选择、交叉、变异等遗传操作,最终求得最优解或近似最优解。 遗传算法步骤 步1在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T； 步2随机产生U中的N个个体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1； 步3计算S中每个个体的适应度f()； 步4若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。
第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==??≥=? （8.1） 特别地，当()f x 为二次函数，而约束是线性约束时，称为二次规划。 记 {}1()0 (1, , );() 0 ,,i e i e X x c x i m c x i m m +===≥= ，称之为可行域（约束域） 。 {}1,,e E m = ，{}1,,e I m m += ，{}()()0 i I x i c x i I ==∈ 称()E I x 是在x X ∈处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints ）。 应该指出的是，如果x *是（1）的局部最优解，且有某个0i I ∈，使得 0()0i c x * > 则将此约束去掉，x *仍是余下问题的局部最优解。 事实上，若x *不是去掉此约束后所得问题的局部极小点，则意味着0δ?>，存在x δ，使得 x x δδ* -<，且()()f x f x δ* <，这里x δ满足新问题的全部约束。注意到当δ充分小时，由0() i c x 的连续性，必有0 ()0i c x δ≥，由此知x δ是原问题的可行解，但()()f x f x δ*<，这与x * 是局部极小 点矛盾。 因此如果有某种方式，可以知道在最优解x *处的积极约束指标集()()A x E I x * *= ，则问题可转化为等式的约束问题： min ()f x .. ()0i s t c x = ()i A x * ∈ （8.2） 一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()A x * 。
《无约束最优化与非线性方程的数值方法》 J.E. Dennis, Jr. & Robert B. Schnabel 介绍 这本书讨论了三大非线性问题计算的方法、运算法则和思路分析：非线性方程组的解法、非线性函数的无约束极小化方法和非线性最小二乘参数选择。1.1节介绍了这些问题和我们对此提出的假设。1.2节
列举了一些非线性难题并且论述了在实际运算中遇到的这类问题的典型特征；对这类问题很熟悉的读者可能会想跳过这个章节。1.3节总结了计算机有限精度算术的特点。为了理解文本中以计算机为依托的算法，这些特点是读者必须要了解的。 1.1 考虑的问题 这本书讨论了实践中经常遇到的三大非线性问题的实际变量。这些是合理假设下建立的数学等价，但我们不打算用相同的算法来处理，而打算展示当前最佳的算法是如何找出每个问题的结构。 联立非线性方程问题（现在简称“非线性方程”）是三大非线性方程问题中最基础的，并且计算中可利用的结构最少。 公式如下：已知 在公式中表示n维欧氏空间。当然，(1.1.1)只是表示含未知数“n”的n非线性方程的标准公式，方程式的右边通常是零。例如： 如果已知且
(1.1.1)公式中计算出来的必然会是的最小值。 表示F的第i个组成函数。这是无约束极小化问题的特殊例子。 （1.1.2）是我们要考虑的第二个问题。通常（1.1.2）是 的缩写。例如： 可以得出 在一些应用中，有人对解决（1.1.3）受限版本有兴趣，其中 是一个封闭连通域。如果（1.1.4）的解法来自的内部，那么（1.1.4） 仍可以看作是一个无约束极小化问题。然而，如果是的边界点， 的极小化超过成为一个约束极小化问题。我们不考虑约束问题，因为目前已知的该如何去解决这个问题的知识还较少，而且其间有很多无约束问题需要我们考虑。此外，解决无约束问题的技巧是解决约束算法的基础。事实上，许多解决约束问题的尝试不是发现相关的无约束最小化问题的答案很接近约束问题的答案，就是发现
最优化理论与方法（线性部分）思考题 1.就你学过的运筹学问题，写出能够建立线性规划模型的问题，并 举例（建立模型）。 工厂生产利润最大化问题 2.举例（说明问题、建立模型）论述线性规划在交通、运输、物流 和安全管理中的应用。 3.对一个用单纯形法求解不会产生循环（且能求得最优解）的n个 变量m个约束的线性规划问题，估算一下基本计算次数。 4.简述线性规划求解算法的改进历史。 5.证明课本（清华版运筹学（第三版））2.5题。 6.有人说：“原问题有多重解（多个最优解），对偶问题一定也有多 重解”，此话是否正确？请举一算例。 7.D-W分解算法适合哪种类型的线性规划问题？请举一算例。 8.何谓“原始-对偶”单纯形法？请举一算例。 9.何谓有界变量的线性规划问题？如何求解？请举一算例。 10.何谓线性规划的逆问题，分别对“最优解的逆线性规划问题”和 “对目标函数值的线性规划逆最优值问题”举出算例。 11.对同一优化问题，是否存在决策变量一样但所建模型不一样的情 况？请举例；是否存在目标函数中没有决策变量的最优化问题？ 12.简述建立线性多目标规划的过程，自选一个实际问题，建立模型 并用图解法和单纯形法求解。
要求每个人所举例题都不一样，否则视为抄袭！ 最优化理论与方法（线性部分）思考题 1.解：以工厂生产利润最大化问题： 某工厂生产Ⅰ、Ⅱ两种产品，已知有关数据见下表。试求获利最大的生产方案。 设、分别代表Ⅰ、Ⅱ两种产品生产量，其线性规划模型表述为： max 10 2.解：以管理(指派)问题： 有一份中文说明书，需翻译为日、英、德、法四种文字，分别记作A、B、C、D、现有甲乙丙丁四人，他们将中文说明书翻译成不同语种的说明书所需要的时间如下表所示。问应指派何人去完成何种工作，使所需总时间最少？ ()表示指派第i人去完成j项任务的时间，引入，其取值只能使0和1。并另取1时表示指派第i个人去完成第j项工作；取0时