英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料
基于参数线性规划的非线性规划主动集算法
1、引言
虽然非线性规划的内点法由于能够有效地求解具有许多不等式约束的大规模问题而受到欢迎，但主动集法仍然是求解非线性优化问题的重要工具。与内点法相比，主动集法通常能够提供更精确的解和灵敏度信息，从而更清楚地识别出主动约束集。它们还可以更有效地利用“热启动”过程中的良好起点（例如，在解决一系列密切相关的问题时）。此外，主动集方法有时比内点方法更稳定，因为它们对初始点的选择和问题的缩放不太敏感。
由于这些原因，积极集方法仍然很流行，并且正在进行大量的改进工[3,7,10,11,14,16,24,28]。传统的顺序二次规划（sqp）方法（如[1,14,17,18]）证明了其鲁棒性和有效性，前提是问题的自由度不太大。然而，当代的大多数SQP方法的实现都需要在每个外切处形成并分解一个简化的Hessian矩阵。即使Hessian矩阵是稀疏的，简化后的Hessian通常也不会是稀疏的，因此对于自由度超过2000度的问题，这种方法通常代价高昂。
为了克服传统SQP方法的一些瓶颈，近年来又出现了所谓的“eqp”形式的顺序二次规划。这些方法不是用不等式约束来求解二次规划的子问题，而是先用辅助机制来生成主动集的估计，然后在每次迭代时求解一个等式约束的二次规划（qp），将主动集估计中的约束作为等式，暂时忽略了其他限制。Fletcher和Sainz de la Maza[12]首先提出了一种连续线性二次规划（SLQP）算法。该方法基于非线性程序在当前迭代时的线性化，通过求解线性程序（LP）来估计每次迭代时的活动集。
在本文中，我们提出了SLQP方法的一个扩展，它解决了一系列线性程序，而不是一个单一的线性程序，以估计每次迭代的活动集。这种参数线性规划方法允许我们在主动集识别阶段引入一些二次信息，以期产生更好的主动集估计。我们将这种新方法称为参数化SLQP（简称PSLQP），以区别于标准的SLQP算法。
论文的组织结构如下。在第2节中，我们简要介绍了SLQP，特别是[3,4]的方法，并讨论了这种方法的一些缺点。然后，我们在第3节中介绍了新的参数化主动集识别方法。在第4节中，我们讨论了这种新方法与梯度投影算法之间的关系。接下来，在第5节中，我们将描述具体的PSLQP实现的细节。我们提供了数值结果，将我们的参数化SLQP方法与第6节中的标准SLQP方法和梯度投影进行了比较，并与第7节中的一些最后评论进行了比较。
2.SLQP方法概述
SLQP算法首先由Fletcher和Sainz de la Maza提出[12]。最近，Chin和Fletcher[6]提出了一种基于滤波器阶跃接受机制的SLQP算法，Byrd等人[3,4]提出了一种基于信任区域的SLQP方法，该方法使用了41种惩罚方法。
与传统的顺序二次规划方法相比，SLQP方法在每次迭代时都要求解带有不等式约束的一般QP，首先求解LP估计主动集，然后求解等式约束二次规划（EQP）生成一个步骤。这种方法的一个吸引人的特点是，它避免了形成约化黑森矩阵的需要，只需要求解Lp和Eqp子问题，在大规模的情况下，这两个问题都可以有效地求解。
由于本文所介绍的方法可以看作是对SLQP的一种扩展，因此下面对SLQP作一个简要的概述是很有用的，重点介绍了[3,4]的方法。让我们编写非线性程序（NLP），我们希望将其求解为
= f（x） （1a）
subject to hi(x) = 0, i isin; E, (1b)
gi(x) ge; 0, i isin; I, (1c)
SLQP方法将在每次迭代k时，根据以下形式的一个lp，生成一个活动集估计。
nabla;f(xk)Td (2a)
subject to hi(xk) nabla;hi(xk)Td = 0, i isin; E, (2b)
gi(xk) nabla;gi(xk)Td ge; 0, i isin; I, (2c)
ǁdǁinfin; le; OLP. (2d)
k
这里，OLP 是一个（无穷范数）信任区域半径，它确保lp是有界的，并且以一种试图获得一个好的活动集估计的方式来选择。该参数在算法中起着重要作用，因为它在每次迭代中的选择都会极大地影响主动集估计的质量。Lp（2）是通过在当前迭代xk时对目标函数（1a）和约束（1b）–（1c）进行线性近似而形成的。该子问题解的线性化问题约束（2b）–（2c）被用来形成主动集估计，我们称之为工作集。由于信任域约束（2d），此子问题可能不可行。因此，我们使用41种惩罚方法来放松问题约束（2b）–（2c）。我们定义一个分段线性模型
4k(d) = f(xk) nabla;f(xk)Td nu;k |hi(xk) nabla;hi(xk)Td|
iisin;E
nu;k max(0, minus;gi(xk) minus; nabla;gi(xk)Td), （3）
iisin;E
它近似于（41）个优点函数，
phi;(xk; nu;k) = f(xk) nu;k . |hi(xk)| nu;k .(max(0, minus;gi(xk)), （4）
其中，nu;k gt; 0是一个惩罚参数。然后我们解决子问题
4k(d) （5a）
subject to ǁdǁinfin; le; OLP, (5b)
k
这总是可行的。虽然（5）是不可微的，但通过添加辅助变量和附加约束，它可以很容易地重新公式化，并作为一个平滑的、一般的lp进行求解。在[3,4]中详细描述了选择v k的过程，可能需要多次求解该lp，以在一次迭代中改变惩罚参数的试验值。一旦由LP机制设置，惩罚参数在迭代的剩余时间内保持不变。
求解线性规划生成工作集k后，通过求解等式约束的qp生成一个试算步骤。
minimize dTH(xk, lambda;k)d nabla;f(xk)Td (6a)
属于 hi(xk) nabla;hi(xk)Td = 0, i isin; E cap; Wk, (6b)
gi(xk) nabla;gi(xk)Td = 0, i isin; I cap; Wk, (6c)
ǁdǁ2 le; Ok, (6d)
式中，lambda;k表示拉格朗日乘子估计的向量，h（xk，lambda;k）是NLP（1）拉格朗日的黑森方程。信任区域约束（6D）用于处理负曲率，如果h（xk，lambda;k）在约束（6b）–（6c）定义的缩减空间中不是正定的，则可能产生负曲率。该信任域独立于LP信任域约束（5b）运行，用于确保优函数phi;（xnu;k）的下降。如果信任区域太小，可能需要放松约束（6b）–（6c），如[3]所述，以确保（6）中的约束兼容。
虽然这种标准SLQP方法的实现提供了一些令人鼓舞的结果[3]，但这种方法的一个显著缺点是，通过LP子问题（5）只使用线性信息来识别活动集。因此，许多信任域约束（2d）在LP的求解中通常是活跃的，算法的效率及其快速识别最优活动集的能力在很大程度上取决于每次迭代中 OLP的选择。虽然已经使用启发式方法来更新在实践[3]中相当有效的 OLP，但一般来说，不清楚如何在每次迭代中最好地选择这个参数。此外，对于高度非线性模型，在主动集识别阶段仅使用线性信息会导致效率低下和不准确的主动集估计。
这促使我们研究一种新的机制来估计每次迭代时的活动集，这是基于解决一系列密切相关的线性程序。该方法受当代约束优化的梯度投影方法的启发，该方法通过沿投影梯度路径最小化二次模型函数来估计活动集。同样，我们的新方法允许我们在主动集识别阶段加入一些二次信息，从而以更有效的方式选择我们的工作集。
3.主动集识别的参数LP方法
为了激励我们的新方法，我们从一个突出选择困难的例子开始，实现一个良好的主动集估计。
示例1考虑图1中所示的示例。椭圆轮廓是我们试图最小化的目标函数的轮廓，解点由x给出。有两个线性不等式约束c1和c2，其可行区域是c2上方和c1右侧的区域，如图所示。虚线框表示LP信任区域半径OLP ={1、2、3}的三个不同值，当前点由x给出。
从图1中我们可以看到，解决方案中唯一激活的约束是c1。对于 OLPle;3，LP解决方案点 xLP将位于C1和C2的交叉点，并错误地将这两个约束标识为激活。对于OLPle;1，这两个约束都位于LP信任区域之外，因此无约束被标识为活动。
c1
f
c2
x
x*
feasible region
Figure 1. LP active-set estimate for OLP = 1, 2, 3.
c1
c2
x LP
x
x *
LP
易域
图2 LP solution for OLP = 2.
为了确定正确的活动集，我们需要选择足够大的OLP来包含C1，但足够小以排除LP解决方案中的C2。例如，如图2所示，很容易看出
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[427231]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
