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

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

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

CLC Number:

O224

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

References

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].

[1]	HAN Yanli, GAO Yan. Determining the discriminating domain for linear differential games based on viability theory [J]. Operations Research Transactions, 2016, 20(1): 105-111.
[2]	LI Lihua, GAO Yan, WANG Gexia. Non-smooth optimality conditions for a class of dynamic systems with variable structure [J]. Operations Research Transactions, 2013, 17(3): 65-72.
[3]	GAO Yan. A Newton Method for a Nonsmooth Nonlinear　Complementarity　Problem [J]. Operations Research Transactions, 2011, 15(2): 53-58.

Fast computation of generalized Jacobians of polyhedral projectors and extensions

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments