当前位置：文档之家 › 第五章 约束非线性优化--最优性条件及算法

第五章 约束非线性优化--最优性条件及算法

  • 格式：ppt
  • 大小：2.34 MB
  • 文档页数：86

下载文档原格式

  / 86

合集下载

约束问题的最优化方法

约束问题的最优化方法

可用于处理等式约束。
§5.3 外点惩罚函数法
三. 几个参数的选择：
r(0) 的选择:
r(0) 过大，会使惩罚函数的等值线变形或偏心，求极值困难。r (0) 过小，迭代次数太多。
建议 ：r0 max ru0 u 1,2,...m
其中：ru0
m gu
0.02 x0 f
x0
x(0) 的选择：
2
若均满足，停止迭代，有约束优化问题的最优点为 x* = xk*； 若有一个准则不满足，则令 x(0) xk * (r(k) ),r(k1) c r(k) , k k 1 并转入第 3 步，继续计算。
§5.2 内点惩罚函数法
算法框图
§5.2 内点惩罚函数法
四. 几个参数的选择： 1. 惩罚因子初始值 r(0) 的选择：
§5.1 引言
有解的条件： ① f(x) 和 g(x) 都连续可微； ② 存在一个有界的可行域； ③ 可行域为非空集； ④ 迭代要有目标函数的下降性和设计变量的可行性。
三. 间接解法的基本思想： 目的：将有约束优化问题转化为无约束优化问题来解决。
方法：以原目标函数和加权的约束函数共同构成一个新的目标函数
（略） 2. 数学模型：
设计变量 ： X x1,x2 T t f ,h T
目标函数 ： min. f x 120x1 x2
单位长度的质量
§5.2 内点惩罚函数法
约束函数 ： g1x x1 0 g 2 x x2 0 g3 x 1 0.25x2 0
g4
x
1
7 45
x1x2
0
g5
x
§5.3 外点惩罚函数法 (衰减函数法）
一. 基本思想：
外点法将新目标函数 Φ( x , r ) 构筑在可行域 D 外， 随着惩罚因子 r(k) 的不断递增， 生成一系列新目标函数 Φ(xk ,r(k))，在可行域外逐步迭 代，产生的极值点 xk*(r(k)) 序 列从可行域外部趋向原目标函 数的约束最优点 x* 。

最优化方法-约束非线性最优化方法

最优化方法-约束非线性最优化方法

解: 令 极大点的必要条件:
L( X ) x12 x2 1 ( 2 x12 2 x1x2 24 )
* * * * * (L / x1 ) x*, * 2 x1 x2 41 x1 21* x2 0 x1 2 * *2 * * x2 4 (L / x2 ) x*, * x1 21 x1 0 * *2 * * * (L / 1 ) x*, * (2 x1 x2 2 x1 x2 24 ) 0 1 1
j 1
以及
h (x)=0， j=1,2, …,l
一、等式约束性问题的最优性条件： (续) 几何意义是明显的：考虑一个约束的情况：
－▽f(x*)
-▽f(ㄡ )
h(x)
这里 x* ---l.opt. ▽f(x*)与 ▽h(x*) 共线，而ㄡ非l.opt. ▽f(ㄡ )与▽h(ㄡ )不共线。
ㄡ ▽h(ㄡ )
充分条件: 如果 L( X *, ) 0 且行列式方程:
所有根Zj>0(j=1,2,…,n-l)，则X*为局部极小点；反 之所有Zj<0，为局部极大点；有正有负非极值点
例题4-1用拉格朗日乘子算法求解:
max f ( X ) x12 , s.t. h1 ( x) 2x12 2x1x2 24 0
2 i 1 j 1 m l
这里( M k , g ( X ), h( X ))是惩罚项： k CM k 1 M 0, 满足约束 ( M k , g ( X ), h( X )) 0, 不满足约束
例题４－３用外点法求解
2 min f ( X ) x12 x2 , s.t. 2x1 x2 4, x1 , x2 0

非线性优化与约束优化问题的求解方法

非线性优化与约束优化问题的求解方法

非线性优化与约束优化问题的求解方法非线性优化问题是在目标函数和约束条件中包含非线性项的优化问题。

约束优化问题是在目标函数中加入了一些约束条件的优化问题。

解决这些问题在实际应用中具有重要意义，因此研究非线性优化和约束优化问题的求解方法具有重要的理论和实际意义。

一、非线性优化问题的求解方法非线性优化问题的求解方法有很多，下面介绍几种常见的方法：1. 黄金分割法：黄金分割法是一种简单但有效的搜索方法，它通过不断缩小搜索范围来逼近最优解。

该方法适用于目标函数单峰且连续的情况。

2. 牛顿法：牛顿法利用目标函数的一阶和二阶导数信息来逼近最优解。

该方法收敛速度较快，但在计算高阶导数或者初始点选取不当时可能产生不稳定的结果。

3. 拟牛顿法：拟牛顿法是对牛顿法的改进，它通过逼近目标函数的Hessian矩阵来加快收敛速度。

拟牛顿法可以通过不同的更新策略来选择Broyden-Fletcher-Goldfarb-Shanno（BFGS）方法或者DFP方法。

4. 全局优化方法：全局优化方法适用于非凸优化问题，它通过遍历搜索空间来寻找全局最优解。

全局优化方法包括遗传算法、粒子群优化等。

二、约束优化问题的求解方法约束优化问题的求解方法也有很多，下面介绍几种常见的方法：1. 等式约束问题的拉格朗日乘子法：等式约束问题可以通过引入拉格朗日乘子来转化为无约束优化问题。

通过求解无约束优化问题的驻点，求得原始约束优化问题的解。

2. 不等式约束问题的罚函数法：不等式约束问题可以通过引入罚函数来转化为无约束优化问题。

罚函数法通过将违反约束条件的点处添加罚项，将约束优化问题转化为无约束问题。

3. 逐次二次规划法：逐次二次规划法是一种常用的求解约束优化问题的方法。

该方法通过依次处理逐个约束来逼近最优解，每次处理都会得到一个更小的问题，直至满足所有约束条件。

4. 内点法：内点法是一种有效的求解约束优化问题的方法。

该方法通过向可行域内部逼近，在整个迭代过程中都保持在可行域内部，从而避免了外点法需要不断向可行域逼近的过程。

最优化：最优性条件

最优化：最优性条件

g i ( x ) T d 0 和 h j ( x ) T d 0, 即d LFD( x, D ) 注意：尽管 LFD( x, D )具有代数表示, 但上面的命题表明 LFD( x, D )是SFD( x, D )的一个子集,因此还不能用 LFD( x, D )替换定理 9.1.1中的SFD( x, D )
令 xk x k d k , 由定义9.1.2知, {xk } D.
为理解序列可行方向, 我们来看看它的几何解释：
xk
D
D
●
dk
●
xdຫໍສະໝຸດ xkdk●●
d
x
(a ) 点x在D内部
(b) 点x在D的边界上
序列可行方向实际 上就是可行方向
显然,
序列可行方向包含可行 方向和边界的切线方向
FD( x, D) SFD( x, D) (只需取d k d )
定义9.1.1 设x D, d R n .若存在数 0, 使得 x d D, (0, ], 则称d是D在x处的一个可行方向.
记x处所有可行方向的集合为FD( x, D)
若记x处函数f 的所有下降方向 集合为GD( x ) * 容易看出, 如果x 是(9.1)的最优 解, 则在该点不存在既下降又 可行的方向, 即
等式 h j ( x) 0 : h j ( x)T d 0
由上面分析可知：d FD( x, D ), 则有 h j ( x )T d 0, j E T g ( x ) d 0, i I 且 g i ( x ) 0 i
但反之不一定成立.
为方便起见, 记
可行域：D {x : g i ( x ) 0, i I ; h j ( x ) 0, j E}

非线性优化理论及算法

非线性优化理论及算法

非线性优化理论及算法随着人工智能、大数据、云计算等技术的快速发展，非线性优化理论及算法逐渐成为研究的热点。

非线性优化是指在满足一定限制条件的情况下，将目标函数最优化的问题，通常具有多个局部最优解，需要通过算法求解全局最优解。

一、非线性优化理论1.1 优化问题的数学形式非线性优化问题的数学形式可以表示为：$$\min_{\boldsymbol{x} \in \mathcal{S}} f(\boldsymbol{x})$$其中，$\boldsymbol{x}$ 是决策变量向量，$\mathcal{S}$ 是定义域，$f(\boldsymbol{x})$ 是目标函数。

1.2 优化问题的分类根据优化问题的约束条件，可以将其分类为以下几种：1）无约束优化问题：没有约束条件，即 $\mathcal{S} =\mathbb{R}^n$；2）等式约束优化问题：存在等式约束条件，即 $\mathcal{S} = \{\boldsymbol{x} \in \mathbb{R}^n \, | \, g_i(\boldsymbol{x}) = 0, \, i = 1, \ldots, l\}$；3）不等式约束优化问题：存在不等式约束条件，即$\mathcal{S} = \{\boldsymbol{x} \in \mathbb{R}^n \, | \,h_i(\boldsymbol{x}) \leq 0, \, i = 1, \ldots, m\}$。

1.3 最优解的性质对于一般的非线性优化问题，其最优解可能具有以下几种性质：1）局部最优解：在解空间中，存在一个局部范围内的最优解，但不一定是全局最优解；2）全局最优解：在解空间中，存在一个全局最优解，但不一定是唯一的；3）不可行解：在优化问题的约束条件下，不存在满足条件的解。

1.4 梯度和海森矩阵梯度和海森矩阵是非线性优化中常用的两个概念。

梯度是目标函数的导数，表示了函数在某个点处增长最快的方向，可用于确定优化问题的搜索方向。

非线性最优化计算方法与算法

非线性最优化计算方法与算法

毕业论文题目非线性最优化计算方法与算法学院数学科学学院专业信息与计算科学班级计算1201学生陶红学号20120921104指导教师邢顺来二〇一六年五月二十五日摘要非线性规划问题是一般形式的非线性最优化问题。

本文针对非线性规划的最优化问题进行方法和算法分析。

传统的求解非线性规划的方法有最速下降法、牛顿法、可行方向法、函数逼近法、信赖域法，近来研究发现了更多的求解非线性规划问题的方法如遗传算法、粒子群算法。

本文对非线性规划分别从约束规划和无约束规划两个方面进行理论分析。

利用最速下降法和牛顿法两种典型算法求解无约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。

另外给出了阻尼牛顿法，探讨其算法的收敛性和稳定性，求解无约束非线性规划比牛顿法的精确度更高，收敛速度更快。

惩罚函数是经典的求解约束非线性的方法，本文采用以惩罚函数法为核心的遗传算法求解有约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。

并改进遗传算法，给出适应度函数，通过变换适应度函数，提高算法的收敛性和稳定性。

关键词：非线性规划；最速下降法；牛顿法；遗传算法ABSTRACTNonlinear 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目录摘要 (I)ABSTRACT .......................................................................................................................... I I 1 前言 .. (4)1.1 引言 (4)1.2 非线性规划的发展背景 (5)1.3 国内外研究现状 (5)1.4 研究主要内容及研究方案 (6)1.4.1 研究的主要内容 (6)1.4.2 研究方案 (6)1.5 研究难点 (7)2 预备知识 (8)2.1 向量和矩阵范数 (8)2.1.1 常见的向量范数 (8)2.1.2 谱范数 (9)2.2符号和定义 (9)2.3 数值误差 (10)2.4 算法的稳定性 (10)2.5 收敛性 (12)3 非线性规划模型 (13)3.1 非线性规划模型 (13)3.2 无约束非线性规划 (14)3.2.1 最速下降法 (16)3.2.2 牛顿法 (18)3.2.2 阻尼牛顿法 (18)3.3 约束非线性规划 (20)3.3.1 惩罚函数法 (21)3.3.2 遗传算法 (21)3.3.3 自适应遗传算法 (22)结论 (26)参考文献 (27)致谢 (28)附录 (29)1 前言1.1 引言我们知道最优化是一门很古老的求极值问题，最优化在求解线性规划，非线性规划，随机规划，多目标规划，非光滑规划，整数规划，几何规划等方面研究得到迅速发展。

运筹学-约束最优化方法


若AT的各个行向量线性无 关.根据Kuhn-Tucker条件, 在该线性规划的最优点y* 处存在乘子向量x*≥0,使得
即Ax*=b 对偶规划约束条件 及(ATy*-c)T x*=0 线性规划互补松弛条件
29
5.1.3 一般约束问题的最优性条件
定理1.3.1 在上述问题中,若 (i)x*为局部最优解, 有效集I*={i|ci(x*)=0,i∈I}; (ii)f(x),ci(x)(1≤i≤m)在x*点可微; (iii)对于i∈E∪I*, 线性无关, 则存在向量l*=(l1*,· · · ,lm*)使得

解:本问题是求点(1,1)T到如图三角形区域的最短 距离.显然唯一最优解为x*=(1/2,1/2)T.
19
例题(Fritz-John条件)
min f(x)=(x1-1)2+(x2-1)2 s.t. c1(x1,x2)=(1-x1-x2)3≥0 c2(x)=x1≥0 c3(x)=x2≥0 即

35
惩罚函数法
惩罚是手段，不是目的
KT条件中li*ci(x*)=0 称为互补松弛条件. 它表明li*与ci(x*)不能 同时不为0.

28
线性规划情形
对于线性规划问题 min f(y)=-bTy s.t. -ATy≥-c 其中 y∈Rm,A∈Rm×n, b∈Rm,c∈Rn 问题有n个约束条件. 各个约束条件关于y 的梯度为-AT的行向 量(-pi).

借助于Farkas引理,可推出存在li*≥0(i∈I*), 使得
类似与Fritz-John条件的证明,可以证明KuhnTucker条件. 有效约束函数的梯度线性无关称为KuhnTucker约束规范. 如果该约束规范不满足,最优点不一定是KT点.

约束非线性规划讲解

g1 ( x ) x1 x2 4,
g1 ( x) [ 1 , 1 ]T
g2 ( x) x1 ,
g2 ( x) [ 1 , 0 ]T 。
g3 ( x) x2 ,
g3 ( x) [ 0 , 1 ]T 。
18
由K T条件得
x1 3 1 1 0 x 3 1 1 2 0 3 1 0 2
分析：
(1) 如果 I ( x*)中只有一个指标，不妨 设 g1 ( x)为积极约束。
则不存在向量d 使得 g1 ( x*)T d 0 T f ( x *) d0 成立。
12
则不存在向量d 使得 g1 ( x*)T d 0 成立。 T f ( x*) d 0
令 Q { x | h( x ) 0 , g ( x ) 0 } , 称 Q 为此约束极值问题的
可行域。
2
min f ( x ) hi ( x ) 0 i 1 , 2 , , m s.t. g j ( x ) 0 j 1 , 2 ,, l
hi ( x ) 0 hi ( x ) 0 hi ( x ) 0
gi ( x ) ( i I ( x*) ) 在 点 x * 处 连 续, { gi ( x*)| i I ( x*) } 线性无关。若 x *是约束极值问题 (1)的 局 部 极 小 点 ， 则存在一组实数 i 使 其 满 足
l f ( x*) i gi ( x*) 0 i 1 () i gi ( x*) 0 , i 0, i 1 , 2 , , l
8
2 g3 ( x ) 0。 2
I ( x ) { 1 , 2 }。

非线性最优化.pptx


第16页/共147页
1.4 凸规划
非线性规划的数学模型
Minf(X)
(1.1)
hi(X)=0 i=1,2, … ,m
(1.2)
gj(X) ≥ 0 j=1,2, … ,l
(1.3)
满足约束条件(1.2)和(1.3)的点称为可行点
(可行解)，所有可行点的集合称为可行域.
若某个可行解使目标函数(1.1)最小，就称
第18页/共147页
• 例5. 求解非线性规划
x2 g2(x) 0
g1(x) 0
A
min f (x) x12 x22 4x1 4 O s.t. g1(x) x1 x2 2 0
2
4
x1
g2 (x) x12 x2 1 0
x1 0, x2 0
最优点A(0.58,1.34), min f 3.8
f(X)在S上的局部极小点, f(X* )为局部极小值。 严格局部极小点(值)：对于所有X≠X* 且
与X*的距离小于ε的X∈S,f(X)>f(X* ),则称 X* 为f(X)在S上的严格局部极小点， f(X* )为
第4页/共147页
严格局部极小值。 全局极小点(值)：对于所有的X ∈S，都
有f(X)≥f(X* ),则称X* 为f(X)在S上的全局 极小点，f(X* )为全局极小值。
则称f(X)为定义在S上的严格凸函数. 将(1.5)和(1.6)中的不等号反向,即可得到凹函数
第8页/共147页
凸函数的性质
• 性质1 设f(X)为定义在凸集S上的凸函数, 则对 任意实数b≥ 0,函数bf(X)也是定义在S上的凸 函数.
• 性质2 设f1(X)和 f2(X)为定义在凸集S上的两 个凸函数,则其和f(X)= f1(X)+f2(X)仍为定义 在S上的凸函数.

约束优化的共轭梯度算法及最优性条件


8
-408.590428
2173.136424
9
-754.887518
1826.839334
10
-2567.158421
14.568431
11
-2581.711672
0.015180
12
-2581.726852
-0.000000
f (xk )− f (x* ) ( ) ( ) f xk−1 − f x*
（约束规格条件） 5.0.1 超平面分离
幻灯片 27
定理 设 S 是 Rn 的一个非空闲凸子集，设 x* ∈ R n 是一个不属于 S 的向量，则，存在
向量 c ∈ R n 使得 c' x* < c' x ，最所有 x ∈ S
证明见 BT.P.170 5.1 凸性下的证明方法
z 假定 x 是一个局部（因此也是整体）最优解
幻灯片 21
KKT：
⎜⎜⎝⎛
1 0
⎟⎟⎠⎞
+
u ⎜⎜⎝⎛
2x1 −1
⎟⎟⎠⎞
+
v⎜⎜⎝⎛
0 1
⎟⎟⎠⎞
=
⎜⎜⎝⎛
0 0
⎟⎟⎠⎞
KKT：乘子不存在，当 (0,0)' 是局部极小值点，检查 ∇g1(0,0)
和 ∇h1(0,0)
3.7 约束规格
Slater 条件：存在 x 0 使得 g j (x0 ) < 0, j = 1,..., p 且
幻灯片 22
hi (x0 ) ，对所有 i = 1,..., m
定理：在 Slater 条件下，KKT 条件是必要的
4 充分性最优性条件
定理 若
z x 是 p 的可行解
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
g1 ( x) 4 x1 x2
g1 ( x ) [ 1 , 1 ]T
g2 ( x ) x1 , g2 ( x ) [ 1 , 0 ]T 。
g3 ( x ) x2 , g3 ( x ) [ 0 , 1 ]T 。
18
由 K T条件得
x1 3 1 1 0 x 3 1 1 2 0 3 1 0 2
(3) 一般情况：设{gi ( x*) | i I ( x*) } 线性无关。 则存在非负实数i ( i I ( x*) ), 使得
f ( x*) i gi ( x*) 0
iI ( x *)
( 2)
( 2) 式可改写为
l f ( x*) i gi ( x*) 0 i 1 i g i ( x*) 0 , i 1 , 2 , , l 0, i 1 , 2 , , l i
g i ( x) 0 , 则称 g i ( x) 0 是点 x 处的积极约束。
或起作用约束（紧约束\积极约束\有效约束）。
记 I ( x) { i | g i ( x) 0 ,1 i l } , 称 I ( x)为点 x 处的积极 约束指标集。
例: 设 g1 ( x) x2 2x12 0 , g 2 ( x) 1 x12 x22 0 ,
x'
▽h(x*)
▽ h(x')
最优性条件即：
f ( x*) j h j ( x*)
* j 1
6
h
(2)不等式约束极值问题的最优性条件
min f ( x) s.t. g ( x) 0
(1)
g1 ( x ) 0
x0 d2 d1
可行域为 Q { x | g ( x) 0 }。
x2 1 3 x2 2 0 2 x2 0 1 2 3
如果 x * 是约束极值问题 (1)的局部极小点，则在 点 x * 处没有可行下降方向。
11
K T 条件（库恩 塔克条件）
设I ( x*)是其积极约束指标集 , 点 x * 是约束极值问题 (1) 的局部极小点 , 则在点x * 处不存在可行下降方向 d。
则由定理2可知，不存在向量 d ，使下式成立 gi ( x*)T d 0 T f ( x *) d0 i I ( x*) 。
约束极值问题也可记为
min f ( x ) s .t . g( x ) 0
3
2 约束极值及最优性条件——Kuhn-Tucker 条件 （1）等式约束性问题的最优性条件 考虑 min f(x) s.t. h(x)=0 回顾高等数学中所学的条件极值： 问题 即： 求z=f(x,y)极值，在ф(x,y)=0的条件下。 min f(x,y)
分析：
(1) 如果 I ( x*)中只有一个指标，不妨 设 g1 ( x)为积极约束。
则不存在向量d 使得 f ( x*)T d 0 T g ( x *) d0 1 成立。
12
g1 ( x*)
则不存在向量d 使得 f ( x*) d 0 成立。 T g1 ( x*) d 0
x' Q , 即 d 为可行方向。
可行下降方向:
设点 x Q ， 给定向量d ，如果d 既是点 x 处的可行方向， 又是该点的下降方向， 则称 d 为点 x 处的可行下降方向。
10
定理2: 给定点 x Q , 记点 x 的积极约束指标集为 I ( x)。给定
向量 d ，如果d 满足 g i ( x)T d 0 T f ( x ) d 0 i I ( x)
x1 d 1 d2
①可行方向与积极约束: 可行方向:
g2 ( x ) 0
设 x0 Q， d 为一个向量。如果存在 实数 0， 使得对任意的 [ 0 , ] 有 x 0 d Q , 则称 d 为 x 0 处的 一个可行方向。
7
积极约束: 设点 x Q , 对于不等式约束g i ( x) 0，如果
令 Q { x | h( x ) 0 , g ( x ) 0 } , 称 Q 为此约束极值问题的
可行域。
2
min f ( x ) hi ( x ) 0 s .t . g j ( x) 0 i 1 , 2 , , m j 1 , 2 , , l
hi ( x ) 0 hi ( x ) 0 hi ( x ) 0
I ( x ) { 1 , 2 }。
x2 g2 ( x ) 0
g3 ( x ) 0
O
g1 ( x ) 0
x
x1
②如何判断一个方向是可行方向 定理1:
给定点 x Q , 记点 x 的积极约束指标集为 I ( x)。给定向量d ， 如果对任意的i I ( x) 有g i ( x)T d 0 , 则d 是点 x 的可行方向。
g2 ( x*) g1 ( x ) 0
g1 ( x*)
g2 ( x ) 0
x*
f ( x*)
存在1 ， 2 0 , 使得 f ( x*) 1g1 ( x*) 2g2 ( x*)。
14

f ( x*) 1g1 ( x*) 2g2 ( x*) 0。
f ( x ) j h j ( x ) 0
* * * j 1
5
l
f ( x ) j h j ( x ) 0
* * * j 1
l
几何意义：考虑一个约束的情况：
-▽f(x*)
-▽f(x')
h(x)
这里 x* 最优，▽f(x*)与 ▽h(x*) 共线，而x' 非最优 ▽f(x')与▽h(x')不共线。
由 K T条件及约束条件得
x1 1 2 3 x 3 1 3 2 1 (4 x1 x 2 ) 0 2 x1 0 3 x2 0 x1 x 2 4 , , , x , x 0 1 2 3 1 2
g i ( x) (i I ( x*) ) 在点 x * 处连续,{ g i ( x*) | i I ( x*) } 线性无关。若x *是约束极值问题（ 1 ）的局部极小点， 则存在一组实数i 使其满足
f ( x*) l g ( x*) 0 i i i 1 () g ( x *) 0 , i 1 , 2 , , l i i 0, i 1, 2 , , l i () 式称为K T条件（库恩 塔克条件），满足 () 式的点
s.t. ф(x,y)=0
引入Lagrange乘子：λ Lagrange函数 L(x,y;λ)= f(x,y)+ λ ф(x,y)
4Leabharlann 若(x*,y*)是条件极值，则存在λ* ，使 fx(x*,y*)+ λ* фx (x*,y*) =0 fy(x*,y*)+ λ* фy(x*,y*) =0 Ф (x*,y*)=0 推广到多元情况，可得到对于等式约束的情况： min f(x) 分量形式： s.t. hj(x)=0 j=1,2, …,l 若x*是其的最优解 , 则存在υ*∈ Rl 使
以下分情况讨论：
19
(1) 若 x1 x 2 0 :
x1 1 2 3 x 3 1 3 由 1 (4 x1 x 2 ) 0 可得 1 0。 2 1 (4 x1 x 2 ) 0 1 2 3 2 3 2 x1 0 这与 2 0 矛盾。 3 x2 0 ( 2) 若 x1 0 , x 2 0 : x1 x 2 4 , , , x , x 0 3 0 1 2 3 1 2
第五章 约束非线性规划
约束极值及最优性条件
等式约束 不等式约束 一般约束问题
约束极值问题的算法
外点法 内点法 乘子法
1
一 、约束极值问题的最优性条件
1、约束极值问题的表示
min f ( x ) hi ( x ) 0 s .t . g j ( x) 0 i 1 , 2 , , m j 1 , 2 , , l
()
17
3. K T点的计算
例: 求约束极值问题 min
s.t.
的 K T 点。
f ( x) x12 x22 6 x1 6 x2 8 x1 x2 4 x1 0 x 0 2
解： f ( x ) 2 [ x1 3 , x2 3 ]T 。
9
定理1:
给定点 x Q , 记点 x 的积极约束指标集为 I ( x)。给定向量d ， 如果对任意的i I ( x) 有g i ( x)T d 0 , 则d 是点 x 的可行方向。
证明: 令 x' x t d , t 0。 则对任意的i I ( x ) , 有
gi ( x' ) gi ( x ) t gi ( x )T d o( || td ||2 ) t gi ( x )T d o( || td ||2 ) 0
g 3 ( x) x1 0。 令x ( 2 2 T , ) ，求点 x 的积极约束指标集。 2 2
2 2( 解： g1 ( x ) 2 2 2 g2 ( x ) 1 ( ) ( 2
2 2 ) 0, 2 2 2 ) 0, 2
8
2 g3 ( x ) 0。 2
T
g1 ( x ) 0
x*
f ( x*)
则有
f ( x*) g1 ( x*) , 0。
即