Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2016, Vol. 45(2): 299-308
Convergence Analysis of an Infeasible Quasi-Newton Bundle Method for Nonsmooth Convex Programming

SHEN Jie1,GUO Fangfang2, PANG Liping2

1. 辽宁师范大学数学学院, 大连, 辽宁, 116029;
2. 大连理工大学数学科学学院, 大连, 辽宁, 116024
1. School of Mathematics, Liaoning Normal University, Dalian,Liaoning, 116029, P. R. China;
2. School of Mathematical Sciences,Dalian University of Technology, Dalian,Liaoning, 116024, P. R. China

收稿日期: 2014-09-06
出版日期: 2016-03-10
2016, Vol. 45(2): 299-308
DOI: 10.11845/sxjz.2014139b

[446 KB]

    /   /   推荐

摘要 利用改进函数将非光滑凸约束优化问题转化成无约束优化问题, 构造了一个具有迫近形式的不可行拟牛顿束算法. 值得注意的是, 随着每次迭代的进行, 该算法的无约束优化子问题的目标函数可能发生改变(取零步目标函数不改变, 取下降步则更新目标函数), 为此必须做必要的调整以保证算法的收敛性. 本文主要采用了 Sagastizàbal 和 Solodov 的不可行束方法的思想, 在每个迭代点不一定是原始可行的情况下, 得出了算法产生序列的每一个聚点是原问题最优解的收敛性结果. 进一步, 本文针对目标函数强凸情况下的 BFGS 拟牛顿算法, 得到了全局收敛结果中保证拟牛顿矩阵有界的条件以及迭代序列的R-线性收敛结果.
Abstract:By utilizing the improvement function, we change the nonsmooth convex constrained optimization into an unconstrained optimization, and construct an infeasible quasi-Newton bundle method with proximal form. It should be noted that the objective function being minimized in unconstrained optimization subproblem may vary along the iterations (it does not change if the null step is made, otherwise it is updated to a new function). It is necessary to make some adjustment in order to obtain the convergence result. We employ the main idea of infeasible bundle method of Sagastizà|bal and Solodov, and under the circumstances that each iteration point may be infeasible for primal problem, we prove that each cluster point of the sequence generated by the proposed algorithm is the optimal solution to the original problem. Furthermore, for BFGS quasi-Newton algorithm with strong convex objective function, we obtain the condition which guarantees the boundedness of quasi-Newton matrices and the R-linear convergence of the iteration points.
PACS:  O221.2  
基金资助:国家自然科学基金(No. 11301246, No. 11171049).
[1] Bonnans, J.F., Gilbert, J.Ch., Lemarê}chal, C. and Sagastizàbal, C.A., A family of variable metric proximal methods, Math. Program., 1995, 68(1/2/3): 15-47.
[2] Byrd, R.H. and Nocedal, J., A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer. Anal., 1989, 26(3): 727-739.
[3] Fletcher, R. and Leyffer, S., A bundle filter method for nonsmooth nonlinear optimization, Numerical Analysis Report NA/195, Dundee: Department of Mathematics, The University of Dundee, 1999.
[4] Frangioni, A., Generalized bundle methods, SIAM J. Optim., 2002, 13(1): 117-156.
[5] Hare, W. and Sagastizàbal, C.A., A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 2010, 20(5): 2442-2473.
[6] Kiwiel, K.C., Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Math., Vol. 1133, Berlin: Springer-Verlag, 1985.
[7] Kiwiel, K.C., Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization, Math. Program., 1991, 52(1/2/3): 285-302.
[8] Kiwiel, K.C., A proximal bundle method with approximate subgradient linearizations, SIAM J. Optim., 2006, 16(4): 1007-1023.
[9] Kiwiel, K.C., A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming,
SIAM J. Optim., 2006, 17(4): 1015-1034.
[10] Lemarê}chal, C. and Sagastizàbal, C.A., Practical aspects of the Moreau-Yosida regularization: Theoretical preliminaries, SIAM J. Optim., 1997, 7(2): 367-385.
[11] Mifflin, R., An algorithm for constrained optimization with semismooth functions, Math. Oper. Res., 1977, 2(2): 191-207.
[12] Mifflin, R., A modification and an extension of Lemarechal's algorithm for nonsmooth minimization, In: Nondifferential and Variational Techniques in Optimization (Sorensen, D.C.and Wets, R.J.-B. eds.), Math. Program. Stud., Vol. 17, Berlin: Springer-Verlag, 1982, 77-90.
[13] Mifflin, R., Sun, D.F. and Qi, L.Q., Quasi-Newton bundle-type methods for nondifferentiable convex optimization, SIAM J. Optim., 1998, 8(2): 583-603.
[14] Oliveira, W. and Solodov, M., A doubly stabilized bundle method for nonsmooth convex optimization, 2013,\_HTML/2013/04/3828.html.
[15] Pironneau, O. and Polak, E., Rate of convergence of a class of methods of feasible directions, SIAM J. Numer. Anal., 1973, 10(1): 161-174.
[16] Sagastizábal, C.A. and Solodov, M., An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter, SIAM J. Optim., 2005, 16(1): 146-169.
[1] 唐国吉, 李延恕. Banach空间中强伪单调变分不等式解的唯一性和稳定性[J]. 数学进展, 2018, 47(3): 455-462.
[2] 杨怡光. 数值最优化的弧搜索方法[J]. 数学进展, 2017, 46(2): 161-170.
[3] 王月虎. 带上下界均衡问题解的存在性及H ?lder连续性[J]. 数学进展, 2016, 45(5): 778-786.
[4] 刘金魁, 杜祥林. 非线性单调方程组的三项无导数投影算法[J]. 数学进展, 2018, 47(4): 624-634.
Full text



首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录

© 2015-2017 北京大学图书馆 .