CAREER: Fast and Certifiable Nonconvex Optimization for Perception and Control of Autonomous Systems

This NSF CAREER project aims to make autonomous systems safer and more reliable by developing optimization tools that are both fast and theoretically sound. Many high-stakes autonomy tasks—building 3D maps from images, planning robot motions, or choosing actions from raw sensor data—are formulated as nonconvex optimization problems that today are typically handled by heuristics that can fail unpredictably. This project will bring transformative change by enabling “certifiable” decision-making: algorithms that return high-performance solutions together with mathematical certificates of global (or near-global) optimality, so practitioners can verify when an answer is trustworthy. This will be achieved by creating a unified open-source toolbox for fast, certifiable perception, and control and validating it on real robotic platforms and public benchmarks. The intellectual merit of the project includes new theory and algorithms that bridge nonconvex autonomy problems with scalable convex relaxations, and methods that tightly integrate optimization with modern learning systems. The broader impacts of the project include open educational resources and software that democratize trustworthy autonomy, integration into undergraduate and graduate courses, and hands-on mentoring and outreach opportunities that prepare students—from high school to graduate levels—for careers at the intersection of optimization, robotics, and AI. Technically, this project will advance the moment and sums-of-squares (moment–SOS) relaxation framework, which converts broad classes of nonconvex polynomial optimization problems into semidefinite programs (SDPs) whose solutions provide optimality certificates, but is currently limited by scalability and weak integration with data-driven learning. Three thrusts address the full autonomy stack. Thrust 1 develops a certifiable structure-from-motion pipeline by using vision foundation models (e.g., monocular depth predictors) to “lift” image measurements into a polynomial formulation, then solving a tight first-order relaxation with fast low-rank SDP methods and differentiating through the solver to fine-tune perception models. Thrust 2 creates real-time certifiable trajectory optimization by exploiting problem sparsity to shrink higher-order relaxations and by designing parallel, GPU-friendly first-order SDP solvers with learned warm starts and step sizes. Thrust 3 extends certifiable planning to perception-based control with learned world models by using polynomial approximation and kernel-based SOS techniques, and by embedding certifiable planners into inverse reinforcement learning to improve world-model training. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria. NSF Award ID: 2543352 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Heng Yang | Institution: Harvard University, CAMBRIDGE, MA | Award Amount: $545,000 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2543352 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2543352.html