非线性规划-优化模型

数学建模第二讲简单的优化模型数学建模是利用数学方法对实际问题进行建模、分析和求解的过程。

在实际问题中，常常需要针对一些指标进行优化，以达到最优的效果。

本讲将介绍一些简单的优化模型。

一、线性规划模型线性规划是一种重要的数学优化方法，广泛应用于工程、经济、管理等领域。

其数学模型可以表示为：\begin{aligned}&\text{max} \quad c^Tx \\&\text{s.t.} \quad Ax \leq b, \quad x \geq 0\end{aligned}\]其中，$x$为决策变量，$c$为目标函数系数，$A$为约束条件系数矩阵，$b$为约束条件右端向量。

线性规划模型指的是目标函数和约束条件都是线性的情况。

通过线性规划模型，可以求解出使得目标函数取得最大（或最小）值时的决策变量取值。

二、非线性规划模型非线性规划模型指的是目标函数或约束条件中存在非线性部分的情况。

非线性规划模型相对于线性规划模型更为复杂，但在实际问题中更为常见。

对于非线性规划问题，通常采用数值优化方法进行求解，如梯度下降法、牛顿法等。

这些方法通过迭代的方式逐步靠近最优解。

三、整数规划模型整数规划模型是指决策变量必须为整数的规划模型。

整数规划在实际问题中应用广泛，如物流配送问题、工程调度问题等。

整数规划模型通常难以求解，因为整数规划问题是一个NP难问题。

针对整数规划问题，常用的求解方法有枚举法、分支定界法、遗传算法等。

四、动态规划模型动态规划模型是指将问题划分为子问题，并通过求解子问题最优解来求解原问题最优解的方法。

动态规划通常用于求解具有重叠子问题和最优子结构性质的问题。

动态规划模型具有递推性质，通过递归或迭代的方式求解子问题的最优解，并保存中间结果，以提高求解效率。

五、模拟退火模型模拟退火是一种用来求解组合优化问题的随机优化算法。

模拟退火算法基于固体退火过程的模拟，通过温度的控制和随机跳出来避免陷入局部最优解。

运筹学模型的类型运筹学模型是指通过数学方法来描述和解决复杂问题的一种工具。

根据问题的性质和要求，运筹学模型可以分为以下几种类型：1. 线性规划模型（Linear Programming Model，简称LP）：线性规划是一种优化问题，它的目标是在满足一些约束条件下，使某个线性函数取得最大或最小值。

线性规划模型广泛应用于生产调度、资源分配、物流运输等领域。

2. 整数规划模型（Integer Programming Model，简称IP）：整数规划是线性规划的扩展，它要求决策变量只能取整数值。

整数规划模型常用于生产调度、排产计划、网络设计等问题。

3. 非线性规划模型（Nonlinear Programming Model，简称NLP）：非线性规划是一种优化问题，它的目标函数和约束条件都可以是非线性的。

非线性规划模型广泛应用于经济学、金融学、工程学等领域。

4. 动态规划模型（Dynamic Programming Model，简称DP）：动态规划是一种优化方法，它将一个复杂问题分解为若干个子问题，并逐步求解这些子问题。

动态规划模型常用于生产调度、资源分配、投资决策等问题。

5. 排队论模型（Queuing Theory Model，简称QT）：排队论是一种研究等待线性的数学理论，它可以用来描述和分析顾客到达、服务时间、系统容量等因素对系统性能的影响。

排队论模型广泛应用于交通运输、通信网络、医疗卫生等领域。

6. 决策树模型（Decision Tree Model，简称DT）：决策树是一种分类和回归的方法，它可以将一个问题分解为若干个子问题，并逐步求解这些子问题。

决策树模型常用于金融风险评估、医学诊断、市场营销等领域。

总之，不同类型的运筹学模型适用于不同的问题领域和求解目标，选择合适的模型可以帮助我们更好地解决实际问题。

四类基本模型1 优化模型1.1 数学规划模型线性规划、整数线性规划、非线性规划、多目标规划、动态规划。

1.2 微分方程组模型阻滞增长模型、SARS 传播模型。

1.3 图论与网络优化问题最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。

1.4 概率模型决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。

1.5 组合优化经典问题● 多维背包问题(MKP)背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。

如何将尽可能多的物品装入背包。

多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。

如何选取物品装入背包，是背包中物品的总价值最大。

多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。

该问题属于NP 难问题。

● 二维指派问题(QAP)工作指派问题：n 个工作可以由n 个工人分别完成。

工人i 完成工作j 的时间为ij d 。

如何安排使总工作时间最小。

二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。

二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。

● 旅行商问题(TSP)旅行商问题：有n 个城市，城市i 与j 之间的距离为ij d ，找一条经过n 个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。

● 车辆路径问题(VRP)车辆路径问题（也称车辆计划）：已知n 个客户的位置坐标和货物需求，在可供使用车辆数量及运载能力条件的约束下，每辆车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆数、最小的车辆总行程完成货物的派送任务。

TSP 问题是VRP 问题的特例。

● 车间作业调度问题(JSP)车间调度问题：存在j 个工作和m 台机器，每个工作由一系列操作组成，操作的执行次序遵循严格的串行顺序，在特定的时间每个操作需要一台特定的机器完成，每台机器在同一时刻不能同时完成不同的工作，同一时刻同一工作的各个操作不能并发执行。

非线性规划什么是非线性规划？非线性规划（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. 分类方法分类方法是一种将非线性规划问题分解为若干个子问题求解的方法。

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

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

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

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

非线性规划问题的数学算法设计与优化引言：非线性规划是数学优化领域中的一个重要分支，它研究的是在约束条件下寻找目标函数的最优解。

与线性规划相比，非线性规划问题更加复杂，因为它涉及到非线性函数的优化。

为了解决这类问题，数学家们提出了许多有效的算法，并不断进行改进和优化。

本文将介绍几种常见的非线性规划算法，并探讨它们的优化方法。

一、梯度下降法梯度下降法是一种常用的非线性规划算法，它通过迭代的方式逐步优化目标函数。

该算法的基本思想是沿着目标函数的负梯度方向进行搜索，直到找到最优解为止。

梯度下降法的优化过程可以分为两个步骤：计算目标函数的梯度和更新参数。

在计算梯度时，可以使用数值方法或者解析方法，具体选择取决于问题的复杂程度和计算效率的要求。

在更新参数时，可以采用固定步长或者自适应步长的方式，以控制搜索的速度和精度。

二、牛顿法牛顿法是一种经典的非线性规划算法，它利用目标函数的二阶导数信息进行搜索。

该算法的核心思想是通过构造二次逼近模型来近似目标函数，并求解该模型的最优解。

牛顿法的优化过程可以分为三个步骤：计算目标函数的一阶导数、二阶导数和更新参数。

在计算导数时，可以使用数值方法或者解析方法，具体选择取决于问题的复杂程度和计算效率的要求。

在更新参数时，可以采用精确求解或者近似求解的方式，以控制搜索的速度和精度。

三、拟牛顿法拟牛顿法是一种改进的非线性规划算法，它通过构造目标函数的拟牛顿方程来近似目标函数的二阶导数。

该算法的基本思想是利用历史搜索信息来更新参数，并通过迭代的方式逐步优化目标函数。

拟牛顿法的优化过程可以分为四个步骤：计算目标函数的一阶导数、构造拟牛顿方程、求解拟牛顿方程和更新参数。

在构造拟牛顿方程时，可以使用不同的方法，例如DFP方法、BFGS方法等，以逼近目标函数的二阶导数。

在求解拟牛顿方程时，可以采用精确求解或者近似求解的方式，以控制搜索的速度和精度。

四、全局优化方法除了上述的局部优化方法，全局优化方法也是解决非线性规划问题的一种重要途径。

数学建模模型常用的四大模型及对应算法原理总结四大模型对应算法原理及案例使用教程：一、优化模型线性规划线性回归是利用数理统计中回归分析，来确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法，在线性回归分析中，只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。

如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。

案例实操非线性规划如果目标函数或者约束条件中至少有一个是非线性函数时的最优化问题叫非线性规划问题，是求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。

建立非线性规划模型首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系，即目标函数。

然后将各种限制条件加以抽象，得出决策变量应满足的一些等式或不等式，即约束条件。

整数规划整数规划分为两类：一类为纯整数规划，记为PIP，它要求问题中的全部变量都取整数；另一类是混合整数规划，记之为MIP，它的某些变量只能取整数，而其他变量则为连续变量。

整数规划的特殊情况是0-1规划，其变量只取0或者1。

多目标规划求解多目标规划的方法大体上有以下几种：一种是化多为少的方法，即把多目标化为比较容易求解的单目标，如主要目标法、线性加权法、理想点法等；另一种叫分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。

目标规划目标规划是一种用来进行含有单目标和多目标的决策分析的数学规划方法，是线性规划的特殊类型。

目标规划的一般模型如下：设xj是目标规划的决策变量，共有m个约束条件是刚性约束，可能是等式约束，也可能是不等式约束。

设有l个柔性目标约束条件，其目标规划约束的偏差为d+, d-。

设有q个优先级别，分别为P1, P2, …, Pq。

在同一个优先级Pk中，有不同的权重，分别记为[插图], [插图]（j=1,2, …, l）。

数学模型的优化方法数学模型是指用数学表达语言对实际问题进行抽象和描述的工具。

通过数学模型，我们可以对问题进行量化分析，提出合理的决策和解决方案。

然而，在实际应用中，数学模型常常存在着复杂的约束条件和多个决策变量，因此需要采用优化方法对数学模型进行求解，以得到最优的决策结果。

本文将介绍几种常见的数学模型的优化方法。

I. 线性规划线性规划是一种常见的数学模型优化方法，适用于目标函数和约束条件均为线性的情况。

线性规划试图寻找一个线性模型，使目标函数达到最大或最小值。

线性规划问题可以表达为以下形式：$\max\limits_{x}\ \mathbf{c}^T\mathbf{x}$$s.t.$$\begin{align*}\mathbf{A}\mathbf{x} & \leq \mathbf{b} \\\mathbf{x} & \geq \mathbf{0}\end{align*}$其中，$\mathbf{c}$为目标函数的系数向量，$\mathbf{A}$为约束条件的系数矩阵，$\mathbf{b}$为约束条件的右侧常数向量，$\mathbf{x}$为决策变量向量。

II. 非线性规划非线性规划是一类目标函数和约束条件均为非线性的优化问题。

非线性规划相比线性规划更具挑战性，但在实际中有广泛应用。

非线性规划问题可以表达为以下形式：$\max\limits_{x}\ f(\mathbf{x})$$s.t.$$\begin{align*}g_{i}(\mathbf{x})&\leq 0, \ i = 1,2,\ldots,m \\h_{j}(\mathbf{x})&= 0, \ j = 1,2,\ldots,p\end{align*}$其中，$f(\mathbf{x})$为目标函数，$g_{i}(\mathbf{x})$为不等式约束条件，$h_{j}(\mathbf{x})$为等式约束条件，$\mathbf{x}$为决策变量向量。

非线性规划非线性规划(Nonlinear Programming ，简记为NP)研究的对象是非线性函数的数值最优化问题，是运筹学的最重要分支之一，20世纪50年代形成一门学科，其理论和应用发展十分迅猛，随着计算机的发展，非线性规划应用越来越广泛，针对不同的问题提出了特别的算法，到目前为止还没有适合于各种非线性规划问题的一般算法，有待人们进一步研究.§1 非线性规划基本概念一、引例例7.1 一容器由圆锥面和圆柱面围成. 表面积为S ，圆锥部分高为h ，h 和圆柱部分高2x 之比为a ,1x 为圆柱底圆半径.求21,x x 使面积最大.解： 由条件 a x h =2/22121231x x x ax V ππ+=21212222112221x x x x a x x S πππ+++⋅⋅=所以，数学模型为：212)311(max x x a V π+=s.t. S x x x x a x x =+++21212222112πππ0,21≥x x例7.2 某高校学生食堂用餐，拟购三种食品，馒头0.3元/个，肉丸子1元/个，青菜0.6/碗.该学生的一顿饭支出不能够超过5元.问如何花费达到最满意？解： 设该学生买入馒头，肉丸子，青菜的数量分别为321,,x x x ； 个人的满意度函数即为效用函数为321321321),,(aaax x Ax x x x u =.于是数学模型为321321321),,(max aaax x Ax x x x u =s.t.56.03.0321≤++x x x 321,,x x x 为非负整数二、数学模型称如下形式的数学模型为数学规划（Mathematical Programming 简称MP ） )(min x f z = （7.1） （MP ） t s . 0)(≥x g i m i ,,1 = （7.2） 0)(=x h j l j ,,1 = （7.3）其中Tn x x x x ),,,(21 =是n 维欧几里得空间nR 中的向量（点），)(x f 为目标函数，0)(,0)(=≥x h x g j i 为约束条件.称满足约束条件的向量x 为（MP ）问题的一个可行解，全体可行点组成的集合称为可行域.K ={}l j x h mi x g R x j i n,,2,10)(,,2,10)( ===≤∈如果)(),(),(x h x g x f j i 均为线性函数，就是前面所学的线性规划问题(LP).如果至少有一个为非线性函数称为非线性规划问题.由于等式约束0)(=x h j 等价于下列两个不等式约束 0)(,0)(≥-≥x h x h j j 所以(MP)问题又可表示为 )(min x f z =s.t. 0)(≥x g i m i ,,1 = （7.4） 三、数学基础 1、线性代数知识考虑二次型Az z T ，z 为n 维向量正定的二次型：若对于任意0≠z ，有0>Az z T； 半正定的二次型：若对于任意0≠z ，有0≥Az z T ； 负定的二次型：若对于任意0≠z ，有0<Az z T ； 半负定的二次型：若对于任意0≠z ，有0≤Az z T ；不定二次型：0≠∃z ，有0>Az z T，又0≠∃z ，有0<Az z T.二次型Az z T 为正定的充要条件是它的矩阵A 的左上角各阶主子式都大于零. 二次型Az z T 为负定的充要条件是它的矩阵A 的左上角各阶主子式负正相间.2、分析数学知识（1）方向导数和梯度(二维为例)考虑函数),(21x x f Z =，及方向j i lϕϕsin cos +=梯度：Tx f x f j x f i x f x x f ),(),(212121∂∂∂∂=∂∂+∂∂=∇ ； 方向导数：⎪⎪⎭⎫⎝⎛∂∂∂∂=∂∂+∂∂=∂∂ϕϕϕϕsin cos ),(sin cos 2121x f x f x f x f l f )),,(cos(||),(||),(),(21212121l x x gardf x x gardf lx x gardf lx x f T=⋅=⋅∇=考虑等值线00201),(c x x f =上一点),(0201x x 梯度方向 ),(0201x x gardf 即为法线方向n.如果)(x f 二次可微，称⎪⎪⎪⎪⎪⎭⎫⎝⎛=)()()()()()()()()()(212222111211x h x h x h x h x h x h x h x h x h x H nn n n n n为)(x f 在点 x 处的Hesse 矩阵.（2）多元函数泰勒公式：若)(,),(0x f R S x x f u n⊆∈=在点0x 处的某个领域具有二阶连续偏导数，则有x x x f x x x f x f x x f T T∆∆+∇∆+∆∇+=∆+)(21)()()(02000θ 10≤≤θ )||(||)(21)()(||)(||)()(2020000x x x f x x x f x f x x x f x f T TT ∆+∆∇∆+∆∇+=∆+∆∇+=οο 四、最优解的类型定义7.1 (MP)问题的一个可行点*x 被称为整体极小点，如果对于任意的可行点K x ∈，都有不等式)()(*x f x f ≥成立.如果对于任意可行点*,x x K x ≠∈均有)()(*x f x f >，称点*x 是)(x f 的可行解集K上的严格整体极小点.定义7.2 问题(MP)的一个可行点*x 被称为一个局部极小点，如果存在一个正数ε使得对于所有满足关系式ε<-*x x 的可行点x 都有)()(*≥x f x f 成立.如果对任意的可行点K x ∈，*≠x x ，存在一个正数ε使得对于所有满足关系式ε<-*x x 的可行点x 都有)()(*>x f x f 成立.则称*x 是)(x f 在K 上的一个局部严格极小点.显然整体极小点一定是局部极小点，反之不然. 五、凸规划定义7.3 集合K 被称为nR 中的一个凸集，如果对于K 中任意两点21,x x 和任一实数]1,0[∈λ，点K x x ∈-+21)1(λλ.几何解释：当一个集合是凸集时，连接此集合中任意两点的线段也一定包含在此集合内，规定φ空集是凸集.定义7.4 凸函数：)(x f 是凸集K 上的实值函数，如果对于K 中任意两点21,x x 和任意实数]1,0[∈λ有不等式)()1()())1((2121x f x f x x f λλλλ-+≤-+成立.严格凸函数：)(x f 是凸集K 上的实值函数，如果对于K 中任意两点21,x x ，21x x ≠和任意实数)1,0(∈λ，有不等式)()1()())1((2121x f x f x x f λλλλ-+<-+成立.定义7.5 )(x f 是定义在凸集K 上的实值函数，如果)(x f -是K 上凸函数，称)(x f 是凹函数.定理7.1 设)(x f 是凸集K 上的凸函数，则)(x f 在K 中的任一局部极小点都是它的整体极小点.证明： 设*x 是一局部极小点而非整体极小点，则必存在可行点K x ∈(可行域))()(*x f x f <∍.对任一]1,0[∈λ，由于)(x f 的凸性，有 )()()1()())1((***x f x f x f x x f ≤-+≤-+λλλλ当0→λ时，*)1(x x λλ-+与*x 充分接近，与*x 是局部极小矛盾. 证毕. 定义7.6 设有(MP)问题)(min x f kx ∈，若可行域K 是凸集，)(x f 是K 上的凸函数，则称此规划问题为凸规划.定理7.2 凸规划的任一局部极小解为整体极小解. 六、非线性规划问题的求解方法 考虑(MP)问题：lj x h m i x g t s x f j i ,,10)(,,10)(.)(min ===≥ （7.5） 一般来说，MP 问题难以求得整体极小点，只能求得局部极小点.以后我们说求(MP)问题，指的是求局部极小点.1、无约束极小化问题（UMP ） )(min x f nRx ∈ （7.6） 这里)(x f 是定义在n R 上的一个实值函数定理7.3（一阶必要条件）如果)(x f 是可微函数.*x 是上述无约束问题（UMP ）的一个局部极小点或局部极大点的必要条件是：0)(*=∇x f .满足0)(=∇x f 的点称为平稳点或驻点.定理7.4 设)(x f 为定义在n R 上的二阶连续可微函数，如果*x 是)(x f 的一个局部极小点，必有nT Ry y x H y x f ∈∀≥=∇0)(0)(**这里)(*x H 表示)(x f 在*x 处的Hesse 矩阵.证明：nE y ∈∀，根据)(x f 在点*x 处的展开式有)()(21)()(2*2**λολλ++=+y x H y x f y x f T)0)((*=∇x f若0)(,*<∍∈∃y x H y R y T n ，当λ充分小时，有 )()(21|2*2λολ>y x H y T∴有)()(**x f y x f <+λ.这和*x 是)(x f 的极小矛盾.定理7.5 设)(x f 是定义在nR 上的二阶连续可微函数，如果点*x 满足0)(*=∇x f ，而且存在*x 的一个邻域0)(),(,),(*≥∈∀∈∀∍*y x H y x x R y x T n 有 ，则*x 是)(x f 的一个局部极小点.在高等数学中求解极值点方法先求出满足0)(=∇x f 的点及不可导点.在这些点判断)(x f 是否取得极小值.2、等式约束的极小化问题考虑 )(min x fl j x h t s j ,,10)(. == （7.7）定义7.7 如果)(,),(),(21x h x h x h l ∇∇∇ 在点x 处线性无关，则称点x 是此约束条件的一个正则点.Langrange 乘子法：引进拉格朗日函数 ∑=-=lj jj x h u x f u x L 1)()(),(其中Tl u u u u ),,,(21 =被称为拉格朗日乘子向量.定理7.6 设l j x h x f j ,,1),(),( =是连续可微函数，*x 是)(x f 在可行集中的一个局 部极小点.在*x 是正则点的假定下必存在一个拉格朗日乘子向量u ，使得),(*u x 满足方程组)(0)()(*1**==∇-∇∑=x h x h u x f lj j j对等式约束，用拉格朗日乘子法求解出平稳点，判断是否极值点.用上述解析法求解无约束和等式约束极值问题的平稳点，再判断是否为极值点.该方法有一定的局限性：（1）它们要求函数是连续的，可微的，实际问题中不一定满足这一条件； （2）上述求平稳点的方程组求解比较困难，有些解不出来； （3）实际问题中有大量的不等式约束.因此求解非线性规划应有更好的新方法.实际应用中一般用迭代法来求解非线性规划问题，即求近似最优解的方法.3、非线性规划问题的求解方法—迭代法迭代法一般过程为：在(MP)问题的可行域K 内选择初始点0:,0=k x ，确定某一方向k p ，使目标函数)(x f 从k x 出发，沿k p 方向使目标函数值下降，即)0(,>∈+=λλK p x x k ，有)()(0x f x f <，进一步确定kλ，使)(m i n )(0k k k k k p x f p x f λλλ+=+>，令k k k k p x x λ+=+1.如果1+k x 已满足某终止条件，1+k x 为近似最优解.否则，从1+k x 出发找一个方向1+k p ，确定步长1+k λ，使K p x x k k k k ∈+=++++1112λ，有)(min )(1102++>++=k k k p x f x f λλ.如此继续，将得到点列{}kx .显然有 >>>>)()()(1kx f x f x f ,即点列{}kx 相对应的目标函数是一个单调下降的数列.当{}kx 是有穷点列时，希望最后一个点是(MP)问题的某种意义下的最优解.当{}kx 为无穷点列时，它有极限点，其极限点是(MP)的某种意义下的最优解（此时称该方法是收敛的）.迭代法求解(MP)的注意点：该方法构造的点列{}kx ，其极限点应是近似最优解，即该算法必须是收敛的.迭代法一般步骤：①. 选取初始点0x ，0:=k ②. 构造搜索方向kp ③. 根据kp 方向确定k λ ④. 令k k k k p x xλ+=+1⑤. 若1+k x已满足某终止条件，停止迭代，输出近似最优解1+k x.否则令1:+=k k ，转向第②步.计算终止条件在上述迭代中有：若1+k x满足某终止条件则停止计算，输出近似最优解1+k x.这里满足某终止条件即到达某精确度要求.常用的计算终止条件有以下几个：（1）自变量的改变量充分小时，11||||ε<-+k k x x，或21||||||||ε<-+kk k x x x ，停止计算. （2）当函数值的下降量充分小时，31)()(ε<-+k kx f x f ，或41|)(|)()(ε<-+k k k x f x f x f ， 停止计算.（3）在无约束最优化中，当函数梯度的模充分小时51||)(||ε<∇+k x f ，停止计算.迭代法的关键：① 如何构造每一轮的搜索方向kp ② 确定步长k λ关于k λ，前面是以)(min kk p x f λλ+产生的，也有些算法k λ取为一个固定值，这要根据具体问题来确定.关于kp 的选择，在无约束极值问题中只要是使目标函数值下降的方向就可以了，对于约束极值问题则必需为可行下降方向.定义7.8 设0,,:1≠∈→p R x R R f nn，若存在0>δ使),0(δλ∈∀，)()(x f p x f <+λ则称向量p 是函数)(x f 在点x 处的下降方向.定义7.9 设0,,,≠∈∈∈p R p K x R K nn，若存在0>λ使得K p x ∈+λ，称向量p 是点x 处关于K 的可行方向. 若一个向量p 既是目标函数f 在点x 处的下降方向，又是该点处关于可行域K 的可行方向，则称p 为函数f 在点x 处关于区域K 的可行下降方向.根据不同原理产生了不同的kp 和k λ的选择方法，就产生了各种算法. 在以后的讨论中，一维极值的优化问题是讨论求解步长k λ.无约束极值中讨论的最速下降法，共轭方向法，坐标轮换法，牛顿法，变尺度法及有约束极值中讨论的可行方向法都是根据不同的原理选择kp 得到的迭代算法.七、迭代算法的收敛性定义7.10 设有一算法A ，若对任一初始点（可行点），通过A 进行迭代时，或在有限步后停止得到满足要求的点；或得到一个无穷点列，它的任何一个聚点均是满足要求的点，则称此算法A 具有全局收敛性.定义7.11 设（UMP ）问题的目标函数Px Qx x x f T+=21)(，Q 为对称半正定矩阵， 若由算法A 进行迭代时，不论初始点0x 如何选择，必能在有限步后停止迭代，得到所要求的点，则称此算法A 有二次有限终止性.定义7.12 设序列{}kr收敛于*r，定义满足∞<=--≤**+∞−→−βhkk k rr r r 1______lim0的非负数h 的上确界为{}k r 的收敛级.若序列的收敛级为h ，就称序列是h 级收敛的.若1=h 且1<β就称序列是以收敛比β线性收敛的. 若1>h 或1=h 且0=β就称序列是超线性收敛的. 如何判别算法的收敛性和收敛速度问题本书不讨论.本书给出的算法中，最速下降法具有全局收敛性、是线性收敛的；改进牛顿法具有全局收敛性、二次有限终止性、是二阶线性收敛的；变尺度法和共轭方向法具有全局收敛性和二次有限终止性、是超线性收敛的；Zoutenddijk 法不具有全局收敛性、改进的T-V 法具有全局收敛性；制约函数法具有全局收敛性.关于这些算法的收敛性的讨论和证明有兴趣的读者可参考其他文献.§2 一维极值问题的优化方法前面讨论迭代算法时,从kx 出发确定沿k p 方向的步长k λ是这样求解的),(min 0k k p x f λλ+>这里k x ,k p 已知.所以,若记)()(λλg p x f k k =+,则为求解)(min 0λλg >的过程.于是我们考虑如下形式的极值问题.)(min x f bx a ≤≤ (7.8)b a R x ,,1∈为任意实数很显然可应用高等数学中学过的解析法,即令0)('=x f 求出平稳点,但如前面所述如果该方程解不出来,怎么办?可用下述迭代算法—0.618法.定义7.13 )(x f 定义在],[b a 上,若存在点∍∈],[*b a x 当*x y x ≤<,有)()(y f x f >,当*x y x ≥>时,)()(y f x f >,称)(x f 在],[b a 中为单峰函数(单谷函数).显然满足定义要求的点*x 是)(x f 在],[b a 中的极小点.在],[b a 中任选两点21,x x ,且b x x a <<<21,根据)(x f 的单峰性,若)()(21x f x f <,则*x 必然位于],[2x a 内,如果)()(21x f x f >,则*x 必然位于],[1b x 内.如果)()(21x f x f =,则*x 必然位于],[21x x ,记此区间为],[11b a .如此继续,得闭区间套⊃⊃⊃⊃],[],[],[11n n b a b a b a .显然 ,1,0],,[*=∈i b a x i i ，又0→-i i a b .由闭区间套性质, *x 为极小值点.闭区间套的选择方法不同,求得的*x 的快慢及求解过程的计算量是不一样的，有一个常用的方法是0.618法.0.618法： 取],[],[b a =βα① 在],[βα中选取1λ和2λ,)(618.0),(382.021αβαλαβαλ-+=-+=,求出)(1λf 和)(2λf 进入②.② 若)()(21λλf f <,取],[],[2λαβα=,若αλ-2已足够小,停止,否则进入③.若)()(21λλf f >,取],[],[1βλβα=,若1λβ-已足够小,停止,否则进入④. 若)()(21λλf f =,取],[],[21λλβα=,若12λλ-已足够小,停止,否则进入①. ③ 取上一步中的1λ为2λ,显然有)(618.02αβαλ-+=,令)(382.01αβαλ-+=,求出)(1λf ,返回②.④ 取上一步的2λ为1λ,则有)(382.01αβαλ-+=,令)(618.02αβαλ-+=,求出)(2λf 返回②.设初始区间为],[b a ，用0.618法，经过k 次迭代后],[βα的长度ka b 618.1)(-=-αβ，只要k 充分大αβ-可以小于任何给定的正数.例7.3 用0.618法求解λλλ2)(min 2+=f单峰区间为[-3，5]，2.0=ε解：[α，β]=[-3，5]1λ=-3+0.382×8=0.056 )(1λf =0.1152λ=-3+0.618×8=1.944 )(2λf =7.667由于)(1λf <)(2λf 所以新的不定区间为[α，β] =[-3，1.944] 由于β-α=4.944>0.22λ:=1λ=0.056 )(2λf :=)(1λf =0.115 1λ=-3+0.382×4.944=-1.112 )(1λf =-0.987如此反复得下表7-1：在进行8次迭代后,2.0112.1936.0<+-=-αβ取中间值024.1*-=λ或032.12-=λ作为近似最优解.显然真正极小点是-1.0.一维收索方法很多，如函数逼近法、牛顿法等可参考其他文献.§3 无约束极值的优化方法考虑无约束最优化问题（UMP ）)(min x f nR x ∈ (7.9) 前面已经讨论过,求解此无约束优化问题,可以求出平稳点及不可导点的方法.令0)(*=∇x f ,求出平稳点.如果)(*2x f ∇是正定的,则*x 是UMP 的严格局部最优解.若)(x f 在n R 上是凸函数,则是整体最优解.在求解0)(*=∇x f 这n 维方程组比较困难时，就用最优化算法——迭代法.本节将介绍最速下降法,牛顿法,共轭方向法,坐标轮换法,变尺度法.这些算法就是用不同的方法来选择搜索方向k p 而得到的.当然kp 必须是下降方向.定理7.7 设R R f n→:，在点x 处可微,若存在nR p ∈,使0)(<∇p x f T,则向量p是f 在x 处的下降方向.证明:)(x f 可微(在x 处)，由泰勒展开式,有 ||)(||)()()(p p x f x f p x f Tλολλ+∇+=+ ,0,0)(><∇λp x f T0)(<∇∴p x f Tλ），（当δλδ0∈∃∴时,有0||)(||)(<+∇p p x f Tλολ),0()()(δλλ∈∀<+∴x f p x fp ∴是)(x f 在点x 的下降方向. 证毕.一、最速下降法最速下降法又称梯度法,选择负梯度方向作为目标函数值下降的方向,是比较古老的一种算法，其它的方法是它的变形或受它的启发而得到的，因此它是最优化方法的基础. 基本思想:迭代法求解无约束最优化(5.9)问题的关键是求下降方向kp .显然最容易想到的是使目标函数值下降速度最快的方向.从当前点kx 出发,什么方向是使)(x f 下降速度最快呢? 由泰勒展开知:||)(||)()()(k k T k k k k p p x f p x f x f λολλ+∇-=+-略去λ的高阶无穷小项,取)(kkx f p -∇=时,函数值下降最多.而)(kx f ∇为)(x f 在kx 处的梯度，所以下降方向kp 取为负梯度方向时,目标函数值下降最快.最速下降法:①. 取初始点0x ,允许误差0>ε,令0:=k ②. 计算)(kkx f p -∇=③. 若ε<||||k p ,停止，点k x 为近似最优解.否则进入④.④. 求 k λ,使)(min )(0kk k k k p x f p x f λλλ+=+≥ ⑤. 令kk k k p x xλ+=+1，1:+=k k ，返回②例7.4 用最速下降法求解下列无约束优化问题1222121225),(m in x x x x x f -+=取初始点Tx )2,2(0= 终止误差 610-=ε解：很显然，该问题的整体最优解为Tx )0,1(*=⎪⎪⎭⎫⎝⎛-=∇215022)(x x x f ，令0,10)(21==⇒=∇x x x f易验证)(*2x f ∇是正定的， ∴是整体最优解. 下面用最速下降法求解T T x x x f x f x f )50,22(),()(2121-=∂∂∂∂=∇ T x )2,2(0=T x f )100,2()(0=∇∴取Tp )100,2(0-=由⎪⎪⎭⎫⎝⎛--=⎪⎪⎭⎫ ⎝⎛--+⎪⎪⎭⎫ ⎝⎛=+λλλλ10022210022200p x4)22(2)1002(25)22()(2200+---+-=+λλλλp x f得0)1002(5000)22(4=----=λλλd df020007679.0500008100080==⇒λ⎪⎪⎭⎫⎝⎛-=⎪⎪⎭⎫ ⎝⎛--+⎪⎪⎭⎫ ⎝⎛=+=0007679.0959984642.11002020007679.0220001p x x λ重复上述过程得 Tx )01824717.0,009122542.1(2=789850288.0)(,078282.0)(,100)(21-=-==x f x f x f图7-1从图7-1可知，{}kx 随着迭代次数的增加，越来越接近与最优解)0,1(，同时也看到，随着迭代次数的增加，收敛速度越来越慢.极小点附近沿着一种锯齿形前进，即产生“拉锯”现象：{}kx沿相互正交的方向小步拐进，趋于最优解的过程非常缓慢.这种现象怎样解释？如何克服？在求k λ时，由于)()(kkp x f λλϕ+=，求导得0)('=λϕ，k λ是)(λϕ的极小点.故有0)()('=⋅+∇=k T k k k k p p x f λλϕ，即0)(=⋅+∇kk k k p p x f λ，又)(11++-∇=k k x f p，即0)(1=⋅+k T k p p 或0)()(1=∇⋅∇+k T k x f x f .也就是最速下降法相邻两个搜索方向是彼此正交的.因此最速下降法是局部下降最快，但不一定是整体下降最快的.在实际应用中一般开始几步用最速下降法，后来用下面介绍的牛顿法.这样两个算法结合起来，求解速度较快.二、牛顿法 基本思想：考虑无约束优化问题(5.9))(min x f nRx ∈ 由前面的讨论知，若能解出方程组0)(=∇x f ，求出平稳点*x ，则可验证*x 是否为极值点.由于0)(=∇x f 难以求解.如果)(x f 具有连续的二阶偏导数,则考虑用)(x f 在点*x 二阶泰勒展开式条件替代)(x f ∇，即由22||)(||))(()(21)()()()(k k k T k k T k k x x x x x f x x x x x f x f x f -+-∇-+-∇+=ο))(()(21)()()()()(2kk T k k T k k x x x f x x x x x f x f x g x f -∇-+-∇+=≈⇒令0))(()()()(2=-∇+∇=∇≈∇kk k x x x f x f x g x f)())((121k k k k x f x f x x ∇∇-=⇒-+即从kx 出发，搜索方向为)())((12kkkx f x f p ∇∇-=-，步长恒为1，得到下一个迭代点1+k x.牛顿法：①． 选取初始点0,0=：k x ，精度0>ε ②． 计算)(kx f ∇，如果ε≤∇||)(||kx f ，计算终止.否则计算)(2kx f ∇，求出搜索方向)())((12kk k x f x f p ∇∇-=-. ③． 令1:,1+=+=+k k p x x k k k ，返回②.例7.5 考虑无约束问题22122214)(m in x x x x x f -+=试分别取初始点（1）T x )1,1(0=，（2）T x )4,3(0=（3）Tx )0,2(0=，取精度要求310-=ε，用牛顿法求解.解：⎪⎪⎭⎫ ⎝⎛--=∇212211228)(x x x x x x f ⎪⎪⎭⎫⎝⎛---=∇22228)(1122x x x x f (1) 取Tx )1,1(0=有Tx f )1,6()(0=∇ ε>=∇0828.6||)(||0x f⎪⎪⎭⎫⎝⎛--=∇2226)(02x fT x f x f p )2500.2,7500.1()())((01020--=∇⋅∇-=-Tp x x )2500.1,7500.0(01--=+= 重复计算结果得表7-2.ε<=0||)(||4x f T x )0,0(4=∴为近似最优解.实际上，该问题最优解为**)0,0(=x(2) 取Tx )4,3(0=,同上计算,得TT x x x )4,8284.2(,)4,8333.2(),4,3(21===有ε<=∇=∇=∇0||)(||,1667.0||)(||,1||)(||210x f x f x f ，这一迭代结果收敛到)(x f 的鞍点T)4,22(.(3) 取Tx )0,2(0=T x f )4,16()(0-=∇ ⎪⎪⎭⎫⎝⎛--=∇2448)(02x f0)(02=∇x f , 即)(02x f ∇不可逆，所以无法求得点1x .牛顿法的主要缺点:（1） 该法的某次迭代反而使目标函数值增大(见上例).（2） 初始点0x 距极小点*x 较远时,产生的点列{}kx可能不收敛,还会出现)(*2x f ∇的奇异情况.（3） )(*2x f ∇的逆矩阵计算量大. 牛顿迭代法的主要优点:当目标函数)(x f 满足一定条件,初始点0x 充分接近极小点*x 时,由牛顿法产生的点列{}kx 不仅能够收敛到*x,而且收敛速度非常快.实际应用中常将最速下降法和牛顿法结合起来使用.牛顿法的改进:上面介绍的牛顿法中,kx 处的搜索方向为)())((12kkkx f x f p ∇∇-=-,步长恒为 1.若通过一维搜索来取最优步长k λ,可防止在迭代中步长恒为1时标目标函数值增大的可能. 改进的牛顿法:①. 取初始点nR x ∈0,允许误差0:,0=>k ε.②. 检验是否满足ε<∇||)(||kx f ,若是,迭代停止,得到k x 为近似最优解.否则进入③.③. 令)())((12kk k x f x f p ∇∇-=-.④. 求k λ,使)()(min kk k k k p x f p x f λλλ+=+. ⑤. 令k k k k p x x λ+=+1,令1+=k k ：转②.三、坐标轮换法既然求解非线性规划问题的迭代法是给出初始点0x ,求出一个方向kp ,根据kp 确定步长k λ,使k k k k p x xλ+=+1，如果1+k x 满足某精度要求则停止，否则继续找方向1+k p .显然构造出搜索方向有一定的困难，能否按既定的搜索方向寻找最优解,省去找搜索方向kp 呢?在最速下降法中我们看到相邻两个搜索方向kp 和1+k p是正交的.我们知道在n 维欧氏空间中坐标轴向量n εεε,,,21 是正交的，可否选坐标轴向量为搜索方向kp 为呢?回答是肯定的，这样我们得到了坐标轮换法.基本思想:从1x 出发,取11ε=p ,沿1p 进行一维搜索得到1112p x x λ+=.若2x 满足精度要求,则停止.否则取22ε=p ,2223p x x λ+=.如此继续,, 取n n n n n n p x x p λε+==+1,，若1+n x 满足精度要求,则停止.否则令11ε=+n p ,1112+++++=n n n n p x x λ,如此反复连续,可以求出近似最优解.坐标轮换法的缺点是收敛速度较慢,搜索效率较低,但基本思想简单,沿坐标轴的方向进行搜索.四、共轭方向法和共轭梯度法共轭方向法是一类方法的总称,它原来是为求解目标函数为二次函数的问题而设计的.这类方法的特点是:方法中的搜索方向是与二次函数的系数矩阵Q 有关的所谓共轭方向，用这类方法求解n 元二次函数的极小化问题最多进行n 次一维搜索便可以得到极小点.由于可微的非二次函数在极小点附近的性态近似于二次函数,因此这类方法也用于求可微的非二次函数的UMP 问题.定义7.14 设Q 为n n ⨯对称正定矩阵,如果0=Qy x T称n 维向量x 和y 关于Q 共轭.定义7.15 设k p p p ,,,21 为nR 中一组向量, Q 是一个n n ⨯对称正定矩阵.如果k j i j i Qp p Qp p i T i j T i ,,2,1,,,0,0 =≠≠=,称k p p p ,,,21 为Q 共轭向量组,也称它们为一组Q 共轭方向.当E Q =(单位矩阵)时,为正交方向.定理7.8 若k p p p ,,,21 为矩阵Q 共轭向量组,则它们必线性无关. 证明: 若存在k l l l ,,,21 ,使011=++k k p l p l ,则对任一k j ,,2,1 =,由 0)(11===∑∑==j T j j ki j T j iki iiT jQp p l Qp pl p l Q p又0>j Tj Qp p , 0=∴j l∴ k p p p ,,,21 线性无关. 证毕.由高等代数知识可知, Q 共轭向量组中最多包含n 个向量, n 是向量的维数.反之,可以证明,由n 维空间的任一组基出发可以构造出一组Q 共轭方向11,,,-n pp p .前面我们已经讲述了坐标轮换法，在n 维欧几里德空间中, n εεε,,,21 是一组线性无关的正交向量.从0x 出发,依次使用n εεε,,,21 作为下降方向进行一维精确搜索来确定n x x x ,,,21 ,重复进行得点列{}k x ,最终求得满足精度要求的最优解.刚才我们引进了共轭向量组11,,,-n p p p ,又证明了它们的线性无关性,那么是否可以用这共轭向量组像坐标轮换法一样,从0x 出发依次用11,,,-n pp p 作为下降方向来确定{}kx,最终求得近似最优解?回答是肯定的.这个方法称为共轭方向法.共轭方向法适合任何可微凸函数,且对于二次函数极值)(min x f x p Qx x T T+=21特 别有效.下面的定理告诉我们用共轭方向法求解二次函数的极值，经过n 次迭代就能求得最优解.定理7.9 设Q 为n n ⨯对称正定矩阵,函数x p Qx x x f T T+=21)(,又设 110,,,-n p p p 为一组Q 共轭向量组,且每个i p 是(下面形成的)i x 点处的下降方向.则由任一点0x 出发,按如下迭代至多n 步后收敛,k k k k p x xλ+=+1,这里k λ满足)(m i n )(0k k k k k p x f p x f λλλ+=+>.证明: 欲证至多n 步收敛,即证0)(=∇nx f .下证)(nx f ∇和11,,,-n pp p 正交.p Qx x f +=∇)( p Qx x f kk+=∇∴)( p p x Q p Qx xf k k k k k ++=+=∇++)()(11λkk k k k k Qp x f p Qp Qx λλ+∇=++=)( =+∇=∇---111)()(n n n n Qpx f x f λ 11111)(--++++++∇=n n k k k Qp Qp xf λλQ p Q p x f x f Tn n T k k T k T n )()()()(11111--++++++∇=∇λλkT n n k T k k k T k k T n Qp p Qp p p x f p x f )()()()(11111--++++++∇=∇λλ000+++= )2,,2,1,0(-=n k 又0)(1=∇-n Tn px f0)(=∇∴kT n p x f )1,,1,0(-=n k)(nx f ∇∴和11,,,-n pp p 正交， 又110,,,-n pp p 线性无关.0)(=∇∴nx fnx ∴是问题的最优解. 证毕. 共轭方向法具有二次有限终止性. 由于共轭方向组11,,,-n p p p 的取法有很大的随意性,用不同方式产生一组共轭方向就得到不同的共轭方向法.如果利用迭代点处的负梯度向量为基础产生一组共轭方向,这样的方法叫共轭梯度法.下面对二次函数讨论形成Q 共轭梯度方向的一般方法,然后引到求解无约束化问题上.任取初始点n R x ∈0,若0)(0≠∇x f ,取)(0x f p -∇=,从0x 点沿方向0p 进行一维搜索 ,求得0λ.令0001p x x λ+=,若0)(1=∇x f ,则已获得最优解1*x x =.否则，取0011)(p x f p υ+-∇=,其中0υ的选择要使1p 和0p 关于Q 共轭，由0)(01=Qp p T ,得0100)()()(Qp p x f Q p T T ∇=υ一般地,若已获得Q 共轭方向kp p p ,,,1和依次沿它们进行一维搜索的得到的点列110,,,+k x x x ,若0)(1=∇+k x f ,则最优解为1*+=k x x ,否则∑=+++-∇=ki i i k k p xf p011)(α为使1+k p 和11,,,-k pp p 是共轭,可证0110====-k ααα所以有 k k k k p x f pυ+-∇=++)(11又1+k p和kp 是Q 共轭的.有0)(1=+k Tk Qp p，得kT k k T k k Qpp x f Q p )()()(1+∇=υ 2,,2,1,0-=n k 进一步可得k υ221||)(||||)(||k k x f x f ∇∇=+ 2,,1,0-=n k综合起来得 Fletcher-Reeves 公式2)21110||(||||)(||)()(k k k k k k k x f x f p x f px f p ∇∇=+-∇=-∇=+++υυ 2,,2,1,0-=n k （7.10）共轭梯度法： ①． 选取初始点0x ，给定终止误差0>ε. ②． 计算)(0x f ∇，若ε≤∇||)(||0x f ,停止迭代，输出0x .否则进行③.③． 取)(0x f p -∇=，令0:=k④． 求k λ，)(min )(0kkkk kp x f p x f λλλ+=+≥，令k k k k p x xλ+=+1⑤． 计算)(1+∇k xf ，若ε≤∇+||)(||1k x f ，停止迭代，1*+=k x x 为最优解.否则转⑥.⑥． 若n k =+1，令nx x =:0，转③(已经完成一组共轭方向的迭代,进入下一轮)否则转⑦ ⑦． 取kk k k p xf pυ+-∇=++)(11,其中221||)(||||)(||k k k x f x f ∇∇=+υ,令1:+=k k ,转④当)(x f 是二次函数时上述共轭梯度法至多进行n 步可求得最优解.当)(x f 不是二次函数,共轭梯度法也可以构造11,,,-n p p p ,但已不具有有限步收敛的性质，于是和坐标轮换法一样经过一轮迭代后,采用重新开始的技巧.上述共轭梯度法就是带有再开始技巧的F-R 法.例7.6 用F-R 法求下面问题 2212121252),(m in x x x x x f +-=取初始点T x )2,2(0=,终止误差为610-=ε解:在例7.4中已得Tx f p )100,2()(0-=-∇= Tx )0007679.0,959984642.1(1-= Tx f )038395.0,919969284.1()(1-=∇000368628.010004687756228.3||)(||||)(||20210==∇∇=x f x f υ ⎪⎪⎭⎫ ⎝⎛-=⎪⎪⎭⎫ ⎝⎛--+⎪⎪⎭⎫ ⎝⎛-=+-∇=0015322.092070654.11002000368628.0038395.0919969284.1)(0011p x f p υ⎪⎪⎭⎫ ⎝⎛+--=+0015322.00007679.092070654.1959984642.111λλλp x0378228399.7687703443.3)(11=+-=+λλλd p x df499808794.01=∴λ⎪⎪⎭⎫ ⎝⎛≈⎪⎪⎭⎫ ⎝⎛-=⎪⎪⎭⎫⎝⎛⨯+--⨯+=+=010********.0999998622.00015322.0499808794.00007679.0)92070654.1(499808794.0959984642.11112p x x λε<=∇0||)(||2x f , ∴最优解⎪⎪⎭⎫⎝⎛==012*x x .五、变尺度法当初始点为)(x f 的其极值点附近时牛顿法收敛速度很快，但缺点是需计算)(2kx f ∇的逆矩阵，在实际问题中目标函数往往相当复杂，计算二阶导数的工作量或者太大或者不可能，在x 的维数很高时，计算逆矩阵也相当费事.如果能设法构造另一个矩阵kH ，用它来逼近二阶导数矩阵的逆矩阵12))((-∇kx f 则可避免上述问题.下面就来研究如何构造12))((-∇kx f 的近似矩阵kH .我们希望：每一步都能以现有的信息来确定下一个搜索方向，每做一次迭代，目标函数值均有所下降，这些近似矩阵最后应收敛于最优解处的海赛矩阵的逆矩阵12))((-∇kx f .p Qx x f xp Qx x x f T T+=∇+=)(21)(考虑于是 )]()([)()()(11111k k k k k k k k x f x f Q x x x x Q x f xf ∇-∇=-⇒-=∇-∇+-+++当)(x f 是非二次函数时，令)]()([111k k k k k x f x f H x x ∇-∇=-+++ （7.11）称为拟牛顿条件.显然，我们构造出来的近似矩阵k H 必须满足上述拟牛顿条件及递推性：k k k H H H ∆+=+1，这里k H ∆称为矫正矩阵.记 k k k kk k x x x x f x f G -=∆∇-∇=∆++11)()( 有 kk k k k k G H H G H x ∆∆+=∆=∆+)(1 .变尺度法即DEP 法是由Davidon 首先提出，后来又被Fletcher 和Powell 改进的算法.记kk T k kT k k k k T k T k k k k kk T k kT k k k k T k T k k kG H G HG G H x G x x H H G H G H G G H x G x x H ∆∆∆∆-∆∆∆∆+=∆∆∆∆-∆∆∆∆=∆+)()()()()()()()(1 （7.12）容易验证1+k H 满足拟牛顿条件，称上式为DEP 公式.变尺度方法计算步骤：（１） 给出初始点nR x ∈0，允许误差0>ε.（２） 若ε<∇||)(||0x f ，停止，0x 为近似最优解；否则转下一步.（３） 取I H =0（单位矩阵），0=：k . （４） )(kk k x f H p ∇-=（５） 求k λ，使)(min )(0kk k k k p x f p x f λλλ+=+≥. （６） 令kk k k p x xλ+=+1（７） 若ε<∇+||)(||1k xf ，1+k x 为最优解，停止；否则当1-=n k 时，令n x x =：0转（３）.（即迭代一轮n 次仍没求得最优解，以新的0x 为起点重新开始一轮新的迭代）.k k k k k kx x x x f xf G n k -=∆∇-∇=∆-<++11),()(1时，令当.计算kk T k kT k k k k T k T k k kk G H G H G G H x G x x H H∆∆∆∆-∆∆∆∆+=+)()()()(1，令1+=k k ：，转（４）. §4 约束极值的最优化方法考虑(MP)问题：0)(0)(..)(min =≥x H x g t s x f （7.13）其中Tl T m x h x h x h x g x g x g ))(,),(()(,))(,),(()(11 ==是向量函数.显然 0)(0)(0)(≥-≥⇔=x h x h x h ，　于是（MP ）问题可以写为：Tm x g x g x g x g t s x f ))(,),(()(0)(..)(min 1 =≥ （7.14）一、积极约束设0x 是（MP ）问题（5.14）的一个可行解.对0)(0≥x g i 来说，在点0x 有两种情况：或者0)(0>x g i ，或者0)(0=x g i .0)(0>x g i 时，则0x 不在0)(0=x g i 形成的边界上，称这一约束为0x 的非积极约束；0)(0=x g i 时，0x 处于由0)(0≥x g i 这个约束条件形成的可行域边界上，当0x 有变化时就不满足0)(0=x g i 的条件，所以称为积极约束，记为：{}()|()0,1i I x i g x i m ==≤≤.定义7.16 设x 满足约束条件0)(0≥x g i ),,1(m i =，0)(|{)(==x g i x I i ，}m i ≤≤1，如果)(x g i ∇，)(x I i ∈线性无关，则称点x 是约束条件的一个正则点.二、可行方向、下降方向的代数条件前面我们已经给出可行方向和下降方向的定义，下面给出其代数条件.可行方向：设K 是（MP ）问题（5.14）的可行域，K x ∈,0,≠∈p R p n.若存在00>λ使得],0[0λλ∈时有K p x ∈+λ，称p 为x 点处的一个可行方向.由泰勒公式：||)(||)()()(p p x g x g p x g T i i i λολλ+∇+=+当x 为)(x g i 的积极约束时，有0)(=x g i .只要0>λ足够小，)(p x g i λ+和p x g T i )(∇λ同号，于是当0)(>∇p x g T i 时有0)(≥+p x g i λ )(x I i ∈.当x 为)(x g i 的非积极约束时，有0)(>x g i .由)(x g i 的连续性，当0>λ足够小时，由保号性知 0)(≥+p x g i λ )(x I i ∉.所以只要 0)(>∇p x g T i ，)(x I i ∈就可保证0)(≥+p x g i λ，于是p 为x 点处的一个可行方向.称0)(>∇p x g T i ，)(x I i ∈ 为p 在点x 处是可行方向的代数条件.下降方向：设K 是（MP ）问题的可行域，K x ∈,0,≠∈p R p n.若存在00>λ使得],0[0λλ∈时，有)()(x f p x f <+λ，称p 为x 点处的一个下降方向.由泰勒公式：||)(||)()()(p p x f x f p x f Tλολλ+∇+=+.当λ足够小时，只要0)(<∇p x f T，有)()(x f p x f <+λ. 称0)(<∇p x f T为p 在x 点处的一个下降方向的代数条件.三、可行下降方向设K 为（MP ）问题（5.14）的可行域，K x ∈，若存在0,≠∈p R p n，p 既是x 点处的下降方向又是可行方向，则称p 为点x 处的可行下降方向.定理7.10 考虑非线性规划问题（5.14），K x ∈，),,1)()(m i x g x f i =（和在x点处可微，若*x 是局部极小点，则x 点处必不存在可行下降方向，即不存在p 同时满足：⎪⎩⎪⎨⎧∈>∇<∇)(0)(0)(x I i p x g p x f Ti T证明：反证法，设局部极小点x 处存在可行下降方向p ，于是1λ∃，当],0[1λλ∈时有)()(x f p x f <+λ，又p 为可行方向．2λ∃∴当],0[2λλ∈时K p x ∈+λ，这与x 是。

几种常见的决策模型决策模型是指用于建立决策过程和辅助决策的数学模型。

常见的决策模型有多种，下面将介绍其中几种常见的决策模型。

1. 线性规划模型（Linear Programming）：线性规划是一种常见的优化方法，用于在给定的约束条件下寻找线性目标函数的最优解。

线性规划模型适用于许多实际问题，如生产计划、资源分配等。

该模型的数学表达式为最大化或最小化目标函数，同时满足一系列线性等式或不等式约束。

2. 多目标决策模型（Multi-objective Decision Model）：多目标决策模型是用于处理多个相互矛盾目标的决策问题。

在多目标决策模型中，决策者需要权衡各个目标之间的优先级，并找到一个最优解或一组最优解。

方法包括权重法、直接偏好法和效用函数法等。

3. 非线性规划模型（Nonlinear Programming）：非线性规划模型是一种考虑非线性目标函数和非线性约束条件的优化方法。

这种模型适用于许多实际问题，如供应链优化、投资组合优化等。

非线性规划模型需要使用数值优化算法进行求解。

4. 随机决策模型（Stochastic Decision Model）：随机决策模型是用于处理存在不确定性和风险的决策问题。

该模型考虑到不同决策结果的概率分布，并使用概率统计方法评估各个决策的风险。

常见的方法包括决策树、马尔可夫链和蒙特卡洛模拟等。

5. 排队论模型（Queueing Theory Model）：排队论模型是一种用于分析和优化排队系统的数学模型。

排队论模型可以用于评估系统性能指标，如平均等待时间、平均队长等，并提供决策者关于系统优化的建议。

排队论模型广泛应用于运输、通信、服务等领域。

6. 博弈论模型（Game Theory Model）：博弈论模型是一种用于分析决策者之间互动行为的数学模型。

博弈论模型主要研究决策者在决策过程中的策略选择和利益分配，并研究在不同策略组合下的最优解。

博弈论模型适用于许多领域，如经济学、管理学和政治学等。