WorksPhysics and Astronomy
Many Physical Design Problems are Sparse QCQPs
Abstract
Physical design refers to mathematical optimization of a desired objective (e.g. strong light–matter interactions, or complete quantum state transfer) subject to the governing dynamical equations, such as Maxwell's or Schrodinger's differential equations. Computing an optimal design is challenging: generically, these problems are highly nonconvex and finding global optima is NP hard. Here we show that for linear-differential-equation dynamics (as in linear electromagnetism, elasticity, quantum mechanics, etc.), the physical-design optimization problem can be transformed to a sparse-matrix, quadratically constrained quadratic program (QCQP). Sparse QCQPs can be tackled with convex optimization techniques (such as semidefinite programming) that have thrived for identifying global bounds and high-performance designs in other areas of science and engineering, but seemed inapplicable to the design problems of wave physics. We apply our formulation to prototypical photonic design problems, showing the possibility to compute fundamental limits for large-area metasurfaces, as well as the identification of designs approaching global optimality. Looking forward, our approach highlights the promise of developing bespoke algorithms tailored to specific physical design problems.
Precise fabrication techniques and high-quality materials are enabling unprecedented control over photonic and quantum physical systems, opening exciting frontiers for applications from metasurface optics [1, 2] to quantum computing [3, 4]. Yet this flexibility is accompanied by a proportionate complexity: the design spaces are enormous, and classical and quantum wave-interference effects make them highly oscillatory and nonconvex. The corresponding design problem, of discovering optimal patterns in space and/or time, is generically NP hard [5]. In this article, we identify a surprising mathematical structure in design problems arising from the typical differential equations of physics: in many cases, they can be transformed to sparse, quadratically constrained quadratic programs (sparse QCQPs). It is well known that sparse QCQPs can be close to convex optimization problems, in a sense we make precise below, implying that the transformed design problems may have significantly smoother landscapes and that global optima may be easier to approach. The seemingly impenetrable nonconvexity of conventional formulations of physical design has limited scientists and engineers to black-box algorithms or gradient-based local optimization. Our transformations enable direct connection to a wide swath of modern optimization theory, where advances in convex optimization and semidefinite programming have enabled remarkable progress in trajectory optimization (e.g., rocket landings) [6, 7], matrix completion (recommendation systems) [8–10], compressed sensing (network routing) [11, 12], and more. We show that for prototypical problems in domains such as photonic design and quantum control, one can leverage the sparse-QCQP structure to find fundamental limits for large-scale devices, and offer the possibility of identifying designs near global optimality. We develop a general theory for connecting these ideas in nanophotonics, quantum control, and beyond, and offer a new, convex-optimization-based direction for physical design.
In the 1990’s it was recognized that a key dividing line between “easy” and “hard” optimization problems was not linearity versus nonlinearity, but rather convexity versus nonconvexity [13]. Convex optimization problems, with convex objective functions and convex constraint sets, share a remarkable property: all local optima are global optima [14]. Convex optimization problems can be solved efficiently (in polynomial time) for global optima, e.g., by now-standard interior-point methods [14]. Original applications of convex optimization primarily arose in operations research, but over the past two decades, a surprising number of optimization problems have been shown to be transformable to convex, or nearly convex, formulations. In addition to the three applications mentioned above, further examples include ptychography [15, 16], in which wide-field-of-view, high-resolution images are formed from low-resolution samples, and phase retrieval [17, 18], in which one infers phase values from intensity measurements. By contrast, quantum and classical wave dynamics create interference patterns and oscillatory objective landscapes that are clearly nonconvex.
Confronted by the nonconvexity of physical design, two approaches are typically taken. One is to compute gradients of the objective function with respect to the designable degrees of freedom and “ascend” or “descend” using the gradient. A particular breakthrough in the efficiency of such algorithms came from the “adjoint variable” technique [19–21] (or “backpropagation” [22]), which forms the basis of approaches known as “inverse design” [23–25] and “topology optimization” [26–28] in photonics, and “GRAPE” and “Krotov” in quantum control [29–33]. Such inverse-design techniques have been used across linear, nonlinear [34, 35], and even chaotic [36] physical systems. However, as gradient-based techniques, they may get stuck in low-quality local extrema, and they offer no insight into global bounds (or, “fundamental limits”).
Alternatively, one can use techniques intended for global optimization; early interest in evolutionary algorithms has largely been supplanted by modern research in neural networks. Yet neural networks typically excel in scenarios where modeling is difficult and an extraordinary amount of data is available (such as image recognition and large language models). In physical design, data is expensive to generate (full differential-equation simulations), we have exact models (the differential equations themselves), and learning across architectures, material platforms, and frequency ranges has proven difficult. There have been a number of pioneering efforts in applying machine learning to physical design [37, 38, 39, 40], but it is highly unclear whether they can generally out-perform gradient-based inverse design once all computational costs associated with training are included.
A complementary approach to bottom-up, iterative optimization has been a recent surge of interest in fundamental limits, particularly in optics and photonics [41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57]. Conventionally, bounds such as the Yablonovitch enhancement limit in electromagnetism [58], or the Mandelstamm–Tamm bounds in quantum control [59], arise from identifying singular constraints in physical systems (density of states and energy–time uncertainty, for the two examples). Recently, an alternative approach was proposed in which computational bounds could be found from an infinite set of constraints implied by integral [54, 60, 61] or differential [62] [5] equations. The differential-equation-based approaches requires a transformation to real-valued variables and a relaxation of the design problem (cf. SM), while the matrices in the integral QCQPs are dense, due to their integral-equation origins, leading to two issues: First, solving their semidefinite relaxations for bounds requires computational time, for degrees of freedom, which quickly becomes prohibitive and restricts analysis to few-degree-of-freedom systems. Second, the ranks of the solutions of the semidefinite relaxations are unbounded; as we describe in depth below, this means that the solutions of the semidefinite programs may have little-to-no correlation with physically meaningful structures, let alone optimal designs.
The approach we describe here is a new, joint formulation of physical design and its fundamental limits. Starting with a generic specification of a physical design problem with differential-equation constraints, we describe general techniques for transformation to a sparse QCQP optimization problem. We show that the new problem is mathematically equivalent to the original, yet with a structure more similar to that of pytchography, trajectory optimization, or matrix completion, instead of conventional physical design. The “dual” [14] of our sparse-QCQP problem is a (convex) semidefinite program (SDP), whose solution always represents a fundamental limit across the design space of interest. Moreover, the sparse nature of the differential operators leads to bounds on the rank of the solution of the SDP, which often must be small (e.g., independent of the diameter of a metasurface). A rank-one solution would represent the globally optimal design across the design space; low-rank solutions can potentially be regularized towards rank-one solutions. We give an example of exactly such an approach, leading to a plausibly globally optimal nanophotonic structure for a prototype problem on which “inverse design” struggles to overcome moderate-quality local optima. Our formulation enables the identification of bounds for optimal design with linear differential equations, and offers a new approach to circumvent the oscillatory landscapes that plague the design of wave-based systems.
Reformulating Physical Design
The prototypical design problem has a physical field (electromagnetic, quantum, etc.), designable degrees of freedom (a susceptibility, a control-Hamiltonian amplitude, etc.), and a differential equation linking the two. We consider differential equations that are linear in the field variable. We denote by a vector-field excitation (which can be zero for an eigenproblem), representing an incoming wave or initial condition. The goal is to maximize (or minimize) some objective that is a function of the field variable. Then the design problem can be written:
where represents the linear differential operator. We include as an argument to to emphasize the dependence of on the design variables. In nanophotonics, where one might seek an optimal susceptibility pattern in space to harness electromagnetic waves of frequency , the differential operator is . In quantum control, one might seek an optimal pulse sequence representing the time-dependent amplitude of a control Hamiltonian, , relative to a background Hamiltonian, , in the Schrodinger operator, . And similarly for elastic waves, with the Christoffel equation, and many other linear differential equations of physics. To simplify the exposition and clarify the complexity analysis, we will assume any sufficiently high-resolution numerical discretization into spatial/temporal/polarization/Hilbert-space/etc. degrees of freedom, in which case the variables and are vectors and is an matrix (with suitable boundary conditions encoded). The task of scientists and engineers in disciplines from aerodynamic wing design to nanophotonics to quantum information theory is to solve optimization problems with forms similar to Eq. (1).
Physical design problems as QCQPs
Equation (1) is computationally prohibitive to solve for a global optimum because the differential-equation constraint is nonconvex in the variables and . (It is “bilinear” in the pair of variables and , but that is of little help in searching for global optima.) In this section, we show how to convert the differential-equation constraints to quadratic constraints, ultimately leading to the sparse-QCQP formulation of the design problem.
We consider the prototypical case in which there is a binary choice for the design variable over each designable DOF, denoted and , such as, for example, designing a pattern of air holes in silicon, or a sequence of on/off pulses in quantum control. We further assume, for simplicity, that our design space has the full degrees of freedom shared by the response fields. Typically the number of degrees of freedom will be smaller than ; for example, perfectly matched layers are not part of the designable region. The constraints associated with nondesignable regions are straightforward and described in detail in the SM, and do not change the analysis below. Our approach generalizes to different numbers of degrees of freedom as well as to multilevel design problems, as we discuss in the SM, but again these assumptions will clarify the key logic and analysis. It is simple to enumerate the design space: there are degrees of freedom, each of which can take one of two values, such that there are possible designs. The possible designs each have fields that must satisfy the differential-equation constraints of Eq. (1).
The crucial insight is as follows: at each spatial/temporal point in the design space, either or . (The “” symbol should be interpreted, for example, as selecting a single row of a finite-difference matrix, or as integrating against a single basis function in a finite element discretization.) Consider the scalar-field case, for which each expression is a scalar expression. Then, enforcing a logical OR condition between two scalar values is exactly equivalent to forming a single constraint in which the two scalar expressions are multiplied together; in other words, enforcing OR is equivalent to enforcing . For the general vector-field case, the vector OR condition can be replaced by pairwise inner-product constraints. Each of these inner products is of the form:
where is the matrix that encodes the evaluation of the two terms in square brackets associated with a particular susceptibility degree of freedom and represents the adjoint (conjugate transpose) operation. For example, in a finite-difference scheme, is a block-diagonal matrix (or any linear combination thereof) whose only nonzero elements occur at point in space/time, with nonzero off-diagonal elements only in polarization/Hilbert space. Enforcing Eq. (2) over all independent block-diagonal matrices is equivalent to enforcing the logical-OR condition at all points in space/time, as intuitively justified above and rigorously proven in the SM. The number of independent constraints of the form of Eq. (2) scales linearly with , as one intuitively expects for degrees of freedom.
Clearly the constraints of Eq. (2) are necessarily satisfied by any solution of the original design problem, Eq. (1). Perhaps surprisingly, the constraints of Eq. (2) are also sufficient conditions for the design problem. Hence we can discard the original differential equation constraints, and specify a new, equivalent design problem:
To see why the constraints of Eq. (3) are sufficient conditions, consider an optimal solution of Eq. (3). From , one can check every constraint to determine at each space/time point whether or is the optimal design variable at that point. The resulting pair of and will then necessarily satisfy the constraint of Eq. (1), implying that any solution of Eq. (3) is a viable solution of Eq. (1). As the optimal solutions of each problem are within the other’s feasible set, and the objectives are the same, the optimal solutions must coincide. Hence, the two design problems have equivalent optima.
What is the intuition behind the quadratic constraints of Eq. (3)? They turn out to have a simple, general physical interpretation. Each constraint in Eq. (3) represents a complex-valued conservation law at each point in space/time of the designable domain (cf. SM for a derivation). In electromagnetism, they represent local conservation of real and reactive power flow. In quantum control, they represent local conservation of complex probability. And similarly for other physical systems. A close analog arises in circuit design. When one wants to find the steady-state response of a complex configuration of resistors, capacitors, and inductors, the first choice typically is not solving circuit differential equations. Instead, one solves Kirchhoff’s current and voltage laws, two conservation laws for every node of the system. The constraints of Eq. (3) are akin to generalized Kirchhoff’s laws for any linear-differential-equation-based design problem.
The design problem of Eq. (3) has a different mathematical structure from Eq. (1). First, in Eq. (3), the design variable is no longer a degree of freedom. Instead, the possible design configurations are encoded in the quadratic constraints of Eq. (3). Now, the only degrees of freedom are in the field variable , and the constraints are all quadratic forms in . Objective functions of interest, such as power flow or momentum transfer in electromagnetism or state transfer, fidelity, and related objectives in quantum control, will also be quadratic (or linear) forms of . Hence, our new design problem is a quadratically constrained quadratic program, or QCQP.
Figure 1 schematically illustrates the change in viewpoint brought on by the transformation to a QCQP. We consider as an example the Helmholtz equation, in which wave speed can take values 1 (background) or 1/2 (patterned material), which corresponds to susceptibility values of and , respectively. The domains depicted in Fig. 1 are 5 wavelengths in size (with half-wavelength perfectly matched layers surrounding them). Figure 1(a) shows the specification of a structure in space, which prescribes the precise form of the corresponding linear operator. From the structure-specific operator, one can compute the fields. This is a powerful simulation tool, but it inhibits optimization approaches beyond gradient descent (local structural perturbations). Figure 1(b) shows the QCQP perspective, in which quadratic constraints are formed that must be satisfied by all possible designs. Optimizing over fields that satisfy these constraints, for example via semidefinite-programming techniques, can lead to discovery of optimal designs.

Figure 1. (a) The usual writing of a differential equation specifies different operator values at different space/time points according to the design variable (e.g. material susceptibility) . One can specify a structure (top right, a material with and approximately half-wavelength thickness, for a finite-difference discretization of the Helmholtz equation) and compute the corresponding field response (bottom right). (b) Our approach identifies quadratic constraints satisfied by all possible designs. Any field that satisfies these constraints (e.g. top right) will imply a corresponding design (bottom right, ) that produces the field. If the field optimizes an objective of interest, then the corresponding structure will be an optimal design.
Many sparse QCQPs are nearly convex
The next question is whether the QCQP of Eq. (3) offers mathematical advantages over the original problem. QCQPs are generally NP hard [63, 64], just as the original problem is. (If this were not true, Eq. (3) would prove that P = NP.) Yet QCQPs arise across many areas of science and engineering, and there is well-developed machinery for exploiting their specific mathematical structure [65, 66, 67, 68] [15, 17]. Geometrically, a set of quadratic constraints represents the intersection points of hyperboloids and ellipsoids; direct optimization over such intersections requires combinatorial algorithms. However, one can “lift” the problem to a higher-dimensional space, where the quadratic constraints in the original variables become linear (and therefore convex) constraints in a new matrix variable. This process introduces two additional constraints: a (convex) positive-semidefinite matrix constraint, and a nonconvex constraint on the rank of the new matrix. In this new, higher-dimensional setting, the objective and all constraints are convex, except for the rank constraint. In essence, all of the nonconvexity of the problem is isolated into the single rank constraint. This offers two exciting possibilities. First, one can simply drop the rank constraint, leaving a convex problem whose efficiently computable solution will always represent a bound, or fundamental limit, on the problem of interest. Second, the sparsity of differential operators can in some cases provably lead to low-rank solutions of this relaxed, convex problem, suggesting that many physical design problems may be “nearly convex” in this high-dimensional space. Then one may be able to introduce a rank-penalizing regularization that leads to high-quality, high-performance optimal designs that are superior to those found by typical gradient-descent-based techniques. In this section we first introduce the general “lifting” procedure, then we describe our proposed convexity-related approach to fundamental limits and novel designs.
The QCQP of Eq. (3) can be expressed generally as:
where iterates over all constraints (space/time/polarization/etc.), and are defined by the objective of interest, and equations are kept real-valued by separating the real and imaginary parts of the constraints of Eq. (3). “Lifting” is now well-known and well-understood (cf. Ref. [67] is one review); we include here a brief summary. The objective and each constraint of Eq. (4) are scalars, and one can trivially take the matrix trace of each. A trace is invariant under cyclic permutations; for example, . If we denote a new matrix variable , the quadratic form becomes a linear form, , in the new, higher-dimensional matrix variable . The linear forms in the original equation are straightforward to handle with conventional methods [67], ultimately leading to modified matrices and whose expressions are explicitly given in the SM. However, the entries of the matrix variable are not free to take on any values; because represents the outer product of a vector with itself, it must have rank 1 and be positive semidefinite. Following these steps, we can rewrite the QCQP of Eq. (3) and Eq. (4) as:
The trace-based objective and constraints are linear in , while the positive-semidefinite requirement is a convex cone constraint. Whereas each differential-equation-based constraint of the original problem was nonconvex, our new, equivalent problem in Eq. (5) has a convex objective and many convex constraints; the only nonconvex part of the problem is the rank-one constraint.
The observation that the rank-1 constraint is the only nonconvex part of the problem offers insights into “how convex” the design problem is in the lifted, higher-dimensional space. If we just drop the rank-1 constraint, the resulting problem, a semidefinite program (SDP), is convex. The question, then, is how large of a penalty one pays by dropping the rank-1 constraint and solving the SDP. For the famous NP-hard “max-cut” problem, in which one seeks to identify the maximum number of edges in a graph partition, an SDP relaxation is guaranteed to have a solution that is within 12% of the global optimum [66]. For most examples of lifting there is no such known bound; instead, the rank of the solution of the SDP is used as a measure of how convex the problem is. For example, if the rank of the SDP solution is quite large, then the solutions of the SDP and the original QCQP may be wildly different. In that case, the rank-1 constraint is clearly important for finding the correct solution, and it is unclear if a convex problem can lead one close to the optimal solution. By contrast, if the rank of the convex problem is small, then one can imagine making slight tweaks to the problem (e.g. adding a regularization or penalty function) to find a rank-1 solution of a related convex problem, which may be a high-quality solution of the original problem. (We show a numerical example of this type below.) Hence, the rank of the relaxed problem, the SDP, is an indication of how nonconvex the design problem is.
Strikingly, in certain physical scenarios we can use the sparsity of differential operators to prove that the rank of the computed solution of the relaxed problem is “small”; in particular, that the rank of the solution is bounded above by a constant that is independent of the long dimension of the problem. Bounds on the solutions of SDPs are common in problems with sparse
matrices [69], which we use in tandem with the differential operators that comprise and of Eq. (5). The matrix entries of the variable form a set of vertices, and the nonzero entries of the objective and data matrices, and , comprise edges of an undirected graph on those vertices. If the graph is chordal, then the size of the largest clique is known to be a bound on the maximum rank of a solution of the SDP [69]. (A brief review of the relevant graph-theoretic terms is provided in the SM.) If the graph is not chordal, then a bound can be found from any chordal extension of the graph. As we show in the SM, for any linear-differential-equation-based physical design problem that has one “long” dimension (e.g. waveguides, metasurfaces with translational or rotational symmetry, quantum control problems with time as the long dimension), the clique number is bounded above by a problem-size-independent constant. These physical design problems are provably “close” to convex optimization problems.
A convex optimization paradigm for physical design
In this section, we formulate two convex-optimization-related approaches to the design problem of Eq. (5). First, we define the SDP discussed above, with the rank-1 constraint dropped from the problem, which leads to bounds on any design problem of interest. Our second approach is to augment the SDP with a penalty term (typically convex) that encourages very-low-rank or even rank-1 solutions to the semidefinite program. This offers a new approach to designing physical structures, which comes with the possibility of avoiding many low-quality local optima.
Our first formulation simply drops the rank-1 constraint from Eq. (5), leaving the SDP:
Equation (6) is a relaxation of the original physical design problem, and as a convex optimization problem, its global optima can be found efficiently via interior-point methods [14]. A key feature of the solution is that it will always represent an upper (lower) bound to the objective to be maximized (minimized). This results directly from the dropping of the rank-one constraint; alternatively, it is known that Eq. (6) is equivalent to the dual problem of Eq. (5), and dual-problem solutions always bound their “primal” counterparts. A key feature of Eq. (6) is that it can be decomposed into smaller, coupled sub-problems when the matrices and are sparse. From Eq. (3), one can see that the sparsity of the matrices is determined primarily by , the differential operator, which is typically (e.g. in the case of the Laplacian) quite sparse. Fig. 2 demonstrates the sparsity patterns of the product that arises in Eq. (6), for the differential operators of electromagnetism and quantum mechanics. Significant dimensionality reduction requires a strong form of sparsity: not only many zero entries, but also chordal sparsity. The chordal completion of the operator is depicted in green in Fig. 2(b); the sparsity of this matrix determines the extent to which the SDP can be compressed (losslessly). Moreover, a sparse chordal completion leads to small maximal clique sizes, as depicted in Fig. 2(c), in stark contrast to SDPs formed from dense matrices. These maximal clique sizes are bounded above by a constant unrelated to the long dimension of the problem, suggesting that the SDP solutions may be informative for many design problems, which we support with numerical evidence in the next section.

Figure 2. (a) Differential equations on any domain (black grid) have a sparsity pattern that can be represented in an undirected graph (vertices 0–8). The chordal completion of that graph can be decomposed into “cliques,” smaller domains on which the problem can be defined. (b) The rank of the corresponding SDP, a measure of the nonconvexity of the design problem, is bounded above by the largest clique size. For dense matrices (as arise in integral equations), this is simply proportional to the size of the problem (red). By contrast, the sparsity of differential operators leads to maximum clique sizes that are bounded above by a constant unrelated to the “long” dimension of a physical-design problem. (C) Chordal completions of the sparsity patterns arising in various differential-equation-based design problems in electromagnetism and quantum information theory.
The second approach is to augment the semidefinite program of Eq. (6) to promote solution matrices with ranks close to or equal to one. While the rank operator itself is a nonconvex quantity, there are well-known proxy quantities that promote low rank, such as the matrix trace, which is known to be the best convex lower bound on rank for matrices with constrained singular values [70]. In feasibility problems, as occur, for example, in ptychographic imaging, one replaces the rank-1 constraint with an objective that promotes low rank [15]. For design problems, in which there is already an objective of interest, we can add a regularizer, i.e., a penalty for high-rank solutions, to the original objective. If we denote by a functional proxy for the rank of a matrix , then we can modify Eq. (6) to form the augmented program,
where can be adjusted to balance the original objective with the goal of a low-rank solution. The key idea is simple: if Eq. (7) has a rank-one solution (thanks to the regularization), then one has found the global optimum of a QCQP that is not exactly equivalent to the original QCQP of Eq. (5), but is similar to it. (The smaller is, the more similar the two problems are.) Intuitively, the global optimum of a slightly modified problem is likely to be a high-quality solution of the original problem, an idea that has been supported in previous numerical experiments across optimization theory, ptychography, and optimal power flow [66, 67, 68, 71] [6, 15], and is further supported by our results in the next section.
Equations (5–7) are key results of this paper. Equation (5) is the culmination of an exact transformation of a wide range of physical design problems, with objectives subject to differential-equation constraints, into sparse QCQPs. This connection to a common mathematical structure leads to Eqs. (6,7), the first of which is a convex problem that is guaranteed to identify bounds for the problem of interest, and the second of which offers a new approach to physical design, with the possibility for circumventing low-quality local optima. In the next two sections, we perform numerical experiments that demonstrate the power of these transformations.
Large-scale computational bounds
In this section, we demonstrate the utility of our sparse-QCQP-based SDP, of Eq. (6), for enabling computational bounds of large-scale systems for which such analysis is impossible with the current state-of-the-art methods. “Metasurfaces,” in which one patterns a wavelength-scale-thickness material to achieve high-performance optics functionality in compact form factors, offer a compelling example [72, 73, 74, 75, 76] [1, 2]. A metalens is a metasurface that focuses light to a single focal spot, and one typically wants a maximally efficient metalens with a diameter significantly larger than the free-space optical wavelength. In Figure 3, we consider a two-dimensional metasurface with diameter , thickness , refractive index , and numerical aperture , and pose a fundamental question: what is the maximum possible efficiency any designable pattern could achieve? To answer this question, we formulate the Maxwell-constrained design problem of Eq. (1), transform the problem to the sparse QCQP of Eq. (5), and relax the problem to the SDP of Eq. (6). We exploit the sparsity of the differential operators using the clique-decomposition technique outlined in Fig. 2, with the open-source software package SparseCoLO [77], to dramatically reduce the size of the SDP and enable computation of large-scale bounds. Figure 3(b,c) show bounds on the field intensities as a function of metalens diameter. One can see that the maximum field intensity depends sensitively on the metasurface thickness, and is well below the “unitary bound” arising from imposing unitarity constraints on the scattering matrix (cf. SM). A natural question is whether these bounds are achievable, and we include in Figure 3(b) four notable data points (black markers): designs taken from the first singular vectors of the SDP solutions can achieve real performance levels almost exactly coinciding with the bounds themselves; the designs found by this SDP procedure are shown in the blue inset patterns.

Figure 3. (a) Metalenses use nanophotonic patterning to focus incoming light. As a function of the diameter and thickness of the metalens, bounds on the maximal focal-point field intensity can be computed, shown in (b), using the SDP of Eq. (6). If the solution is low rank, as for the red curve, the solution of the SDP can be used to find designs (field intensity in black markers, structure in insets) that nearly achieve the global bound. (c) Conservation-law bounds can be much smaller than simpler approaches, such as unitarity. (d) The differential form of the Maxwell equations in the SDP leads to much linear-in-diameter scaling of computation times, enabling bounds for diameters up to 100 wavelengths.
Crucially, the sparsity enables computation at very large scale sizes. Whereas integral-equation formulations of QCQP bounds, as in Refs. [54, 60], require computational times that scale with the fourth power of the metasurface diameter, the differential-equation-based bounds scale linearly, enabling bounds for devices with diameters up to 100 free-space wavelengths in size.
A new approach to design
Having shown the success of the SDP approach to large-scale bounds, we now turn to the question of whether our lifted-QCQP framework can lead to a new design approach altogether. The idea is to use the regularized form of the lifted QCQP, in Eq. (7), to promote a rank-one solution of the lifted problem, which will be a global solution of a closely related QCQP. To test this approach, we consider a canonical example that showcases the difficulty of physical design in the presence of wave-interference effects: a multilayer nanophotonic film, with waves scattering back and forth between the many possible layers. We consider a maximum-reflection problem as shown in Figure 4, with a design region of multiple (in this case, four) free-space wavelengths, to achieve perfect reflection (reflection magnitude 1) with a specific reflection phase (arbitrarily chosen to be ). We consider a slightly lossy material (with refractive index , with a loss tangent typical of lossy materials in the visible); otherwise, any random collection of enough scatterers could generate perfect reflection (as in white paint). First, we run 100 full optimizations of “inverse design” [23, 26]; we use a typical implementation of inverse design, with the widths of the films as the degrees of freedom, and adjoint-based simulations to speed up the gradient calculations. We use a standard quasi-Newton “interior-point” algorithm of Matlab, with default convergence criteria, and we start with about half of the region as air and half as the material, with 80 layers whose widths are randomly chosen between 0 and 100 nm. (With significantly fewer than 80 layers, the optimizations tend to fall into even more low-quality local optima, while going well above 80 imposes a significant computational burden. The choice of 80 optimizes the tradeoffs between these competing effects.) Results from the 100 optimization runs are shown in Figure 4(b), with the bulk of the optimizations converging to designs with reflectivity between 40–50%, and the very best single design achieving only 88% reflectivity. Ten designs—eight random, alongside the two best—are shown on the left-hand side of Figure 4(b), showing the many different locally optimal designs that are discovered. Clearly one can see that gradient-based algorithms are prone to converging to local optima, especially for a problem with significant wave reflections.

Figure 4. (a) Schematic of a simple design problem with significant wave-interference effects: achieving large reflection, with a specific phase, from a multilayer stack of a slightly lossy material and an air background. (b) Inverse designs using interior-point methods to use adjoint-based gradient information can easily be trapped in local optima; the bulk of the optimization runs converge to 40–50% locally optimal efficiencies, while the best run, out of 100, finds a design with 88% reflectivity. (c,d) A single, iterative optimization using the augmented-SDP of Eq. (7) leads to a design (design widths in SM) that achieves 96.9% efficiency, far outperforming even the best of the 100 inverse-design runs.
To tackle this problem with an augmented SDP, per Eq. (7), we adapted an algorithm developed in Ref. [78] for QCQPs that arise in optimal power flow applications. The rank of a matrix can be written as a summation of step functions applied to the singular values of the matrix; in Ref. [78], they use a smooth approximation for the step function to construct the rank-penalization function . This function is well-suited for a majorization–minimization (MM) algorithm that is tailored to concave objectives subject to a convex constraint set. The MM algorithm applied as in Ref. [78] iteratively solves semidefinite programs with rank-penalized objectives until a locally optimal rank-one solution is found, at which point a hyperparameter can be tweaked if one wants a certificate of global optimality.
hyperparameter can be tweaked if one wants a certificate of global optimality. We find the latter step unnecessary, with a single (iterative) local optimum repeatedly showing quite good performance. Running the algorithm on the lossy-material high-reflection optimization discussed above leads to the result is shown in Figure 4(c): a design that achieves 96.9% reflectivity (and the correct phase), in a single optimization run, without any fine-grained hyperparameter tuning. One can see the difference between this approach and the inverse design approach in Figure 4(d), where the 100 initial reflectivities and locally optimal inverse-design reflectivities are shown in gray and orange, respectively, and the single lifted-QCQP-based optimization is shown in the blue marker. Clearly, the lifted-QCQP approach leads to a better design, with a more robust design process. One cannot directly compare the number of simulations used in each approach, as the lifted-QCQP optimization does not do any “simulations” at each iteration, but the typical inverse-design optimization required 21 seconds on a 2021 Macbook Pro, for a total of 35 minutes for the 100 optimization runs, with a maximum reflectivity of 88%. The lifted-QCQP optimization took 5 minutes on the same computer, leading to a design with 96.9% reflectivity. (The reported time is the full runtime, with all subroutines and iterations included.) Moreover, the design discovered in the lifted-QCQP approach appears to be a quite plausible global optimum for this problem. Having seen the design, one can explain the physics of its operation: the spacings between consecutive films are nearly exactly half a wavelength, to create constructive interference in the reflected wave. Moreover, the films show a thickness gradation, which is sensible given the lossiness of the material: the first layers are likely to interact with many scattered waves, and should be thin to avoid material losses, while the rear layers simply need to reflect the waves at any cost and can be thicker as a result. (The thicker first layer likely sets the correct phase.) Hence this result shows not only very good performance, but is suggestive of discovering a near-globally-optimal design, as anticipated in the theoretical derivations of Sec. I C.
Discussion and Conclusion
In this paper, we have connected design problems subject to the dynamics of the linear differential equations of physics to modern convex optimization theory. By rewriting these design problems as conservation laws defined by differential operators, we identify a unique structure pervasive across physical design problems: they can be transformed to sparse QCQPs. Sparse QCQPs can be lifted to higher dimensions, where their SDP relaxations offer a general framework for large-scale computational bounds. Tantalizingly, regularizing the SDP can lead to efficient techniques for identify designs that may often approach the global optima, as we demonstrated for an electromagnetic design problem subject to significant amounts of speckle and wave-interference effects.
Many areas of science and engineering, including optimal power flow [68, 71], ptychography [15, 16], VLSI design and Ising problems [79], and more, have benefited from connections to semidefinite programming going back two decades [67]. It had seemed that wave-physics and related physical design problems simply had unfavorable mathematical structure, where such techniques would not work, but our approach shows that even wave-based design problems can fit into this paradigm. One concern might be the significant computational cost of standard SDP solvers—they have polynomial run-times, but the polynomial is typically 3.5 or 4 (i.e., runtime scales as or for degrees of freedom), which prevents the application of SDPs to large-scale optimization problems [67]. Auspiciously, there has been significant recent progress in computational algorithms for semidefinite programming [80, 81, 82, 83] [16]; in one recent work [16], SDPs with designable degrees of freedom, corresponding to matrix variables, were solved.
Moreover, whereas we used the chordal sparsity in tandem with clique decompositions that are possible when one dimension of the problem is significantly larger than any others, newer SDP techniques such as those of [16] can exploit broader sparsity characteristics, beyond just chordal sparsity. These improvements may be readily adaptable to our physical-design SDPs.
Looking forward, there is ample opportunity to apply this technique broadly across many applications in photonics, quantum control, elasticity, and more. In addition to the scalability improvements enabled by the differential-equation formulation, discussed above, another feature of our approach is that it can work seamlessly with the many open-source and commercial differential-equation solvers in widespread use. As an example, in the SM, we show that one can create an SDP directly from the governing matrix equations created by Comsol [84] and successfully identify the correct bounds. This suggests the possibility for our approach to become widely adopted across common differential-equation solvers.
An interesting contrast between our approach versus “inverse design” and deep-learning approaches is that the latter are “structure-blind”: aside from changes in the oracle functions to be called, the algorithms are not meaningfully modified for different design problems (linear, nonlinear, chaotic, etc.). Our approach specifically applies to physical design problems with bilinear structure in the field and geometric degrees of freedom (which are quite widespread), and cannot be generically applied to any problem. This is consistent with the “no free lunch” theorem [85]: there cannot be a single optimization method that is superior to others on all optimization problems. Our results suggest that a bespoke approach, with algorithms tailored to the underlying mathematical structure of the design problem of interest, may lead to a suite of design approaches that are superior to the structure-blind algorithms used today.
Acknowledgments
We thank Javad Lavaei and Somayeh Sojoudi for helpful discussions regarding sparse-QCQP formulations of optimal power flow. This work was supported by the Army Research Office under Grant No. W911NF-19-1-0279 and by the Air Force Office of Scientific Research under Grant No. FA9550-22-1-0393.
Supplementary Materials: Many Physical Design Problems are Sparse QCQPs
Shai Gertler; Zeyu Kuang; Colin Christie; Owen D. Miller
Detailed Constraint-Formulation Methodology
In this section, we provide further details on the form of the quadratic constraints introduced in the main text. We start with the differential equation
We will assume a discretization for which there are designable points in space/time, there are non-designable points in space/time (e.g. PML regions, background materials, etc.), and that there are vector (polarization, Hilbert-space, etc.) degrees of freedom at each point in space/time. Then and both have sizes , and is a matrix of size . We will take the typical case in which the control field can be controlled at each designable space/time point, but does not have independent levers of control along the polarization/Hilbert/etc. axis. (For example, we are assuming one cannot independently control the material properties of each polarization at a given point in space in a nanophotonics problem. Such control in fact slightly reduces the size of the ultimate QCQPs, and slightly simplifies the analysis below.)
First, let us tackle what happens at a designable point in the domain. If we denote this point , then
is a vector for each of and . We want to enforce the condition that
where the zeros are the right-hand sides are the zero vectors. Consider two vectors and , both of size , for which we want to enforce the condition that either one of the vectors is the zero vector. How can we do that? The key is to enforce
i.e., to force each pairwise inner product to be zero. This expression says that for each , one of the two entries must be zero. (Or both, but that is typically forbidden by the form of . ) The only way for this condition to be met for all and is for all of the entries of one of the vectors to be zero. This can be proven by contradiction. Suppose both vectors are nonzero—that is, each have at least one element that is not zero—and that they satisfy Eq. (4). Then choose and to be the indices of nonzero elements in each vector. Their product is not zero, contradicting the requirement that Eq. (4) be satisfied. Thus we see that Eq. (4) requires (at least) one of the vectors to be zero, which is exactly the either–or condition that we desire.
We can alternatively write the condition of Eq. (4) in matrix form,
where is a matrix with all zeros except a single entry of 1 in its element. Now let us return to the differential equations of above. We can just directly substitute for , and similarly but with for , to get
Finally, we clean up the notation a bit. In Eq. (6), is an index for the space/time point, while and are indices in the polarization/Hilbert space. We can wrap all of these into a single index that iterates over all space/time points and all polarization/Hilbert-space combinations; we can also enlarge to be a fully matrix (instead of smaller matrices iterated times), now just with all entries of the larger matrix being zero except at single at the th entry. Then we can drop the evaluation of the vectors at (since multiplication by the entire matrix effectively does this already), and we can write Eq. (6) in exactly the same form as expressed in the main text,
Next, we tackle the non-designable points in the design space. At each of those points, there are not two possibilities for , but instead only a single one—whatever the background material is at that point in the domain. Hence, we enforce linear constraints of the form
However, once the problem is lifted and relaxed in a higher-dimensional space, it is not clear that these constraints will be binding, and indeed it has been found quite useful for some QCQPs to add seemingly redundant constraints to their formulation; those constraints are not redundant in the lifted, relaxed space [1]. We find it helpful to add quadratic forms exactly equivalent to Eq. (7) at each nondesignable point, except that now both terms have in them:
The constraints of Eqs. (7–(16) form all of the constraints of the system. In total, there are quadratic constraints, and linear constraints.
What if one has multilevel level controls? If there were three possible control-field values, , , and , then the natural analog of the approach above is to multiply each of the three expressions, , together, to form a single constraint, which would then be a third-order polynomial in . More generally, for possible control-field values, one would form th-order polynomial constraints by this approach. It is well-known that optimization problems with polynomial objectives and polynomial constraints are a subclass of QCQPs—cf. Sec. 2.1 of Ref. [2]. The key idea is the extra variables can be introduced to reduce the order of the problem, at the expense of additional constraints. For example, if a constraint is , one equivalently enforce and ; in this example, two second-order (at most) constraints are equivalent to the single third-order constraint.
Interpreting the quadratic constraints as conservation laws
In this section, we justify our statement that a constraint of the form
represents a conservation law. To do so, we first go back to the continuous representation, in which is an operator and is a vector field, and rewrite Eq. (17) as an overlap integral. The matrix in Eq. (17) has a single nonzero entry; its purpose is to isolate a single space/time point and specific polarizations (Hilbert-space indices) for the two equations. A similar isolation of specific space/time/polarization/etc. locations can be achieved in continuous space by taking an inner product with a function that encodes the desired localization. Hence we can write
where , and denotes the adjoint operator. To simplify notation below, we will assume is always zero, and rewrite as , as the “background” control field can always be shifted to make this true, such that the quadratic constraint is:
In the following subsections, we use the explicit forms of in electromagnetism and quantum control to show that Eq. (19) can be interpreted as a conservation law.
Electromagnetic design
We consider Maxwell’s equation describing a monochromatic field at frequency in a nonmagnetic material (i.e., the relative permeability is everywhere in space). The electric field can be written as
where are source currents, is the (designable) susceptibility, and we use dimensionless units where the vacuum permittivity and permeability are both 1. In line with the discussion above we take to be allowed two values, 0 or . Then,
To simplify our notation, we will define a background- operator,
so that . Then Eq. (19) can be written:
Multiplying by a factor and rearranging leaves us with the constraint:
To see the equivalence of this form to a power conservation law, we introduce the “polarization density”
Using this definition in the constraint we have derived in Eq. (24) we have
We can further simplify the second term; using Maxwell’s equation and the vector identity , we have
where in the last step we used the divergence theorem to express the second term as a surface integral. Next, we turn to the first term in Eq. (26); at points where we know that . This is not true in regions where , however, in these regions . Hence, we can rewrite the inner product as . All together, this leaves us with
which is precisely the complex Poynting theorem for the case of non-magnetic material [3].
Six-vector notation
We can write a general six-vector form for Maxwell’s equations; denoting the fields and the current sources , we have
where is the material susceptibility tensor, which can have both electric and magnetic (and magnetoelectric) components. We assume the susceptibility tensor can take one of two values at each point in space , and we can define the operator
such that we have the constraint
Defining a “polarization field”
we have
As we saw earlier, in regions where we have , and where the polarization vanishes (), such that we can rewrite the first term
Taking the real part of Eq. (34), we have a statement of the real Poynting’s theorem [4]
We can follow a similar procedure to obtain the imaginary part of Poynting’s theorem. Interestingly, it does not arise simply from taking the imaginary part of Eq. (34).
Quantum control
In this subsection we show that our quadratic-constraint formulation of quantum control problems also represents conservation laws. We start with a Hamiltonian of the form
where is the non-controllable part of the Hamiltonian, is the controllable part, and is the control trajectory to be designed. The Schrodinger equation describes the temporal dynamics of the time-evolution operator (for some initial time ), given by
In this case, rather than source term, we have an initial condition at time . Using Eqs. (36) and (37), we have
where we have set . We assume the control parameter can take one of two values , and denoting the operator
we have the constraint:
Multiplying by and rearranging leaves us with the constraint:
Inserting the expression for into the term on the right-hand side and rearranging gives
Taking the real part of this equation leaves us with:
where “Im” denotes the anti-Hermitian part of the operator, and we have used the fact that . In the case of real-valued control parameter and Hermitian operators, i.e., , we have
which represents conservation of probability in a Hermitian (closed) system. In a non-Hermitian system, the term on the right-hand side would simply give the probability loss due to the non-Hermiticity. Taking the imaginary part of Eq. (42) leads to a “reactive” probability conservation, in analogy with reactive power conservation in electromagnetism.
Forming the SDP by lifting the QCQP
In this section we provide the explicit transformations from the QCQP form of the problem to the SDP relaxation. This procedure is well-known, cf. Ref. [5], but we also include the formulation here, for reproducibility. We start by writing the QCQP:
where is the set of indices in the designable domain, is the set of indices in the PML, and refers to the set of -dimensional complex-valued vectors. Before any transformations, we can compactify our notation:
To arrive at Eq. (47), we use four steps. First, we combine the quadratic constraints of Eq. (46) into a single form, differentiated only by index , in the now larger set . Second, we form the linear constraints by multiplying over a basis set of vectors . Third, we define . Finally, we take the real parts of the quadratic and linear constraint equations of Eq. (46), and we account for the imaginary parts by allowing for and to take unit entries or their complex counterparts (i.e., multiplied by the imaginary unit).
The first step to simplifying Eq. (47) is to homogenize the problem, which means to transform the linear terms in the QCQP to quadratic terms, so that all terms in Eq. (46) are either quadratic or scalar. We can do this by introducing a new slack variable into the objective and constraints, multiplying the linear terms. This slack variable must have absolute value 1, but it can be positive or negative; a negative one value would be compensated in by multiplying by . With this new slack variable, the problem can be written
in which all of the expressions are either quadratic in the combined variable , or scalar values. We can again make the notation more compact, and write this problem as a homogenized, complex-valued QCQP:
To then convert this to a complex-valued SDP, we simply take the trace of each expression, which does not modify any values, then use the invariance of trace under cyclic permutations to form the product , which we define to be a new positive semidefinite, rank-one matrix . The equivalent problem for this matrix variable is
We can relax this problem by dropping the rank-one constraint, leaving the standard-form (complex-valued) SDP:
In this form, the problem can be solved in any SDP solver. (If the solver does not accept complex-valued matrices, it is simple to double all dimensions and separate the real and imaginary parts of the vectors and matrices.)
Graph Theory for Semidefinite Programming
Graphs distill real-world relations into abstract lines and vertices, for social networks in sociology, genetic networks in biology, communication networks in computer science, lattice structures in physics, and molecular chains in chemistry. Complex dynamics can simplify when occurring on graphs with special structure. In particular, chordal graphs represent a class of connections where many hard problems can be easily solved, including graph coloring, clique finding, and matrix factorization [6]. In this section, we review basics of graphs and chordal graphs, as well as theorems that foreground chordal graphs in sparse semidefinite programming.
A graph comprises a set of vertices and their connecting edges . The vertices and edges uniquely define the graph: . We consider undirectional graph whose edges are unordered pairs, denoted by curly brackets such as . If a series of edges leads one vertex back to itself, then these edges form a cycle. Two vertices and are adjacent if there is an edge between them, i.e., if . Vertices that are all adjacent to each other form a clique. A clique can expand upon admitting new vertices that are adjacent to all its existing members. If no such new vertices exist, the clique is then called a maximal clique of the graph.
Many large problems can be simplified if their graph is a chordal. A chordal graph is a graph in which every cycle of length four and greater has a chord (an edge between nonconsecutive vertices of the cycle). In other words, if you trace a cycle of four (or more) edges without finding a shortcut, then the graph is not a chordal graph. Any graph can be made chordal by adding extra edges. In the extreme case, supplying every possible edges guarantees a chordal graph, but then there can be no problem-size reduction. The art is to add as few edges as possible to make a graph chordal. This procedure is called chordal completion, often implemented via heuristic algorithms [7].
Sparsity in matrices map to specific graph representations of the matrix data. Zeros in a symmetric matrix are missing edges in the corresponding undirected graph : . Two groups of symmetric matrices are of particular interest in sparse semidefinite programming. The first are matrices that are positive semidefinite and sparse, with sparsity pattern given by the graph :
where (without argument) refers to the set of positive definite symmetric matrices. The second group consists of matrices that are not necessarily positive semidefinite or sparse but can be “completed” into positive semidefinite matrices. To motivate this, consider an inner product between the symmetric matrix and a sparse symmetric matrix whose sparsity is given by the graph . The inner product multiplies matrices element-wise, so only the elements in that correspond to the edges in the graph are involved in the computation of the inner product. If the rest of the elements in can be altered to turn into a positive semidefinite matrix, say , then we say belongs to a group of completable partial symmetric matrices:
The two matrix spaces, and , are both convex cones and, in fact, are duals of each other [6]. Together, they constitute the basic matrix spaces in sparse semidefinite programming.
Crucially, if the graph is a chordal graph, both types of matrices above can be decomposed into smaller matrices defined on the maximal cliques of the graph, . Aiding this decomposition is a projection matrix that projects a matrix into its principle submatrix , and reads if and zero otherwise, where is the -th vertex in . If the matrix is positive semidefinite completable, i.e., , then all the submatrices are all positive semidefinite, as dictated by Grone’s theorem [8]:
If the matrix is sparse positive semidefinite, i.e., , then all the submatrices are positive semidefinite and uniquely expand the matrix , as dictated by Agler’s theorem [9]:
Agler’s theorem in Eq. (55) allows one to decompose sparse semidefinite programs in their dual forms, where the matrix variable directly inherits the sparsity of the problem; Grone’s theorem in Eq. (54) allows one to decompose sparse semidefinite programs in their primal forms, where the the matrix variable does not inherit the sparsity but is multiplied by matrices that do. We discuss this second scenario in the next section.
Fast Semidefinite Programming on Chordal Graphs
Semidefinite programs are challenging to solve for large-dimensional problems, unless there is sparsity to be leveraged. Sparsity mainly accelerates two operations in the semidefinite programming in Eq. (51): multiplying matrix by matrix , and verifying the semidefinite constraint, , is satisfied. These two operations are the numerical bottleneck for most semidefinite programming algorithms [5, 10], both costing at least per iteration for an -dimensional problem. To accelerate these two operations, one needs to consider the aggregate sparsity pattern of the semidefinite program in Eq. (51), which are the places where all the objective and constraint matrices, , are zero. The aggregate sparsity pattern is given by the sparsity pattern of the matrix in the QCQP in Eq. (46), which is shown as the black and red squares in Fig. 1(b) in the main text for a number scenarios. Most sparsity can accelerate matrix-matrix multiplications by multiplying only the nonzero entries. On the other hand, only a special type of aggregated sparsity based on chordal graphs can accelerate the verification of the semidefinite constraint, which we explain below.
The major bottleneck of large-scale semidefinite programming is the verification of its semidefinite constraint, which is resolvable if the underlying sparsity pattern corresponds to a chordal graph [6]. There is a unique mapping between sparsity pattern of symmetric matrices and undirected graphs: an nonzero entry of the former maps to a edge between the and vertices of the latter. (See Section IV for a quick review on graph theories.) A chordal graph, in particular, is a graph where all cycles of four or more vertices have a chord. As shown in the Fig. 1(a) of the main text, the sparsity pattern of the operator in our photonic problem does not necessarily correspond to a chordal graph but it can be made into one by adding extra chords (the green lines in Fig. 1(a)). Chordal graph is desirable because it allows one to distribute certain complex operations into different “cliques”, a set of vertices in the graph that are all connected to each other (as in Fig. 1(a)). In particular, if the aggregate sparsity of the semidefinite program in Eq. (51) can be completed into a chordal graph, then Grone’s theorem in Eq. (54) shows its semidefinite constraint can be replaced by “smaller” semidefinite constraints on each of its cliques: , where denoting the indices for the th clique. The optimization problem of Eq. (51) becomes
where to denotes the total number of cliques in the chordal graph. The only difference between the decomposed semidefinite program and the original semidefinite program is the semidefinite constraints are now applied to smaller cliques. As the semidefinite constraint is the main computational bottleneck that increases as with the matrix size , breaking a large into many smaller ones in Eq. (56) allows us to significantly accelerate the SDP computations.
Implementation of the Majorization-Minimization Algorithm
To obtain a rank-1 solution to the QCQP, a proxy function for rank is incorporated into the objective as a penalty term to be minimized:
We successfully generated rank-1 solutions to Eq. (57), following the methods introduced by Liu, Sun, and Tsang in Ref. [11], producing designs from the modified-SDP formulation. Here we summarize the key steps of Ref. [11] that we implemented.
The first step is to find an approximate representation of the rank. One way to write the rank is to count the number of nonzero singular values, which is given by
where is the singular value of and is the Heaviside step function, equal to 1 if and 0 if for H(x)$ is non-differentiable and therefore cannot be used in gradient-based optimization, but it can be approximated by the smooth, differentiable function
with , noting that . Defining
the goal is to solve Eq. (57) with . The non-differentiability of the rank function has been removed, but is still concave.
A concave function has a special property: it is bounded above everywhere by any tangent plane intersecting the function at one point. In other words, the value of the function at a given point (matrix), plus a term given by the inner product gradient of the function and the difference between the two points, will always be an upper bound to objective function itself. In this case the approximate rank function has (elementwise) gradient
where is the singular value decomposition of (equivalent to its eigendecomposition, since is positive semidefinite). Then, for any feasible matrix obtained at the iteration,
The first term on the right-hand side of Eq. (62) is constant with respect to , while the second term is linear. Hence minimizing the second term is a convex optimization problem, and will result in a minimization of Eq. (62), which is itself an upper bound on rank. We define the objective to minimize as :
Thus by iteratively solving convex optimization problems, we can continuously push down an upper bound on the rank, and thereby the rank itself, ideally near 1. This is an example of a “majorization–minimization” algorithm [12]. To select an initial point for the optimization, we solve Eq. (57) with . For positive-semidefinite matrices, the trace is a well-known proxy for rank. Additionally, since becomes highly concave as , which is liable to cause computational difficulty, we execute the MM algorithm iteratively over decreasing values of until convergence. Putting everything together, with convergence tolerances , we implement the following process:
Define arbitrary initial .
Solve Eq. (57) with to obtain an initial .
Define arbitrary initial .
Solve Eq. (57) with for the optimal solution . Repeat until .
Define the output of Step 4 as . Decrease by an arbitrary factor and repeat Step 4. Repeat until .
Repeat steps 2-5, increasing by an arbitrary factor , until .
We make simple (non-optimized) choices , , , , , , and .
Metalens bound calculation
Formulation of the target function
We consider a two-dimensional scattering problem for a TE-polarized electric field (such that it can be treated as a scalar electric field) and we seek to optimize the intensity of the field at a target point . We denote the field at the target point as , and calculate a bound on the maximal value of the quantity , given a narrow design region of length in which each point in can be vacuum or a material with susceptibility (see Fig. 2(a) of the main text). We can express the field at the target point as
where is the incident field at the target point, i.e., in the absence of material, and is the scattered field at the target point. Note, that the background field solves the background- operator, i.e., . The target point is set at a distance from the design region, such that the numerical aperture (given by is set to .
We can express the scattered field at the target point using a Green’s function
where is the polarization currents in the design material, given by
For clarity of notation, we will denote the integration as an operator (numerically, this a row from the matrix representing the Greens’ function).
A natural way to proceed is to substitute Eqs. (65) and (66) into Eq. (64) and squaring:
However, in this case, the target function has a matrix of the form , which is not sparse, and we will not be able to exploit the sparse structure of the problem in the optimization.
An alternative formulation of the target function, which preserves sparsity, is given by
where is an auxiliary angle. After the optimization procedure, we can square the result to obtain . Explicitly, we have
which is linear in the term and preserves the sparse nature of the problem. Together with Eq. (24), this forms the QCQP to be solved.
Fig. 1 shows the results of the optimization process for different values of , from which the maximum can be selected. While this approach requires multiple optimizations (sweeping over different values of ), the speed-up provided by the sparseness of this form is significantly faster compared to non-sparse formulations, and enables the optimization over large domains (see Fig. 2(d) in the main text).

Figure 1 (PDF p. 23). Optimization results for the field intensity focused by a metalens of different lengths (), using an auxiliary angle (see Eq. (69)).
Scattered-field formulation
The target function in Eq. (70), as well as the constraints from Eq. (24) are quadratic form in the total field (). Alternatively, the QCQP can be written where the quadratic form is of the scattered field (given by ). Using Eqs. (65) and (66) we can rewrite the target function in terms of :
Similarly, we can express the constraints from Eq. (24) in terms of scattered field:
Using and rearranging, we are left with:
Together, the target function (Eq. (71)) and the constraints (Eq. (74)) form a QCQP in the scattered field .
Unitary bound
In this section, we derive a bound for the efficiency of a metalens of length based on the unitarity of the scattering matrix describing the system. In the most general case, we can write the field at the target point using Green’s functions:
where and are the electric and magnetic Green’s functions, respectively, and and represent electric and magnetic current sources, respectively. After discretizing the domain, we have the matrix form:
where is the discretization step size, and squaring the field at the target point, leaves us with:
Assuming the incident field is a plane wave with amplitude 1, we can normalize the current distributions:
We can now write the intensity maximization problem:
In order to solve the equation above, we define a normalized current , such that the problem can be rewritten in the following form:
The optimization problem is now in the form of a Rayleigh quotient, where the maximum of the target function is given by the largest eigenvalue of . The results of this bound calculation are shown in Fig. 2(c) of the main text.
Compatibility with FEM solvers
The formulation we present here utilizes the differential form of the physical equation, which is used in many commercially available solvers. These can be both finite difference (FDFD) solvers, as well as finite element (FEM) solvers. Here, we demonstrate how an FEM electromagnetic solver (COMSOL) can be used to calculate a bound in a simple photonic problem. We model a 2D system, with a geometry shown in Fig. 2(a). We set periodic boundary conditions for the top and bottom boundaries and simulate perfectly matched layers (PML) on the sides on the structure. Fig. 2 After setting current sources, we export the matrix and vector describing the linear system as constructed by the software. We choose the point that comprise a ‘design’ region (see Fig. 2(b) for an example) and calculate bounds for the maximal value of the target function
i.e., integrated field intensity over the entire design region . In this example, the material has a refractive index of , and the optical wavelength was set to . For comparison, we repeat the calculation with a finite-time frequency domain solver (FDFD). Fig. 2(c) shows the calculated bounds as a function of design region length. We see that the FDFD and FEM based bound calculations agree, showing a linear dependence of the target function with the design region length.
Discussion of related work
Ref. [13] is a delightful review of approaches to inverse design and performance bounds, especially techniques that had been developed by early 2021. Yet Ref. [13] goes significantly further, offering a unified, generalized mathematical framework for these approaches. Here we discuss the bound approach, newly developed in Ref. [13], that is close to the approach we propose in the main text.

Figure 2 (PDF p. 25). (a) COMSOL-generated mesh, and a magnified view of the degrees of freedom being solved for. (b) Calculated bound as a function of design region length, using differential operators from FEM (red) and FDFD (blue) solvers. Simulation results of an unstructured dielectric (using both solvers) are shown for reference.
The starting point of Ref. [13] is a physical design problem written in the form
where is a design-independent differential operator (plus, possibly, the identity matrix scaled by background constants), is a diagonal matrix whose diagonal elements are the designable degrees of freedom, is the field of interest, and comprises the sources.
The matrices and vectors in the physical design equation are all assumed to be real-valued. From this assumption, they derive “power inequalities” of the form
which is equivalent to the power-conservation bounds of [14, 15], when all of the equations are real-valued.
Yet in nearly all cases of interest, the fields and design variables cannot be trivially assumed as real-valued. Complex values are of course built into quantum dynamics. In electromagnetism, open boundaries require complex-valued fields (e.g., through perfectly matched layers). Plasmonic structures require loss. Perhaps the one exception is the calculation of modes of closed, periodic systems (e.g. photonic crystals), for eigenstate properties. For any scattering problem with a source, however, the power from the source must be dissipated in either the material or into far-field radiation, with complex-valued fields as a result.
The formulation of Ref. [13] does not lead to a design QCQP when the fields are complex-valued. In order to transform the original, complex-valued physical design equation to a real-valued form of the type of Eq. (82), one must perform a standard doubling of the dimensions of the vectors and matrices, separating the real and imaginary parts of all variables involved. (See Ref. [16] for detailed descriptions of these steps.) This leads to a vector of design variables that is twice as large as the number of degrees of freedom, and within which the first and second halves of the vector should be equal. Such a constraint is a pain to enforce, however (it possibly could be enforced by the methods of Ref. [17], and instead is dropped in [13, 16]. Hence, that approach leads to a relaxed QCQP that can be used for bounds, but not a QCQP formulation of the design problem, as proposed in the main text.
References
- [37]J. Peurifoy, Y. Shen, L. Jing, Y. Yang, F. Cano-Renteria, B. G. DeLacy, J. D. Joannopoulos, M. Tegmark, and M. Soljačić, Nanophotonic particle simulation and inverse design using artificial neural networks, Science advances 4, ea arXiv:ear4206 (2018).DOI
- [38]J. Jiang and J. A. Fan, Global optimization of dielectric metasurfaces using a physics-driven neural network, Nano letters 19, 5366 (2019).DOI
- [39]M. Raissi, P. Perdikaris, and G. E. Karniadakis, Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations, Journal of Computational physics 378, 686 (2019).DOI
- [40]Y. Kiarashinejad, S. Abdollahramezani, and A. Adibi, Deep learning approach based on dimensionality reduction for designing electromagnetic nanostructures, npj Computational Materials 6, 1 (2020).DOI
- [41]Z. Yu, A. Raman, and S. Fan, Fundamental limit of nanophotonic light trapping in solar cells, Proc. Natl. Acad. Sci. U. S. A. 107, 17491 (2010).DOI
- [42]O. D. Miller, A. G. Milleridis, M. T. H. Reid, C. W. Hsu, B. G. Delacy, J. D. Joannopoulos, M. Soljačić, and S. G. Johnson, Fundamental limits to optical response in absorptive systems, Optics Express 24, 3329 (2016).DOI
- [43]O. D. Miller, S. G. Johnson, and A. W. Rodriguez, Shape-independent limits to near-field radiative heat transfer, Physical Review Letters 115, 204302 (2015).DOI
- [44]J.-P. Hugonin, M. Besbes, and P. Ben-Abdallah, Fundamental limits for light absorption and scattering induced by cooperative electromagnetic interactions, Physical Review B 91, 180202(R) (2015).DOI
- [45]Miller, O. D., Ilic, O., Christensen, T., Reid, M. T. H., Atwater, H. A., Joannopoulos, J. D., Soljačić, M., & Johnson, S. G. (2017). Limits to the optical response of graphene and two-dimensional materials. Nano Letters, 17, 5408.
- [46]S. Sanders and A. Manjavacas, Analysis of the limits of the local density of photonic states near nanostructures, ACS Photonics 10.1021/acsphotonics.8b00225 (2018).DOI
- [47]H. Zhang, C. W. Hsu, and O. D. Miller, Scattering concentration bounds: Brightness theorems for waves, Optica 6, 1321 (2019), 1810.02727.DOI
- [48]H. Shim, L. Fan, S. G. Johnson, and O. D. Miller, Fundamental Limits to Near-Field Optical Response over Any Bandwidth, Phys. Rev. X 9, 11043 (2019).DOI
- [49]S. Molesky, P. Chao, W. Jin, and A. W. Rodriguez, Global T operator bounds on electromagnetic scattering: Upper bounds on far-field cross sections, Phys. Rev. Res. 2, 033172 (2020).DOI
- [50]Gustafsson, M., Schab, K., Jelinek, L., & Capek, M. (2020). Upper bounds on absorption and scattering. New Journal of Physics, 22, 073013.
- [51]R. Trivedi, G. Angeris, L. Su, S. Boyd, S. Fan, and J. Vuckovic, Fundamental bounds for scattering from absorptionless electromagnetic structures, arXiv Prepr. arXiv2003.00374 , 1 (2020), arXiv:2003.00374.DOI
- [52]S. Molesky, P. S. Venkataram, W. Jin, and A. W. Rodriguez, Fundamental limits to radiative heat transfer: Theory, Phys. Rev. B 101, 35408 (2020), arXiv:1907.03000.DOI
- [53]Z. Kuang and O. D. Miller, Computational bounds to light–matter interactions via local conservation laws, Physical Review Letters 125, 263607 (2020), arXiv:2008.13325.DOI
- [54]S. Molesky, P. Chao, and A. W. Rodriguez, Hierarchical mean-field t operator bounds on electromagnetic scattering: Upper bounds on near-field radiative purcell enhancement, Physical Review Research 2, 043398 (2020).DOI
- [55]F. Presutti and F. Monticone, Focusing on bandwidth: achromatic metalens limits, Optica 7, 624 (2020).arxiv.org/abs/2001.10899
- [56]S. Li and C. W. Hsu, Thickness bound for nonlocal wide-field-of-view metalenses, Light: Science & Applications 11, 338 (2022).DOI
- [57]Miller, D. A. (2023). Why optics needs thickness. Science, 379, 41.
- [58]Yablonovitch, E. (1982). Statistical ray optics. J. Opt. Soc. Am., 72, 899.
- [59]Mandelstam, L., & Tamm, I. (1945). The Uncertainty Relation Between Energy and Time in Non-relativistic Quantum Mechanics. J. Phys. USSR, 9, 249.
- [60]Z. Kuang and O. D. Miller, Computational bounds to light–matter interactions via local conservation laws, Physical Review Letters 125, 263607 (2020).DOI
- [61]H. Zhang, Z. Kuang, S. Puri, and O. D. Miller, Conservation-law-based global bounds to quantum optimal control, Physical Review Letters 127, 110506 (2021), arXiv:2105.06054 [quant-ph].DOI
- [62]G. Angeris, T. Diamandis, J. Vučković, and S. Boyd, Bounds on efficiency metrics in photonics, arXiv preprint arXiv:2204.05243 (2022).arXiv
- [63]Sahni, S. (1974). Computationally related problems. SIAM Journal on computing, 3, 262.
- [64]J. Park and S. Boyd, General heuristics for nonconvex quadratically constrained quadratic programming, arXiv preprint arXiv:1703.07870 (2017).arXiv
- [65]Boyd, S., El Ghaoui, L., Feron, E., & Balakrishnan, V. (1994). Linear matrix inequalities in system and control theory.
- [66]M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM) 42, 1115 (1995).DOI
- [67]Luo, Z.-Q., Ma, W.-K., So, M.-C., Ye, Y., & Zhang, S. (2010). Semidefinite relaxation of quadratically constrained quadratic optimization problems. IEEE Signal Process. Mag., 27, 20.
- [68]S. Sojoudi and J. Lavaei, Physics of power networks makes hard optimization problems easy to solve, in 2012 IEEE Power and Energy Society General Meeting (IEEE, 2012) pp. 1–8.DOI
- [69]Vandenberghe, L., Andersen, M. S., & al., . et . (2015). Chordal graphs and semidefinite optimization. Foundations and Trends® in Optimization, 1, 241.
- [71]Madani, R., Sojoudi, S., & Lavaei, J. (2014). Convex relaxation for optimal power flow problem: Mesh networks. IEEE Transactions on Power Systems, 30, 199.
- [72]Aieta, F., Kats, M. A., Genevet, P., & Capasso, F. (2015). Multi-wavelength achromatic metasurfaces by dispersive phase compensation. Science, 347, 1342.
- [73]A. Arbabi, Y. Horie, M. Bagheri, and A. Faraon, Dielectric metasurfaces for complete control of phase and polarization with subwavelength spatial resolution and high transmission, Nature nanotechnology 10, 937 (2015).DOI
- [74]O. Avayu, E. Almeida, Y. Prior, and T. Ellenbogen, Composite functional metasurfaces for multispectral achromatic optics, Nature communications 8, 14992 (2017).DOI
- [75]S. M. Kamali, E. Arbabi, A. Arbabi, and A. Faraon, A review of dielectric optical metasurfaces for wavefront control, Nanophotonics 7, 1041 (2018).arxiv.org/abs/1804.09802
- [76]Chung, H., & Miller, O. D. (2020). High-NA achromatic metalenses by inverse design. Optics Express, 28, 6945. 1905.09213
- [77]Kim, S., Kojima, M., Mevissen, M., & Yamashita, M. (2011). Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Mathematical Programming, 129, 33.
- [78]Liu, T., Sun, B., & Tsang, D. H. K. (2019). Rank-one solutions for SDP relaxation of QCQPs in power systems. IEEE Trans. Smart Grid, 10, 5.
- [79]Barahona, F., Grötschel, M., Jünger, M., & Reinelt, G. (1988). An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36, 493.
- [80]S. Barahona and R. D. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming 95, 329 (2003).DOI
- [81]Arora, S., & Kale, S. (2016). A combinatorial, primal-dual approach to semidefinite programs. Journal of the ACM (JACM), 63, 1.
- [82]N. Boumal, V. Voroninski, and A. Bandeira, The non-convex burer-monteiro approach works on smooth semidefinite programs, Advances in Neural Information Processing Systems 29 (2016).arxiv.org/abs/1606.04970
- [83]Ding, L., Yurtsever, A., Cevher, V., Tropp, J. A., & Udell, M. (2021). An optimal-storage approach to semidefinite programming using approximate complementarity. SIAM Journal on Optimization, 31, 2695.
- [84]Comsol multiphysics. (n.d.). Comsol multiphysics.
- [85]Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1, 67.