第二章约束非线性规划总结

非线性规划高考知识点归纳总结非线性规划是运筹学中的一个重要分支，它主要研究在非线性目标函数和非线性约束条件下的优化问题。

在高考数学中，非线性规划通常不会作为主要考点，但了解其基本概念和简单应用对于提高数学素养和解决实际问题具有重要意义。

首先，非线性规划问题可以定义为：给定一个目标函数 \( f(x_1,x_2, ..., x_n) \) 和一组约束条件 \( g_i(x_1, x_2, ..., x_n) \leq 0 \)（对于 \( i = 1, 2, ..., m \)），以及 \( h_j(x_1,x_2, ..., x_n) = 0 \)（对于 \( j = 1, 2, ..., p \)），求 \( x \) 的值，使得目标函数 \( f \) 达到最大值或最小值。

在高考中，非线性规划的知识点通常包括以下几个方面：1. 目标函数与约束条件：理解目标函数和约束条件在非线性规划中的作用，以及它们如何影响问题的解。

2. 可行域：掌握如何根据约束条件确定可行域，这是求解非线性规划问题的基础。

3. 拉格朗日乘数法：了解拉格朗日乘数法的基本原理，以及如何利用它求解带有等式约束的非线性规划问题。

4. KKT条件：掌握KKT（Karush-Kuhn-Tucker）条件，这是求解非线性规划问题的必要条件。

5. 数值方法：了解一些基本的数值方法，如梯度下降法、牛顿法等，这些方法在实际求解非线性规划问题时非常有用。

6. 实际应用：能够将非线性规划的概念应用到实际问题中，如资源分配、成本最小化等。

在复习非线性规划时，建议从以下几个步骤进行：- 理解概念：首先，要理解非线性规划的基本概念，包括目标函数、约束条件、可行域等。

- 掌握方法：其次，要掌握求解非线性规划问题的基本方法，如拉格朗日乘数法和KKT条件。

- 练习题目：通过大量的练习题目来巩固知识点，提高解题能力。

- 实际应用：尝试将非线性规划的概念应用到实际问题中，提高解决实际问题的能力。

非线性规划知识点讲解总结1. 非线性规划的基本概念非线性规划是指目标函数和/或约束条件包含非线性项的优化问题。

一般来说，非线性规划问题可以表示为如下形式：\[\min f(x)\]\[s.t. \ g_i(x) \leq 0, \ i=1,2,...,m\]\[h_j(x)=0, \ j=1,2,...,p\]其中，\(x \in R^n\)是优化变量，\(f(x)\)是目标函数，\(g_i(x)\)和\(h_j(x)\)分别表示不等式约束和等式约束。

目标是找到使目标函数取得最小值的\(x\)。

2. 非线性规划的解决方法非线性规划问题的求解是一个复杂的过程，通常需要使用数值优化方法来解决。

目前，常用的非线性规划求解方法主要包括梯度方法、牛顿方法和拟牛顿方法。

（1）梯度方法梯度方法是一种基于目标函数梯度信息的优化方法。

该方法的基本思想是在迭代过程中不断沿着梯度下降的方向更新优化变量，以期望找到最小值点。

梯度方法的优点是简单易实现，但缺点是可能陷入局部最优解，收敛速度慢。

（2）牛顿方法牛顿方法是一种基于目标函数的二阶导数信息的优化方法。

该方法通过构造目标函数的泰勒展开式，并利用二阶导数信息来迭代更新优化变量，以期望找到最小值点。

牛顿方法的优点是收敛速度快，但缺点是计算复杂度高，需要计算目标函数的二阶导数。

（3）拟牛顿方法拟牛顿方法是一种通过近似求解目标函数的Hessian矩阵来更新优化变量的优化方法。

该方法能够克服牛顿方法的计算复杂度高的问题，同时又能保持相对快速的收敛速度。

拟牛顿方法的典型代表包括DFP方法和BFGS方法。

3. 非线性规划的应用非线性规划方法在实际生活和工程问题中都有着广泛的应用。

以下将介绍非线性规划在生产优化、资源分配和风险管理等领域的应用。

（1）生产优化在制造业中，生产线的优化调度问题通常是一个非线性规划问题。

通过对生产线的机器设备、生产工艺和生产速度等因素进行建模，并设置相应的目标函数和约束条件，可以使用非线性规划方法来求解最优的生产调度方案，以最大程度地提高生产效率和减少成本。

求解带约束的非线性规划问题罚函数法求解带约束的非线形规划问题的基本思想是：利用问题的目标函数和约束函数构造出带参数的所谓增广目标函数，把约束非线形规划问题转化为一系列无约束非线形规划问题来求解。

增广目标函数由两个部分构成，一部分是原问题的目标函数，另一部分是由约束函数构造出的“惩罚”项，“惩罚”项的作用是对“违规”的点进行“惩罚”。

罚函数法主要有两种形式。

一种称为外部罚函数法，或称外点法，这种方法的迭代点一般在可行域的外部移动，随着迭代次数的增加，“惩罚”的力度也越来越大，从而迫使迭代点向可行域靠近；另一种成为内部罚函数法，或称内点法，它从满足约束条件的可行域的内点开始迭代，并对企图穿越可行域边界的点予以“惩罚”，当迭代点越接近边界，“惩罚”就越大，从而保证迭代点的可行性。

1. 外部罚函数法(外点法)约束非线形规划问题min f(x),s.t. g(x)>=0,其中g (x) = (g 1(x),…,gm(x)),将带约束的规划问题转化为无约束非线形规划问题来求解的一个直观想法是：设法加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束问题的最优解，于是对于可行域 S= { x | g(x) >= 0} 作一惩罚函数P(x) = 0, x∈S;K, else其中K是预先选定的很大的数。

然后构造一个增广目标函数F (x) = f (x) + P (x) ,显然x∈S时，F（x）与f (x)相等，而x S 时，相应的F值很大。

因此以F(x)为目标函数的无约束问题minF x) = f(x) + P (x) （1）的最优解也是原问题（NP）的最优解。

上述P(x)虽然简单，但因它的不连续性导致无约束问题（1）求解的困难。

为此将P(x)修改为带正参数M（称为罚因子）的函数P(x) =M ∑[min (0,gj(x))]²则min F(x,M) = f(x) + M∑[min (0,gj(x))]²的最优解x(M) 为原问题的最优解或近似最优解。

(1)带约束的非线性优化问题解法小结考虑形式如下的非线性最优化问题(NLP):min f(x)「g j (x )“ jI st 彳 g j (x)=O j L其 中， ^(x 1,x 2...x n )^ R n， f : R n > R ， g j :R n > R(j I L) ， I 二｛1,2,…m ｝， L ={m 1,m 2...m p}。

上述问题(1)是非线性约束优化问题的最一般模型，它在军事、经济、工程、管理以 及生产工程自动化等方面都有重要的作用。

非线性规划作为一个独立的学科是在上世纪 50年 代才开始形成的。

到70年代，这门学科开始处于兴旺发展时期。

在国际上，这方面的专门性 研究机构、刊物以及书籍犹如雨后春笋般地出现，国际会议召开的次数大大增加。

在我国， 随着电子计算机日益广泛地应用，非线性规划的理论和方法也逐渐地引起很多部门的重视。

关于非线性规划理论和应用方面的学术交流活动也日益频繁，我国的科学工作者在这一领域 也取得了可喜的成绩。

到目前为止，还没有特别有效的方法直接得到最优解，人们普遍采用迭代的方法求解： 首先选择一个初始点，利用当前迭代点的或已产生的迭代点的信息，产生下一个迭代点，一 步一步逼近最优解，进而得到一个迭代点列，这样便构成求解( 1)的迭代算法。

利用间接法求解最优化问题的途径一般有：一是利用目标函数和约束条件构造增广目标 函数，借此将约束最优化问题转化为无约束最优化问题，然后利用求解无约束最优化问题的 方法间接求解新目标函数的局部最优解或稳定点，如人们所熟悉的惩罚函数法和乘子法；另 一种途径是在可行域内使目标函数下降的迭代点法，如可行点法。

此外，近些年来形成的序 列二次规划算法和信赖域法也引起了人们极大的关注。

在文献［1］中，提出了很多解决非线性 规划的算法。

下面将这些算法以及近年来在此基础上改进的算法简单介绍一下。

1. 序列二次规划法序列二次规划法，简称SQ 方法.亦称约束变尺度法。

非线性规划什么是非线性规划？非线性规划（Nonlinear Programming，简称NLP）是一种数学优化方法，用于求解包含非线性约束条件的优化问题。

与线性规划不同，非线性规划中的目标函数和约束条件都可以是非线性的。

非线性规划的数学表达式一般来说，非线性规划可以表示为以下数学模型：minimize f(x)subject to g_i(x) <= 0, i = 1, 2, ..., mh_j(x) = 0, j = 1, 2, ..., px ∈ R^n其中，f(x)是目标函数，g_i(x)和h_j(x)分别是m个不等式约束和p个等式约束，x是优化变量，属于n维实数空间。

非线性规划的解法由于非线性规划问题比线性规划问题更为复杂，因此解决非线性规划问题的方法也更多样。

以下列举了几种常用的非线性规划求解方法：1. 数值方法数值方法是最常用的非线性规划求解方法之一。

它基于迭代的思想，通过不断优化目标函数的近似解来逼近问题的最优解。

常见的数值方法有梯度下降法、牛顿法、拟牛顿法等。

2. 优化软件优化软件是一类针对非线性规划问题开发的专用软件，它集成了各种求解算法和优化工具，可以方便地求解各种类型的非线性规划问题。

常见的优化软件有MATLAB、GAMS、AMPL等。

3. 线性化方法线性化方法是一种将非线性规划问题转化为等价的线性规划问题的求解方法。

它通过线性化目标函数和约束条件，将非线性规划问题转化为线性规划问题，然后利用线性规划的求解方法求解得到最优解。

4. 分类方法分类方法是一种将非线性规划问题分解为若干个子问题求解的方法。

它将原始的非线性规划问题分解为多个子问题，然后将每个子问题分别求解，并逐步逼近原始问题的最优解。

以上仅是非线性规划求解方法的一小部分，实际上还有很多其他的方法和技巧可供选择。

在实际应用中，选择合适的方法和工具是非常重要的。

非线性规划的应用非线性规划在实际生活和工程中有着广泛的应用。

1.非线性规划我们讨论过线性规划，其目标函数和约束条件都是自变量的线性函数。

如果目标函数是非线性函数或至少有一个约束条件是非线性等式（不等式）,则这一类数学规划就称为非线性规划。

在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。

由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计，管理科学，风险管理，系统控制，求解均衡模型，以及数据拟合等领域得到越来越广泛的应用。

非线性规划的研究始于三十年代末，是由W.卡鲁什首次进行的，40年代后期进入系统研究，1951年•库恩和.塔克提出带约束条件非线性规划最优化的判别条件，从而奠定了非线性规划的理论基础，后来在理论研究和实用算法方面都有很大的发展。

非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。

无约束问题的求解方法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。

关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。

总的原则是设法将约束问题化为无约束问题；把非线性问题化为线性问题从而使复杂问题简单化。

求解方法有可行方向法、约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。

虽然这些方法都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。

非线性规划举例［库存管理问题］考虑首都名酒专卖商店关于啤酒库存的年管理策略。

假设该商店啤酒的年销售量为A箱，每箱啤酒的平均库存成本为H元，每次订货成本都为F元。

如果补货方式是可以在瞬间完成的，那么为了降低年库存管理费用，商店必须决定每年需要定多少次货以及每次订货量。

A A我们以Q表示每次定货数量，那么年定货次数可以为 -，年订货成本为F -。

由于平Q Q均库存量为Q，所以，年持有成本为2H Q ,2,年库存成本可以表示为A HC(Q)F QQ2将它表示为数学规划问题：A Hmin C(Q) F QQ 2s.t. Q 0其中Q为决策变量，因为目标函数是非线性的，约束条件是非负约束，所以这是带约束条件的非线性规划问题。

非线性规划的理论与算法非线性规划（Nonlinear Programming, NLP）是数学规划的一个重要分支，其研究对象是带有非线性约束条件的最优化问题。

非线性规划模型常见于各类工程技术问题的优化，如工业系统优化、经济系统优化、交通运输系统优化等。

本文将介绍非线性规划的基本理论和常用的求解算法。

一、非线性规划模型min f(x)s.t.g(x)≤0,h(x)=0其中，f(x)为目标函数；g(x)≤0与h(x)=0为约束条件；x为决策变量，其取值范围由约束条件决定。

非线性规划模型常见的类型包括无约束问题、等式约束问题和不等式约束问题等。

二、非线性规划的求解算法1. 顺序二次规划算法（Sequential Quadratic Programming, SQP）顺序二次规划算法是一种常用的非线性规划求解算法。

该算法通过构造拉格朗日函数来将非线性规划问题转化为一系列二次规划子问题。

通过迭代求解这些二次规划子问题，最终得到原始非线性规划问题的最优解。

SQP算法具有高效、稳定性强等优点，已广泛应用于实际问题中。

2. 内点法（Interior Point Methods）内点法是一种常用的非线性规划求解算法，可以有效处理约束条件较多的非线性规划问题。

该算法通过构造适当的增广 Lagrange 函数，将非线性规划问题转化为一系列无约束优化问题。

通过迭代求解这些无约束优化问题，最终找到原始非线性规划问题的解。

内点法具有收敛速度快、计算精度高等优点。

3. 遗传算法（Genetic Algorithm, GA）遗传算法是一种模拟生物进化过程的启发式优化算法，常用于求解非线性规划问题。

该算法通过借鉴自然选择、交叉和突变等遗传操作，逐步演化出一组较好的解，寻找最优解。

遗传算法不需要假设目标函数和约束条件的具体形式，因此适用于复杂的非线性规划问题。

4. 粒子群优化算法（Particle Swarm Optimization, PSO）粒子群优化算法是一种模拟鸟群觅食行为的优化算法，也常用于求解非线性规划问题。

第3讲非线性规划在目标和约束中有非线性成分 非线性规划问题§1 基本概念一、非线性规划的数学模型1. 引例例1某公司经营产品I, II (见下表).I(x1) II(x2) 限时服务时间0.5 2+0.25x2800 售价30(元) 450(元)求最大营业计划. 问题归结为1212212max ()304500.5(20.25)800(),0;f x x x x x x x x =+++≤⎧⎨≥⎩非线性 例2 产品销售与多因素相关, 设已知比值/,/ij i ja i j w w ==重要性重要性 1111n n nn a a J a a ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦L L L LL求各权重(1,2,,);i w i n =L 12[,,,]Tn w w w w =L ,使2111min (),,,1,2,,;1;0,1,2,...,n nij j i i j i ij j nii i a w w w a w i j n ww i n===-===≥=∑∑∑L2. 一般非线性模型(其余可化作此类型)1min (),[,...,]()0;1,2,...,;()0;1,2,...,;Tn i j f X X x x h X i m g X j l ⎧=⎪==⎨⎪≥=⎩()0()0h X h X ≥======>-≥min (),()0;1,2,...,;j f X g X j l ⎧⎪≥⎨⎪=⎩或较一般的形式min (),{|()0;1,2,...,;j f X X R ER X g X j l ∈⊂⎧⎨=≥=⎩R 称为问题的可行域若遇≤, 则两边乘1-若遇max ()f x , 可换为min {-()f x } 二、二维问题图解 (高维意义类似) 立体上分析例1 2212min ()(2)(2)2f X x x =-+-+12()60h X x x =+-=最优解为123,3,4x x f ***===演示若1260x x +-≤ 则最优解为122,2,2x x f ***===(注:此时约束1260x x +-=无效)1x 2x ()f X 1260x x +-=4f *=平面上分析 在平面12,x x 上 作目标函数等值线 →()f X c =. 可行域如AB 线段;()6f X =→变小→…→()4f X = 最小123,3x x **== 例2 (含等式和不等式)1260x x +-=1x 2x 23()4f X =()6f X =B A2212min ()(2)(1)f X x x =-+-212212125050,0,0x x x x x x x +-=+-≥≥≥可行域为ABCD 段 最小值点(4,1),最小值8.B:是AC 段上最小值点 D:是ABCD 上最小值点2x 201x 23A4511•目标值变小B CD ••三、函数极值概念 设(),()nf X X R E ∈⊂开(严格)局部极小值: ()()(),(,),f X f X X U X ε**≤<∈o (严格)全局极小值: ()()(),,f X f X X R *≤<∈X R *分别称为(严格)局部(全局)极小值点. ()f X *称为(严格)局部(全局R)极上值.极大值点和极大值的概念类似;四、多元函数极值存在条件对一元(二阶可微)有若()0f x *'=, ()0f x *''> →()f x *极小值, 若()0f x *'=, ()0f x *''< →()f x *极大值, 对于n 元函数 类似有 1. 定理1(必要)设(),()nf X X R E ∈⊂在开集上有一阶连续偏导, 且在X R *∈处取得极值, 则梯度应有 ()1(),,0,,0TT X n ff f f X Xx x **⎛⎫∂∂∂∇=== ⎪∂∂∂⎝⎭K K极值点+可偏导⇒稳定点(驻点) ⇒可能的最值点 (1)每点梯度是函数值增长最快(定义域内)的方向. (2)每点梯度与过该点等值线正交2. 二次型11()n nij i j i j f X a x x ===∑∑其中()ij A a =是实对称阵1x 2x ()f X 1f x ∂∂2fx ∂∂0()f X ∇正定()0,0f X X >∀≠有关二次型的正定、半正定、负定、半负定、不定 与实对称阵的正定、半正定、负定、半负定、不定 的概念, 性质∈高等代数 3. 多元泰勒公式 (差量形式)(0)(0)(0)()()()()Tf X f Xf XX X=+∇-(0)2(0)1()()()2T X X f X X X +-∇-或(带高阶)(0)(0)(0)()()()()Tf X f Xf XX X=+∇-()2(0)2(0)(0)1()()()2T X X f X X X o X X +-∇-+-其中(0)(0)(),01X X X Xθθ=+-<<(增量形式)若(0)X XP =+(增量), 则(0)(0)(0)()()()Tf XP f X f XP +=+∇21()2T P f X P +∇4. 充分条件 定理2(充分)设(),()n f X X R E ∈⊂在开上有二阶连续偏导,.X R *∈ 若()0,f X *∇=且()f X 2*∇正定,则X R *∈为()f X 的严格局部极小点, 其中2211122221()n TX n n n X f f x x x x ff X X Xf f x x x x ***⎡⎤∂∂⎢⎥∂∂∂∂⎢⎥∂⎢⎥∇==∂∂⎢⎥∂∂⎢⎥⎢⎥∂∂∂∂⎣⎦L L L L L称为()f X 在X *的海赛Hesse 阵.*2*0()0X f X X *⎧<⎪∇>⎨⎪⎩极大值点极小值点=0不定例3 对2212()f X x x =-, 易得()0f X ∇=→120,0x x ==和20()02f X 2⎡⎤∇=⎢⎥-⎣⎦不定→(0,0)TX =非极值点. (此点为鞍点)五、凸、凹函数(弦定义法) 1．一元凸函数:(01)α<< (1)(2)(1)(2)((1))()(1)()f xx f x f x αααα+-≤+-一元凹函数(01)α<< (1)(2)(1)(2)((1))()(1)()f xx f x f x αααα+-≥+-当上式为严格不等式时,相应函数称为严格凸、凹函数.(1)(2)((1))f x x αα+-(2)x(1)x (1)(2)()(1)()f x f x αα+-()f x O x(1)(2)((1))f x x αα+-(2)x(1)x (1)(2)()(1)()f x f x αα+-()f x O x2 凸函数的性质(i) 凸域上的凸函数的正线性组合仍为凸函数,即 若()i f x 是凸域c R 上的凸函数, 0,1,2,...i i m β≥=, 则1()mi i c i f x R β=∑为上的凸函数.凹函数有类似的性质.(ii) 设()f X 是凸域c R 上的凸函数, 则β∀实数,{|,()}c S X X R f X ββ=∈≤是凸集.证 因为对任意01α<<和 (1)(2),,X XS β∀∈令(1)(2)(1)c X XXR αα=+-∈由凸函数的性质, 得(1)(2)()((1))f X f XXαα=+-(1)(2)()(1)()f X f Xαα≤+-(1)αβαββ≤+-=.所以,X S β∈ 即S β是凸集. 凹函数也有类似的性质.1x 2x ()f X :()S f X ββ≤()f X β=cR3．凸函数的判定 定理3(一阶条件)设()(),nc f X R E ⊂在开凸集上有一阶连续偏导数 则(1)(2)(),,c f X R X X⇔∀在上凸对有(2)(1)(1)(2)(1)()()()()Tf Xf X f X XX ≥+∇-证 见右图.(切在曲下)(2)x(1)x(2)()f x ()f x x(1)(1)(2)(1)()()()f X f X X X +∇-O必要性:⇒凸f x X f X f X (2)(1)(2)(1)((1))()(1)()αααα+-≤+- f X X X f X f X f X (1)(2)(1)(1)(2)(1)(())()()()αα+--⇒≤-移项重组Tf x XXf Xf X(1)(2)(1)(2)(1)()()()().α→====>∇-≤-⇒0移得证项充分性: 由(1)(2)(1)X XX αα=+-及(1)(1)()()()()Tf X f X f X XX ≥+∇-Tf X f X f X XX (1)(1)()[()()()]αα→≥+∇-同样有 (2)(2)()()()()T f Xf X f X XX ≥+∇-Tf Xf X f X XX (2)(2)(1)()(1)[()()()]αα→-≥-+∇-组合得(1)(2)()(1)()()f X f X f X αα+-≥.证毕.凹函数, 严格凸, 严格凹都类似可证.(二阶条件)设()(),nc f X R E ⊂在开凸集上有二阶连续偏导数 则c f X R f X R ().⇔∈在上为凸在的海赛阵半正定证 必要性 2(),c X R f X 对的∀∈∇ 记2()()f X H X ∇= 再任取(0)nZ E ≠∈,因为c R 是开集,任一点均为内点. 所以 0, [,], a st a a a ∃>∈- ,X aZ R +∈有由凸性得 ()()()Tf X aZ f X f X aZ +≥+∇ 由泰勒公式得221()()()()()2TT f X aZ f X a f X Z a Z X Z o a +=+∇++ZXX aZ+R222212()()()0()02T To a a Z H X Z o a Z H X Z a⇒+≥⇒+≥ ()0TZ H X Z ≥, 故得()H X 半正定.充分性, , X X R X X X ∆∀∈=-对，令由泰勒公式得1()()()(),2TTf X f X f X X X H X X X λ=+∇∆+∆+∆∆其中0 1.λ<<由R 是凸集，得X X R λ+∆∈()0H X X λ⇒+∆≥， 从而()()().Tf X f X f X X ≥+∇∆ 其它类似证.例3 证明2212()f X x x =--是凹函数.证10()01H X -⎡⎤=⎢⎥-⎣⎦负定,所以()f X 是严格凹函数. 4. 凸函数的极值定理5设()f X 是凸集R 上凸函数, 若()f X *是R 内的极小值, 则()f X *是R 上的最小值, 且极小值点集是一个凸集.1x 2x ()f X {|min ()}X f X R证 设X *是R 内任一极小点，则必有()(),()f X f X X N X δ**≥∈对, , 0<<1, Y R λλ∀∈∃(1)()X Y N X δλλ使**-+∈(注=0λ,1的情形)由凸性得(1)()()[(1)]()f X f Y f X Y f X λλλλ***-+≥-+≥因此得()()f Y f X *≥, 即()f X *是R 上最小值.Y*X-+X Y*(1)λλY λ另外由前性质, 得集{|()()}X f X f X β*≤=是凸集.定理6 设()f X 是凸集R 上的可微凸函数, 若, , X R X R *∃∈∈对一切有()()0T f X X X **∇-≥则().f X R *是上最小值 证 由凸性及题设即得T f X f X f X X X f X ()()()()()****≥+∇-≥.()()0T f X X X **∇-≥:*X 边的点X R ()∈均为增大点.注1若, ()0.X f X **∇=是内点则注2若X *是边界点, 则如上图所示 →内点X *上取最优值()0.f X *⇔∇=579*()f X ∇*XX•*X X -579*()f X ∇*X X•*X X -六、凸规划(凸集上凸函最优化问题)设()f X 是凸函数, (),1,...,j g X j l =是凹函数, 则称min (){|()0,1,...,}X Rc j f X R X g X j l ∈⎧⎪⎨=≥=⎪⎩为凸规划,具有:(1) 可行解集是凸集; (2) 最优解集是凸集(若有); (3) 局部最优=>全局最优;(4) 若f (X )严格凸,且存在最优解, 则最优解唯一.1x 2x ()j g X {|()0}j R X g X =≥()f X略证(1) (1)(2),,01c X XR α∀∈<<, 则(1)(2)(1)(2)[(1)][](1)[]0i i i g XXg X g Xαααα+-≥+-≥→(1)(2)(1)c XXR αα+-∈→c R 是凸集(2) 前已叙证; (3) 前已叙证;(4) 反证法, 若不唯一, (1)(2)c XXR ∃≠∈ 有(1)(2)()()f X f X=取01α<<, 则1x 2x ()j g X {|()0}j R X g X =≥()f X(1)(2)(1)c XXR αα+-∈,再由()f X 在凸集R c 上严格凸, 知(1)(2)(1)(2)[(1)][](1)[]f XX f X f X αααα+-<+-(1)[]f X =→说明有更优解→矛盾→故唯一.“非规”与“线规”关系:因 z =CX ,AX =b 视作凹凸均可, 故 线性规划⊂凸规划.例4 试说明以下问题是凸规划2211111222123142min ()44()20,()10,()0,()0.f X x x x g X x x g X x x g X x g X x ⎧=+-+⎪=-+≥⎪⎪=-+-≥⎨⎪=≥⎪⎪=≥⎩ 解 20,02f H f ⎡⎤=∴⎢⎥⎣⎦Q 正定是严格凸函数. 因134(),(),(),g X g X g X ⊂是线性函数凹函数2220()00g g X H -⎡⎤=⎢⎥⎣⎦的半负定2().g X ⇒⊂凹函数 故原问题是凸规划.最小值点 (0.58, 1.34); 最小值3.8. 如图所示.1x 2x 1()0g X ≥O2()0g X ≥23.81461七、下降迭代算法理想--最值求法: 若可微*0f X ⇒∇=⇒令解出 现实--(很多) f 不可微或难微 迭代法;原则--初解(0)(1)(1)(0),()()...X X st f X f X <→u u u u u u u x 某算法,→ ()*lim 0.k k XX→+∞-=具体--步骤: (1) 选初值(0),0;X k = (2) 选方向()k P ; (3) 选步长k λ; (1)()()k k k k XXP λ+=+, 能使(1)()()()()()()k k k k k f Xf XP f Xλ+=+<即可(4) 检满停; 未达令k =k +1, 转(2).1x 2x (1)XP (0)0λ(0)X ()f XX*()k X (1)k X+()k k Pλ()k P 201510(1)()()k k f X P +∇⊥注1: 各种算法的主要区分点是: 搜索方向的选择. 注2: 大多算法中的步长为()()(1)()():min (),;k k k k k k k f X P XX P λλλλ+⎧+⎪⎨=+⎪⎩ 实质: 对λ一元函数进行极小;称此过程为: (最优)一维搜索 = 线搜索; 称步长k λ为: 最佳步长;(关于该向()k P ) 重要特点为: 搜索方向()k P⊥最佳步长处的梯度(1)()k f X+∇定理7 设()f X 具有一阶连续偏导数, (1)k X +如下得()()(1)()():min (),;k k k k k k k k f X P XX P λλλ+⎧+⎪⎨=+⎪⎩ 则有(1)()()0.k T k f X P +∇=证 设()()()()k k f X Pϕλλ=+, 令()0,ϕλ'=即()()()()()d ()0()0d k k k k Tk kf XPf XPPλλλλ+=⇒∇+=⇒求得()()()(1)()()0()0.k k T k k T k k f X P P f X P λ+⇒∇+=⇒∇=即有 (1)()().k k f XP +∇⊥常用终止准则: (i) 两次迭代绝对误差可行域内: (1)()1k k XXε+-<函数值域: (1)()2(()k k f Xf Xε+-<(ii) 两次迭代相对误差可行域内: (1)()3()k k k XXX ε+-<函数值域:(1)()4()(()()k k k f Xf Xf X ε+-<分母不零或不接近零. (iii) 梯度模小()5()k f Xε∇<→梯度向量短→局部曲面平缓. 多用(i).好算法标准： ()k X X 准、快最优解*⇒α阶收敛：(1)()()() k k XXXXαβ若+**-≤-,其中00,1,k k βα>≥>某正整数.1x 2x ()f X 1f x ∂∂2f x ∂∂()()k f X ∇当1,01αβ=<<且时, 称为线性收敛; 当12α<<时, 称为超线性收敛; 当2α=时, 称为二阶收敛; 当1α>时, 都称为好算法. 关于步长的补充()()i) =0.1;ii), ;iii):min ().k k k k k f X P λλλ固定小步长,如等大小可变下降即可,称可接受算法最佳步长,⎧⎪⎨⎪+⎩作业:试判定下述非线性规划是否为凸规划: (a) 12max ()2,f X x x =+221229.0x x st x ⎧+≤⎨≥⎩ (b) 222123min ()2f X x x x =++ 2212131230.510,,0x x st x x x x x ⎧+≤⎪+=⎨⎪≥⎩。