Objective: To minimize surface area of the box.
Model: min f (x, y, z) 2xy 2xz 2yz
s.t xyz V
x, y, z 0
Constrained
2020/7/4
Ludong University
6
数学规划
设 x (x1,L , xn )T Rn ， f (x); gi (x),i 1,L , p;hj (x), j 1,L , q; Rn a R , 如下的数学模型称为数学规划(Mathematical Programming, MP)：
非线性规划
Nonlinear Programming
Ludong University
第四章 非线性规划
由前几章知道，线性规划的目标函数和约束条件都是其自变 量的线性函数，如果目标函数或约束条件中包含有自变量的 非线性函数，则这样的规划问题就属于非线性规划。有些实 际问题可以表达成线性规划问题，但有些实际问题则需要用 非线性规划的模型来表达，借助于非线性规划解法来求解。
若 xk1 满足某种终止条件，停止，输出近似解 xk1 。
定义 4.1.3 设 f : Rn a R, x Rn , p Rn , p 0 ，若存在 0 ，使 f (x tp) f (x), t (0, 处的下降方向。
定义 4.1.4 设 X Rn , x X , p Rn , p 0 ，若存在 t 0 ，使 x tp X ,
f (x*) f (x), x X, x x*,
则称 x* 是(MP)的严格整体最优解或严格整体极小点，称 f (x*) 是(MP)的严格整 体最优值或严格整体极小值。
定义 4.1.2 对于非线性规划(MP)，若 x* X ，并且存在 x* 的一个领域
N (x*) x Rn x x* ( 0, R) ，
7
向量化表示
令 其中 g : Rn a
g(x) (g1(x),L , gp (x))T ， h(x) (h1(x),L , hq (x))T ， R p , h : Rn a Rq ，那么(MP)可简记为
min f (x)
s.t. g(x) 0, 或者 min f (x) 。
h(x) 0.
2020/7/4
Ludong University
4
Example 1
(a1,b1)
(a2,b2)
(x, y)
(a3,b3)
Three customers with known locations on a plane described by coordinates (ai,bi ), i=1,2,3.
2020/7/4
Ludong University
9
最优解的几何位置
min s.t.
f x1, x2 x12 x22
1 x1 x2 0, x1 1 0, x2 1 0.
x2
x*
x1
2020/7/4
Ludong University
10
非线性规划方法概述
选取初始点 x0 ，构造搜索方向 pk ，确定步长 tk ，令 xk 1 xk tk pk 。
使 f (x*) f (x), x N (x*) I X ，则称 x* 是(MP)的局部最优解或局部极小点，称 f (x*) 是(MP)的局部最优值或局部极小点。如果有 f (x*) f (x), x N (x*) I X , x x* ，则称 x* 是(MP)的严格局部最优解或严格局部极小点，称 f (x*) 是(MP)的严格局部最优值 或严格局部极小点。
min f (x)
s.t. gi (x) 0,i 1,L , p,
hj (x) 0, j 1,L , q.
其中X
x
R
n
gi (x) 0,i 1,L hj (x) 0, j 1,L
, p , q
约束集或可行域
x X
MP的可行解或可行点
2020/7/4
Ludong University
xX
当p=0，q=0时，称为无约束非线性规划或无约束最优化问
题。否则称为约束非线性规划或约束最优化问题。
2020/7/4
Ludong University
8
最优解和极小点
定义 4.1.1 对于非线性规划(MP)，若 x* X ，并且有
f (x*) f (x), x X,
则称 x* 是(MP)的整体最优解或整体极小点，称 f (x*) 是(MP)的整体最优值或整 体极小值。如果有
min f (x, y) (x ai )2 ( y bi )2
i 1
2020/7/4
Ludong University
5
Unconstrained
Example 2
Using the minimum material to make a box. The volume of the box has to be V=1000. Decision: Box length: x, width: y, height: z.
f(x)
2020/7/4
0
x
Local minimum
Global minimum
Ludong University
2
第四章 非线性规划
基本概念 凸函数和凸规划 一维搜索方法 无约束最优化方法 约束最优化方法
2020/7/4
Ludong University
3
基本概念
非线性规划问题
非线性规划方法概述
Problem:To find a location for a depot so that the total distance to the three customers is minimized.
Variable: (x,y) the coordinates of the depot
Model: 3
则称向量 p 是函数 f x 在点 x 处关于 X 的可行方向。
2020/7/4
Ludong University
11
非线性规划基本跌代格式
第 1 步 选取初始点 x0 ， k B0 ； 第 2 步 构造搜索方向 pk ； 第 3 步 根据 pk ，确定步长 tk ； 第 4 步 令 xk1 xk tk pk 。 若 xk1 已满足某种终止条件，停止迭代，输出近似 解 xk1 ；否则令 k Bk 1，转回第 2 步。