04 第四章 非线性数规划.pptx

第1页：第四章非线性规划与例1

第四章 非线性规划 Nonlinear Programming　§1 问题的提出　[eg.1] 某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过 80 米。为使建筑面积最大，应如何选择长宽尺寸？

分析：设长为 x1 米、宽为 x2 米，则目标函数 f(x) 为非线性函数（面积与长宽尺寸相关），约束条件为围墙与隔墙总长 ≤ 80。

第2页：例2曲线拟合参数估计

例2　设某物理过程具有如下规律，现要确定参数，用试验法使所得试验点构成的曲线与理论曲线的误差平方和为最小，且满足给定的约束条件。

本页公式以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对模型表达式。

第3页：非线性规划的定义

非线性规划：目标函数或（和）约束条件为非线性函数的规划。

分析：本例中 f(x) 为非线性函数，求其最小值。

第4页：§2基本概念与数学模型

§2 基本概念　2.1 非线性规划的数学模型　数学模型的一般描述见本页图示（目标函数与约束条件中允许出现非线性函数）。

第5页：数学模型的另一种形式

非线性规划模型的另一种等价写法：目标函数取 min f(x)，约束条件写为 g_i(x) ≥ 0（i = 1,…,m）与 h_j(x) = 0（j = 1,…,l）的形式。

本页为公式页，源文件文字提取较少，建议对照原课件图片核对。

第6页：非线性规划的图解法

2.2 非线性规划的图示　例1　求解如下非线性规划问题（图中坐标范围为 o 到 6，可行域与目标函数等值线如图）。

本页公式与图形以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对。

第7页：最优解位置的说明

分析：非线性规划的最优解可能在可行域的任一点达到，而不一定出现在可行域的顶点上，这与线性规划有本质区别。

第8页：极值存在的条件

2.3 极值问题　极值存在的条件：本页为标题页，一阶必要条件与二阶充分条件的完整表述见后续页。

第9页：一元函数的极值条件

本页为极值条件的推导页，源文件仅提取到页码等少量文字。内容为一元函数取极值的必要条件（一阶导数为零）与充分条件（二阶导数符号），建议对照原课件图片核对公式。

第10页：多元函数的极值条件

本页为极值条件的推导页，源文件仅提取到页码等少量文字。内容为多元函数取极值的必要条件 ∇f(x) = 0，建议对照原课件图片核对公式。

第11页：二阶条件与海赛矩阵

本页为极值条件的推导页，源文件仅提取到页码等少量文字。内容为用海赛矩阵（Hesse 矩阵）的正定、负定判别极小点与极大点，建议对照原课件图片核对公式。

第12页：极值条件例题推导

本页为极值条件的例题推导页，源文件仅提取到页码等少量文字。内容为代入具体函数求驻点并判别极值类型，建议对照原课件图片核对。

第13页：极值问题收尾页

本页为极值问题小节的收尾页，源文件仅提取到页码等少量文字，正文内容以图片形式呈现，建议对照原课件图片补充本页要点。

第14页：2.4凸函数与凸规划

2.4 凸函数与凸规划　1、凸函数与凹函数：设 f(x) 定义在凸集上，若对任意 x(1)、x(2) 与 0 < α < 1 都有 f(αx(1) + (1 − α)x(2)) ≤ αf(x(1)) + (1 − α)f(x(2))，则称 f(x) 为凸函数；不等号反向时为凹函数。

源文件本页标题写作「凸函熟与凹函熟」，按学科规范用词修正为「凸函数与凹函数」，特此说明。

第15页：函数f(x)曲线图

函数 f(x) 图示：本页用曲线图对比凸函数与凹函数的形状特征（凸函数曲线位于任意两点连线的下方，凹函数反之）。

第16页：凸性的判别

2、凸性的判别：可用一阶判别条件（梯度单调性）与二阶判别条件（海赛矩阵半正定）判断函数的凸性，具体条件见本页图示。

第17页：例3判别函数凸性

例3　用凸性判别条件判断所给函数的凸性（演算过程以图片形式呈现）。源文件文字提取较少，建议对照原课件图片核对。

第18页：凸规划的定义

3、凸函数的极值　对于定义在凸集上的凸函数，其极小点就是最小点，极小值就是最小值。

4、凸规划　下述问题为凸规划：可行域为凸集，且目标函数为凸函数（求极小）或凹函数（求极大）。

第19页：凸规划的性质

凸规划的局部最优解为全局最优解；当凸规划的目标函数为严格凸函数时，若存在最优解，则最优解必定唯一。

凸规划是一类比较简单而又具有重要理论意义的非线性规划。

第20页：判断凸规划的例题

例　如下非线性规划是否为凸规划？（本页给出待判定的模型，目标函数与约束条件以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对。）

第21页：海赛矩阵判定凸规划

计算目标函数的海赛矩阵，由海赛矩阵正定（或半正定）可知目标函数为凸函数，可行域亦为凸集，所以该问题为凸规划。

第22页：最优解在C点取得

如图所示，该问题的最优解（最小点）在 C 点取得。

第23页：下降迭代算法

5、下降迭代算法　从初始点出发，每一步沿使目标函数下降的方向搜索并确定步长，得到新的迭代点，如此重复直至满足终止准则。算法要素包括：搜索方向、步长与终止准则。

第24页：终止迭代的准则

几种终止迭代的准则：

• 梯度模长 ||∇f(x^(k))|| < ε；
• 相邻迭代点距离 ||x^(k+1) − x^(k)|| < ε；
• 目标函数值下降量 |f(x^(k+1)) − f(x^(k))| < ε。

本页准则以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对。

第25页：§3无约束非线性规划的解法

§3 无约束非线性规划的解法　无约束非线性规划的数学描述：min f(x)，x ∈ En。

解法分类：

解析法

利用函数的解析性质（一阶、二阶导数），如梯度法、共轭梯度法、变尺度法等。

直接法

只利用问题的函数值，如步长加速法等。

第26页：梯度法的基本原理

梯度法　1. 基本原理：函数沿负梯度方向下降最快，故取搜索方向 d^(k) = −∇f(x^(k))。

第27页：梯度法的步长条件

对于充分小的步长 λ > 0，有 f(x^(k) + λd^(k)) < f(x^(k))，即沿负梯度方向取足够小的步长必能使目标函数下降。

本页为公式推导页，源文件文字提取较少，建议对照原课件图片核对。

第28页：梯度法的求解步骤

2、求解步骤　（1）选定初始点 x⁽⁰⁾ 与精度 ε，计算梯度 ∇f(x⁽⁰⁾)，取搜索方向为负梯度方向。

第29页：梯度法的迭代过程

其中步长由一维搜索（或最优步长）确定，由此得到下一次迭代点 x^(k+1) = x^(k) + λ_kd^(k)，重复迭代，直至满足精度为止。

第30页：梯度法算例

例　用梯度法求解所给的无约束极小化问题（初始点与函数表达式以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对）。

第31页：寻找下一个迭代点

由当前点出发，沿负梯度方向作一维搜索，找下一点 x⁽¹⁾（计算过程以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对）。

第32页：算例的迭代结果

于是得到迭代后的点与相应的目标函数值（数值以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对）。

第33页：梯度法的几何分析

几何分析　D(1,1)：对于等值线为圆的无约束极小化问题，不管初始点选在哪里，只要一次迭代即可求得最优解。

第34页：§4有约束的非线性规划

§4 有约束的非线性规划　有约束非线性规划数学描述：min f(x)，约束 g_i(x) ≥ 0（i = 1,…,m），h_j(x) = 0（j = 1,…,l）。

第35页：4.1库恩-塔克条件

4.1 库恩-塔克（Kuhn-Tucker）条件　1. 几何说明：在最优解处，目标函数的负梯度落在起作用约束梯度的非负线性组合锥内。

第36页：K-T条件的梯度关系

对于起作用约束，存在乘子使 ∇f(x*) = Σ λ_i∇g_i(x*)，且 λ_i ≥ 0。

本页为公式推导页，源文件文字提取较少，建议对照原课件图片核对。

第37页：K-T条件的表述

2. 库恩-塔克（Kuhn-Tucker）条件　设 x* 为最优解，则存在乘子 λ_i、μ_j，使梯度条件、可行性条件、互补松弛条件 λ_ig_i(x*) = 0 与 λ_i ≥ 0 同时成立。

第38页：K-T条件各式的说明

式中：λ_i 对应不等式约束的乘子（非负），μ_j 对应等式约束的乘子（无非负限制），互补松弛条件表示不起作用约束对应的乘子为零。

本页为公式说明页，源文件文字提取较少，建议对照原课件图片核对。

第39页：用K-T条件求解的例题

例　用 K-T 条件求解如下非线性规划（模型以图片形式呈现，源文件文字提取有限，建议对照原课件图片核对）。

第40页：引入乘子构造拉格朗日函数

引入乘子 λ₁、λ₂ 等，构造拉格朗日函数 L(x, λ) = f(x) − Σ λ_ig_i(x)，并写出 K-T 条件方程组。

本页为公式推导页，源文件文字提取较少，建议对照原课件图片核对。

第41页：例题的分情形讨论

讨论：按乘子是否为零分情形讨论（λ > 0 表示约束起作用，λ = 0 表示约束不起作用），逐一求解并检验互补松弛条件，确定最优解。

本页为求解过程页，源文件文字提取较少，建议对照原课件图片核对。

第42页：4.2二次规划

4.2 二次规划　二次规划的数学描述：目标函数为 x 的二次函数（含对称矩阵 H 与向量 c），约束条件为线性不等式与等式。

第43页：二次规划的K-T条件

1. 二次规划的 K-T 条件　求相应问题的梯度：∇f(x) = Hx + c，约束梯度为系数矩阵的行向量，据此写出 K-T 条件。

第44页：引入拉格朗日乘子

引入拉格朗日乘子 λ、μ，把 K-T 条件中的梯度方程与互补松弛条件联立，转化为可用线性规划或线性互补方法求解的形式。

第45页：转化为线性规划的描述

2. 线性规划描述　引入松弛变量及人工变量，把二次规划的 K-T 条件改写为等价的线性规划问题。

第46页：选取初始基变量

取人工变量为初始基变量，建立初始单纯形表，并对互补条件作相应限制（同组变量不同时入基）。

本页为推导页，源文件文字提取较少，建议对照原课件图片核对。

第47页：转化得到的线性规划问题

于是得到相应的线性规划问题：其最优解满足互补松弛条件，即为原二次规划 K-T 条件的解，从而得到二次规划的最优解。

第48页：二次规划求解收尾

以所得线性规划的最优表为基础，回代得到原二次规划的最优解与最优值。

本页为收尾页，源文件文字提取较少，建议对照原课件图片核对。

第49页：第四章收尾页

本页为第四章的收尾页，源文件仅提取到页码等少量文字，正文内容以图片形式呈现，建议对照原课件图片补充本页要点。