{"id":"e17f765c-8483-4352-92d1-a2f4902f69e2","arxiv_id":"2504.13170","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new semidefinite relaxation jointly optimizes trajectories, control inputs, and time scaling for linear and piecewise-affine systems, and extends to mode-sequence optimization via graphs of convex sets.","lead":"This paper introduces a semidefinite relaxation that lets trajectory optimization for linear and piecewise-affine systems include the time step as a decision variable, avoiding the bilinear terms that make such problems nonconvex. It combines the relaxation with a graph-of-convex-sets framework to also optimize over discrete mode sequences in a single convex program.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Tightness claim not supported: reported gaps up to 24.4% and the gap metric assumes NLP global optimality, which is not certified.","rationale":"The reader's weakest assumption correctly identifies the gap metric as a load-bearing weakness: the empirical tightness claim rests on δ computed against an NLP solution that is not certified globally optimal. This is the same concern I find most significant. The reported 24.4% gap in Table I further contradicts the 'tightness' claim, and the abstract's single-SDP statement is not matched by the two-stage pipeline actually used. These issues are addressable with better benchmarks and clearer claims, so the CONDITIONAL verdict remains appropriate; no verdict change is needed.","tokens_in":11237,"tokens_out":9647,"duration_ms":82119,"concrete_test":"Run the small inverted-pendulum-with-wall instance from Example V.1 with a global optimal control solver that provides certificates (e.g., exhaustive enumeration of mode sequences on a dense time grid, or a branch-and-bound MICP solver on the original nonconvex formulation). Compute the true optimum C_true and compare with both C_GCS (relaxation value) and C_NLP (refined cost). Report δ_true = (C_true − C_GCS)/C_true for all initial conditions. If δ_true exceeds the reported δ, the tightness claim fails. Also verify whether C_NLP equals C_true; if C_NLP > C_true, the reported δ underestimates the true gap. Additionally, on a small linear example, solve the dense second-order SDR to obtain a tighter lower bound and compare with C_GCS to test whether the TFR is as tight as claimed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of empirical tightness is not established. Table I reports relaxation gaps δ = (C_NLP − C_GCS)/C_NLP up to 24.4% (Task 3), which is not 'tight' by any ordinary standard; the paper's statement that the method 'consistently produces empirically tight solutions' is internally contradicted. Moreover, the metric is unreliable: C_NLP is the cost from an NLP solver warm-started at the GCS+TFR solution. If the relaxation is loose, the warm start may be biased toward a local solution with cost near C_GCS, making δ artificially small. The paper provides no global optimality certificate for C_NLP. There is also no comparison against a known global optimum or an alternative independent lower bound. Finally, the abstract's claim that PWA problems are 'solved through a single semidefinite program' is not what the experiments do: Section VI-C explicitly refines the GCS+TFR solution with a nonlinear program. The reported experiments therefore test a two-stage pipeline, not a single SDP. The tightness and single-SDP claims lack empirical and theoretical support.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a semidefinite relaxation (TFR) for discrete-time linear optimal control with time scaling, where the time step h multiplies the state and control variables and creates bilinear nonconvexities. The formulation lifts the variables to y=(1,h,r,hr) and uses Y=yy^T/h, with a sparse variant that couples only adjacent time steps. The relaxation is then extended to piecewise-affine systems: for a fixed mode sequence, per-mode spectrahedra are coupled through a matrix \\bar{Y}; for unknown mode sequences, the problem is cast as a shortest-path problem in a graph of convex sets (GCS). The method is tested on an inverted pendulum with wall contacts and a 7-DOF double-integrator robot arm, reporting relaxation gaps and comparisons to MICP and direct collocation. The paper claims that the relaxations are empirically tight and that PWA optimal-control problems can be solved through a single semidefinite program.","tokens_in":11445,"tokens_out":7164,"duration_ms":62939,"significance":"If the empirical tightness claim were established, this would be a meaningful step: the sparse TFR is much smaller than a full second-order SDR, and the GCS integration gives a convex way to search over mode sequences with variable dwell times. The construction is self-contained and does not fit parameters to data, and the experiments cover a relevant class of problems. However, the reported evidence does not currently support the main claims: the relaxation gaps in Table I are large, the gap metric depends on an unverified NLP global-optimality assumption, and the actual pipeline is not a single SDP. With revised claims and stronger experimental validation, the work could be a useful contribution as a lower-bound and warm-start method for time-scaled trajectory optimization.","major_comments":[{"comment":"Table I reports relaxation gaps of 14.3% (Task 2) and 24.4% (Task 3), which is inconsistent with the statement in §VII-B that the formulation 'consistently produces empirically tight solutions.' Please either define a quantitative threshold for 'tight', or provide an independent lower bound (for example from a branch-and-bound solver or a stronger SDR) to demonstrate that the large reported gaps do not reflect true suboptimality of the NLP-refined solution.","section":"§VII-B, Table I"},{"comment":"The gap definition δ=(C_NLP−C_GCS)/C_NLP assumes that C_NLP is the global optimum of the original nonconvex problem (9). Because the NLP is warm-started from the GCS+TFR solution, a loose relaxation can bias the local solver toward a trajectory with cost close to C_GCS, artificially reducing δ. No global optimality certificate is provided for C_NLP. The paper should compare against a certified global solver on small instances, or report an independent lower bound, before claiming empirical tightness.","section":"§VII-A"},{"comment":"The abstract (and Section I) states that PWA optimal-control problems can be solved 'through a single semidefinite program', but §VI-C describes a two-stage pipeline that refines the GCS+TFR trajectory with an NLP solver on the original bilinear program (9). The SDP relaxation alone yields a lower bound and an approximate trajectory, not a solution of the original problem. Please revise the wording to describe the method as an SDP-based lower bound and warm-start generator followed by NLP refinement.","section":"Abstract and §VI-C"},{"comment":"The comparison with the MICP relaxation in Fig. 5 uses different discretizations: the MICP baseline uses h=0.005 and K=160, while TFR uses K=20 per mode with a variable time step. Since the gap definitions also differ (δ for TFR is measured against C_NLP, whereas for MICP it is measured against C_opt), the reported 'much tighter' conclusion is not directly supported. Please harmonize the discretizations and the optimality reference, or clearly state why the comparison is meaningful.","section":"§VII-A, Fig. 5"}],"minor_comments":[{"comment":"Because Y=yy^T/h, the (1,1) entry is 1/h and the (2,2) entry is h; the text explains this, but a short remark near the equation would help the reader parse the block structure.","section":"§IV-A, Eq. (5)"},{"comment":"The superscript n in x_n^k (rendered as 'xn k' in the text) is the mode index; please state this explicitly at first use to avoid confusion with powers.","section":"§V"},{"comment":"The phrase 'approximately optimal trajectory' should be defined; presumably it means the projection or rounding of the SDP solution, but this step is not described.","section":"§VI-C"},{"comment":"No wall-clock time, SDP dimension, or solver settings are reported, so the claimed computational efficiency over MICP and direct collocation cannot be assessed; please add these data.","section":"§VII-B and Table I"},{"comment":"The video links are missing; please include them.","section":"Fig. 1 caption"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and the self-citations to [27] are appropriate. My main concern is that the current abstract and Section VII overstate the method; I would ask the authors to rework the claims and experiments rather than merely polish the presentation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real contribution to convex relaxation for time-scaled optimal control, but the paper oversells tightness and the headline claim about single-SDP solving does not match the experiments.\n\nWhat is new: the lifted variable set (1, h, r, hr) and the sparse consistency constraints in (14) are genuinely tailored to the bilinear dynamics, and they give a much smaller PSD block than the standard second-order SDR. Extending the per-mode relaxation to GCS to optimize mode sequences is a natural but useful step; it cuts mode-decision binary variables from per-time-step to per-switch. The derivations in Section IV and the appendix are straightforward, and the relaxation is valid as a lower bound.\n\nSoft spots. First, the empirical tightness claim is not supported as stated. Table I reports gaps of 0.9% to 24.4% for the robot tasks; 24.4% is not tight. The paper says \"consistently produces empirically tight solutions\" (Section VII-B), which is directly contradicted by its own table. Second, the gap metric δ=(C_NLP−C_GCS)/C_NLP assumes C_NLP is globally optimal, but C_NLP comes from an NLP warm-started from the same relaxation. If the relaxation is loose, the warm start can pull the NLP toward a local solution near the relaxed trajectory, making δ artificially small. No certificate or independent lower bound is given. This is the load-bearing weakness, not a minor quibble. Third, the abstract's claim that PWA problems are \"solved through a single semidefinite program\" is not what the experiments do: Section VI-C explicitly refines with an NLP. The SDP is a relaxation plus warm start; the claim should be restated. Fourth, no code or data is provided, so the numbers cannot be checked. That is addressable.\n\nWho it is for: people working on convex relaxations for motion planning, GCS, and SDR-based optimal control. They will get ideas from the variable selection and the sparse coupling constraints. The empirical claims need a careful rewrite and a stronger evaluation before publication.\n\nRecommendation: send to peer review, but require major revision. The core technique is worth refereeing; the unsupported tightness claim and the mismatch between abstract and experiments need fixing first.","headline":"A genuinely useful SDR construction for time-scaled optimal control, but the tightness claims and the 'single SDP' framing overstate what the experiments show.","tokens_in":11965,"tokens_out":2376,"would_cite":true,"duration_ms":21669,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces a semidefinite relaxation that keeps the discretization time step as a free variable in linear and piecewise-affine optimal control, producing empirically tight lower bounds from a single convex program.","keywords":["semidefinite relaxation","time-flexible relaxation","time scaling","piecewise-affine systems","graph of convex sets","trajectory optimization","mixed-integer convex programming","minimum-time control"],"falsifier":"Take a small minimum-time PWA problem whose true optimum is certified by exhaustive mode enumeration and a fine grid or branch-and-bound; if the GCS+TFR lower bound is strictly below that certified optimum by more than the small gaps the paper reports on similar tasks, or the NLP refinement initialized from the relaxation lands at a worse feasible trajectory, the empirical-tightness claim fails.","tokens_in":11058,"feed_emoji":"🤖","tokens_out":9433,"duration_ms":83305,"temperature":0.7,"pith_summary":"Time-scaled optimal control is nonconvex because the discretization step $h$ multiplies the states and controls, so most methods fix the duration or alternate between path optimization and timing. This paper proposes a semidefinite relaxation that keeps $h$ free by building a PSD matrix from precisely the bilinear products that occur in the dynamics and cost—$h$, $hr$, and $hrr^\\top$—while omitting the redundant $h^2$ and $r r^\\top$ terms. Empirically this relaxation is tight on the minimum-time problems tested and much cheaper than the full second-order SDR. For piecewise-affine systems, the same relaxation becomes the convex set in a shortest-path graph, so one semidefinite program proposes both the mode sequence and the time-flexible trajectory, and an NLP refinement step polishes the result.","feed_headline":"One convex relaxation optimizes trajectory and timing together","feed_subtitle":"For linear and piecewise-affine systems, mode choice, duration, and states come out of one semidefinite program.","key_machinery":"The central object is the time-flexible relaxation (TFR). For a trajectory variable $r=(x_0,\\dots,x_K,u_0,\\dots,u_{K-1})$, the paper builds $y=(1,h,r,hr)$ and the PSD matrix $Y=(1/h)yy^\\top$, whose blocks contain $h$, $r$, $hr$, $rr^\\top$, $hrr^\\top$, and their transposes. The multiplication by $1/h$ converts $h^2rr^\\top$ into the needed $hrr^\\top$. The sparse variant replaces the global $Y$ with local blocks $Y_k=(1/h)y_ky_k^\\top$, where $y_k=(1,h,(x_k,x_{k+1},u_k),h(x_k,x_{k+1},u_k))$, plus consistency equalities identifying shared states. For mode transitions, a coupling matrix $\\bar Y$ ties boundary terms like $h_n\\bar x$, $h_{n+1}\\bar x$, and their cross products across consecutive modes. These spectrahedra serve as the convex sets of a graph-of-convex-sets problem, so a single SDP searches over mode sequences and trajectories together.","core_discovery":"The central claim is that the nonconvexity introduced by treating the time step as a decision variable can be removed without paying for a full second-order moment relaxation. The time-flexible relaxation selects the products that actually appear in the problem—$h$, $hr$, and $hrr^\\top$—and encodes them in a PSD matrix, yielding lower bounds that the paper reports as within 0.9–24.4% of the refined NLP cost on its tasks, while using a smaller matrix than the standard second-order SDR. For piecewise-affine systems, the relaxation is embedded in a graph-of-convex-sets formulation, turning mode-sequence optimization into a single semidefinite program; the relaxed trajectory then initializes an NLP that recovers a feasible, dynamically consistent trajectory.","pith_inferences":["The term-selection principle—include only the bilinear products the problem actually contains—might transfer to other biconvex control problems, such as speed-scaled motion planning or contact-rich manipulation with variable stiffness.","A natural next test is branching on mode sequences when the relaxation gap is nonzero; because the SDP provides a lower bound, branch-and-bound could turn this method into a global solver for small piecewise-affine problems.","The coupling-matrix construction for mode transitions could generalize to other switched systems with shared boundary states, even when the per-mode dynamics are not affine.","The reported gaps vary widely across robot-arm tasks, so a useful benchmark would be a suite of small instances with certified global optima to map exactly where the relaxation stays tight and where it loosens."],"forward_implications":["Minimum-time trajectories can be optimized without fixing the horizon, removing the need for a prespecified final time or a separate outer loop on duration.","Longer horizons and higher-dimensional states become more tractable because the sparse TFR keeps only small local PSD blocks per time step rather than one giant PSD matrix.","For piecewise-affine systems, the number of discrete switching decisions scales with the number of mode switches rather than with the total time-step count, so mode sequences can be explored inside the SDP.","The relaxed trajectories serve as warm starts for NLP refinement, which is how the paper produces feasible, dynamically consistent trajectories from the convex solution."],"supporting_citations":[{"why":"Supplies the standard QCQP semidefinite relaxation that the TFR modifies and compares against.","marker":"[35]"},{"why":"Provides the shortest-path-in-GCS formulation and its tight convex relaxation used to optimize mode sequences.","marker":"[27]"},{"why":"Gives the baseline mixed-integer PWA optimal-control formulation with fixed time step that the paper compares with.","marker":"[26]"},{"why":"Supplies the inverted-pendulum-with-wall parameters and contact model used in the validation.","marker":"[24]"},{"why":"Is the direct-collocation baseline used for robot-arm trajectory comparisons.","marker":"[2]"},{"why":"Decomposes the arm's configuration space into convex regions used by the planner.","marker":"[49]"}],"fun_headline_variants":["Time-scaling control via one tight semidefinite program","Convex handle on nonconvex time-scaling control","PWA control: one SDP selects modes and timing","Cutting out bilinear grief: SDP for time-flexible control","Tight SDR for linear and piecewise-affine optimal control"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The empirical-tightness claim assumes that the NLP-refined cost is the true global optimum of the nonconvex problem, because the reported gap is measured against that NLP cost and no global optimality certificate is provided.","fun_headline_variants_meta":{"raw":{"variants":["Time-scaling control via one tight semidefinite program","Convex handle on nonconvex time-scaling control","PWA control: one SDP selects modes and timing","Cutting out bilinear grief: SDP for time-flexible control","Tight SDR for linear and piecewise-affine optimal control"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000185,"raw_usage":{"total_tokens":1291,"prompt_tokens":881,"completion_tokens":410,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":497,"completion_tokens_details":{"reasoning_tokens":324}},"tokens_in":497,"tokens_out":410,"duration_ms":4497,"temperature":1.0,"reasoning_tokens":324,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T12:12:55.691449+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small minimum-time PWA problem whose true optimum is certified by exhaustive mode enumeration and a fine grid or branch-and-bound; if the GCS+TFR lower bound is strictly below that certified optimum by more than the small gaps the paper reports on similar tasks, or the NLP refinement initialized from the relaxation lands at a worse feasible trajectory, the empirical-tightness claim fails.","supporting_citations":[{"cited_title":"Semidefinite relaxation of quadratic optimization problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the standard QCQP semidefinite relaxation that the TFR modifies and compares against."},{"cited_title":"Mixed-integer formulations for optimal control of piecewise-affine systems,","cited_arxiv_id":null,"evidence_quote":"Gives the baseline mixed-integer PWA optimal-control formulation with fixed time step that the paper compares with."},{"cited_title":"Approximate hybrid model predictive control for multi-contact push recovery in complex environments,","cited_arxiv_id":null,"evidence_quote":"Supplies the inverted-pendulum-with-wall parameters and contact model used in the validation."},{"cited_title":"An introduction to trajectory optimization: How to do your own direct collocation,","cited_arxiv_id":null,"evidence_quote":"Is the direct-collocation baseline used for robot-arm trajectory comparisons."}],"review_version":1}