The goal of this methodology-focused project is to develop new, efficient algorithms and computational tools for convex non-symmetric cone programming problems that are scalable for a wide range of applications. Unlike optimization over symmetric cones (linear, second-order cone, and semidefinite programming), non-symmetric cone programming has minimal algorithmic support and virtually no reliable software available to the community. The project is aimed at addressing this need.

Overview. The research program of this proposal is concerned with the design and mathematical analysis of numerical methods for large-scale deterministic and stochastic optimization problems which (among other applications) will enable the assessment and more widespread use of novel radiotherapy treatment modalities. The primary research objectives of this proposal are (1) to develop numerical algorithms for large-scale stochastic constrained optimization with provable rates of convergence (and their application to better account for dose delivery uncertainty in certain radiotherapy treatment modalities), and (2) to develop numerical algorithms for very large scale convex conic optimization problems in which even a single Newton-step is too expensive (and their application to rigorously quantify the maximum achievable benefit of novel radiotherapy treatment modalities over conventional treatments). A number of recent mathematical, physical, and biological insights motivate the departure from conventional treatments (known as intensity-modulated radiotherapy, or IMRT treatments), including spatiotemporally fractionated treatments; proton therapy; combined photon, proton, and electron therapy; and arc therapy. Intellectual merit. Research on adaptive sampling strategies has so far largely focused on unconstrained optimization problems with either stochastic objective functions or objective functions where even a single gradient evaluation is expensive, and hence the objective gradient needs to be sampled. (The most common application of this literature is data science.) Additionally, most research in the area has been limited to convex optimization. The proposed research will substantially extend existing results by considering non-convex objectives, deterministic convex constraints, and also probabilistic constraints that need to be sampled similarly to the objective function. The proposed research on large-scale conic programming will result in a comprehensive approach utilizing first-order approaches, projection-free methods, and constraint generation. The benefits of the recent and experimental radiotherapy treatment modalities mentioned above include substantially lower physical dose burden on healthy tissue, improved incorporation (and in some cases, taking advantage of) nonlinear biological phenomena, and substantially shorter treatment time. However, they all require new algorithmic approaches to treatment planning optimization. Broader impacts. Around 1.7 million patients are diagnosed with cancer every year in the United States alone, and about 50% of them receive radiotherapy as part of their treatment. Therefore, the impact of this research is expected to be substantial. The primary education objective of this proposal is to equip students, and the future workforce, with the mathematical and algorithmic skills and intuition to model complex decision making problems as practically solvable optimization problems. This will be done by developing the first undergraduate course at the PI's department on mathematical optimization, and by creating new and updating existing graduate courses. Both the mathematical and the applied components of the proposal are ripe for integration into computational and modeling components of the courses to be developed. The primary outreach objective of this proposal is to broaden the public's appreciation and understanding of current applied mathematics research. This will be done by expanding the PI's recently started outreach collaboration with artists and designers. Students (from both the design and the sciences side) will continue to be involved in these activities.

Overview. The goal of this project is to develop efficient computational tools for polynomial optimization that are scalable for applications, particularly those involving high-degree or highly multivariate polynomials. One of the most common approaches to the (global) optimization of polynomials utilizes semidefinite programming hierarchies, which arise from combining the algebraic theory of sum-of-squares polynomials and the observation that sum-of-squares polynomials are semidefinite representable. While theoretically satisfactory, the translation of optimization problems involving sum-of-squares polynomials to semidefinite programs is not always practical, for two reasons. First, the semidefinite programming representation of sum-of-squares polynomials roughly squares the number of optimization variables. For example, certifying that a univariate polynomial of degree d is sum-of-squares using the most efficient semidefinite programming methods requires O(d^{6.5}) time, which is 3 orders of magnitude worse than one expects from a symmetric cone optimization problem involving O(d) decision variables. The second problem is numerical. For example, if the polynomials involved are represented in the monomial basis, then the dual variables are semidefinite Hankel matrices whose condition numbers grow exponentially with the degree, which is detrimental for a floating point implementation. This can be somewhat mitigated using an orthogonal basis, but the degree of polynomials that can be reliably handled this way still remains under about 40. The project builds on recent results from the PI and others to derive the algorithmic theory and practical computational tools needed to circumvent the use of the standard semidefinite programming based approach to sum-of-squares optimization, with the aim of solving both the efficiency and the numerical issues outlined above. Stable floating point methods and polynomial-time exact-arithmetic approaches will both be studied. Intellectual merit. It has been an established paradigm that sum-of-squares optimization equals semidefinite programming, with no alternative approaches in the literature for optimization over the sum-of-squares cone. It is, therefore, expected that the proposed research will stimulate further research in both the optimization and the algebraic geometry community. The research will contribute significantly to the budding literature of optimization over nonsymmetric cones, well beyond the case of sum-of-squares optimization. Additionally, as many other applications of semidefinite optimization involve a similar ``lifting'' of the problem to much higher dimensional spaces than the problems' intrinsic dimension, the research will put many applications of semidefinite optimization into a new perspective. Numerical solvers for semidefinite programs have lead to several fast algorithms in algebraic geometry and combinatorial optimization in the past; it is expected that the numerical methods developed in the proposed research will have the same effect. The polynomial-time exact-arithmetic methods will complement the existing numerical-symbolic approaches to the computation of nonnegativity certificates in computational algebraic geometry. The applications considered in the proposal bring together researchers from different fields, including algebraic geometry, constructive approximation theory, theoretical computer science and engineering, and are thus naturally suited for collaborations between researchers in these fields. Broader impacts. The generality of the tools to be developed ensures that the proposed project can have a profound impact in all fields that already make heavy use of polynomial optimization models and algorithms. The resources of this award will enable the PI to continue and increase his mentoring of undergraduate and graduate students. The PI also intends to continue promoting mathematics more generally by participating in activities organized at NC State for high-school and undergraduate students.