Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

A New Semidefinite Relaxation for Linear and Piecewise-Affine Optimal Control with Time Scaling

T0 review · 4 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict A genuinely useful SDR construction for time-scaled optimal control, but the tightness claims and the 'single SDP' framing overstate what the experiments show. read the letter →

arxiv 2504.13170 v1 pith:2JDQQVA2 submitted 2025-04-17 cs.RO cs.SYeess.SYmath.OC

Lujie Yang , Tobia Marcucci , Pablo A. Parrilo , Russ Tedrake This is my paper · ORCID
classification cs.ROcs.SYeess.SYmath.OC MSC 90C2290C26
keywords semidefiniterelaxationtime-flexibletimescalingpiecewise-affinesystemsgraphofconvexsetstrajectoryoptimizationmixed-integerprogrammingminimum-timecontrol
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [§VII-B, Table I] 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.
  2. [§VII-A] 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.
  3. [Abstract and §VI-C] 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.
  4. [§VII-A, Fig. 5] 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.
minor comments (5)
  1. [§IV-A, Eq. (5)] 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.
  2. [§V] 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.
  3. [§VI-C] 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.
  4. [§VII-B and Table I] 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.
  5. [Fig. 1 caption] The video links are missing; please include them.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the relaxation is derived directly from the OCP; GCS citations are to published external work and are not load-bearing.

full rationale

The central derivation in Sections II-V is self-contained. Starting from the nonconvex OCP (4), the paper defines the lifting y=(1,h,r,hr) and Y=yy^T/h in (5) precisely so that the bilinear products h r and h r r^T become linear entries of Y (objective (12a)-(13a)); constraints (13b)-(13i) are exact algebraic consequences of the dynamics and projection constraints multiplied by r, 1/h, h, etc., with the rank-1 condition relaxed to PSD. No parameter is fitted to data and no output is a renamed input. The PWA/GCS construction leans on the authors' GCS paper [27], but that is a published SIAM J. Optim. result with independent content (including the NP-hardness theorem) and is not used as an unverified uniqueness assertion, so it does not create circularity. The empirical tightness benchmark against NLP-refined costs is a standard evaluation; the gap delta=(C_NLP-C_GCS)/C_NLP is not forced to zero by construction, although warm-starting the NLP from the relaxation can bias the gap optimistically. The abstract's 'single semidefinite program' claim is hard to reconcile with the explicit NLP refinement in Section VI-C; that is a correctness/validity concern, not circularity. Honest non-finding: no significant circularity.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No parameters are fitted to experimental data; the method's design choices are the monomial selection and per-mode horizon, which are user choices rather than fitted constants. No new physical entities are introduced; the spectrahedra are standard convex sets and the lifted variables are standard SDR constructs. The main assumptions are the validity of the SDR relaxation itself, the Euler discretization model, the tightness of the GCS relaxation from prior work, and the PWA modeling of hybrid systems.

free parameters (2)
  • Per-mode horizon K_n = 20 (pendulum), not fully specified for arm
    The number of discrete steps per mode is a user choice; the paper uses K=20 per mode for the pendulum and does not fully report the setup for the robot arm. This discretization choice affects tightness and computational cost, but it is not fitted to data.
  • Lifted monomial set
    The choice of y=(1,h,r,hr), excluding h^2 and r⊗r, is a hand-selected subset of second-order monomials. The paper argues empirically that this selection suffices, but provides no rule for when it remains exact or tight.
assumptions (4)
  • standard math Dropping the rank-1 constraint in the QCQP SDR yields a valid lower bound on the original problem.
    Used in Section II and IV to justify that the TFR is a relaxation; standard SDR theory from [35].
  • domain assumption The Euler discretization x_{k+1}=x_k+h(Ax_k+Bu_k) accurately represents the continuous-time system for the problems considered.
    Used throughout Sections IV and V; the paper validates on examples but does not discuss discretization error or step-size adequacy.
  • domain assumption The GCS convex relaxation from [27] is tight enough that mode-sequence optimization via a single SDP yields a useful lower bound and warm start.
    Invoked in Section VI; the paper relies on prior work by the same group rather than re-deriving or benchmarking the GCS relaxation here.
  • domain assumption The PWA system (8) with polytopic domains and exactly N mode switches is an adequate model of the hybrid dynamics.
    Assumed in Section V; contact-rich systems are approximated this way, following [24] and [26], but the approximation error is not analyzed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A New Semidefinite Relaxation for Linear and Piecewise-Affine Optimal Control with Time Scaling." pith.science (2026). https://pith.science/paper/2JDQQVA2

@misc{pith2026250413170,
  author       = {Pith},
  title        = {Pith review of: A New Semidefinite Relaxation for Linear and Piecewise-Affine Optimal Control with Time Scaling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2JDQQVA2}},
  note         = {Machine review of arXiv:2504.13170}
}
read the original abstract

We introduce a semidefinite relaxation for optimal control of linear systems with time scaling. These problems are inherently nonconvex, since the system dynamics involves bilinear products between the discretization time step and the system state and controls. The proposed relaxation is closely related to the standard second-order semidefinite relaxation for quadratic constraints, but we carefully select a subset of the possible bilinear terms and apply a change of variables to achieve empirically tight relaxations while keeping the computational load light. We further extend our method to handle piecewise-affine (PWA) systems by formulating the PWA optimal-control problem as a shortest-path problem in a graph of convex sets (GCS). In this GCS, different paths represent different mode sequences for the PWA system, and the convex sets model the relaxed dynamics within each mode. By combining a tight convex relaxation of the GCS problem with our semidefinite relaxation with time scaling, we can solve PWA optimal-control problems through a single semidefinite program.

Figures

Figures reproduced from arXiv: 2504.13170 by the authors.

Figure 1
Figure 1. Minimum-time trajectories for a 7D double integrator [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Comparison of different SDRs for the minimum-time [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Effect of the coupling variable on balancing the in [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Time-optimal trajectories for the inverted pendulum [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: Performance comparison for balancing the inverted [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: Trajectories for balancing the inverted pendulum [PITH_FULL_IMAGE:figures/full_fig_p005_6.png]
Figure 7
Figure 7. Figure 7: Performance comparison for balancing the inverted [PITH_FULL_IMAGE:figures/full_fig_p006_7.png]
Figure 8
Figure 8. Figure 8: Minimum-time trajectories for the robot arm. The [PITH_FULL_IMAGE:figures/full_fig_p006_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A biconvex method for minimum-time motion planning through sequences of convex sets

    cs.RO 2025-04 accept novelty 6.0 of 10

    A biconvex alternating method computes near time-optimal, dynamically feasible trajectories through sequences of convex sets, with completeness and anytime guarantees.

Reference graph

Works this paper leans on

49 extracted references · 38 canonical work pages · cited by 1 Pith paper

  1. [1]

    Survey of numerical methods for trajectory optimization,

    J. T. Betts, “Survey of numerical methods for trajectory optimization,” Journal of Guidance, Control, and Dynamics , vol. 21, no. 2, pp. 193– 207, 1998

    1998

  2. [2]

    An introduction to trajectory optimization: How to do your own direct collocation,

    M. Kelly, “An introduction to trajectory optimization: How to do your own direct collocation,” SIAM Review , vol. 59, no. 4, pp. 849–904, 2017

    work page 2017

  3. [3]

    Model predictive control: Theory and practice—a survey,

    C. E. Garcia, D. M. Prett, and M. Morari, “Model predictive control: Theory and practice—a survey,” Automatica, vol. 25, no. 3, pp. 335– 348, 1989

    1989

  4. [4]

    E. F. Camacho and C. Bordons, Model Predictive Control. Springer, 2007

    work page 2007

  5. [5]

    Time-optimal planning for quadrotor waypoint flight,

    P. Foehn, A. Romero, and D. Scaramuzza, “Time-optimal planning for quadrotor waypoint flight,” Science Robotics , vol. 6, no. 56, p. eabh1221, 2021

    work page 2021

  6. [6]

    Time optimal ergodic search,

    D. Dong, H. Berger, and I. Abraham, “Time optimal ergodic search,” arXiv preprint arXiv:2305.11643 , 2023

    arXiv 2023

  7. [7]

    Time-optimal trajectory generation for dynamic vehicles: A bilevel optimization approach,

    G. Tang, W. Sun, and K. Hauser, “Time-optimal trajectory generation for dynamic vehicles: A bilevel optimization approach,” in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2019, pp. 7644–7650

    work page 2019

  8. [8]

    Fast path plan- ning through large collections of safe boxes,

    T. Marcucci, P. Nobel, R. Tedrake, and S. Boyd, “Fast path plan- ning through large collections of safe boxes,” IEEE Transactions on Robotics, 2024

    work page 2024

Show all 49 references
  1. [9]

    A sequential two-step algorithm for fast generation of vehicle racing trajectories,

    N. R. Kapania, J. Subosits, and J. Christian Gerdes, “A sequential two-step algorithm for fast generation of vehicle racing trajectories,” Journal of Dynamic Systems, Measurement, and Control , vol. 138, no. 9, p. 091005, 2016

    2016

  2. [10]

    Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments,

    C. Richter, A. Bry, and N. Roy, “Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments,” in Robotics Research: The 16th International Symposium ISRR . Springer, 2016, pp. 649–666

    2016

  3. [11]

    Direct trajectory optimization using nonlinear programming and collocation,

    C. R. Hargraves and S. W. Paris, “Direct trajectory optimization using nonlinear programming and collocation,” Journal of Guidance, Control, and Dynamics , vol. 10, no. 4, pp. 338–342, 1987

    1987

  4. [12]

    Robust variable horizon model predictive control for vehicle maneuvering,

    A. Richards and J. P. How, “Robust variable horizon model predictive control for vehicle maneuvering,” International Journal of Robust and Nonlinear Control: IFAC-Affiliated Journal , vol. 16, no. 7, pp. 333– 351, 2006

    2006

  5. [13]

    Milp formulation for solving minimum time optimal control problems,

    F. D. Carvallo, A. W. Westerberg, and M. Morari, “Milp formulation for solving minimum time optimal control problems,” International Journal of Control , vol. 51, no. 4, pp. 943–947, 1990

    1990

  6. [14]

    Numerical synthesis of the time optimal nonlinear state controller via mixed integer programming,

    H. P. Rothwangl, “Numerical synthesis of the time optimal nonlinear state controller via mixed integer programming,” in Proceedings of the 2001 American Control Conference.(Cat. No. 01CH37148), vol. 4. IEEE, 2001, pp. 3201–3205

    2001

  7. [15]

    Aircraft trajectory planning with collision avoidance using mixed integer linear programming,

    A. Richards and J. P. How, “Aircraft trajectory planning with collision avoidance using mixed integer linear programming,” in Proceedings of the 2002 American Control Conference (IEEE Cat. No. CH37301) , vol. 3. IEEE, 2002, pp. 1936–1941

    2002

  8. [16]

    Mixed integer programming for multi-vehicle path planning,

    T. Schouwenaars, B. De Moor, E. Feron, and J. How, “Mixed integer programming for multi-vehicle path planning,” in 2001 European Control Conference (ECC). IEEE, 2001, pp. 2603–2608

    2001

  9. [17]

    Efficient mixed-integer planning for uavs in cluttered environments,

    R. Deits and R. Tedrake, “Efficient mixed-integer planning for uavs in cluttered environments,” in 2015 IEEE International Conference on Robotics and Automation (ICRA) . IEEE, 2015, pp. 42–49

    2015

  10. [18]

    Aggressive quadrotor flight through cluttered environments using mixed integer programming,

    B. Landry, R. Deits, P. R. Florence, and R. Tedrake, “Aggressive quadrotor flight through cluttered environments using mixed integer programming,” in 2016 IEEE International Conference on Robotics and Automation (ICRA) . IEEE, 2016, pp. 1469–1475

    2016

  11. [19]

    Footstep planning on uneven terrain with mixed-integer convex optimization,

    R. Deits and R. Tedrake, “Footstep planning on uneven terrain with mixed-integer convex optimization,” in 2014 IEEE-RAS International Conference on Humanoid Robots . IEEE, 2014, pp. 279–286

    2014

  12. [20]

    Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot,

    S. Kuindersma, R. Deits, M. Fallon, A. Valenzuela, H. Dai, F. Per- menter, T. Koolen, P. Marion, and R. Tedrake, “Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot,” Autonomous Robots, vol. 40, pp. 429–455, 2016

    2016

  13. [21]

    Simultaneous contact, gait, and motion planning for robust multilegged locomotion via mixed-integer convex optimization,

    B. Aceituno-Cabezas, C. Mastalli, H. Dai, M. Focchi, A. Radulescu, D. G. Caldwell, J. Cappelletto, J. C. Grieco, G. Fern ´andez-L´opez, and C. Semini, “Simultaneous contact, gait, and motion planning for robust multilegged locomotion via mixed-integer convex optimization,” IEE...

    2017

  14. [22]

    Optimal manipulator path planning with obstacles using disjunctive programming,

    L. Blackmore and B. Williams, “Optimal manipulator path planning with obstacles using disjunctive programming,” in 2006 American Control Conference. IEEE, 2006, pp. 3–pp

    2006

  15. [23]

    Mixed-integer programming for optimal path planning of robotic manipulators,

    H. Ding, G. Reißig, D. Groß, and O. Stursberg, “Mixed-integer programming for optimal path planning of robotic manipulators,” in 2011 IEEE International Conference on Automation Science and Engineering. IEEE, 2011, pp. 133–138

    2011

  16. [24]

    Approximate hybrid model predictive control for multi-contact push recovery in complex environments,

    T. Marcucci, R. Deits, M. Gabiccini, A. Bicchi, and R. Tedrake, “Approximate hybrid model predictive control for multi-contact push recovery in complex environments,” in 2017 IEEE-RAS 17th Interna- tional Conference on Humanoid Robotics (Humanoids) . IEEE, 2017, pp. 31–38

    2017

  17. [25]

    Feedback control of the pusher-slider system: A story of hybrid and underactuated contact dynamics,

    F. R. Hogan and A. Rodriguez, “Feedback control of the pusher-slider system: A story of hybrid and underactuated contact dynamics,” arXiv preprint arXiv:1611.08268, 2016

    2016 arXiv

  18. [26]

    Mixed-integer formulations for optimal control of piecewise-affine systems,

    T. Marcucci and R. Tedrake, “Mixed-integer formulations for optimal control of piecewise-affine systems,” in Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, 2019, pp. 230–239

    2019

  19. [27]

    Shortest paths in graphs of convex sets,

    T. Marcucci, J. Umenberger, P. Parrilo, and R. Tedrake, “Shortest paths in graphs of convex sets,” SIAM Journal on Optimization , vol. 34, no. 1, pp. 507–532, 2024

    2024

  20. [28]

    Graphs of convex sets with applications to optimal con- trol and motion planning,

    T. Marcucci, “Graphs of convex sets with applications to optimal con- trol and motion planning,” Ph.D. dissertation, Massachusetts Institute of Technology, 2024

    2024

  21. [29]

    Mo- tion planning around obstacles with convex optimization,

    T. Marcucci, M. Petersen, D. von Wrangel, and R. Tedrake, “Mo- tion planning around obstacles with convex optimization,” Science Robotics, vol. 8, no. 84, p. eadf7843, 2023

    2023

  22. [30]

    Non-euclidean motion planning with graphs of geodesically-convex sets,

    T. Cohn, M. Petersen, M. Simchowitz, and R. Tedrake, “Non-euclidean motion planning with graphs of geodesically-convex sets,” inRobotics: Science and Systems (RSS) , 2023

    2023

  23. [31]

    Towards tight convex relaxations for contact- rich manipulation,

    B. P. Graesdal, S. Y . Chia, T. Marcucci, S. Morozov, A. Amice, P. A. Parrilo, and R. Tedrake, “Towards tight convex relaxations for contact- rich manipulation,” in Robotics: Science and Systems (RSS) , 2024

    2024

  24. [32]

    P. A. Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology, 2000

    2000

  25. [33]

    Semidefinite programming relaxations for semialgebraic prob- lems,

    ——, “Semidefinite programming relaxations for semialgebraic prob- lems,” Mathematical Programming, vol. 96, pp. 293–320, 2003

    2003

  26. [34]

    Global optimization with polynomials and the problem of moments,

    J. B. Lasserre, “Global optimization with polynomials and the problem of moments,” SIAM Journal on Optimization , vol. 11, no. 3, pp. 796– 817, 2001

    2001

  27. [35]

    Semidefinite relaxation of quadratic optimization problems,

    Z.-Q. Luo, W.-K. Ma, A. M.-C. So, Y . Ye, and S. Zhang, “Semidefinite relaxation of quadratic optimization problems,” IEEE Signal Process- ing Magazine, vol. 27, no. 3, pp. 20–34, 2010

    2010

  28. [36]

    Piecewise-linear motion planning amidst static, moving, or morphing obstacles,

    B. El Khadir, J. B. Lasserre, and V . Sindhwani, “Piecewise-linear motion planning amidst static, moving, or morphing obstacles,” in 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021, pp. 7802–7808

    2021

  29. [37]

    Convex geometric motion planning on lie groups via moment relaxation,

    S. Teng, A. Jasour, R. Vasudevan, and M. Ghaffari, “Convex geometric motion planning on lie groups via moment relaxation,” arXiv preprint arXiv:2305.13565, 2023

    2023 arXiv

  30. [38]

    Semi-definite relaxation-based admm for cooperative planning and control of connected autonomous vehicles,

    X. Zhang, Z. Cheng, J. Ma, S. Huang, F. L. Lewis, and T. H. Lee, “Semi-definite relaxation-based admm for cooperative planning and control of connected autonomous vehicles,” IEEE Transactions on Intelligent Transportation Systems , vol. 23, no. 7, pp. 9240–9251, 2021

    2021

  31. [39]

    Nonlinear optimal control via occupation measures and lmi-relaxations,

    J. B. Lasserre, D. Henrion, C. Prieur, and E. Tr ´elat, “Nonlinear optimal control via occupation measures and lmi-relaxations,” SIAM Journal on Control and Optimization , vol. 47, no. 4, pp. 1643–1666, 2008

    2008

  32. [40]

    Global adaptive dynamic programming for continuous-time nonlinear systems,

    Y . Jiang and Z.-P. Jiang, “Global adaptive dynamic programming for continuous-time nonlinear systems,” IEEE Transactions on Automatic Control, vol. 60, no. 11, pp. 2917–2929, 2015

    2015

  33. [41]

    Approximate optimal controller synthesis for cart-poles and quadrotors via sums-of-squares,

    L. Yang, H. Dai, A. Amice, and R. Tedrake, “Approximate optimal controller synthesis for cart-poles and quadrotors via sums-of-squares,” IEEE Robotics and Automation Letters , 2023

    2023

  34. [42]

    Fast and certifiable trajectory optimization,

    S. Kang, X. Xu, J. Sarva, L. Liang, and H. Yang, “Fast and certifiable trajectory optimization,” arXiv preprint arXiv:2406.05846 , 2024

    2024 arXiv

  35. [43]

    Globally optimal solution to inverse kinematics of 7dof serial manipulator,

    P. Trutman, M. S. El Din, D. Henrion, and T. Pajdla, “Globally optimal solution to inverse kinematics of 7dof serial manipulator,” IEEE Robotics and Automation Letters , vol. 7, no. 3, pp. 6012–6019, 2022

    2022

  36. [44]

    Inverse kinematics for serial kinematic chains via sum of squares optimization,

    F. Mari ´c, M. Giamou, S. Khoubyarian, I. Petrovi ´c, and J. Kelly, “Inverse kinematics for serial kinematic chains via sum of squares optimization,” in 2020 IEEE International Conference on Robotics and Automation (ICRA) . IEEE, 2020, pp. 7101–7107

    2020

  37. [45]

    Globally optimal estimates for geometric reconstruction problems,

    F. Kahl and D. Henrion, “Globally optimal estimates for geometric reconstruction problems,” International Journal of Computer Vision , vol. 74, pp. 3–15, 2007

    2007

  38. [46]

    Certifiably optimal outlier-robust geometric perception: Semidefinite relaxations and scalable global optimization,

    H. Yang and L. Carlone, “Certifiably optimal outlier-robust geometric perception: Semidefinite relaxations and scalable global optimization,” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 45, no. 3, pp. 2816–2834, 2022

    2022

  39. [47]

    Blekherman, P

    G. Blekherman, P. A. Parrilo, and R. R. Thomas, Semidefinite opti- mization and convex algebraic geometry . SIAM, 2012

    2012

  40. [48]

    A perspective-based convex relaxation for switched-affine optimal control,

    N. Moehle and S. Boyd, “A perspective-based convex relaxation for switched-affine optimal control,” Systems & Control Letters , vol. 86, pp. 34–40, 2015

    2015

  41. [49]

    Growing convex collision-free regions in configuration space using nonlinear programming,

    M. Petersen and R. Tedrake, “Growing convex collision-free regions in configuration space using nonlinear programming,” arXiv preprint arXiv:2303.14737, 2023

    2023 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.