English

运筹学学报 >

2023 , Vol. 27 >Issue 4: 61 - 80

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.04.004

 

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

  • 邓生翔 ,
  • 郦旭东
展开
  • 1. 复旦大学大数据学院, 上海 200433

收稿日期: 2023-05-02

  网络出版日期: 2023-12-07

基金资助

国家自然科学基金(12271107);国家自然科学基金(62141407);上海市科学技术委员会基础研究重点项目(21JC1400600)

收起

Fast computation of generalized Jacobians of polyhedral projectors and extensions

  • Shengxiang DENG ,
  • Xudong LI
Expand
  • 1. School of Data Science, Fudan University, Shanghai 200433, China
郦旭东, E-mail: lixudong@fudan.edu.cn

Received date: 2023-05-02

  Online published: 2023-12-07

Fold

摘要

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

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

本文引用格式

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

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

参考文献

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.
3 HagerW W,ZhangH.Projection onto a polyhedron that exploits sparsity[J].SIAM Journal on Optimization,2016,26(3):1773-1798.
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.
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]. 
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.
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.
9 DykstraR L.An algorithm for restricted least squares regression[J].Journal of the American Statistical Association,1983,78(384):837-842.
10 HighamN J.Computing the nearest correlation matrix-a problem from finance[J].IMA Journal of Numerical Analysis,2002,22(3):329-343.
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.
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.
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.
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.
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.
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.
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.
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.
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.
26 SunD,SunJ.Semismooth matrix-valued functions[J].Mathematics of Operations Research,2002,27(1):150-169.
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.
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.
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.
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.
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.
37 ZengX,FigueiredoM A T.Decreasing weighted sorted ${\ell_1} $ regularization[J].IEEE Signal Processing Letters,2014,21(10):1240-1244.
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]. 
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]. 
Options
文章导航

/

〈 〉