第十章+可行方向法

可行方向法基本算法考虑线性规划问题： Min (),{|()0,1,2,...}{n j f X X R E R X g X j l ∈⊂=≥= 设()k X 是它的一个可行解，但不是要求的极小点，为了求它的极小点或近似极小点，应在()k X 点的可行下降方向中选取某一方向()k D ，并确定步长k λ，使得 (1)()k k k k X X D R λ+=+∈(1)()()()k k f X f X +<若满足精度要求，迭代停止，(1)k X +就是所求的点。

否则，从(1)k X +出发继续进行迭代。

直到满足要求为止。

上述这种方法称为可行方向法。

设()k x 点的起作用约束集非空，为求()k x 点的可行下降方向，可由下述不等式组确定响亮D ：()()()0()0,k T k T i f X D g X D j J ⎧⎪⎨⎪⎩∇<∇>∈ 这等价于由下面的不等式组求向量D 和实数η：()()k T f X D η∇≤()(),i k T g X D j J η-∇≤∈0η<现使()()k T f X D ∇和()()i k T g X D -∇（对所有j J ∈）的最大值极小化（必须同时限制向量D 的模），即可将上述选取搜索方向的工作，转换为求解下述线性规划问题：Min η()()k T f X D η∇≤()()(),()k i k T g X D j J X η-∇≤∈11,1,2,3,..i d i n -≤≤=式中(1,2,3,...,)i d i n =为向量D 的分量。

在上式中加入最后一个限制条件，位的是使该线性规划有有限最优解；由于我们的目的在于寻找搜索方向D ，只需知道D 的各分量的相对大小即可。

将上述线性规划的最优解记为()(,)k k D η，如果求出的0k η=，说明在()k X 点不存在可行下降方向，在()()k j g X ∇（此处()()k j J X ∈）线性无关的条件下，()k X 为一K-T 点，若解出0k η<，则得到可行下降方向()k D ，这就是我们所要的所搜方向。

最优化可行方向法最优化问题是数学中的一类重要问题，目标在于找到使得目标函数取得最大或最小值的变量取值。

可行方向法是一种常用的最优化算法，它通过在每个迭代步骤中确定一个可行方向，并将变量值沿该方向进行调整，逐步逼近最优解。

可行方向法的核心思想是从当前解的邻域中选择一个可以改进目标函数的方向。

具体而言，它通过计算目标函数的梯度（或是次梯度）来确定一个可行方向，并沿该方向对解进行调整。

这个过程可以反复迭代，直到满足终止条件为止。

在可行方向法中，选择合适的可行方向是一个关键问题。

一种常用的方法是梯度下降法，它使用目标函数的梯度方向作为可行方向，以减小目标函数的值。

另一种常用的方法是牛顿法，它使用目标函数的海森矩阵（Hessian Matrix）作为可行方向，以更快地逼近最优解。

可行方向法的具体步骤如下：1.初始化变量的取值。

2.计算目标函数在当前解的梯度或次梯度。

3.判断是否满足终止条件。

如果满足，结束迭代，输出当前解；否则，继续下面的步骤。

5.根据可行方向，计算变量的调整量。

6.更新变量的取值。

7.转到步骤2可行方向法的收敛性分析是一个重要的研究课题。

对于一般的最优化问题，如果目标函数是Lipschitz连续可微的，并且可行解集是非空、有界的，则可行方向法在有限步后可以找到一个近似最优解。

但对于非凸问题或非平滑问题，可行方向法的收敛性可能会有所不同。

除了梯度下降法和牛顿法外，可行方向法还有其他的变种，如共轭梯度法、拟牛顿法等。

这些方法在选择可行方向和调整变量值的方式上有所差别，但其基本思想仍然是寻找使目标函数得以改进的方向。

在实际应用中，可行方向法通常结合其他算法一起使用，以充分发挥各种算法的优势。

例如，可以使用可行方向法寻找一个大致的最优解，然后再使用更精确的算法对该解进行优化。

总之，可行方向法是一种重要的最优化方法，它通过选择合适的可行方向来逼近最优解。

尽管不同的变种方法有所差异，但它们的核心思想都是通过迭代调整变量值来逐步逼近最优解。

可行方向法摘要可行方向法是求解最优化问题的重要方法，在可行方向法求解过程中，一般需要构造一个求解可行下降方向的子问题，而可行方向法的不同取决于所采用的求解可行下降方向的子问题，它具有如下特点：迭代过程中所采用的搜索方向为可行方向，所产生的迭代点列是中在可行域内，目标函数值单调下降，由此可见，很多方法都可以归入可行方向法一类，本文主要介绍Frank-Wolf 方法。

一、问题形式min ().. 0f x Ax b s t x ≥⎧⎨≥⎩ （11.1）其中A 为m n ⨯矩阵，m b R ∈，n x R ∈。

记{},0,n D x Ax b x x R =≥≥∈并设()f x 一阶连续可微。

二、算法基本思想D 是一个凸多面体，任取0x D ∈，将()f x 在0x 处线性展开 000()()()()()T L f x f x f x x x f x ≈+∇-= 用min ().. 0L f x Ax b s t x ≥⎧⎨≥⎩ 或 0min ().. 0T f x xAx b s t x ∇≥⎧⎨≥⎩ （11.2）逼近原问题，这是一个线性规划问题，设0y D ∈是其最优解。

1）若000()()0T f x y x ∇-=，则0x 也是线性规划问题（11.2）的最优解，此时可证0x 为原问题的K-T 点。

2）若000()()0T f x y x ∇-≠，则由0y 是（11.2）的最优解，故必有0000()()T T f x y f x x ∇<∇从而 000()()0T f x y x ∇-<即00y x -为()f x 在0x 处的下降方向，沿此方向作有约束的一维搜索 00001min (())f x y x λλ≤≤+-设最佳步长因子为0λ，令100000000()(1)()x x y x y x D λλλ=+-=+-∈当λ充分小时100000001()min (())(())f x f x y x f x y x λλλ≤≤=+-≤+-00000()()()()()T f x f x y x o f x λλ=+∇-+< 用1x 取代0x ，重复以上计算过程。

基于MATLAB 可行方向法求极值的实现姓名：xxx学号：xxx（北京理工大学机械与车辆学院车辆工程，北京 100081）摘要：在工程实际的优化设计中，随着设计变量数和约束条件数的增加，随机方向搜索法和复合形法等直接优化解法的求解效率会偏低。

可行方向法，顾名思义，一种始终在可行域内寻找下降方向的搜索法，以其收敛速度快、效果好的优点已成为求解约束非线性问题的一种有代表性的直接解法，同时也是求解大型约束优化问题的主要方法之一。

本文将简单介绍可行方向法的数学思想，采用线性规划法和约束最优步长法编写MATLAB 程序，最后通过算例完成对优化问题的求解。

关键字：可行方向法；MATLAB ；优化方法。

1. 可行方向法的基本数学思想1.1可行方向法的搜索策略可行方向法迭代的第一步都是从可行域的某一初始点(0)X 出发，沿负梯度(0)()f X -∇方向移至某一个或J 个起作用约束面的交集()k X 上。

以后的搜索路线和迭代计算可根据约束函数和目标函数的不同性状，分别采用以下三种不同策略继续搜索。

1）由点()k X 出发，沿可行方向作一维最优化搜索，若所得新点(1)k X +在可行域内，则再沿(1)()k f X +-∇方向作一维最优化搜索；若所得的新点不在可行域内，则将它移至约束面上再反复重复上述步骤，若(1)()k f X ε+∇≤，则停止迭代，如图1.1所示。

2）由点()k X 出发，沿可行方向作一维最优化搜索，若所得新点(1)k X +在可行域外，则沿可行方向以最大步长到达另一个约束面上一点，将该点作为迭代点(1)k X +进行反复搜索，直至满足给出的K-T 条件，如图1.2所示。

3） 沿着约束面进行搜索。

对于只具有线性约束的非线性规划问题，如图1.3所示，从点()k X 出发，沿约束面移动，在有限的几步内即可搜索到约束最优点；对于非线性约束函数，如图1.4所示情况，就是沿着约束面的切线移动，但这样将会进入非可行域，使问题变得复杂。

最速下降法：算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点。

沿负梯度方向函数值下降很快的特点，容易使认为这一定是最理想的搜索方向，然而事实证明，梯度法的收敛速度并不快．特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢。

其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象。

从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快.牛顿法：基本思想：利用目标函数的一个二次函数去近似一个目标函数，然后精确的求出这个二次函数的极小点，从而该极小点近似为原目标函数的一个局部极小点。

优点 1. 当目标函数是正定二次函数时，Newton 法具有二次终止性。

2. 当目标函数的梯度和Hesse 矩阵易求时，并且能对初始点给出较好估计时，建议使用牛顿法为宜。

缺点：1. Hesse 矩阵可能为奇异矩阵，处理办法有：改为梯度方向搜索。

共轭梯度法：优点：收敛速度优于最速下降法，存贮量小，计算简单.适合于优化变量数目较多的中等规模优化问题.缺点：变度量法：较好的收敛速度，不计算Hesse 矩阵1．对称秩1 修正公式的缺点（1）要求( ) ( ) ( ) ( ) ( ) 0 k k k T k y B s s − ≠0（2）不能保证B ( k ) 正定性的传递2．BFGS 算法与DFP 算法的对比对正定二次函数效果相同，对一般可微函数效果可能不同。

1） BFGS 算法的收敛性、数值计算效率优于DFP 算法；（2） BFGS 算法要解线性方程组，而DFP 算法不需要。

基本性质：有效集法：算法思想：依据凸二次规划问题的性质2，通过求解等式约束的凸二次规划问题，可能得到原凸二次规划问题的最优解。

有效集法就是通过求解一系列等式约束凸二次规划问题，获取一般凸二次规划问题解的方法。