pith. sign in

arxiv: 1906.08922 · v2 · pith:GEULRN5Unew · submitted 2019-06-21 · 🧮 math.OC

Several classes of stationary points for rank regularized minimization problems

Yulan Liu , Shaohua Pan This is my paper

Pith reviewed 2026-05-25 19:21 UTC · model grok-4.3

classification 🧮 math.OC
keywords rank regularized minimizationstationary pointsMPECexact penaltypositive semidefinite conenormal conelow-rank solutionsoptimization
0
0 comments X

The pith

Rank-regularized minimization admits several interrelated classes of stationary points via MPEC and penalty reformulations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines multiple classes of stationary points for rank regularized minimization problems, drawing from the original formulation as well as equivalent versions such as mathematical programs with equilibrium constraints, their global exact penalties, and surrogates obtained by removing dual variables. It maps the relationships among these points in a chart that indicates which reformulation to use when searching for low-rank solutions. Additionally, it derives a weaker sufficient condition under which a local minimizer of the MPEC formulation is an M-stationary point, based on properties of the directional limiting normal cone to the graph of the normal cone operator for the positive semidefinite cone.

Core claim

Several classes of stationary points are introduced for the rank regularized minimization problem using the problem itself and its equivalent reformulations including the MPEC, the global exact penalty of the MPEC, and the surrogate from eliminating the dual part in the exact penalty. A relation chart is established among these stationary points to guide selection of reformulations for low-rank solutions. As a byproduct, a weaker condition is provided for a local minimizer of the MPEC to be M-stationary by characterizing the directional limiting normal cone to the graph of the normal cone mapping of the PSD cone.

What carries the argument

The relation chart connecting stationary points of the original rank-regularized problem to those of its MPEC reformulation, global exact penalty, and dual-eliminated surrogate; the directional limiting normal cone to the graph of the normal cone mapping of the positive semidefinite cone.

Load-bearing premise

The reformulations of the rank regularized problem as an MPEC, its global exact penalty, and the dual-eliminated surrogate preserve the correspondence of stationary points with the original problem.

What would settle it

A concrete counterexample consisting of a rank regularized problem where a stationary point in one reformulation does not match the predicted relation in the chart, or where the new condition for M-stationarity does not hold for some local minimizer.

read the original abstract

For the rank regularized minimization problem, we introduce several kinds of stationary points by the problem itself and its equivalent reformulations including the mathematical program with an equilibrium constraint (MPEC), the global exact penalty of the MPEC,the surrogate yielded by eliminating the dual part in the exact penalty. A clear relation chart is established for these stationary points, which guides the user to choose an appropriate reformulation for seeking a low-rank solution. As a byproduct, we also provide a weaker condition for a local minimizer of the MPEC to be the M-stationary point by characterizing the directional limiting normal cone to the graph of the normal cone mapping of the positive semidefinite (PSD) cone.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript introduces several classes of stationary points for rank-regularized minimization problems, defined via the original problem and its equivalent reformulations as an MPEC, the global exact penalty of that MPEC, and the surrogate obtained by eliminating the dual part of the exact penalty. It establishes an explicit relation chart among these stationarity notions (with conditions for each implication) and derives, as a byproduct, a characterization of the directional limiting normal cone to the graph of the normal-cone mapping of the PSD cone, yielding a weaker sufficient condition for an MPEC local minimizer to be M-stationary.

Significance. If the equivalences and relation chart hold under the stated conditions, the framework guides selection of reformulations for computing low-rank solutions. The normal-cone characterization is a direct contribution to variational analysis of the PSD cone and does not rely on unstated regularity assumptions.

minor comments (3)
  1. [§1] §1 (Introduction) and the relation chart: while conditions for each implication are stated, the chart itself would benefit from an accompanying table or diagram that explicitly lists the one-way and two-way implications together with the precise assumptions (e.g., constraint qualifications) under which each arrow holds.
  2. The definition of the dual-eliminated surrogate (around Eq. (3.12) or equivalent) is introduced after the exact-penalty reformulation; a short paragraph summarizing how the dual variables are eliminated and why the resulting stationarity notion is well-defined would improve readability for readers outside variational analysis.
  3. Notation: the symbol for the directional limiting normal cone (e.g., N^D or similar) is used consistently after its introduction, but the first appearance would be clearer if accompanied by a one-sentence reminder of its relation to the standard limiting normal cone.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive summary, and recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces stationary-point notions for the rank-regularized problem directly from its own formulation and from explicitly stated equivalent reformulations (MPEC, global exact penalty, dual-eliminated surrogate), then proves implication relations among them under explicitly listed conditions. The byproduct normal-cone characterization is obtained from the intrinsic properties of the PSD cone and its normal-cone mapping, without any reduction to fitted parameters, self-citations that carry the central claim, or renaming of known results. All steps are self-contained variational constructions whose validity rests on the stated assumptions rather than on circular re-use of the target conclusions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Work rests on standard properties of the positive-semidefinite cone and normal-cone mappings from variational analysis; no free parameters or invented entities are visible in the abstract.

axioms (1)
  • standard math Directional limiting normal cone to the graph of the normal cone mapping of the PSD cone admits the stated characterization
    Invoked in the byproduct result on M-stationarity (abstract, final sentence)

pith-pipeline@v0.9.0 · 5636 in / 1156 out tokens · 34916 ms · 2026-05-25T19:21:20.419920+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    S. J. Bi and S. H. Pan , Multistage convex relaxation approach to rank regularized minimizataion problems based on equivalent mathematical program with a generalized complementarity constraint, SIAM Journal on Control and Optimization, 55(2017): 2493-2518

    work page 2017

  2. [2]

    O. P. Burdakov, C. Kanzow and A. Schw artz , Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method, SIAM Journal of Optimization, 26(2016): 397-425

    work page 2016

  3. [3]

    M. A. Da venport and J. Romberg , An overview of low-rank matrix recovery from incomplete observations, IEEE Journal of Selected Topics in Signal Processing, 10(2016): 608-622

    work page 2016

  4. [4]

    C. Ding, D. F. Sun and K. C. Toh , An introduction to a class of matrix cone programming, Mathematical Programming, 144(2014): 141-179

    work page 2014

  5. [5]

    C. Ding, D. F. Sun and J. J. Ye , First order optimality conditions for mathe- matical programs with semidefinite cone complementarity constraints, Mathematical Programming, 144(2014): 141-179

    work page 2014

  6. [6]

    A. L. Dontchev and R. T. Rockafellar , Implicit Functions and Solution Map- pings, Springer Monographs in Mathematics, LLC, New York, 2009

    work page 2009

  7. [7]

    F azel, Matrix Rank Minimization with Applications, Stanford University, PhD thesis, 2002

    M. F azel, Matrix Rank Minimization with Applications, Stanford University, PhD thesis, 2002. 20

    work page 2002

  8. [8]

    F azel, H

    M. F azel, H. Hindi and S. Boyd , Log-det heuirstic for matrix rank minimiza- tion with applications to Hankel and Euclidean distance matrices, American Control Conference, 2003. Proceedings of the 2003, 3: 2156-2162

    work page 2003

  9. [9]

    F azel, T

    M. F azel, T. K. Pong, D. F. Sun and P. Tseng , Hankel matrix rank mini- mization with applications to system identification and realization, SIAM Journal on Matrix Analysis, 34(2013): 946-977

    work page 2013

  10. [10]

    M. L. Flegel and C. Kanzow , On M-stationary points for mathematical pro- grams with equilibrium constraints, Journal of Mathematical Analysis and Applica- tions, 310(2005): 286-302

    work page 2005

  11. [11]

    Gfrerer and D

    H. Gfrerer and D. Klatte , Lipschitz and Holder stability of optimization prob- lems and generalized equations, Mathematical Programming, 158(2016): 35-75

    work page 2016

  12. [12]

    Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Transactions on Information Theory, 57(2011): 1548-1566

    D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Transactions on Information Theory, 57(2011): 1548-1566

    work page 2011

  13. [13]

    A. D. Ioffe and J. V. Outrata , On metric and calmness qualification conditions in subdifferential calculus, Set-Valued Analysis, 16(2008): 199–227

    work page 2008

  14. [14]

    A. J. King and R. T. Rockafellar , Sensitivity analysis for nonsmooth gener- alized equations, Mathematical Programming, 55(1992): 193-212

    work page 1992

  15. [15]

    M. J. Lai, Y. Y. Xu and W. T. Yin , Improved iteratively reweighted least squares for unconstrained smoothedℓq minimization, SIAM Journal on Numerical Analysis, 51 (2013): 927-957

    work page 2013

  16. [16]

    Lancaster, On eigenvalues of matrices dependent on a parameter, Numerische Mathematik, 6(1964): 377-387

    P. Lancaster, On eigenvalues of matrices dependent on a parameter, Numerische Mathematik, 6(1964): 377-387

    work page 1964

  17. [17]

    H. Y. Le , Generalized subdifferentials of the rank function, Optimization Letters, 7(2013):731-743

    work page 2013

  18. [18]

    A. B. Levy , Implicit multifunction theorems for the sensitivity analysis of varia- tional conditions, Mathematical Programming, 74(1996): 333-350

    work page 1996

  19. [19]

    A. S. Lewis and H. Sendov , Nonsmooth analysis of singular values, Set-Valued Analysis, 13(2005): 213-241

    work page 2005

  20. [20]

    A. S. Lewis , The convex analysis of unitarily invariant matrix functions, Jounral of Convex Analysis, 2(1995): 173-183

    work page 1995

  21. [21]

    Y. L. Liu, S. J. Bi and S. H. Pan,Equivalent Lipschitz surrogates for zero-norm and rank optimization problems, Journal of Global Optimization, 72(2018): 679-704

    work page 2018

  22. [22]

    Y. L. Liu and S. H. Pan, Regular and limiting normal cones to the graph of the subdifferential mapping of the nuclear norm, Set-Valued and Variational Analysis, 27(2019): 71-85. 21

    work page 2019

  23. [23]

    W. M. Mao, S. H. Pan and D. F. Sun , A rank-corrected procedure for matrix completion with fixed basis coefficients, Mathematical Programming, 159(2016): 289– 338

    work page 2016

  24. [24]

    Mohan and M

    K. Mohan and M. F azel , Iterative reweighted algorithm for matrix rank mini- mization, Journal of Machine Learning Research, 13(2012): 3441-3473

    work page 2012

  25. [25]

    B. S. Mordukhovich,Complete characterization of openess, metric regularity, and Lipschitzian properties of multifunctions, Transactions of the American Mathematical Society, 340(1993): 1-35

    work page 1993

  26. [26]

    Negahban and M

    S. Negahban and M. J. W ainwright , Estimation of (near) low-rank matrices with noise and high-dimensional scaling, Annals of Statistics, 39(2011): 1068-1097

    work page 2011

  27. [27]

    F. Nie, H. Huang and C. Ding , Low-rank matrix recovery via efficient schat- ten p-norm minimization, In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012: 655-661

    work page 2012

  28. [28]

    L. L. Pan, Z. Y. Luo and N. H. Xiu , Restricted robinson constraint qualification and optimality for cardinality-constrained cone Programming, JournalofOptimziation Theory and Application, 175(2017): 104-118

    work page 2017

  29. [29]

    J. S. Pang, M. Raza viyayn and A. Al v arado , Computing B-stationary points of nonsmooth dc programs, Mathematics of Operations Research, 42(2017): 95-118

    work page 2017

  30. [30]

    Pietersz and P

    R. Pietersz and P. J. F. Groenen , Rank reduction of correlation matrices by majorization, Quantitative Finance, 4(2004): 649-662

    work page 2004

  31. [31]

    R. T. Rockafellar , Convex Analysis, Princeton University Press, 1970

    work page 1970

  32. [32]

    R. T. Rockafellar and R. J-B. Wets , Variational Analysis, Springer, 1998

    work page 1998

  33. [33]

    D. F. Sun and J. Sun , Semismooth matrix valued functions, Mathematics of Op- erations Research, 27(2002): 150-169

    work page 2002

  34. [34]

    Torki , Second-order directional derivatives of all eigenvalues of a symmetric matrix, Nonlinear analysis, 46(2001): 1133-1150

    M. Torki , Second-order directional derivatives of all eigenvalues of a symmetric matrix, Nonlinear analysis, 46(2001): 1133-1150

    work page 2001

  35. [35]

    G. A. W atson, Characterization of the subdifferential of some matrix norms, Linear Algebra and Applications, 170(1992): 33-45

    work page 1992

  36. [36]

    J. Wu, L. W. Zhang and Y. Zhang , Mathematical programs with semidefinite cone complementary constraints: constraint qualifications and optimality conditions, Set-Valued and Variational Analysis, 22(2014): 155-187

    work page 2014

  37. [37]

    Y. Q. Wu, S. H. Pan and S. J. Bi , KL property of exponent1/2 for zero-norm regularized quadratic function on sphere and its application, arXiv:1811.04371, 2018. 22 Appendix: Directional limiting normal cone togphNSn + In this part we characterize the directional limiting normal cone togphNSn +. For this purpose, for a givenA∈ Sn, we denote byλ(A)∈ Rn the...

    work page arXiv 2018