多面体投影算子广义雅克比的高效计算及拓展

doi:10.15960/j.cnki.issn.1007-6093.2023.04.004

运筹学学报 ›› 2023, Vol. 27 ›› Issue (4): 61-80.doi: 10.15960/j.cnki.issn.1007-6093.2023.04.004

多面体投影算子广义雅克比的高效计算及拓展

邓生翔¹, 郦旭东¹^,*()

1. 复旦大学大数据学院, 上海 200433

收稿日期:2023-05-02 出版日期:2023-12-15 发布日期:2023-12-07
通讯作者: 郦旭东 E-mail:lixudong@fudan.edu.cn
基金资助:
国家自然科学基金(12271107);国家自然科学基金(62141407);上海市科学技术委员会基础研究重点项目(21JC1400600)

Fast computation of generalized Jacobians of polyhedral projectors and extensions

Shengxiang DENG¹, Xudong LI¹^,*()

1. School of Data Science, Fudan University, Shanghai 200433, China

Received:2023-05-02 Online:2023-12-15 Published:2023-12-07
Contact: Xudong LI E-mail:lixudong@fudan.edu.cn
About author:郦旭东, E-mail: lixudong@fudan.edu.cn

摘要/Abstract

摘要：

多面体投影算子在现代优化中发挥着基础且重要的作用。近年来，多面体投影算子的广义雅可比的计算研究取得了重要进展。本文回顾了一些关于多面体投影和它们的广义雅可比的理论和计算发展。类似的分析也扩展到了强凸二次规划问题的解映射和连续分段仿射正则化函数的邻近映射。

关键词: 多面体投影, 广义雅可比, 非光滑分析

Abstract:

Polyhedral projectors play a fundamental role in modern optimization. Recently, significant progress has been made in the computation of generalized Jacobians of projectors over polyhedral convex sets. In this paper, we review some recent theoretical and computational developments related to polyhedral projectors and their generalized Jacobians. Similar analyses are also extended to solution mappings of strongly convex quadratic programming problems, and proximal mappings of continuous piecewise affine regularizers.

Key words: projection onto polyhedrons, generalized Jacobians, nonsmooth analysis

中图分类号:

O224

邓生翔, 郦旭东. 多面体投影算子广义雅克比的高效计算及拓展[J]. 运筹学学报, 2023, 27(4): 61-80.

Shengxiang DENG, Xudong LI. Fast computation of generalized Jacobians of polyhedral projectors and extensions[J]. Operations Research Transactions, 2023, 27(4): 61-80.

参考文献 43

1	Gurobi Optimization LLC. Gurobi optimizer reference manual[EB/OL]. (2021-12-01)[2023-05-01]. https://www.gurobi.com/documentation/9.5/refman/index.html.
2	WrightS J,NowakR D,FigueiredoM A T.Sparse reconstruction by separable approximation[J].IEEE Transactions on Signal Processing,2009,57(7):2479-2493. doi: 10.1109/TSP.2009.2016892
3	HagerW W,ZhangH.Projection onto a polyhedron that exploits sparsity[J].SIAM Journal on Optimization,2016,26(3):1773-1798. doi: 10.1137/15M102825X
4	WangY,ShenC,ZhangL H,et al.Proximal gradient/semismooth newton methods for projection onto a polyhedron via the duality-gap-active-set strategy[J].Journal of Scientific Computing,2023,97(1):3. doi: 10.1007/s10915-023-02302-6
5	Ghaoui L E, Viallon V, Rabbani T. Safe feature elimination for the Lasso and sparse supervised learning problems[DB/OL]. (2011-05-08)[2023-05-01]. https://doi.org/10.48550/arXiv.1009.4219.
6	NdiayeE,FercoqO,GramfortA,et al.Gap safe screening rules for sparsity enforcing penalties[J].The Journal of Machine Learning Research,2017,18(1):4671-4703.
7	MalickJ.A dual approach to semidefinite least-squares problems[J].SIAM Journal on Matrix Analysis and Applications,2004,26(1):272-284. doi: 10.1137/S0895479802413856
8	QiH,SunD.A quadratically convergent Newton method for computing the nearest correlation matrix[J].SIAM Journal on Matrix Analysis and Applications,2006,28(2):360-385. doi: 10.1137/050624509
9	DykstraR L.An algorithm for restricted least squares regression[J].Journal of the American Statistical Association,1983,78(384):837-842. doi: 10.1080/01621459.1983.10477029
10	HighamN J.Computing the nearest correlation matrix-a problem from finance[J].IMA Journal of Numerical Analysis,2002,22(3):329-343. doi: 10.1093/imanum/22.3.329
11	LiX,SunD,TohK C.On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope[J].Mathematical Programming,2020,179(1-2):419-446. doi: 10.1007/s10107-018-1342-9
12	HarauxA.How to differentiate the projection on a convex set in hilbert space[J].Journal of the Mathematical Society of Japan,1977,29(4):615-631.
13	PangJ S.Newton's method for B-Differentiable equations[J].Mathematics of Operations Research,1990,15(2):311-341. doi: 10.1287/moor.15.2.311
14	Robinson S M. Implicit B-Differentiability in Generalized Equations[M]. University of Wisconsin-Madison, Mathematics Research Center, 1985.
15	PangJ S,RalphD.Piecewise smoothness, local invertibility, and parametric analysis of normal maps[J].Mathematics of Operations Research,1996,21(2):401-426. doi: 10.1287/moor.21.2.401
16	ClarkeF H.Optimization and Nonsmooth Analysis[M].Philadelphia:Society for Industrial and Applied Mathematics,1990.
17	HanJ,SunD.Newton and quasi-Newton methods for normal maps with polyhedral sets[J].Journal of Optimization Theory and Applications,1997,94(3):659-676. doi: 10.1023/A:1022653001160
18	LiX,SunD,TohK C.On efficiently solving the subproblems of a level-set method for fused Lasso problems[J].SIAM Journal on Optimization,2018,28(2):1842-1866. doi: 10.1137/17M1136390
19	LinM,LiuY J,SunD,et al.Efficient sparse semismooth Newton methods for the clustered Lasso problem[J].SIAM Journal on Optimization,2019,29(3):2026-2052. doi: 10.1137/18M1207752
20	LuoZ,SunD,TohK C,et al.Solving the OSCAR and SLOPE models using a Semismooth Newton-Based augmented Lagrangian method[J].Journal of Machine Learning Research,2019,20(106):1-25.
21	ZhangY,ZhangN,SunD,et al.An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems[J].Mathematical Programming,2020,179(1-2):223-263. doi: 10.1007/s10107-018-1329-6
22	FacchineiF,PangJ.Finite-dimensional Variational Inequalities and Complementarity Problems[M].New York:Springer,2003.
23	MifflinR.Semismooth and semiconvex functions in constrained optimization[J].SIAM Journal on Control and Optimization,1977,15(6):959-972. doi: 10.1137/0315061
24	KummerB.Newton's method for non-differentiable functions[J].Advances in Mathematical Optimization,1988,45,114-125.
25	QiL,SunJ.A nonsmooth version of Newton's method[J].Mathematical Programming,1993,58(1-3):353-367. doi: 10.1007/BF01581275
26	SunD,SunJ.Semismooth matrix-valued functions[J].Mathematics of Operations Research,2002,27(1):150-169. doi: 10.1287/moor.27.1.150.342
27	BonnansJ F,ShapiroA.Perturbation Analysis of Optimization Problems[M].New York:Springer Science & Business Media,2013.
28	Hiriart-UrrutyJ B,StrodiotJ J,NguyenV H.Generalized Hessian matrix and second-order optimality conditions for problems with $C^{1, 1}$ data[J].Applied Mathematics and Optimization,1984,11(1):43-56. doi: 10.1007/BF01442169
29	ZhaoX Y,SunD,TohK C.A Newton-CG augmented Lagrangian method for semidefinite programming[J].SIAM Journal on Optimization,2010,20(4):1737-1765. doi: 10.1137/080718206
30	FischerA,KanzowC.On finite termination of an iterative method for linear complementarity problems[J].Mathematical Programming,1996,74,279-292.
31	SunD,HanJ,ZhaoY.On the finite termination of the damped-Newton algorithm for the linear complementarity problem[J].Acta Mathematica Applicatae Sinica,1998,21(1):148-154.
32	RockafellarR T.Convex Analysis[M].Princeton:Princeton University Press,1997.
33	TibshiraniR,SaundersM,RossetS,et al.Sparsity and smoothness via the fused Lasso[J].Journal of the Royal Statistical Society Series B: Statistical Methodology,2005,67(1):91-108. doi: 10.1111/j.1467-9868.2005.00490.x
34	FriedmanJ,HastieT,HöflingH,et al.Pathwise coordinate optimization[J].The Annals of Applied Statistics,2007,1,302-332.
35	SunD.The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications[J].Mathematics of Operations Research,2006,31(4):761-776. doi: 10.1287/moor.1060.0195
36	WuB,DingC,SunD,et al.On the Moreau-Yosida regularization of the vector $k$-norm related functions[J].SIAM Journal on Optimization,2014,24(2):766-794. doi: 10.1137/110827144
37	ZengX,FigueiredoM A T.Decreasing weighted sorted ${\ell_1} $ regularization[J].IEEE Signal Processing Letters,2014,21(10):1240-1244. doi: 10.1109/LSP.2014.2331977
38	BogdanM,Van Den BergE,SabattiC,et al.SLOPE—Adaptive variable selection via convex optimization[J].The Annals of Applied Statistics,2015,9(3):1103-1140.
39	SuW,CandesE.SLOPE is adaptive to unknown sparsity and asymptotically minimax[J].The Annals of Statistics,2016,44(3):1038-1068.
40	Zeng X, Figueiredo M A T. The ordered weighted $\ell_1 $ norm: Atomic formulation, projections, and algorithms[EB/OL]. (2015-04-10)[2023-05-01]. https://doi.org/10.48550/arXiv.1409.4271.
41	Nesterov Y E. A method for solving the convex programming problem with convergence rate $ O (1/k^2) $[C]//Proceedings of the USSR Academy of Sciences, 1983, 269(3): 543-547.
42	LiQ,LiX.Fast projection onto the ordered weighted $\ell_1$ norm ball[J].Science China Mathematics,2020,65,869-886.
43	Davis D. An $ O (n\log (n)) $ algorithm for projecting onto the ordered weighted $\ell_1 $ norm ball[EB/OL]. (2015-06-26)[2023-05-01]. https://doi.org/10.48550/arXiv.1505.00870.

[1]	韩艳丽, 高岩. 基于生存理论的线性微分博弈系统识别域的判别[J]. 运筹学学报, 2016, 20(1): 105-111.
[2]	李丽花, 高岩, 王隔霞. 一类变结构动态系统的非光滑最优性条件[J]. 运筹学学报, 2013, 17(3): 65-72.
[3]	高岩. 非光滑非线性互补问题的牛顿法[J]. 运筹学学报, 2011, 15(2): 53-58.

多面体投影算子广义雅克比的高效计算及拓展

Fast computation of generalized Jacobians of polyhedral projectors and extensions

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 43

相关文章 3

编辑推荐

Metrics

本文评价