当前位置：文档之家 › 第07章 无约束问题

第07章 无约束问题

  • 格式：ppt
  • 大小：5.24 MB
  • 文档页数：182

下载文档原格式

  / 182

合集下载

无约束问题的最优性条件

无约束问题的最优性条件


一阶必要条件的表述
若$x^*$是无约束问题的局部最 优解，则$x^*$处的梯度$nabla f(x^*)=0$。这意味着在最优解处， 目标函数的梯度向量必须为零向 量。
几何解释
一阶必要条件可以理解为，在最 优解处，目标函数的等值面（或 曲线）与任意方向的切线（或切 面）都相切，即没有下降方向。
一阶充分条件
04 二阶最优性条件
二阶必要条件
二阶导数矩阵半正定
在最优解处，目标函数的二阶导数矩阵（即海森矩阵）必须是半正定 的，这意味着对于所有非零向量，海森矩阵与其的乘积至少为零。
梯度为零
同时，目标函数在最优解处的梯度必须为零，这是一阶必 要条件的补充。
约束条件
对于约束优化问题，还需要考虑约束条件的二阶影响。在最优 解处，积极约束的拉格朗日乘子应满足相应的二阶条件。
06 最优性条件的应用举例
线性规划的最优性条件
可行域
线性规划问题的可行域是由线性约束条 件所围成的凸多边形区域。
最优解
在可行域中，使目标函数达到最小 （或最大）值的可行解。
基本可行解
满足所有约束条件的解，且所有非基 变量都取值为0的解。
最优性条件
对于线性规划问题，当且仅当所有非 基变量对应的检验数都小于等于0时， 基本可行解才是最优解。
一阶充分条件的表述
若目标函数$f(x)$在$x^*$处可微，且存在某个正数$alpha$，使得对于所有满足$||d||=1$的 方向$d$，都有$nabla f(x^*)^Td ge alpha$，则$x^*$是无约束问题的严格局部最优解。
几何解释与意义
一阶充分条件表明，在最优解处，不仅梯度为零向量，而且目标函数在最优解附近具有“凸 性”，即对于任意方向$d$，目标函数在$x^*$处的方向导数都大于零。这保证了最优解的 唯一性和全局最优性。
对无约束问题的综述

对无约束问题的综述

对无约束问题的综述
无约束问最优化问题，就是问题中无约束条件，它的数学模型为)(min x f ，无约束最优化计算方法不仅本身有着不少实际应用，而且与约束最优化计算方法有着紧密的联系：一方面有些处理无约束最优化问题的方法能直接推广应用于约束最优化问题；另一方面，还可以把一些约束最优化问题转化为无约束最优化问题来处理.无约束最化问题按维数搜索可分为一维无约束搜索方法和多维无约束最优方法，对于一维无约束搜索方法，也称为一维搜索方法，目前常见的有三点二次插值法、Fibonacci 法、黄金分割法、进退法及牛顿切线法。

其求解方法在理论上都是寻找出局部极值点，即所搜寻区域是单峰函数。

多维无约束最优化方法大多是逐次一维搜索的迭代算法.这类迭代算法可分为两类.一类不涉及导数，只用到函数值，称为直接法.另一类需要用目标函数的导函数，称为解析法.根据搜索方向的取法不同，可以有各种算法.下面主要论述一下解析型算法，解析型的算法有：梯度法：又称最速下降法.这是早期的解析法，收敛速度较慢.牛顿法：收敛速度快，但不稳定，计算也较困难.共轭梯度法：收敛较快，效果较好.变尺度法：这是一类效率较高的方法.根据秩的不同又可分为DFP 和BFGS 两种，是最常用的方法.这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点.然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止.为简单形式n )(min E x x f ∈，（n 维欧氏空间））k k k p x x ()()1(λ+=+且满足f[X(k+1)]<f[X(k)]这样逐步迭代直至满足精度条件
‖▽f[X(k+1)]‖<
ε1 (梯度绝对值<ε1)。

运筹学 无约束极值问题

运筹学 无约束极值问题


f (x) x12 16 x22的极小点。
解：取初始点x(0) (1,2)T ，于是f (x(0) ) 65, f (x) （2x1,32x2）T
f (x(0) ) (2,64)T ,为求x(1)，我们求
min f (x(0) f (x(0) )),即求min（1－2）2＋1（6 2－64）2
称为最优步长。它不但与梯度有关，而且与海赛矩
阵 H(x(k) )有关。
根据一元函数极值条件和多元复合函数求导公式，得
’()= -( f(x(k)-(k)g(k)))T g(k) =0
即
（ f(x(k+1)))T g(k) =0
或
(g(k+1))Tg(k)=0
即
（ f(x(k+1)))T f(x(k)) =0
x=x(0)+ 0 g(0)
0 >0
这里的方向g(0)和步长 0都是待定的。
为了使f(x) 的函数值在x(0)沿方向g(0)移动步长 0后有所
下降，我们将f(x)在x(0)上展开泰勒级数
f(x(0)+ 0 g(0))= f(x(0))+ 0 f(x(0) )T g(0)+o( 0 )
只要 0 f(x(0) )T g(0)<0,就可以保证f(x(0)+ 0 g(0))< f(x(0)) 若记x(1)＝ x(0)+ 0 g(0)，则 f(x(1) ) < f(x(0) ) 现在的问题就是如何方向g(0)和步长 0， 使 0 f(x(0) )T g(0)尽可能的小。 由于 f(x(0) )T g(0)＝ || f(x(0) )T ||. || g(0) ||cos ,
0
0
为方便起见，令g() （1－2）2＋1（6 2－64）2
第7讲 无约束规划

第7讲 无约束规划

4. 无约束规划无约束规划建模——引例无约束规划模型无约束规划的示意图无约束规划的性质无约束规划重要算法用MATLAB解无约束规划引例1：某城市要选定一个供应中心(供电、供水、公天然气、网络接入等)的位置，该中心向城市中由固定位置的m 个用户提供服务。

问如何确定这个中心的位置才是最合理的？解设用户位置为(a i , b i )(i =1,2,...,m )已知，而供应中心的位置是(x 1, x 2)；假设运输线路不受道路影响，只考虑直线距离，则可建立求总距离最短的数学模型为：()()∑=−+−=m i i i b x a x x x f 1222121),(min 其中：c ——运价(元/吨公里)；w i ——第i 个用户的需求量.()()∑=−+−=m i i i i b x a x w c x x f 1222121),(min 若进一步考虑各单位的用量w i 不同，而运价c 按距离计算，则可建立求总总费用最小的数学模型为：“定位问题”——厂址选择等引例2：在某些实际问题中，往往要求决策变量x 1, x 2, ..., x n 满足(或近似满足)某些平衡条件，它表现为要求x 1, x 2, ..., x n 满足方程组pj x x f n j ,,2,1 ,0),,(1L L ==即要求均方误差最小——最小二乘问题，包括线性最小二乘和非线性最小二乘问题，在数学建模中有非常重要的应用。

()∑=m j n x x f 121),,(min L 可转化为求解问题：“最小二乘问题”——解方程组无约束规划模型标准形式：()X f n R X ∈min ):(R R f n →其中()()[]X f X f n n RX R X −=∈∈ min max 转化：等高线1x 2x )(21x x f O 1x 2x 05310X 1X 2X )(0X f )(1X f >)(2X f >无约束规划的示意图多局部极小298.0=f 0=f298.0=f 唯一极小(全局极小)2122212121322)(x x x x x x x x f +−+−=⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂==∇22221222222212122122122)()(n n n n n x f x x f x x f x x f x f x x f x x f x x f x f X H X f L M L M M L L 无约束规划的性质梯度ÆT n x X f x X f x X f X f ⎟⎟⎠⎞⎜⎜⎝⎛∂∂∂∂∂∂=∇)(,,)(,)()(21L Å列向量梯度的特点：1)函数f (X )在X 处增长最快的方向，负梯度方向是函数f (X )在X 处下降最快的方向；2)梯度的模是函数最快的变化率; 3)梯度为零是驻点，极值点是驻点，驻点不一定是极值点。

实验七(无约束优化)

实验七(无约束优化)

一、实验目的1、掌握MATLAB优化工具箱的基本用法，对不同算法进行初步分析、比较。

2、练习用无约束优化方法建立和求解实际问题的模型（包括最小二乘拟合）。

二、实验容项目一：某分子由25个原子组成，并且已经通过实验测量得到了其中某些原子队之间的距离（假设在平面结构上讨论），如表所示。

请你确定每个原子的位置关系。

原子对距离原子对距离原子对距离原子对距离(4,1) 0.9607 (5,4) 0.4758 (18,8) 0.8363 (15,13) 0.5725 (12,1) 0.4399 (12,4) 1.3402 (13,9) 0.3208 (19,13) 0.7660 (13,1) 0.8143 (24,4) 0.7006 (15,9) 0.1574 (15,14) 0.4394 (17,1) 1.3765 (8,6) 0.4945 (22,9) 1.2736 (16,14) 1.0952 (21,1) 1.2722 (13,6) 1.0559 (11,10) 0.5781 (20,16) 1.0422(5,2) 0.5294 (19,6) 0.6810 (13,10) 0.9254 (23,16) 1.8255 (16,2) 0.6144 (25,6) 0.3587 (19,10) 0.6401 (18,17) 1.4325 (17,2) 0.3766 (8,7) 0.3351 (20,10) 0.2467 (19,17) 1.0851 (25,2) 0.6893 (14,7) 0.2878 (22,10) 0.4727 (20,19) 0.4995(5,3) 0.9488 (16,7) 1.1346 (18,11) 1.3840 (23,19) 1.2277 (20,3) 0.8000 (20,7) 0.3870 (25,11) 0.4366 (24,19) 1.1271(21,3) 1.1090 (21,7) 0.7511 (15,12) 1.0307 (23,21) 0.7060 (24,3) 1.1432 (14,8) 0.4439 (17,12) 1.3904 (23,22) 0.8025问题分析：每个原子的位置都是未知的，在坐标系中只有相对的位置参数，不妨固定原子1的坐标为（0，0）。

非线性规划—无约束问题

非线性规划—无约束问题

则称X * 为f(X )在上的全局极小点。 f(X *)为全局极小值。 若对于所有 X X * ，且X ，都有
f(X ) f(X *) 则称X * 为f(X )在上的严格全局极小点。 f(X *)为严格全局极小值。
如果将上述不等式反向 ，即可得到局部极 大值与全局极大值的定 义。
第11页
定理1：极值存在的必要条件
两边乘以“1”。 第5页
非线性规划的图解问题
图解法可以给人以直观概念，当只有两个自变量时， 非线性规划也像线性规划一样，可以利用图解法。
例：min f (X ) (x1 2)2 (x2 1)2
x1 x2 5 0
A
若令目标函数f ( X）＝C
C为某一常数。
则f ( X）＝C就代表一条曲线，
一般地，解非线性规划问题要比解线性规划问 题困难的多，因为它不像解线性规划问题有单纯形 法这一通用的方法，非线性规划目前还没有适合于 各种问题的一般算法，各个方法都有自己特定的应 用范围。
第2页
非线性规划模型
例：某金属制品厂要加工一批容积为1米3的长方 形容器，按规格要求，上下底的材料为25元/m2，侧 面的材料为40元/m2，试确定长、宽、高的尺寸，使 这个容器的成本最低。
设容器的长为x1，宽为x2，则高为1/x1x2。根据题意 得：
min
f
( x1 ,
x2 )
50 x1x2
80[
1 x1x2
( x1
x2 )]
x1, x2 0
第3页
例：某公司经营两种设备，第一种设备每件售价30元， 第二种设备每件售价为450元，根据统计，售出一件 第一种设备所需营业时间平均为0.5小时，第二种设备 为（2＋0.25x2）小时，其中x2是第二种设备的售出数 量，已知该公司在这段时间内的总营业时间为800小 时，试决定使其营业额最大的营业计划。
无约束问题的数值解

无约束问题的数值解

无约束问题的数值解
无约束问题是指没有任何条件限制的数学问题。

对于这类问题，通常需要使用数值方法来求解。

常用的数值方法包括：
1. 精确法：通过暴力枚举的方式，找到问题的精确解。

这种方法适用于问题规模较小的情况，但是当问题规模增大时，计算量会变得非常大。

2. 迭代法：通过不断迭代，逼近问题的解。

这种方法适用于问题规模较大的情况，但是收敛速度可能会比较慢。

3. 随机化算法：通过引入随机性，来寻找问题的解。

这种方法适用于一些难以求解的问题，但是收敛速度也可能比较慢。

4. 神经网络方法：通过构建神经网络模型，来逼近问题的解。

这种方法适用于一些复杂的非线性问题，但是需要大量的训练数据和计算资源。

需要注意的是，对于不同的问题，选择不同的数值方法可能会产生不同的效果。

因此，在实际应用中，需要根据具体的问题特点和计算要求，选择适合的数值方法。

清华大学数学实验_实验7无约束优化1

清华大学数学实验_实验7无约束优化1

实验7无约束优化生医0 王言2010013212【实验目的】1．掌握用MATLAB优化工具箱的基本用法，对不同算法进行初步分析、比较。

2．练习用无约束优化方法建立和求解实际问题模型（包括最小二乘拟合）。

【实验内容】5. 某分子由25个原子组成，并且已经通过实验测量得到了其中某些原子对之间的距离（假设在平面结构上讨论），如表7.8所示。

请你确定每个原子的位置关系。

表7.8解：分析与建模： 不妨设第i 点坐标为，其中第一个点坐标为，问题即为求达到最小值的解，则问题转化为无约束优化：，其中：Matlab 代码如下：M 文件：function f=location(x,d);x(1)=0; x(26)=0;f(1)=(x(4))^2+(x(29))^2-d(1)^2; f(2)=(x(12))^2+(x(37))^2-d(2)^2; f(3)=(x(13))^2+(x(38))^2-d(3)^2; f(4)=(x(17))^2+(x(42))^2-d(4)^2; f(5)=(x(21))^2+(x(36))^2-d(5)^2;f(6)=(x(5)-x(2))^2+(x(30)-x(27))^2-d(6)^2; f(7)=(x(16)-x(2))^2+(x(41)-x(27))^2-d(7)^2; f(8)=(x(17)-x(2))^2+(x(42)-x(27))^2-d(8)^2; f(9)=(x(25)-x(2))^2+(x(50)-x(27))^2-d(9)^2; f(10)=(x(5)-x(3))^2+(x(30)-x(28))^2-d(10)^2; f(11)=(x(20)-x(3))^2+(x(45)-x(28))^2-d(11)^2; f(12)=(x(21)-x(3))^2+(x(46)-x(28))^2-d(12)^2; f(13)=(x(24)-x(3))^2+(x(49)-x(28))^2-d(13)^2;),(i i y x )0,0(),(11=y x ∑--+-ji ij j i j id y y x x,2222])()[(∑--+-ji ij j i j i d y y x x ,2222])()[(min ⎥⎦⎤⎢⎣⎡=252432252432y y y y x x x x xf(14)=(x(5)-x(4))^2+(x(30)-x(29))^2-d(14)^2;f(15)=(x(12)-x(4))^2+(x(37)-x(29))^2-d(15)^2;f(16)=(x(24)-x(4))^2+(x(49)-x(29))^2-d(16)^2;f(17)=(x(8)-x(6))^2+(x(33)-x(31))^2-d(17)^2;f(18)=(x(13)-x(6))^2+(x(38)-x(31))^2-d(18)^2;f(19)=(x(19)-x(6))^2+(x(44)-x(31))^2-d(19)^2;f(20)=(x(25)-x(6))^2+(x(50)-x(31))^2-d(20)^2;f(21)=(x(8)-x(7))^2+(x(33)-x(32))^2-d(21)^2;f(22)=(x(14)-x(7))^2+(x(39)-x(32))^2-d(22)^2;f(23)=(x(16)-x(7))^2+(x(41)-x(32))^2-d(23)^2;f(24)=(x(20)-x(7))^2+(x(45)-x(32))^2-d(24)^2;f(25)=(x(21)-x(7))^2+(x(46)-x(32))^2-d(25)^2;f(26)=(x(14)-x(8))^2+(x(39)-x(33))^2-d(26)^2;f(27)=(x(18)-x(8))^2+(x(43)-x(33))^2-d(27)^2;f(28)=(x(13)-x(9))^2+(x(38)-x(34))^2-d(28)^2;f(29)=(x(15)-x(9))^2+(x(40)-x(34))^2-d(29)^2;f(30)=(x(22)-x(9))^2+(x(47)-x(34))^2-d(30)^2;f(31)=(x(11)-x(10))^2+(x(36)-x(35))^2-d(31)^2;f(32)=(x(13)-x(10))^2+(x(38)-x(35))^2-d(32)^2;f(33)=(x(19)-x(10))^2+(x(44)-x(35))^2-d(33)^2;f(34)=(x(20)-x(10))^2+(x(45)-x(35))^2-d(34)^2;f(35)=(x(22)-x(10))^2+(x(47)-x(35))^2-d(35)^2;f(36)=(x(18)-x(11))^2+(x(43)-x(36))^2-d(36)^2;f(37)=(x(25)-x(11))^2+(x(50)-x(36))^2-d(37)^2;f(38)=(x(15)-x(12))^2+(x(40)-x(37))^2-d(38)^2;f(39)=(x(17)-x(12))^2+(x(42)-x(37))^2-d(39)^2;f(40)=(x(15)-x(13))^2+(x(40)-x(38))^2-d(40)^2;f(41)=(x(19)-x(13))^2+(x(44)-x(38))^2-d(41)^2;f(42)=(x(15)-x(14))^2+(x(40)-x(39))^2-d(42)^2;f(43)=(x(16)-x(14))^2+(x(41)-x(39))^2-d(43)^2;f(44)=(x(20)-x(16))^2+(x(45)-x(41))^2-d(44)^2;f(45)=(x(23)-x(16))^2+(x(48)-x(41))^2-d(45)^2;f(46)=(x(18)-x(17))^2+(x(43)-x(42))^2-d(46)^2;f(47)=(x(19)-x(17))^2+(x(44)-x(42))^2-d(47)^2;f(48)=(x(20)-x(19))^2+(x(45)-x(44))^2-d(48)^2;f(49)=(x(23)-x(19))^2+(x(48)-x(44))^2-d(49)^2;f(50)=(x(24)-x(19))^2+(x(49)-x(44))^2-d(50)^2;f(51)=(x(23)-x(21))^2+(x(48)-x(46))^2-d(51)^2;f(52)=(x(23)-x(22))^2+(x(48)-x(47))^2-d(52)^2;end主文件：d=[0.9607 0.4399 0.8143 1.3765 1.2722 0.5294 0.6144 0.3766 0.6893 0.94880.8000 1.1090 1.1432 0.4758 1.3402 0.7006 0.4945 1.0559 0.6810 0.3587 0.3351 0.2878 1.1346 0.3870 0.7511 0.4439 0.8363 0.3208 0.1574 1.2736 0.5781 0.92540.6401 0.2467 0.4727 1.3840 0.4366 1.0307 1.3904 0.5725 0.7660 0.4394 1.09521.0422 1.8255 1.4325 1.0851 0.4995 1.2277 1.1271 0.7060 0.8052]';x0=[zeros(1,1),ones(1,24),zeros(1,1),ones(1,24)];[x,norm1]=lsqnonlin(@location,x0,[],[],[],d);xnorm1运行结果x =Columns 1 through 100 0.1925 1.3539 0.8210 0.6910 1.11740.7470 0.9049 0.4348 1.0297Columns 11 through 200.4536 -0.4604 0.7045 0.5812 0.3521 0.12710.4361 1.5726 1.3993 0.9407Columns 21 through 300.2642 1.5103 0.9707 0.3404 0.8626 00.9330 1.6449 0.5483 0.9793Columns 31 through 401.3858 1.2540 0.9459 0.6425 1.2754 1.24390.2204 0.4145 1.2862 0.8651Columns 41 through 500.3007 1.2927 0.4275 0.7643 0.9601 1.83231.3226 1.9180 1.0981 1.1166norm1 =0.0316改变初值：x0=[zeros(1,2),ones(1,22),zeros(1,2),ones(1,22)];结果是：x =Columns 1 through 100 0.8285 0.5479 0.8712 0.8802 1.5054 0.7397 1.0346 0.0074 1.3647Columns 11 through 201.0327 -0.4290 0.4778 0.6123 0.1921 1.4165 0.6782 1.3906 1.2647 1.0951Columns 21 through 300.0732 1.0151 0.1085 0.7128 1.4644 1.00001.5112 0.0944 0.5051 0.9830Columns 31 through 400.8822 0.7628 0.6989 1.0033 0.7893 1.2701 0.3074 0.6494 0.9350 1.1299Columns 41 through 501.6768 1.1750 -0.0659 0.2455 0.6879 1.1010 0.3047 0.4028 1.2196 1.2407Columns 51 through 521.0000 1.0000norm1 =0.2330这一组norm1较大，因此第一组初值较好。

无约束问题的最优化条件知识讲解

无约束问题的最优化条件知识讲解

➢ 优点：迭代过程简单，使用方便。
➢ 最速下降法的基本思想：从当前点xk出发寻找 使得目标函数下降最快的方向，即负梯度方向。
➢ 关于梯度的复习： ☺梯度是一个向量。n元函数f(x1 ,x2 ,…xn)在点
x处的梯度为： (f ,f ,...,f )T
x1 x2 xn
☺梯度的方向与函数f 的等值线的一个法线方 向相同，从较低的等值线指向较高的等值线。
设 xk 是当前迭代点， 2 f (xk ) 正定，
f
(x)
f
(xk ) f
(xk )T
(x
xk )
1 (x 2
xk )T 2
f
(xk )(x
xk )
Q(k) (x)
f
(xk ) f
(xk )T (x xk )
1 2
(
x
xk
)T
2
f
(xk )(x xk )
令
Q(k) (x) x
0
f
( xk
无约束问题的最优化条件
一、极小点的概念
1．局部极小点 2．严格局部极小点 3．全局（总体）极小点 4．严格全局（总体）极小点。 注：在非线性规划中，大多数算法都致力于求最优化 问题的局部极小点，一般求全局极小点极为困难，仅 当问题为凸规划时，局部极小为全局极小。
二、无约束问题最优性条件
定理 1（一阶必要条件）若 x 是局部极小点，则 f (x) 0 。 定理 2（二阶必要条件）若 x 是局部极小点，则 f (x) 0 ，
继续迭代,计算可得 d(1) 1 1,11 5,x(2) 10.2.8
f( x ( 2 ) ) ( 0 .2 , 0 .2 ) T ,|| f( x ( 2 ) ) || 0 .2 8 2 8,
《无约束极值问题》课件

《无约束极值问题》课件

《无约束极值问题》PPT 课件
人们在探索并解决无约束极值问题上付出了大量努力，因为这是数学、物理、 经济以及机器学习等领域中最具有挑战性的问题之一。
什么是无约束极值问题
定义和概念
无约束极值问题是在没有约束条件下，寻找多元函数的最大值或最小值。
举例说明
例如，在机器学习领域，我们需要寻找一组参数，使得模型对数据的拟合误差最小。
大规模数据集中的无约束极值 问题
2
出了更高的要求，因为它们通常涉及 到高维权重空间。
由于现在拥有更大规模的数据集，如 何在更短的时间内解决无约束极值问
题是当前的研究方向之一。
挑战与机会
无约束极值问题的解决可以为现实世界中的许多领域带来极大的机会，也面临许多挑战。
常见的求解方法
1
牛顿法
2
，需要计算函数的一阶以及二
阶导数。
3
梯度下降法
该方法通过计算函数梯度，并将参数 移动到梯度方向的相反方向上，来搜 索函数极值。
拟牛顿法
该方法是基于牛顿法的一种迭代算法， 用来求解高维非线性优化问题，通常 比牛顿法更加鲁棒。
应用场景
机器学习中的无约束极 值问题
例如，在神经网络学习中，我 们需要优化权重和偏移，来最 小化模型的损失函数。
经济学中的无约束极值 问题
例如，在微观经济学中，我们 需要找到一个解决方案，以最 大化厂商的利润。
物理学中的无约束极值 问题
例如，在理论物理学中，我们 需要用最小作用量原理来描述 自然界中许多现象。
解决无约束极值问题的挑战
1 局部极值点
很多情况下，算法会陷入局部最优，并无法找到全局最优解。
2 收敛性问题
一些算法可能需要大量的时间和额外的控制来保证其收敛性。
实验7 无约束优化

实验7 无约束优化


在第一幅图中，最大的函数值的数量级已到 107，说明画图范围取得过大，函数值为 0 的,点在该图中均呈现一平面， 故需要缩小自变量的范围再绘图。 修改程序 guancha1.m 如下。
[x,y]=meshgrid(-0.1:0.01:1.1,-0.1:0.01:1.1);%选定x,y范围均为[-0.1,1.1] z=((x.*y).^2).*((1-x).^2).*((1-x-y.*((1-x).^5)).^2); mesh(x,y,z);%画三维图像 title('图2.1 三维图像'); pause contour(x,y,z,200) %画等高线 title('图2.2 等高线 ')
2.2 matlab 求解 2.2.1 输出三维图像和等高线，直观观察最优解所在位置 首先，先让 MATLAB 输出的三维图像，直观地观察最优解的大致范围。程序 guancha.m 如下。
[x,y]=meshgrid(-2:0.01:2,-2:0.01:2);%选定x,y范围均为[-2,2] z=((x.*y).^2).*((1-x).^2).*((1-x-y.*((1-x).^5)).^2); mesh(x,y,z);%画三维图像 title('图2.1 三维图像'); pause contour(x,y,z,30) %画等高线 title('图2.2 等高线 ')
3.42E-08 3.41E-08 2.21E-05 3.42E-08 3.41E-08 2.21E-05
2.42E-17 2.40E-17 1.00E-11 2.42E-17 2.40E-17 1.00E-11
18 18 99 18 18 99
2.比较分析梯度与数值梯度对结果的影响 首先计算 f(x)的梯度

无约束问题的符号解

无约束问题的符号解
对于无约束优化问题，符号解（symbolic solution）是指通过符号计算的方法来求解优化问题的解。

这种方法适用于一些难以直接求解的优化问题，例如非线性优化问题、约束优化问题等。

在无约束优化问题中，符号解通常指的是通过符号计算来求解问题的最优解。

具体来说，符号计算是一种使用符号运算来处理数学问题的技术。

它可以使用符号代数来表示变量、函数、表达式等，并且可以对它们进行符号运算和推理。

对于无约束优化问题，符号解的方法通常包括以下几个步骤：
1.定义变量：将问题的决策变量表示为符号变量，例如x1, x2, ... xn。

2.建立优化模型：使用符号表达式来表示问题的目标函数和约束条
件。

3.求解最优解：使用符号计算的方法来求解目标函数的极值点，并
判断是否满足约束条件。

4.提取解：如果找到了最优解，则将其提取出来，以符号形式表示。

需要注意的是，符号解方法通常适用于小规模问题或问题结构较为简单的情况。

对于大规模或复杂的问题，可能需要使用数值方法或其他优化算法来求解。

关于无约束最优化问题的信赖域解法

关于无约束最优化问题的信赖域解法
一、引言
无约束优化问题是实际工程中最常见的问题之一。

这类问题虽然形式比较简单，但是对于某些大规模的或者非线性很强的问题，求解它们仍然是有相当难度的。

无约束问题的算法大致分成两类：一类在计算过程中要用到目标函数的导数，另一类则只要求目标函数值。

本文中所讲述的信赖域法，与牛顿法、最速下降法、共轭梯度法一样，同属于第一类方法。

二、信赖域法的主要内容
2.1 信赖域法的基本思想
虽然信赖域法与最速下降法等同属于一大类，但是在基本思想上还是有所不同。

其他几种方法的基本策略是：给定点x(k)后，定义搜索方向d(k),再从x(k)出发沿d(k)作一维搜索，信赖域法则不然，下面重点阐述一下其基本思想：首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。

然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。

若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭代。

否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。

如此重复下去，直到满足迭代终止条件。

三、 运用信赖域法求解具体问题
考虑无约束问题
432
1122min
()45f x x x x x =++-+。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
f ( X *) xn
T
(7-10)
或 上式中
f ( X *) f ( X *) f ( X *)= x2 x1
f(X*)=0
(7-11)
(7-12)
2014年11月11日星期二
7.1 基本概念
7.1.2 极由数学分析知道， f(X)的方向为f(X)的等值面(等 值线)的法线(在X处）方向，沿这个方向函数值增加最快。 满足式 (7-10)或式 (7-11)的点称为平稳点或驻点，在 区域内部，极值点必为平稳点，但平稳点不一定是极值 点。
2014年11月11日星期二
7.1 基本概念
7.1.1 引言
a11 J a n1 a1n ann
8
其中，元素aij是第i个属性的重要性与第j个属性的重要性 之比。 现需从判断矩阵求出各属性的权重 wi(i=1,2,…,n) 。 为了使求出的权向量 W=(w1,w2,…,wn)T 在最小二乘意义上能最好的反映判断矩阵的估计，由 aij wi/wj，可得
2014年11月11日星期二
7.1 基本概念
7.1.2 极值问题
18
设 f(X) 为定义在 n 维欧氏空间 En 的某一区域 R 上的 n 元实函数，其中 X=(x1,x2,…,xn)T 。对于 X * R ，如果存 在某个 >0，使所有与X*的距离小于 的X R(即X R 且 ||X-X*||< ) 均满足不等式 f(X) f(X*) ，则称 X * 为 f(X) 在 R 上的局部极小点 ( 或相对极小点 ) ， f(X*) 为局部极小 值。若对于所有 X X* 且与 X * 的距离小于 的 X R ， f(X)>f(X*) ，则称 X* 为 f(X) 在 R 上的严格局部极小点， f(X*)为严格局部极小值。
2014年11月11日星期二
7.1 基本概念
7.1.2 极值问题
20
2. 极值点存在的条件 现说明极值点存在的必要条件和充分条件。 定理1 (必要条件)：设R是n维欧氏空间En上的某一 开集，f(X)在R上有一阶连续偏导数，且在点X* R取得 局部极值，则必有
f ( X *) f ( X *) x1 x2 f ( X *) 0 xn
2014年11月11日星期二
7.1 基本概念
7.1.2 极值问题
19
若点X* R，而对于所有X R都有f(X) f(X*)，则 称 X* 为 f(X) 在 R 上的全局极小点， f(X*) 为全局极小值。 若对于所有X R且X X* ，都有f(X)>f(X*)，则称X*为 f(X)在R上的严格全局极小点， f(X*)为严格全局极小值。 如将上述不等式反向，即可得到相应的极大点和极 大值的定义。 下面仅就极小点及极小值加以说明，而且主要研究 局部极小。
2014年11月11日星期二
7.1 基本概念
7.1.1 引言
6
设该公司计划经营第一种产品x1件，第二种产品 x2 件。根据题意，其营业额为 f(X)=30x1+450x2 由于服务时间的限制，该计划必须满足 0.5x1+(2+0.25x2) x2 800 此外，这个问题还应满足 x1 0, x2 0 如此，得到这个瓿的数学模型如下：
2014年11月11日星期二
7.1 基本概念
7.1.2 极值问题
22
定理 2( 充分条件 ) 设 R 是 n 维欧氏空间 En 上的某一开 集 ， f(X) 在 R 上 有 二 阶 连 续 偏 导 数 ， X * R ， 若 f(X*)=0，且对任何非零向量Z En有 (7-13) ZTH(X*)Z>0 则X*为f(X)的严格局部极小点 此处H(X*)为f(X)在点X*处的海赛(Hesse)矩阵：
非线性规划
在科学管理和其他领域中，很多实际问题可以归结 为线性规划问题，其目标函数和约束条件都是自变量的 一次函数。但是，还有另外一些问题，其目标函数和(或) 约束条件很难用线性函数来表达。如果目标函数或约束 条件中含有非线性函数，就称这种规划问题为非线性规 划问题。解这种问题要用非线性规划的方法以。由于很 多实际问题要求进一步精确化以及电子计算机的发展， 使非线性规划在近几十年来得以快速发展。目前，它已 成为运筹学的重要分支之一，并在最优设计、管理科学、 系统控制等许多领域得到越来越广泛的应用。
2014年11月11日星期二
7.1 基本概念
7.1.1 引言
min f (aij w j wi )2
i 1 j 1 n n
9
n wi 1 s .t . i 1 w 0 i
例1的目标函数为自变量的线性函数，但其第一个约 束条件却是自变量的二次函数。因而它是非线性规划问 题。例2的目标函数是自变量的非线性函数，所以它也是 非线性规划问题。
2014年11月11日星期二
7.1 基本概念
7.1.1 引言
hi ( X ) 0 hi ( X ) 0
12
因而，也可将非线性规划的数学模型写成以下形式
min f ( X )
(7-4) (7-5)
s.t .
g j ( X ) 0( j 1, 2,..., l )
2014年11月11日星期二
2014年11月11日星期二
7.1 基本概念
7.1.2 极值问题
17
在高等数学课程中，已学过一元函数和多元函数的 极值问题，现仅扼要说明如下 。 1. 局部极值和全局极值 由于线性规划的目标函数为线性函数，可行域为凸 集，因而求出的最优解就是在整个可行域的全局最优解。 非线性规划则不然，有时求出的某个解虽是一部分可行 域中 的极值点，但却并不一定是整个可行域上的全局最 优解。
其中， X=(x1,x2,…,xn)T 是 n 维欧氏空间 En 中的点 ( 向量 ) ， f(X)为目标函数，hi(X) 0，gj(X) 0为约束条件。
2014年11月11日星期二
7.1 基本概念
7.1.1 引言
11
由于 maxf(X)=-min[-f(X)] ，当需使目标函数极大化 时，只需使其负值极小化即可。因而仅考虑目标函数极 小化，这无损于一般性。 若某约束条件是“ ”不等式时，仅需用“ -1 ”乘 该约束的两端，始可将这个约束变为“ ”的形式。 由于等式约束 hi(X)=0 等价于下述两个不等式约束：
2 f ( X *) 2 f ( X *) 2 f ( X *) 2 x x x x x 1 1 2 1 n 2 f ( X *) 2 f ( X *) 2 f ( X *) 2 H ( X *) x2x1 x 2 x 2 x n 2 2 2 f ( X *) f ( X *) f ( X *) 2 x x x x x 月211日星期二 n 1 年11 n n 2014
2014年11月11日星期二
非线性规划
一般来说，由于非线性函数的复杂性，解非线性规 划问题要比解线性规划问题困难得多。而且，也水像线 性规划有单纯形法等通用方法，非线性规划目前没有适 于各种问题的一般算法，各个方法都有自己特定的适用 范围。这是需要人们更深入地进行研究的一个领域。 为了叙述方便，用大写字母代表 n 维欧氏空间中的 向量(点)，而以相应的小字字母代表该向量的分量(点的 坐标)。此外，所用到的向量，均规定为列向量。
2014年11月11日星期二
7.1 基本概念
7.1.1 引言
2. 非线性规划问题的数学模型 非线性规划数学模型的一般形式是：
min f ( X )
10
(7-1)
(7-2) (7-3)
hi ( X ) 0(i 1, 2,..., m) gi ( X ) 0( j 1, 2,..., l )
2014年11月11日星期二
7.1 基本概念
7.1.1 引言
max f ( X ) 30 x1 450 x2
7
2 0.5 x1 2 x2 0.25 x2 800 s.t . x1 0, x2 0 例2 为了进行多属性问题(假设有n个属性)的综合评 价，就需要确定每个属性的相对重性，即求它们的权重。 为此将各属性的重要性 ( 对评价者或决策者而言 ) 进行两 两比较从而得出如处判断矩阵
2014年11月11日星期二
7.1 基本概念
7.1.1 引言
16
在这个例子中，约束条件(6-7)式对最优解是有影响 的。 现若以 (7-9) h(X)=x1+x2-6 0 代替约束条件(7-7)式，则非线性规划问题(7-6)式、(7-9) 式的最优解是 x1=x2=2 ，即图 6-1 中的 C点 ( 这时 f(X)=0) 。 由于最优点位于可行域的内部，故对这个问题的最优解 来说，约束(7-9)式事实上是不起作用的。在求这个问题 的最优解时，可不考虑约束条件(7-9)式，就相汉于没有 这个约束一样。
(7-14)
7.1 基本概念
7.1.2 极值问题
23
需要指出，定理2中的充分条件(7-13)式并不是必要 的。可以举出这样的例子：X*是f(X)的极小点，但却不 满足条件(7-13)式。例如 f(X)=x*，它的极小点是 x*=0， 但 f ’’(x*)=0，这不满足(7-13)式。 二次型是X=(x1,x2,…,xn)T的二次齐次函数，它在研 究非线性最优化中具有重要作用。现考虑二次型 Z T HZ 。 若对于任意Z 0(即Z的元素不全为0)，二次型ZTHZ的值 总是正的，即ZTHZ >0，则称该二次型是正定的；若对 于任意Z 0总有ZTHZ 0，则称其为半正定；若对于任 意 Z 0 总有 Z T HZ <0 ，则称其为负定；若对于任意
7.1 基本概念
7.1.1 引言
2. 非线性规划问题的图示