文摘

条件下,目标函数的值及其次梯度近似计算,我们引入一个截平面和水平束方法,尽量减少非光滑凸函数结合割平面法的思想距离控制和水平约束。该算法是基于较低和建设上多面近似模型的目标函数和计算新的迭代点解决的子问题模型采用不仅在目标函数也约束。与其他近端包方法相比,新的变体更新最优值的下界,提供额外的有用的停止测试基于最优性差距。另一个优点是,我们的算法使得区分仿射作品展览凸或凹行为相对于当前的迭代。收敛到某种平稳性点一些宽松的条件下证明了。

1。介绍

束方法家庭基于截平面法、第一次描述了在1,2),目标函数的凸性是最基本的假设。非凸包方法的扩展情况并不简单;然而,很明显,许多想法有效凸框架也有价值的非凸的治疗情况。在[3),通过结合割平面法与间接控制,最小化非光滑凸函数,提出一种迭代算法使得区分仿射作品展览一个凸或凹行为相对于当前的迭代过程,但目标函数和次梯度的确切信息是必要的。

水平束方法是另一种方法更容易实现,已经显示出令人鼓舞的数值结果4,5]。一些证据表明,约束水平束方法在一定条件下。另外,更新策略水平参数是现成的6]。

在各种真实的应用程序中,目标函数和/或它的次梯度可以昂贵的(有时是不可能的)来计算。时尤其如此是由一些优化问题;例如,。在这种情况下,必须使用近似的价值观。各种不精确的包使用近似函数值和次梯度的方法评价研究[7]。

在这项工作中,我们结合水平束法与截平面法涉及的近端控制采用不精确的目标函数最小化凸函数的信息。该算法使得区分仿射作品展览凸或凹行为相对于当前迭代点,向下转移仿射的不是任意的。本文的其余部分组织如下。部分2给出了一些初步结果,并介绍了该算法的基本思想。部分3描述了截平面和水平稳定正式包方法不准确数据最小化非光滑凸函数。部分4致力于融合算法的分析与宽松的条件比3]。部分5包含该方法的一些结论。

2。的建设模式

在本文中,我们考虑下面的无约束极小化问题: 在哪里不一定是可微的。我们假设是局部李普希茨;然后几乎在任何地方都是可微的。众所周知,在[8),在上述假设下,定义每一点广义梯度(克拉克的梯度): 在哪里是集,在哪里不是可微的,局部有界。广义梯度是戈尔茨坦的延伸次微分定义为 由戈尔茨坦(第一次描述了9]。戈尔茨坦次微分是外部和内部作为一个多功能的断断续续的和。

在整个论文中,我们假设,oracle提供了一些近似的价值观和分别的目标函数及其次梯度等 在哪里和有一些未知的错误。具体地说,一致有界;也就是说,存在这样 让是当前稳定中心;包可用的信息的集合元素: 在哪里是定义的线性化误差 和。有了这个信息,我们创建线性化 在迭代多面切割平面模型是可用的: 假设存在这样,,一致有界;也就是说,存在这样,。我们回想一下,经典的剖切面方法(1,2)最小化在每个迭代中,最小化可以用线性规划形式: 相当于解决吗 在哪里。我们将设置成两组和定义如下: 我们观察到从来都不是空的自。通过使用和,我们两个分段仿射函数定义: 事实上,可以被视为一个近似函数的区别吗。因为和,从而;它是合理的考虑近似重要的就。因此,我们引入一种信任模型: 让是一个非负标量代表我们的目标是减少多少价值在当前迭代。参数定义相应的水平。自,。然后相关的水平集和是由 我们获得搜索方向通过求解凸二次子问题后,在非负标量参数化,确保前两个约束最后约束代表的思想水平束方法: 观察到自是可行的。因此,最优值不能积极的。

的对偶问题可以书面形式 在哪里和分别是矩阵的列向量,和,和和向量的分量吗,和,,分别。和的向量组件,,,,,。的最优解有关双重优化解决方案由以下公式:

在给出的描述算法之前,我们国家的一些简单性质。

引理1。让;然后以下结论持有:(我) ;(2) ;(3) 。

证明。以来我们省略了证明可以通过模仿获得结论的证明引理2.1 [3]。

引理2。对于任何,以下的结论:(我) ;(2) ;(3) 。

证明。结论可以通过模仿获得的证明引理2.2 [3]。

3所示。算法

在本节中,我们详细的算法和给出一些评论。

算法3。我们有以下。
一步0(初始化)。以下全局参数设置:停止公差,,距离测量,血统参数,切割参数,减少参数,增加参数,水平测量参数。选择一个起点;集;oracle提供了和令人满意的假设(4)。最初的包是由一个元素这是空的,而是一个单例。自,一个下界为是可用的;集。设置迭代计数器。
一步1(第一次停止测试)。如果,然后终止。
一步2(第二次停止试验)。集。如果,然后停止。
一步3可行性检查(水平)。水平参数设置。如果水平集定义为(15)发现是空的,然后设置,回到第2步。否则设置,,。
一步4(定向)。找到解决方案的增加的价值,这样 在哪里等于的最小值如果这样的确实存在;否则设置。
一步5(包更新)。集 计算 如果,然后终止。
其他设置;步骤4。
一步6(试用点计算)。集,计算,,并设置。
一步7(插入索引)。(一)如果和,然后插入元素包的适当的值并设置。
(b),如果,然后插入元素,包的适当的值。
其他(c)找到一个标量这样满足条件和插入元素包的适当的值,在那里。

一步8(测试)。如果,转到步骤5。选择。

如果 设置新的稳定中心,,设置步骤1,去(严重的步骤)。

否则设置,,设置,进入步骤9(零步骤)。

一步9(解决或)。解决或者,同样,,获得原始和双最优解决方案和步骤6。

这是结束的算法。

一些评论算法按照以下顺序。

(一)第一步最优估计是合理的。

步骤2 (b)是另一个停止准则。意味着,,由于更新设置,它认为,对所有。如果算法3停在步骤2,我们有 这意味着是一个近似解问题(1)。如果在步骤2的规则取而代之的是对所有、算法3成为一个近似的近端包算法。

步骤4 (c)可以使用的双二次规划方法10],它可以有效地解决序列相关的子问题有不同。的建设在步骤4可能被反复求解离散增加的值或采用技术中描述的类型(11]。

(d)从来就不是一个选择的结果太小。事实上,我们注意,如果,它认为, 右边上面的不平等比,所以太小不能导致;因此,我们需要增加的价值。

(e)我们的话,一捆指数插入或在步骤7不仅仅是符号的基础上。

(f)水平约束提供了一个额外的有用的停止测试基于某种最优的差距,不是出现在截平面的方法。应该注意的是,这些额外的停止测试是有用的,像往常一样近端包方法有时“花时间”积累足够的信息来认识到一个可接受的近似解已经计算。

(g)保持大小的问题(16)可控的,包应该保持的元素数量有限,不会降低收敛。为此,通常可以使用聚合技术近端包的方法。具体来说,只有组成的模型可以减少飞机,只有两个对应新的线性化和线性化。

4所示。收敛性分析

算法收敛性分析3占所有下列情形: 对于第一种情况(26),如果停止宽容是积极的,那么该方法终止与一个近似解在有限数量的迭代。

引理4。假设水平集为无限多次是空的;然后: 和每一序列的聚点(如果存在)是一个近似解问题(1)。

证明。自,。同时,由步骤3和8;因此 这意味着,如果在迭代是空的,然后更新减少最优性差距至少的一个因素。因此如果这无限多次发生,我们有作为。此外,我们有。作为减少和有下界的吗,我们得出这样的结论: 使(29日)。让是任何的聚点,让子序列收敛于作为。然后 建立了最后的结论。

从现在开始,我们考虑的情况下为足够大。不失一般性,我们可以简单地假设对所有。为例(27)和(28我们做出以下假设:(A1)一组紧凑;(A2)对于任何,定向指令的在存在, 在哪里。

备注5。假设是一个宽松的条件比出现在[3),那里的条件是弱半光滑是必需的。

接下来,我们介绍引理6看看会发生什么如果没有真正生成新的稳定中心;即存在最后稳定中心,从那时起只有零步骤生成。

引理6。假设是最后一个稳定中心后跟零步骤序列这样和 与算法步骤6和9之间的循环。然后下面的结论。(我)存在一个索引这样,对于每个,每一个新的包插入索引和保持不变。(2)步骤7 (c)是定义良好的。(3)每当一个新包插入索引,条件持有,是新包元素相对应的次梯度。

证明。(我)的结论可以通过指出没有包指数可以插入一旦低于阈值。
(2)由于充分下降条件(23)是不满意,接下去 根据假设的不准确数据(4),中值定理存在一个标量这样 因此假设的结论。
(3)观察到的情况通过建设或保障这一事实吗 每当。

现在我们考虑的情况下无限多的血统的步骤;我们证明在第5步实现近似解或我们真的获得一个新的稳定中心。

引理7。的算法3,如果无穷下降步骤生成一个获得第5步的近似解或执行血统一步步骤8。

证明。首先我们证明算法不能为无限多次通过第5步。就像引理4.2的结果(3),我们可以获得的指数新包插入元素并且永远不会被删除。此外,当一篇文章在第五步发生的所有元素的索引是删除。考虑到(18)和约束的对偶问题,存在一个索引这样,,可以表示形式(说什么) 在哪里。但自和,我们有 导致矛盾。
接下来,我们表明,这是不可能的无限多次和血统条件(23)不满意算法步骤6和9之间的循环。索引的的通过这样一个循环,我们观察到,由引理6(我),存在一个索引这样,每一个,序列是有界的,因此收敛不减少的。此外,有界;它承认一个收敛的子序列。上面的考虑也暗示收敛到一个负值的限制,说什么。接下来,我们可以模仿的证明引理4.2 (3]表明,由引理2(3),与事实不符。

最后我们展示在有限数量的下降算法的步骤3停在一个点满足某种近似解的条件。

定理8。对于任何和、算法3停在有限数量的迭代点满足近似稳定性条件 与。

证明。假设结论不成立。它遵循从引理7对于无限多次下降的条件(23)是满意的。让稳定的中心th通道;然后和 自和,所以,在那里李普希茨常数吗在。它遵循从那是有界的距离为零。然后从引理2(3),是有界的距离为零。因此通过我们获得的限制 自,,我们有的价值,这与事实在是正的。

5。结论

在本文中,我们提出一种新的非光滑凸极小化算法采用近似的目标函数值和次梯度。它结合了割平面法,水平束方法,近端控制的想法。目的是利用好所有上述方法的性质,从而加快优化过程。此外,该算法提供了一个有用的基于最优差距停止测试,没有出现在近端包方法。而非光滑凸包方法功能,大量的仿射片似乎在某种程度上任意的转移,但在我们的论文,向下移动的使用仅限于一些特定的情况下。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者要感谢裁判的宝贵建议和有用的评论。这项研究得到了国家自然科学基金(拨款11301246,11301246,11171138)。