{"id":"b0f51459-b87e-4447-9524-67eb637db697","arxiv_id":"1908.10499","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The authors show transition points in parametric semidefinite optimization are finite and give a numerical algebraic geometry algorithm to find nonlinearity intervals and transition points.","lead":"This paper develops a numerical method, based on algebraic geometry, for computing the intervals and boundary points where the optimal solution structure of a semidefinite program changes as the objective is perturbed. It also proves that such boundary points are finite and shows that the optimal solution set can be discontinuous even inside one of these intervals.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 4's d=0 branch invokes Lemma 1 without its strict-complementarity and continuity hypotheses; the transition-point classification is unproved.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap. The theoretical claims (Theorems 1 and 2) and the numerical illustrations are credible, and I found no independent reason to reject them. The Algorithm 4 d=0 rule, however, is the gate through which singular points become transition points in the finite partition; the cited Lemma 1 is a sufficient condition for a nonlinearity interval, not a classification of isolated singular points. The paper acknowledges the global nonsingularity limitation but not this proof gap. Since the concern is a missing justification rather than a demonstrated counterexample, the conditional verdict stands; the concrete enumeration would decide whether the rule is merely unproved or actually false.","tokens_in":26249,"tokens_out":21154,"duration_ms":227682,"concrete_test":"Enumerate small rational parametric SDO instances (n=2,3; m between 2 and t(n)) with fixed A,b,C,Cbar. For each instance, use Bertini to compute all singular points of (10); if a singular point epshat has local dimension zero at the tracked accumulation point Va, compute rank pairs of X and S at epshat-10^-6, epshat, and epshat+10^-6 with a high-precision SDP solver and rank-revealing eigenvalue decomposition. If any instance yields equal rank pairs on both sides and at epshat, Algorithm 4 misclassifies a non-transition point. If no such instance is found, the rule remains empirically plausible but still needs the proof that Lemma 1 does not provide.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4.1.2, the paper says: 'If V(F(V, epshat)) has local dimension zero at Va(epshat), then we can conclude from Lemma 1 that epshat is a transition point, since Va(epshat) turns out to be the unique optimal solution.' This does not follow. Lemma 1 requires strict complementarity and continuity of P* and D* at epshat; local dimension zero supplies neither. By Lemma 2, strict complementarity failure alone makes the Jacobian singular even if the ranks of maximally complementary solutions are locally constant, so an isolated singular non-transition point is not ruled out. The paper's own Example 1 shows singular non-transition points exist, and the d=0 branch is exactly the case where the distinguishing positive-dimensional structure is absent. Moreover, local dimension zero at the accumulation point of one track does not exclude other isolated optimal solutions at epshat, so uniqueness is also not established. Because Algorithm 1 removes the resulting points from Unon, a false positive would puncture a nonlinearity interval and destroy the claimed finite partition.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies parametric semidefinite optimization problems (P_epsilon)/(D_epsilon) with the objective perturbed along a fixed direction. It reviews invariancy sets, nonlinearity intervals, and transition points, and proves that the set of transition points is finite (Theorem 1) using semi-algebraicity. It also shows that the optimal set mapping may fail to be continuous on a nonlinearity interval (Example 1). Under a local nonsingularity condition, the paper develops a numerical algebraic geometry methodology (Algorithms 1-4) for computing invariancy intervals, nonlinearity intervals, and transition points, and under a global nonsingularity condition it claims a full decomposition of int(E). The algorithms are tested on several numerical examples. The ODE tracking framework in Theorem 2 is standard and appears correct, and the semi-algebraic finiteness proof is a solid theoretical contribution. The main weakness is the classification step in Algorithm 4, where the claim that an isolated singular point is necessarily a transition point is not justified.","tokens_in":26430,"tokens_out":15200,"duration_ms":145685,"significance":"If the algorithmic correctness were fully established, this would be the first comprehensive computational procedure for partitioning the parameter space of a parametric SDO problem into invariancy intervals, nonlinearity intervals, and transition points, which is of clear interest for sensitivity analysis, reoptimization, and warm-starting interior-point methods. The paper provides a rigorous proof of finiteness of transition points, a correct analytic continuation argument under nonsingularity (Theorem 2), and reproducible numerical experiments on meaningful examples. These are genuine strengths. However, the classification rule for isolated singular points in Algorithm 4 is currently unsupported, and since this step is load-bearing for the claimed full decomposition, the theoretical underpinning of the algorithm needs repair.","major_comments":[{"comment":"The d=0 branch asserts: 'If V(F(V, epshat)) has local dimension zero at Va(epshat), then we can conclude from Lemma 1 that epshat is a transition point, since Va(epshat) turns out to be the unique optimal solution.' This does not follow. Lemma 1 requires strict complementarity and continuity of the optimal set mappings P* and D* at epshat; local dimension zero supplies neither. Moreover, Lemma 1's conclusion is that epshat belongs to a nonlinearity interval, which is the opposite of being a transition point. Lemma 2 shows that strict complementarity failure alone makes the Jacobian singular even if the ranks of maximally complementary solutions are locally constant, so an isolated singular non-transition point is not ruled out. If such a point exists, the d=0 branch would misclassify it as a transition point, and Algorithm 1 would incorrectly remove it from Unon, splitting a nonlinearity interval and destroying the claimed finite partition. The authors should either prove that for the SDO optimality system (10) an isolated singular solution implies a rank change, or replace the d=0 criterion with a direct rank-change test applied to a maximally complementary solution, as in the d>0 branch.","section":"Section 4.1.2, Algorithm 4"},{"comment":"The proof of Lemma 1 is incomplete. It establishes that the ranks of X*(epsilon) and S*(epsilon) are constant in a neighborhood of epsbar, but Definition 4 requires that the optimal partition pi(epsilon) is injective on the nonlinearity interval, i.e., epsilon1 != epsilon2 implies pi(epsilon1) != pi(epsilon2). The assumption that {epsbar} is a singleton invariancy set only implies that pi is not constant on any neighborhood of epsbar; it does not rule out two distinct nearby points having the same partition. Thus the conclusion that epsbar belongs to a nonlinearity interval does not follow from the stated argument. This gap matters because Lemma 1 is explicitly invoked in the d=0 classification in Algorithm 4, compounding the unsupported step identified above.","section":"Section 3, Lemma 1"},{"comment":"The sentence 'since Va(epshat) turns out to be the unique optimal solution' is not justified. The numerical local dimension test at the point Va(epshat) only certifies that Va(epshat) is isolated within its irreducible component of the complex algebraic set V(F(V, epshat)). It does not exclude other irreducible components that may contain additional isolated real optimal solutions, nor does it rule out other optimal solutions not reached by the tracked branch. Uniqueness of the optimal solution at epshat must be established separately, for example by computing all real solutions of F(V, epshat)=0 that satisfy the semidefinite constraints (11), before any lemma requiring uniqueness can be applied.","section":"Section 4.1.2"}],"minor_comments":[{"comment":"The update rule for Utran is written as a set-builder expression that is hard to read; it should be phrased as 'add alpha_inv to Utran if alpha_inv > Emin, and add beta_inv to Utran if beta_inv < Emax'.","section":"Algorithm 2"},{"comment":"The column 'Approximate singular point' contains values such as 0.025 and 0.0025; a short explanation of the stopping criterion used to select the last mesh point would help the reader interpret the mesh-dependent convergence behavior.","section":"Section 5.1, Table 2"},{"comment":"The phrase 'since the set of transition points is finite, see Theorem 1, the numerical inaccuracy could lead one to miss a transition point' is slightly confusing: the finiteness is a property of the exact problem, not of the numerical mesh; consider rephrasing to indicate that the mesh might not resolve a transition point.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The paper builds on the authors' previous work [32] and [42], and the main contribution is the numerical decomposition algorithm. The gap in the classification of isolated singular points (Algorithm 4, d=0 branch) is the central issue; it is not a matter of presentation but of correctness of the proposed method. The authors should either supply a rigorous proof that for the optimality system (10) local dimension zero at an accumulation point forces a rank change, or remove this branch and rely on rank-change tests in all cases, possibly with an explicit caveat that isolated singular non-transition points are not excluded by the current analysis. With that repair, the paper would likely be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague —\n\nQuick take: the paper is worth engaging. It gives the first full decomposition algorithm for int(E) in parametric SDO, proves finiteness of transition points, and shows that continuity of the optimal set mapping can fail on a nonlinearity interval. Those are real contributions. Theorem 1 via semialgebraicity and Theorem 2 via Davidenko tracking are standard and appear correct. The numerical examples are explicit enough to be reimplemented, and the authors are upfront about the global nonsingularity condition in Proposition 5, which is good.\n\nThe soft spot is in Section 4.1.2, and it is load-bearing. Algorithm 4's d=0 branch says that if the algebraic set V(F(V, epshat)) has local dimension zero at the accumulated solution Va(epshat), then Lemma 1 lets you conclude epshat is a transition point, since Va(epshat) is the unique optimal solution. Neither part follows. Local dimension zero at one point of one component does not rule out other isolated or positive-dimensional solutions at epshat. And Lemma 1 requires strict complementarity plus continuity of P* and D*; local dimension zero supplies neither. In fact Lemma 1's conclusion is that the point belongs to a nonlinearity interval, not that it is a transition point. The paper's own Example 1 shows singular non-transition points exist, and Lemma 2 shows strict complementarity can fail while ranks stay locally constant. So an isolated singular non-transition point is not excluded, and the algorithm would puncture a nonlinearity interval if one occurs.\n\nThe rest of the algorithm may well be fine in practice—the positive-dimensional branch checks rank changes, and the numerical examples look consistent. But the d=0 branch is exactly where the distinguishing structure is absent, and that is where the classification is claimed without proof. The authors also ship no code or data, which makes independent verification more work than it should be.\n\nWho is this for? People working on parametric sensitivity analysis and warm starts for SDO, and people interested in numerical algebraic geometry applied to optimization. They will get value from the theory and the pipeline even if they cannot rely on Algorithm 4 as stated.\n\nRecommendation: send to peer review. The paper deserves referee time. But the referee report should push hard on Section 4.1.2: either prove that local dimension zero plus accumulation from a nonsingular track implies a rank change, or add a hypothesis that makes it true, or soften the claim to a heuristic. As it stands, the full partition algorithm is not proved correct.","headline":"Solid theory and a useful numerical pipeline, but the transition-point classification in Algorithm 4 rests on an invalid inference from Lemma 1, so the full partition algorithm is not yet proved correct.","tokens_in":26968,"tokens_out":4191,"would_cite":true,"duration_ms":43646,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C31","90C51"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the transition points of the optimal partition in parametric semidefinite optimization form a finite set and gives a numerical algebraic geometry procedure that locates them and the surrounding invariancy and…","keywords":["semidefinite optimization","parametric analysis","optimal partition","nonlinearity interval","transition point","numerical algebraic geometry","sensitivity analysis","set-valued continuity"],"falsifier":"Construct a parametric SDO whose optimality system has a singular parameter value whose accumulation point is an isolated solution, but where the ranks of maximally complementary optimal solutions are unchanged on both sides; Algorithm 4 would label that parameter a transition point although no rank change occurs.","tokens_in":26016,"feed_emoji":"📐","tokens_out":8863,"duration_ms":74660,"temperature":0.7,"pith_summary":"This paper studies a family of semidefinite optimization problems obtained by perturbing the objective matrix along a single fixed direction. It proves that the parameter line is organized into finitely many pieces: intervals on which the whole optimal partition is fixed, intervals on which only the ranks of maximally complementary optimal solutions stay fixed while the partition itself rotates, and isolated transition points where the ranks change. The set of transition points is shown to be finite. The paper then develops a numerical algebraic geometry procedure that tracks the unique analytic optimal solution branch by an ordinary differential equation until the optimality system becomes singular, classifies each singular point, and thereby decomposes the parameter domain into invariancy intervals, nonlinearity intervals, and transition points. The payoff is a principled way to know, without re-solving every instance, where the structure of the optimal solution changes as the problem data vary.","feed_headline":"Transition points in parametric SDO are finite and computable","feed_subtitle":"New method splits the parameter line into rank-stable intervals and pinpoints where the optimal partition changes.","key_machinery":"The load-bearing object is the polynomial optimality system $F(V,\\epsilon)=0$, written in the variables $V=(\\operatorname{svec}(X); y; \\operatorname{svec}(S))$ with complementarity $XS=0$ expressed through the symmetric Kronecker product. Its Jacobian $J(V,\\epsilon)$ plays two roles: nonsingularity makes the optimal solution the unique analytic branch by the implicit function theorem, and singularity marks the candidate boundary points. The branch is tracked by the homotopy ODE $dV/d\\epsilon = -J(V,\\epsilon)^{-1}\\,\\partial F(V,\\epsilon)/\\partial \\epsilon$, and at each singular point a numerical local dimension test decides whether the point is a transition point. The optimal partition $(B,T,N)$, built from the column spaces of maximally complementary optimal solutions, is the combinatorial object whose invariance or variation defines the intervals being computed.","core_discovery":"The central claim is that parametric SDO along a fixed direction has a finite combinatorial skeleton: the set of transition points is finite, so the interior of the domain is a finite union of invariancy intervals (optimal partition constant), nonlinearity intervals (ranks of $X^*(\\epsilon)$ and $S^*(\\epsilon)$ constant, partition varying), and isolated transition points. Under a local nonsingularity condition, namely the Jacobian of the polynomial optimality system $F(V,\\epsilon)=0$ being nonsingular along the tracked branch, the boundary points of these intervals can be computed by following the unique analytic optimal solution with an ODE until the Jacobian becomes singular, then classifying each singular point via the local dimension of the algebraic solution set at its accumulation point. With a global nonsingularity condition the procedure yields a complete, finite partition of $\\operatorname{int}(E)$. The same analysis shows that Painlevé-Kuratowski continuity of the optimal set mapping can fail on a nonlinearity interval, and that even a continuous selection through the relative interiors of the optimal sets may fail to exist.","pith_inferences":["The polynomial-tracking approach should extend to perturbations of the right-hand side $b$ or the constraint matrices $A_i$, since those also preserve the KKT polynomial structure; the paper only develops the fixed-direction objective perturbation.","The classification step for isolated singular points could be hardened by explicitly comparing ranks of maximally complementary optimal solutions across the point, as is already done in the positive-dimensional case; this would cover the possibility of an isolated singular point that is not a transition point.","Because continuous selections through relative interiors can fail on nonlinearity intervals, any warm-start or reoptimization scheme should follow the algebraic branch of optimal solutions, not a face of the optimal set."],"forward_implications":["The finiteness of transition points means $\\operatorname{int}(E)$ has a finite description: all invariancy intervals, nonlinearity intervals, and transition points can in principle be listed rather than sampled.","Inside a nonlinearity interval the ranks of maximally complementary optimal solutions stay fixed, so nearby parameter values share the same rank structure and can be handled without resolving the SDO from scratch.","At any transition point, strict complementarity and nondegeneracy fail, so interior-point methods lose quadratic convergence there; the paper raises this as a complexity question on the closure of nonlinearity intervals.","The optimal set mapping is generically continuous only up to a first-category set, and even on nonlinearity intervals inner continuity can fail; sensitivity analyses must therefore check continuity at each point rather than assume it from rank stability."],"supporting_citations":[{"why":"introduces invariancy intervals for parametric SDO and supplies the auxiliary SDO problems (5) whose optima give the interval boundary points.","marker":"[27]"},{"why":"defines nonlinearity intervals and transition points for the optimal partition, the notions this paper analyzes and computes.","marker":"[42]"},{"why":"provides the numerical algebraic geometry treatment of singular boundary points for parametric polynomial systems used in Algorithms 3 and 4.","marker":"[32]"},{"why":"supplies the real-algebraic-geometry facts about semi-algebraic sets and finite boundary sets used to prove Theorem 1.","marker":"[5]"},{"why":"gives the numerical local dimension test used to decide whether a singular point is a transition point.","marker":"[6]"},{"why":"characterizes nonsingularity of the Jacobian as strict complementarity plus nondegeneracy, underlying Lemma 2 and Theorem 2.","marker":"[4]"},{"why":"provides the optimal partition framework and the symmetric Kronecker product representation used in the polynomial system (10).","marker":"[20]"},{"why":"supplies the numerical ODE methods behind the predictor-corrector tracking in Algorithm 3.","marker":"[16]"}],"fun_headline_variants":["Parametric SDO: finite transition set, computable intervals","Finite transition points via algebraic geometry in SDO","Splitting parameter line into finite intervals in SDO","Transition points finite in parametric SDO, intervals computable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The classification step assumes that when the algebraic solution set has local dimension zero at a singular accumulation point, that parameter value must be a transition point, even though the lemma invoked would only force a nonlinearity interval under strict complementarity and continuity conditions that are not established there.","fun_headline_variants_meta":{"raw":{"variants":["Parametric SDO: finite transition set, computable intervals","Finite transition points via algebraic geometry in SDO","Splitting parameter line into finite intervals in SDO","Transition points finite in parametric SDO, intervals computable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001254,"raw_usage":{"total_tokens":5108,"prompt_tokens":881,"completion_tokens":4227,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":497,"completion_tokens_details":{"reasoning_tokens":4160}},"tokens_in":497,"tokens_out":4227,"duration_ms":33801,"temperature":1.0,"reasoning_tokens":4160,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:42:58.653472+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a parametric SDO whose optimality system has a singular parameter value whose accumulation point is an isolated solution, but where the ranks of maximally complementary optimal solutions are unchanged on both sides; Algorithm 4 would label that parameter a transition point although no rank change occurs.","supporting_citations":[{"cited_title":"Goldfarb and K","cited_arxiv_id":null,"evidence_quote":"introduces invariancy intervals for parametric SDO and supplies the auxiliary SDO problems (5) whose optima give the interval boundary points."},{"cited_title":"Mohammad-Nezhad and T","cited_arxiv_id":null,"evidence_quote":"defines nonlinearity intervals and transition points for the optimal partition, the notions this paper analyzes and computes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the numerical algebraic geometry treatment of singular boundary points for parametric polynomial systems used in Algorithms 3 and 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the real-algebraic-geometry facts about semi-algebraic sets and finite boundary sets used to prove Theorem 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the numerical local dimension test used to decide whether a singular point is a transition point."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"characterizes nonsingularity of the Jacobian as strict complementarity plus nondegeneracy, underlying Lemma 2 and Theorem 2."},{"cited_title":"de Klerk , Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applica- tions, vol","cited_arxiv_id":null,"evidence_quote":"provides the optimal partition framework and the symmetric Kronecker product representation used in the polynomial system (10)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the numerical ODE methods behind the predictor-corrector tracking in Algorithm 3."}],"review_version":1}