大规模非凸不可分优化问题的分裂序列二次规划算法

数学物理学报 ›› 2023, Vol. 43 ›› Issue (4): 1284-1296.

大规模非凸不可分优化问题的分裂序列二次规划算法

简金宝(),林惠(),马国栋^*()

广西民族大学数学与物理学院, 广西应用数学中心, 广西混杂计算与集成电路设计分析重点实验室南宁 530006

收稿日期:2022-09-20 修回日期:2023-02-20 出版日期:2023-08-26 发布日期:2023-07-03
通讯作者: 马国栋 E-mail:jianjb@gxu.edu.cn;lh092561@163.com;mgd2006@163.com
作者简介:简金宝, E-mail: jianjb@gxu.edu.cn;|林惠,E-mail: lh092561@163.com
基金资助:
国家自然科学基金(12261008);广西自然科学基金(2020GXNSFDA238017);广西民族大学相思湖青年学者创新团队(2022GXUNXSHQN04);广西高等学校千名中青年骨干教师培育计划资助

A Splitting Sequence Quadratic Programming Algorithm for the Large-Scale Nonconvex Nonseparable Optimization Problems

Jian Jinbao(),Lin Hui(),Ma Guodong^*()

College of Mathematics and Physics, Center for Applied Mathematics of Guangxi, Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Guangxi Minzu University, Nanning 530006

Received:2022-09-20 Revised:2023-02-20 Online:2023-08-26 Published:2023-07-03
Contact: Guodong Ma E-mail:jianjb@gxu.edu.cn;lh092561@163.com;mgd2006@163.com
Supported by:
NSFC(12261008);NSFGX(2020GXNSFDA238017);Xiangsihu Young Scholars Innovative Research Team of Guangxi Minzu University(2022GXUNXSHQN04);Guangxi Scholarship Fund of Guangxi Education Department

摘要/Abstract

摘要：

该文研究了目标函数和约束函数带不可分结构的大规模非凸优化问题, 提出了一个新的分裂序列二次规划算法. 首先, 借助分裂算法思想将传统二次规划 (QP) 子问题的增广拉格朗日问题分解为两个小规模 QP 子问题, 通过求解小规模QP 子问题产生改进的搜索方向. 其次, 以增广拉格朗日函数作效益函数, 通过 Armijo 线搜索产生下一个迭代点. 在较为温和的条件下, 获得新算法的全局收敛性. 最后, 对该算法进行了数值实验, 验证了算法的有效性.

关键词: 非凸不可分优化, 分裂算法, 序列二次规划, 全局收敛性

Abstract:

In this paper, the large-scale nonconvex optimization problems with nonseparable structure of objective function and constraint function are discussed, a new splitting sequence quadratic programming algorithm is proposed. Firstly, the idea of splitting algorithm is embedded into solving the quadratic programming (QP) subproblem approximating the discussed problem, then the QP subproblem is split into two small-scale QPs. Secondly, by taking the augmented Lagrangian function as the merit function, the next iteration point is generated by the Armijo line search. Under the mild conditions, the global convergence of the proposed algorithm is obtained. Finally, some numerical results are reported, which preliminarily show that the proposed algorithm is promising.

Key words: Nonconvex nonseparable optimization, Splitting algorithm, Sequential quadratic programming, Global convergence

中图分类号:

O221

简金宝,林惠,马国栋. 大规模非凸不可分优化问题的分裂序列二次规划算法[J]. 数学物理学报, 2023, 43(4): 1284-1296.

Jian Jinbao,Lin Hui,Ma Guodong. A Splitting Sequence Quadratic Programming Algorithm for the Large-Scale Nonconvex Nonseparable Optimization Problems[J]. Acta mathematica scientia,Series A, 2023, 43(4): 1284-1296.

图/表 2

参考文献 23

[1]	Douglas J, Rachford Jr H H. On the numerical solution of the heat conduction problem in two and three space variables. Transactions of the American Mathematical Society, 1956, 82(2): 421-439 doi: 10.1090/tran/1956-082-02
[2]	Peaceman D W, Rachford Jr H H. The numerical solution of parabolic and elliptic differential equations. Journal of the Society for Industrial and Applied Mathematics, 1955, 3: 28-41 doi: 10.1137/0103003
[3]	Wang F H, Cao W F, Xu Z B. Convergence of multi-block Bregman ADMM for nonconvex composite problems. Science China Information Sciences, 2018, 61: 1-12
[4]	Wang F H, Xu Z B, Xu H K. Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems. arXiv preprint arXiv: 1410.8625, 2014
[5]	Guo K, Han D R, Wu T T. Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints. International Journal of Computer Mathematics, 2017, 94(8): 1653-1669 doi: 10.1080/00207160.2016.1227432
[6]	Chao M T, Zhang Y, Jian J B. An inertial proximal alternating direction method of multipliers for nonconvex optimization. International Journal of Computer Mathematics, 2021, 98(6): 1199-1217 doi: 10.1080/00207160.2020.1812585
[7]	简金宝, 刘鹏杰, 江羡珍. 非凸多分块优化部分对称正则化交替方向乘子法. 数学学报 (中文版), 2021, 64(6): 1005-1026
	Jian J B, Liu P J, Jiang X Z. A partially symmetric regularized alternating direction method of multipliers for nonconvex multi-block optimization. Acta Mathematica Sinica, Chinese Series, 2021, 64(6): 1005-1026
[8]	Jia Z H, Gao X, Cai X J, Han D R. Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization Problems. Journal of Optimization Theory and Applications, 2021, 188(1): 1-25 doi: 10.1007/s10957-020-01782-y
[9]	Li G Y, Pong T K. Global convergence of splitting methods for nonconvex composite optimization. SIAM Journal on Optimization, 2015, 25(4): 2434-2460 doi: 10.1137/140998135
[10]	王娇浪, 方东辉. 一类非凸约束优化问题的近似最优性条件及其混合型对偶. 数学物理学报, 2022, 42A(3): 651-660
	Wang J L, Fang D H. Approximate optimality conditions and mixed type duality for a class of non-convex optimization problems. Acta Mathematica Scientia, 2022, 42A(3): 651-660
[11]	Hong M Y, Luo Z Q. Razaviyayn M. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization, 2016, 26(1): 337-364 doi: 10.1137/140990309
[12]	Guo K, Han D R, Wu T T. Convergence of ADMM for optimization problems with nonseparable nonconvex objective and linear constraints. Pacific Journal of Optimization, 2018, 14: 489-506
[13]	Liu Q H, Shen X Y, Gu Y T. Linearized ADMM for nonconvex nonsmooth optimization with convergence analysis. IEEE Access, 2019, 7: 76131-76144 doi: 10.1109/Access.6287639
[14]	刘鹏杰, 简金宝, 许佳伟, 马国栋. 非凸不可分优化线性近似Bregman 型 Peaceman-Rachford 分裂算法. 数学学报 (中文版), 2023, 66(1): 75-94
	Liu P J, Jian J B, Xu J W, Ma G D. A linear approximation Bregman-type Peaceman-Rachford splitting method for nonconvex nonseparable optimization. Acta Mathematica Sinica, Chinese Series, 2023, 66(1): 75-94
[15]	Wilson R B. A Simplicial Method for Concave Programming[D]. Cambridge: Graduate School of Business Administration, Harvard University, 1963
[16]	Jian J B. A superlinearly convergent implicit smooth SQP algorithm for mathematical programs with nonlinear complementarity constraints. Computational Optimization and Applications, 2005, 31(3): 335-361 doi: 10.1007/s10589-005-3230-5
[17]	简金宝. 光滑约束优化快速算法:理论分析与数值实验. 北京: 科学出版社, 2010
	Jian J B. Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments. Beijing: Science Press, 2010
[18]	Huang M X, Pu D G. A trust-region SQP method without a penalty or a filter for nonlinear programming. Journal of Computational and Applied Mathematics, 2015, 281: 107-119 doi: 10.1016/j.cam.2014.12.021
[19]	Jian J B, Chao M T, Jiang X Z, Han D L. On the convexity and existence of solutions to quadratic programming problems with convex constraint. Pacific Journal of Optimization, 2019, 15(1): 9145-9155
[20]	Jian J B, Zhang C, Liu P J. A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization. Acta Mathematica Scientia, 2023, 43B(1): 1-24
[21]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法. 运筹学学报, 2018, 22(2): 79-92
	Jian J B, Lao Y X, Chao M T, Ma G D. ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization. Operations Research Transactions, 2018, 22(2): 79-92
[22]	Jian J B, Liu P J, Yin J H, Zhang C, Chao M T. A QCQP-based splitting SQP algorithm for two-block nonconvex constrained optimization problems with application. Journal of Computational and Applied Mathematics, 2021, 390(1): 113368 doi: 10.1016/j.cam.2020.113368
[23]	Hock W, Schittkowski K. Tests Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems. Berlin, Heidelbeg, New York: Springer-Verlag, 1981, 187