On the Efficient Computation of Proximal Operators of Affine-Constrained Nonconvex Functions

References

• [1] Absil PA, Mahony R, Sepulchre R (2009) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Google Scholar
• [2] Bertsekas DP (1971) Control of uncertain systems with a set-membership description of the uncertainty. PhD thesis, Massachusetts Institute of Technology.Google Scholar
• [3] Bonnans JF, Shapiro A (2013) Perturbation Analysis of Optimization Problems (Springer, New York).Google Scholar
• [4] Borg I, Groenen PJ (2005) Modern Multidimensional Scaling: Theory and Applications (Springer, New York).Google Scholar
• [5] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Machine Learn. 3(1):1–122.Crossref, Google Scholar
• [6] Chu DI, Brown HC, Chu MT (2003) On least squares Euclidean distance matrix approximation and completion. Technical Rep., Department of Mathematics, North Carolina State University.Google Scholar
• [7] Deng S, Li X, Zhang Y (2025) Alternating minimization for square root principal component pursuit. INFORMS J. Comput., ePub ahead of print December 16, https://dx.doi.org/10.1287/ijoc.2025.1105.Google Scholar
• [8] Deutsch F, Li W, Ward JD (1997) A dual approach to constrained interpolation from a convex subset of Hilbert space. J. Approx. Theory 90(3):385–414.Crossref, Google Scholar
• [9] Ding C, Sun D, Sun J, Toh KC (2018) Spectral operators of matrices. Math. Programming 168(1):509–531.Crossref, Google Scholar
• [10] Drusvyatskiy D, Ioffe AD, Lewis AS (2015) Transversality and alternating projections for nonconvex sets. Found. Comput. Math. 15(6):1637–1651.Crossref, Google Scholar
• [11] Fan J, Li R (2001) Variable selection via nonconcave penalized likelihood and its oracle properties. J. Amer. Statist. Assoc. 96(456):1348–1360.Crossref, Google Scholar
• [12] Glunt W, Hayden TL, Raydan M (1993) Molecular conformations from distance matrices. J. Comput. Chem. 14(1):114–120.Crossref, Google Scholar
• [13] Gong P, Zhang C, Lu Z, Huang J, Ye J (2013) A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems. Sanjoy D and David M, eds. Internat. Conf. Machine Learn. (PMLR, New York), 37–45. Google Scholar
• [14] Hiriart-Urruty JB, Lemaréchal C (2004) Fundamentals of Convex Analysis (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• [15] Hong M, Luo ZQ, Razaviyayn M (2016) Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26(1):337–364.Crossref, Google Scholar
• [16] Hou D, Tang T, Toh KC (2025) A low-rank augmented Lagrangian method for doubly nonnegative relaxations of mixed-binary quadratic programs. Oper. Res. 74(3):1626–1647.Link, Google Scholar
• [17] Hou D, Tang T, Toh KC (2025) A low-rank augmented Lagrangian method for Polyhedral–SDP and Moment–SOS relaxations of polynomial optimization. Preprint, submitted December 6, https://arxiv.org/abs/2512.06359.Google Scholar
• [18] Hou D, Tang T, Toh KC (2026) RiNNAL+: A Riemannian ALM solver for SDP–RLT relaxations of mixed-binary quadratic programs. Math. Programming Comput. 18(3):679–735.Crossref, Google Scholar
• [19] Ioffe AD, Outrata JV (2008) On metric and calmness qualification conditions in subdifferential calculus. Set-Valued Anal. (Oxford) 16(2):199–227.Crossref, Google Scholar
• [20] Krislock N, Wolkowicz H (2012) Euclidean distance matrices and applications. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 879–914.Crossref, Google Scholar
• [21] Kruger AY, Luke DR, Thao NH (2017) About subtransversality of collections of sets. Set. Valued Var. Anal. 25(4):701–729.Crossref, Google Scholar
• [22] Kyrillidis A, Becker S, Cevher V, Koch C (2013) Sparse projections onto the simplex. Sanjoy D, David M, eds. Internat. Conf. Machine Learn. (PMLR, New York), 235–243.Google Scholar
• [23] Leobacher G, Steinicke A (2021) Existence, uniqueness and regularity of the projection onto differentiable manifolds. Ann. Glob. Anal. Geom. (Dordr). 60(3):559–587.Crossref, Google Scholar
• [24] Levy AB, Poliquin RA, Rockafellar RT (2000) Stability of locally optimal solutions. SIAM J. Optim. 10(2):580–604.Crossref, Google Scholar
• [25] Lewis AS, Malick J (2008) Alternating projections on manifolds. Math. Oper. Res. 33(1):216–234.Link, Google Scholar
• [26] Li X, Lin M, Toh KC (2025) On the B-subdifferential of proximal operators of affine-constrained ℓ1 regularizer. Preprint, submitted October 8, https://arxiv.org/abs/2510.06642.Google Scholar
• [27] Li X, Xiu N, Luo Z (2019) Low-rank matrix optimization over affine set. Preprint, submitted December 6, https://arxiv.org/abs/1912.03029.Google Scholar
• [28] Markovsky I, Usevich K (2014) Software for weighted structured low-rank approximation. J. Comput. Appl. Math. 256:278–292.Crossref, Google Scholar
• [29] Mishra B, Meyer G, Sepulchre R (2011) Low-rank optimization for distance matrix completion. 2011 50th IEEE Conf. Decision Control Eur. Control Conf. (IEEE, Piscataway, NJ), 4455–4460.Google Scholar
• [30] Parikh N, Boyd S (2014) Proximal algorithms. Found. Trends Optim. 1(3):127–239.Crossref, Google Scholar
• [31] Poliquin R, Rockafellar R (1996) Prox-regular functions in variational analysis. Trans. Amer. Math. Soc. 348(5):1805–1838.Crossref, Google Scholar
• [32] Poliquin RA, Rockafellar RT (2010) A calculus of prox-regularity. J. Convex Anal. 17(1):203–210.Crossref, Google Scholar
• [33] Poliquin R, Rockafellar R, Thibault L (2000) Local differentiability of distance functions. Trans. Amer. Math. Soc. 352(11):5231–5249.Crossref, Google Scholar
• [34] Qi HD, Yuan X (2014) Computing the nearest Euclidean distance matrix with low embedding dimensions. Math. Programming 147(1):351–389.Crossref, Google Scholar
• [35] Rockafellar RT (1970) Convex Analysis, Princeton Mathematical Series (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [36] Rockafellar RT (1974) Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM J. Control. 12(2):268–285.Crossref, Google Scholar
• [37] Rockafellar RT (1976) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97–116.Link, Google Scholar
• [38] Rockafellar RT (1976) Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5):877–898.Crossref, Google Scholar
• [39] Rockafellar RT, Wets RJ (1998) Variational Analysis (Springer, New York).Crossref, Google Scholar
• [40] Schost É, Spaenlehauer PJ (2016) A quadratically convergent algorithm for structured low-rank approximation. Found. Comput. Math. 16(2):457–492.Crossref, Google Scholar
• [41] Tang T, Toh KC (2024) Solving graph equipartition SDPs on an algebraic variety. Math. Programming 204(1):299–347.Crossref, Google Scholar
• [42] Wang J, Hu L (2025) Solving low-rank semidefinite programs via manifold optimization. J. Sci. Comput. 104(1):33.Crossref, Google Scholar
• [43] Wang Y, Yin W, Zeng J (2018) Global convergence of admm in nonconvex nonsmooth optimization. J. Sci. Comput. 78(1):29–63.Crossref, Google Scholar
• [44] Wang Y, Deng K, Liu H, Wen Z (2023) A decomposition augmented Lagrangian method for low-rank semidefinite programming. SIAM J. Optim. 33(3):1361–1390.Crossref, Google Scholar
• [45] Wei Z, Théra M, Yao JC (2024) Subtransversality and strong CHIP of closed sets in Asplund spaces. Set. Valued Var. Anal. 32(3):23.Crossref, Google Scholar
• [46] Xiao N, Tang T, Wang S, Toh KC (2025) An exact penalty approach for equality constrained optimization over a convex set. Preprint, submitted May 5, https://arxiv.org/pdf/2505.02495.Google Scholar
• [47] Xiao N, Wang S, Tang T, Toh KC (2025) A quadratically convergent alternating projection method for nonconvex sets. Preprint, submitted November 28, https://arxiv.org/abs/2511.22916.Google Scholar