(06)第四章-无约束优化方法(坐标轮换法)

《机械优化设计》

第四章无约束优化方法§4-7 坐标轮换法

§4-3坐标轮换法

间接法：梯度法；牛顿法；变尺度法

共同点：求导数

直接法：直接用函数值

搜索方向如何定？

次搜索记为一轮，轮换迭代，求解极值点。

图4-12 坐标轮换法的基本原理示意图

图4-13坐标轮换法程序框图

的最优解。迭代精度，

0.1ε=z

例题：用坐标轮换法求目标函数

221

2

1212()41060

f x x x x x x =+???+x 初始点(1)

[00]T

=x 的最优解。迭代精度，

0.1ε=z

课后练习题：用坐标轮换法求目标函数221

2

12

()1610f x x x x =++x 初始点(1)

[43]T

=x （迭代两轮）

（迭代两轮）

第四章 非线性规划1-约束极值问题

第四章 非线性规划 ???? ???? 无约束最优化问题线性规划约束最优化问题非线性规划 ?? ?凸规划约束最优化问题非凸规划 ?? ?直接解法约束最优化问题求解方法间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。 直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。 第一节 目标函数的约束极值问题 所谓约束优化设计问题的最优性条件．就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。 对于带有约束条件的目标函数，其求最优解的过程可归结为： 一、约束与方向的定义 一）起作用约束与松弛约束 对于一个不等式约束()0g X ≤来说，如果所讨论的设计点() k X 使该约束()0g X =(或 者说() k X 当时正处在该约束的边界上)时，则称这个约束是() k X 点的一个起作用约束或紧约 束，而其他满足()0g X <的约束称为松弛约束。

冗余约束 40g ≤ 当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为 {}()()()|()0,1,2, ,k k u I X u g X u m === 其意义是对() k X 点此时所有起作用约束下标的集合。 二）冗余约束 如果一个不等式约束条件的约束面(即()0g X =)对可行域的大小不发生影 响，或是约束面不与可行域D 相交，即此约束称为冗余约束。 三）可行方向 可行方向：一个设计点()k X 在可行域内，沿某一个方向S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。 1）设计点为自由点 设计点() k X 在可行域内是一个自由点，在各个方 向上都可以作出移动得到新点仍属于可行域，如图所示。 2）设计点为约束边界点 当设计点()k X 处于起作用约束i g 上时，它的移动就会受到可行性的限制。此时，()k X 点的可行方向S 必满足条件： ()0T k i S g X ?≤ （解释：()()cos ,()T k k T k i i i S g X S g X S g X ?=??，,()90T k i S g X ?≥?）） 当,()90T k i S g X ?=?时，方向S 是约束函数i g 在()k X 点处的切线方向，即()0T k i S g X ?=。 当某个设计点x 同时有几个约束起作用时(如

约束优化设计

行域 φ 内，选择一个初始点 X 然后确定一个可行 得一个目标函数有所改善的可行的新点 X 即完成了 第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： s .t . min f (x ) g u (x ) ≤ 0 h v (x ) = 0 x ∈ R n u = 1, 2,..., m v = 1, 2,..., p < n 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于 这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由 m 个不等式约束条件 gu(x )≤0 所确定的可 0 搜索方向 S ，且以适当的步长沿 S 方向进行搜索，取 1 一次迭代。以新点为起始点重复上述搜索过程，每次 均按如下的基本迭代格式进行计算： X k+1=X k +α k S k (k=0,1,2,..) 逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算 不论何时终止，都可以获得比初始点好的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局 部最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集

φ(X,μ1,μ2)=F(X)+∑μ 1 G??g j X)??+∑μ2H??h k(X)?? a)可行域是凸集；b)可行域是非凸 集 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数 结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优 化问题。 m l j=1k=1 新目标函数 然后对新目标函数进行无约束极小化计算。 加权因子 间接法是结构优化设计中广泛使用的有效方法，其特点： 1）由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和数值计算的稳定性大有提高； 2）可以有效处理具有等式约束的约束优化问题； 3）目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精度，甚至导致计算失败。

约束最优化问题

约束最优化问题 一实习目的 1.熟练掌握科学与工程计算中常用的基本算法； 2.掌握分析问题，设计算法的能力； 3.掌握模块化程序设计的基本思想，注重模块的“高内聚，低耦合”； 4.采用自顶向下，逐步细化的编程思想完成程序书写； 5.牢固建立“清晰第一，效率第二”的软件设计观念； 6.掌握软件调试，测试的基本技能和方法； 7.提高科技报告的书写质量； 8.在掌握无约束最优化问题求解方法的前提下，对一般情形下的约束最优化问题进行研究，通过实习掌握外点罚函数法、内点罚函数法、乘子法、线性近似规划法和序列二次规划法在求解一般情形下的约束最优化问题的应用。 二问题定义及题目分析 问题1： 要求用外点罚函数法和内点罚函数法解决约束问题： Min f(x)=错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 问题2： 要求用乘子法解决约束问题： Min 错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 (错误！未找到引用源。) 问题3： 要求用线性近似规划法和序列二次规划法解决约束问题: Min 错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 三程序概要设计 1.外点罚函数法 Step1. 给定初始点错误！未找到引用源。,罚参数序列{错误！未找到引用源。}(常取错误！未找到引用源。),精度错误！未找到引用源。，并令k=0；

Step2. 构造增广目标函数错误！未找到引用源。; Step3. 求解无约束优化问题min 错误！未找到引用源。,x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则：惩罚项充分小，或等价地错误！未找到引用源。近似可行）若错误！未找到引用源。，或者错误！未找到引用源。,错误！ 未找到引用源。,则得解错误！未找到引用源。，否则令k=k+1，转 Step2. 2.内点罚函数法： Step1. 给定初始可行解错误！未找到引用源。，罚参数序列{错误！未找到引用源。}(常取错误！未找到引用源。),精度错误！未找到引用源。，并令 k=0； Step2. 构造增广目标函数错误！未找到引用源。; Step3. 求解无约束优化问题min 错误！未找到引用源。,x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则）若错误！未找到引用源。，则得解错误！未找到引用源。，否则令k=k+1，转 Step2. 3.乘子法： Step1. 给定初始点错误！未找到引用源。，初始lagrange乘子错误！未找到引用源。,i错误！未找到引用源。罚参数序列{错误！未找到引用源。}, 精度错误！未找到引用源。，并令k=0； Step2. 构造增广目标函数错误！未找到引用源。 Step3. 求解无约束优化问题min 错误！未找到引用源。，x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则）若错误！未找到引用源。,则得解错误！未找到引用源。，否则令 K=k+1,转Step2. 4.线性近似规划法： Step1. 给定初始点错误！未找到引用源。，步长限制错误！未找到引用源。,缩小系数错误！未找到引用源。。精度错误！未找到引用源。,并令k=0；Step2. 求解线性规划问题：min 错误！未找到引用源。

机械优化设计-第04章 多维有约束优化方法

第四章：多维有约束优化方法 4.1概述 一、多维有约束问题的数学模型 机械优化设计问题绝大多数是属于多维有约束非线性规划，其数学模型可表示为 式中a i、b i分别为x i的下界和上界。 在求解约束优化问题时，虽然可以利用第三章的无约束优化方法，再加上约束的逻辑判断，使搜索点保持在可行域内逐步逼近约束最优解，但这样处理太复杂，缺乏严格的科学性。因此，出现了一些直接求解约束优化问题的方法，其基本思路也是数值迭代法。目前，约束优化方法虽然不如无约束优化方法那样多而完善，但对求解工程优化问题已有很多较好的方法。 二、多维有约束优化方法的分类 （1)直接法 直接法包括：网格法、分层降维枚举法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。 (2)间接法 间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、精确罚函数法、广义乘子法、广义简约梯度法和约束变尺度法。 直接法不需要利用目标函数和约束函数的梯度，就可直接利用迭代点和目标函数值的信息来构造搜索方向。间接法要利用目标、约束函数的梯度，其中也包括利用差分来近似梯度的应用。很多约束优化方法是先转变成无约束优化方法来求解。可见，无约束优化方法也是也是约束优化方法的基础。

4.2复合形法 一、方法概述 基本思路：在可行域中选取K个设计点（n+1≤K≤2n）作为初始复合形的顶点。比较各顶点目标函数值的大小，去掉目标函数值最大的顶点(称最坏点)，以坏点以外其余各点的中心为映射中心，用坏点的映射点替换该点，构成新的复合形顶点。 反复迭代计算，使复合形不断向最优点移动和收缩，直至收缩到复合形的顶点与形心非常接近，且满足迭代精度要求为止。 初始复合形产生的全部K个顶点必须都在可行域内。 二、初始复合形的产生 复合形法是一种在可行域内收索最优点大直接解法。 (1)确定可行点作为初始复合形的第一个顶点： 式中： 通过调整随机数，使第一个初始点控制在可行域范围内。 (2)产生其余（K－1）个随机点。 (3)将非可行点调入可行域内。 若从第一个点到第个点均在可行域范围内，但第点不在可行域内，采取下列步骤使其调入可行域范围内： （a）先求出已在可行域范围内的q个点的中心： （b）将点向方向推进：＝＋0.5(－)若推进的点仍不在可行域范围内，则利用上式，使其继续向中心移动，直至新点成为可行点为止。

约束优化设计

第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由m 个不等式约束条件g u (x )≤0所确定的可行域φ内，选择一个初始点0 X 然后确定一个可行搜索方向S ，且以适当的步长沿S 方向进行搜索，取得一个目标函数有所改善的可行的新点1 X 即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算： k+1k k k =+S (k=0,1,2,..)X X α逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好 的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部 最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集 1,2,...,1,2,...,u m v p n ==

间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。 然后对新目标函数进行无约束极小化计算。 间接法是结构优化设计中广泛使用的有效方法，其特点： 1） 由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和 数值计算的稳定性大有提高； 2） 可以有效处理具有等式约束的约束优化问题； 3） 目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精 度，甚至导致计算失败。 a) 可行域是凸集；b)可行域是非凸集 () ()()()121211 ,,m l j k j k X F X G g X H h X φμμμμ==??=++? ?????∑∑ 新目标函数 加权因子

数理经济学第10章具有约束方程的最优化

第10章 具有约束方程的最优化 10.1 基本约束优化问题 10.2 一阶必要条件 10.3 二阶充分条件 10.4 最优解的比较静态分析 10.5 Lagrange 乘子的数学含义 10.6 目标函数最优值的比较静态分析 10.1 基本约束优化问题 一般标准的极大化问题： 12max (,,,)n f x x x 或者：max ()f x 12..(,, ,)j n j s t g x x x b ≤ ..()s t g x b ≤ 12(,,,)i n i h x x x a = ()h x a = 一般标准的极小化问题： 12min (,,,)n f x x x 或者：min ()f x 12..(,, ,)j n j s t g x x x b ≥ ..()s t g x b ≥ 12(,,,)i n i h x x x a = ()h x a = 10.2+10.3：一阶必要条件和二阶充分条件 1、等式约束优化问题 （1）两个变量一个等式约束的情形

极大化问题： max (,)f x y .. (,)s t h x y c = 例：消费者的效用最大化问题 12max (,)U x x 1122.. s t p x p x I += 构造拉格朗日函数： (,,)(,)[(,)]L x y f x y h x y c λλ=-- (,)[(,)]f x y c h x y λ=+- 一阶必要条件： (,)0L c h x y λ=-= 0x x x L f h λ=-= 0y y y L f h λ=-= 注：通过将L 视为三个选择变量的自由函数，将约束优化转化为了无约束优化。 拉格朗日乘数的解释： λ*是Z*（最优值）对约束变化敏感性的度量。 特别的，c 增加（预算增加）的影响表明约束条件的放宽如何影响最优解。 设：根据一阶必要条件得到的最优解为λ*，*x ，*y ，则λ*，

修订过的最优化方法复习题

《最优化方法》复习题 第一章 引论 一、 判断与填空题 1 )].([arg )(arg m in m ax x f x f n n R x R x -=∈∈ √ 2 {}{}.:)(min :)(max 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 ≤+ .

五种最优化方法

五种最优化方法 1.最优化方法概述 最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3）线性优化与非线性优化（目标函数和约束条件是否线性）； 4）静态规划和动态规划（解是否随时间变化）。 最优化问题的一般形式（有约束条件）： 式中f（X）称为目标函数（或求它的极小，或求它的极大），si（X）称为不等式约束，hj（X）称为等式约束。化过程就是优选X，使目标函数达到最优值。 2.牛顿法 简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法： 3）是一种函数逼近法。 原理和步骤 3.最速下降法（梯度法） 最速下降法简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）沿函数在该点处目标函数下降最快的方向作为搜索方向； 最速下降法算法原理和步骤 4?模式搜索法（步长加速法） 简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的 是探测有利的下降方向，而模式移动的目的则是沿着有利方向加速移动。

模式搜索法步骤 5.评价函数法 简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下： min (f_1(x),f_2(x),…,f_k(x)) .g(x)<=o 传统的多目标优化方法本质是将多目标优化中的各分目标函数, 经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有“线性加权和法”、“极大极小法”、“理想点法”。选取其中一种线性加权 求合法介绍。 线性加权求合法 6.遗传算法 智能优化方法是通过计算机学习和存贮大量的输入-输出模式映射关系，进而达到优化的一种方法，主要有人工神经网络法，遗传算法和模拟退火法等。遗传算法基本概念 1.个体与种群 个体就是模拟生物个体而对问题中的对象 (一般就是问题的解)的一种称呼。种群就是模拟生物种群而由若干个体组成的群体，它一般是整个搜索空间的一个很小的子集。 2.适应度与适应度函数 适应度就是借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度。 适应度函数就是问题中的全体个体与其适应度之间的一个对应关系。该函数就是遗传算法中指导搜索的评价函数。 遗传算法基本流程 的就是对一定数量个体组成的生物种群进行选择、交叉、变异等遗传操作，最终求得最优解或近似最优解。 遗传算法步骤

天津大学-研究生-最优化方法复习题

《最优化方法》复习题 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg m in m ax x f x f n n R x R x -=∈∈ √ 2 {}{}.:)(min :)(max 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 算法迭代时的终止准则（写出三种）：_____________________________________。

天津大学《最优化方法》复习题(含答案)

天津大学《最优化方法》复习题（含答案） 第一章 概述(包括凸规划) 一、 判断与填空题 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 ≤+ .

有约束优化问题

分数: ___________ 任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业四 学生姓名： 学号： 提交时间：

一、问题重述 形如下式的寻优问题称为无约束最优化问题，这类问题的最优解称为约束最优解。 min f(x).. (x)0,i 1,...p h (x)0,j 1,...q 0,0i j s t g p q ??≤=?? ==? ?>>? 约束优化问题的最优性条件是，在满足灯饰和不等式约束条件下，其目标函数值最小的点所必须满足的条件。 约束优化设计问题求解方式有两种，间接法和直接法。直接法是在满足不等式约束的可行设计区域内直接搜索问题的最优解和最小值，常用的方法有随机方向法、复合形法。间接法是将优化问题转化为一系列无约束优化问题来求解，常用的方法有内惩罚函数法、外惩罚函数法以及混合惩罚函数法。 本次作业以为例，介绍无约束最优化问题的寻优方法。 二、算法原理 复合形法是求解约束非线性寻优问题的一种重要的直接方法。 复合形法的核心在于可行域内构造的不断逼近最优点的复合形。每次迭代，计算各顶点的目标函数值，找到目标函数值最大的顶点(称最坏点)，然后按相应的原则求出目标函数可行的下降点，以此代替最坏点，构成新的复合形。复合形每改变一次，各个顶点就向最优点移动一步，直至满足终止条件，找到最优点。 复合形法的顶点数K 通常取12n K n +≤≤，其中n 表示搜索环境的维度。初始图形的顶点是由设计者确定或者随机产生的，但一定要保证在可行域内。如果随机产生的初始点没有在可行域内，可以通过以下步骤将其调入可行域内。 （1）计算在可行域内点的初始点集中心X (s); （2）将可行域外的点向X (s)靠拢，每次前进间距的一半，直至进入可行域内。 复合行法的终止条件可以有以下几种形式，满足终止条件后，可将最后复合形的好点及其函数值作为最优解输出。 （1）各顶点与好点函数值之差的均方根小于误差限； （2）各顶点与好点的函数之差平和小于误差限； （3）各顶点与好点函数值差的绝对值之和小于误差限。

ch17-有约束最优化问题

第17章 有约束最优化问题 17.1 线性规划 线性规划是处理线性目标函数和线性约束的一种较为成熟的方法，目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。 线性规划的求解方法主要是单纯形法（Simple Method ）。该法由Dantzig 于1947年提出，以后经过多次改进。单纯形法是一种迭代算法，它从所有基本可行解的一个较小部分中通过迭代过程选出最优解。其迭代过程的一般描述如下。 ① 将线性规划化为典范形式，从而可以得到一个初始基本可行解)0(x （初始顶点），将它作为迭代过程的出发点，其目标值为)()0(x z 。 ② 寻找一个基本可行解)()(,)0()1()1(x z x z x ≤使 。方法是通过消去法将产生)0(x 的典范形式化为产生)1(x 的典范形式。 ③ 继续寻找较好的基本可行解，使目标函数值不断改进。当某个基本可行解再也不能被其它基本可行解改进时，它就是所求的最优解。 MATLAB 优化工具箱中采用的是投影法，它是单纯形法的一种变种。 17.1.1 基本数学原理 线性规划问题的标准形式是(矩阵形式) ?? ? ? ?≥--=--=0m in X b AX ，C CX z 线性方程组为常行向量线性函数 线性规划的标准形式要求使目标函数最小化，约束条件取等式，变量x 非负。不符合 这几个条件的线性模型要首先转化成标准形式。 17.1.2 有关函数介绍 在 MA TLAB 工具箱中，可用 linprog 函数求解线性规划问题。 假设线性规划问题的数学模型为： ??? ????≤≤=--≤ub x lb beq x Aeq b Ax x f T 线性方程组m in 式中 f,x,b,beq,lb 和ub 为向量，A 和 Aeq 为矩阵。 linprog 函数的调用格式如下： ● x=linprog(f,A,b)——只有约束条件A*x<=b 。 ● x=linprog(f,A,b,Aeq,beq)——有等式约束，若没有不等式约束，此时要增加 A=[ ]、b=[ ]。 ● x=linprog(f,A,b,Aeq,beq,Ib,ub)——定义设计变量x 的下界 Ib 和上界ub ，使得 x 始终在该范围内。若没有等式约束，令 Aeq=[ ]、beq=[ ]。 ● x=linprog(f,A,b,Aeq,beq,Ib,ub,x0)——设置初值为x0。该选项只适用于中型问