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

Abstract

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

CLC Number:

O221

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.

Trendmd

Figures/Tables 2

References 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

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

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

Figures/Tables 2

References 23

Related Articles 15

Metrics

Comments

Recommended 10

[1]	Liu Pengjie, Wu Yanqiang, Shao Feng, Zhang Yan, Shao Hu. Two Extended HS-type Conjugate Gradient Methods with Restart Directions [J]. Acta mathematica scientia,Series A, 2023, 43(2): 570-580.
[2]	Ning Zhang,Jinkui Liu. Spectral LS-type Projection Algorithm for Solving Nonlinear Pseudo-Monotone Equations [J]. Acta mathematica scientia,Series A, 2022, 42(6): 1886-1897.
[3]	Tingwei Pan,Suxiang He. The Greedy Simplex Algorithm for Double Sparsity Constrained Optimization Problems [J]. Acta mathematica scientia,Series A, 2022, 42(3): 920-933.
[4]	Gonglin Yuan,Yulun Wu,Hongtruong Pham. A Modified HS-DY-Type Method with Nonmonotone Line Search for Image Restoration and Unconstrained Optimization Problems [J]. Acta mathematica scientia,Series A, 2022, 42(2): 605-620.
[5]	Zhibin Zhu,Yuanhang Geng. A Modified Three-Term WYL Conjugate Gradient Method [J]. Acta mathematica scientia,Series A, 2021, 41(6): 1871-1879.
[6]	Guodong Ma. Improved PRP and HS Conjugate Gradient Methods with the Strong Wolfe Line Search [J]. Acta mathematica scientia,Series A, 2021, 41(3): 837-847.
[7]	Xiaoni Chi,Rong Zeng,Sanyang Liu,Zhibin Zhu. A Regularized Nonmonotone Inexact Smoothing Newton Algorithm for Weighted Symmetric Cone Complementarity Problems [J]. Acta mathematica scientia,Series A, 2021, 41(2): 507-522.
[8]	Guodong Ma. A Strongly Convergent Generalized Gradient Projection Method for Minimax Optimization with General Constraints [J]. Acta mathematica scientia,Series A, 2020, 40(3): 641-649.
[9]	HU Chao-Ming, WAN Zhong, WANG Xu. A New Nonmonotone Spectral Conjugate Gradient Algorithm [J]. Acta mathematica scientia,Series A, 2013, 33(1): 78-88.
[10]	TANG Jing-Yong, HE Guo-Ping. A One-step Smoothing Newton Method for Second-order Cone Programming [J]. Acta mathematica scientia,Series A, 2012, 32(4): 768-778.
[11]	FENG Ting-Ting, HAN Cong-Ying, HE Guo-Ping. A Modified SQP Parallel Variable Distribution Algorithm [J]. Acta mathematica scientia,Series A, 2012, 32(2): 336-343.
[12]	Zhang Li; Zhou Weijun. On the Global Convergence of the Hager-Zhang Conjugate Gradient Method with Armijo Line Search [J]. Acta mathematica scientia,Series A, 2008, 28(5): 840-845.
[13]	Tong Xiaojiao ;He Wei. Lagrangian Globalization Projection Methods for Nonlinear Constrained Equations [J]. Acta mathematica scientia,Series A, 2008, 28(1): 96-108.
[14]	Zhou Changyin; He Guoping; Wang Yongli. An Active Constraints Identification Technique-based SSLE Algorithm and Its Convergence Analysis [J]. Acta mathematica scientia,Series A, 2007, 27(3): 535-540.
[15]	GAO Zi-You, Ren Hua-Ling, HE Guo-Ping. A New Sequential Systems of Linear Equations Algorithm Without Strict Complementary Slackness [J]. Acta mathematica scientia,Series A, 2004, 24(3): 275-284.