A stochastic primal-dual method for a class of nonconvex constrained optimization

被引:0
作者
Lingzi Jin
Xiao Wang
机构
[1] University of Chinese Academy of Sciences,School of Mathematical Sciences
[2] Peng Cheng Laboratory,undefined
来源
Computational Optimization and Applications | 2022年 / 83卷
关键词
Nonconvex optimization; Augmented Lagrangian function; Stochastic gradient; -stationary point; Complexity; 90C30; 90C06; 65K05; 92C15;
D O I
暂无
中图分类号
学科分类号
摘要
In this paper we study a class of nonconvex optimization which involves uncertainty in the objective and a large number of nonconvex functional constraints. Challenges often arise when solving this type of problems due to the nonconvexity of the feasible set and the high cost of calculating function value and gradient of all constraints simultaneously. To handle these issues, we propose a stochastic primal-dual method in this paper. At each iteration, a proximal subproblem based on a stochastic approximation to an augmented Lagrangian function is solved to update the primal variable, which is then used to update dual variables. We explore theoretical properties of the proposed algorithm and establish its iteration and sample complexities to find an ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon$$\end{document}-stationary point of the original problem. Numerical tests on a weighted maximin dispersion problem and a nonconvex quadratically constrained optimization problem demonstrate the promising performance of the proposed algorithm.
引用
收藏
页码:143 / 180
页数:37
相关论文
共 50 条
[31]   Primal-dual accelerated gradient methods with small-dimensional relaxation oracle [J].
Nesterov, Yurii ;
Gasnikov, Alexander ;
Guminov, Sergey ;
Dvurechensky, Pavel .
OPTIMIZATION METHODS & SOFTWARE, 2021, 36 (04) :773-810
[32]   A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information [J].
Jian Lv ;
Li-Ping Pang ;
Fan-Yun Meng .
Journal of Global Optimization, 2018, 70 :517-549
[33]   A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information [J].
Lv, Jian ;
Pang, Li-Ping ;
Meng, Fan-Yun .
JOURNAL OF GLOBAL OPTIMIZATION, 2018, 70 (03) :517-549
[34]   On Iteration Complexity of a First-Order Primal-Dual Method for Nonlinear Convex Cone Programming [J].
Zhao, Lei ;
Zhu, Dao-Li .
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA, 2022, 10 (01) :53-87
[35]   A primal-dual interior point method whose running time depends only on the constraint matrix [J].
Vavasis, SA ;
Ye, YY .
MATHEMATICAL PROGRAMMING, 1996, 74 (01) :79-120
[36]   On Iteration Complexity of a First-Order Primal-Dual Method for Nonlinear Convex Cone Programming [J].
Lei Zhao ;
Dao-Li Zhu .
Journal of the Operations Research Society of China, 2022, 10 :53-87
[37]   Robust Primal-Dual Proximal Algorithm for Cooperative Localization in WSNs [J].
Zhang, Mei ;
Shen, Xiaojing ;
Wang, Zhiguo ;
Varshney, Pramod K. .
2024 27TH INTERNATIONAL CONFERENCE ON INFORMATION FUSION, FUSION 2024, 2024,
[38]   ROBUST ACCELERATED PRIMAL-DUAL METHODS FOR COMPUTING SADDLE POINTS [J].
Zhang, Xuan ;
Aybat, Necdet serhat ;
Guerbuezbalaban, Mert .
SIAM JOURNAL ON OPTIMIZATION, 2024, 34 (01) :1097-1130
[39]   BLOCK STOCHASTIC GRADIENT ITERATION FOR CONVEX AND NONCONVEX OPTIMIZATION [J].
Xu, Yangyang ;
Yin, Wotao .
SIAM JOURNAL ON OPTIMIZATION, 2015, 25 (03) :1686-1716
[40]   Duality gaps in nonconvex stochastic optimization [J].
Darinka Dentcheva ;
Werner Römisch .
Mathematical Programming, 2004, 101 :515-535