betaFeedback

WorksComputer Science

Formally Verified Semidefinite Programming

Abstract

We present a formally verified Rust implementation of a first-order semidefinite programming solver, a nontrivial piece of numerical software. We wrote the solver by hand and then directed Claude to generate the entire verification in Verus, an automated theorem prover for Rust programs. We discuss the algorithm underlying the solver, its implementation in Rust, and our pragmatic approach to proving it correct in Verus.

Introduction

Semidefinite programming (SDP) is a powerful framework in convex optimization that sits atop a hierarchy of important conic programming classes, including second-order cone programming and, at the bottom, linear programming. Thanks to its expressive power, SDP has provided new computational techniques for combinatorial optimization [1], [2], matrix completion [3], and quantum information theory [4], to name a few. Indeed, SDP is (numerically) solvable, up to a desired accuracy tolerance, in polynomial time by interior-point methods [5], which have given rise to open-source, performant SDP solvers [6], [7].

Interior-point methods, however, involve solving iteration-dependent Hessian systems—second-order information that scales with the number of linear constraints. As this number can be quadratic in the dimension of the decision variable, these methods are unsuitable for large-scale problems. To address this issue, researchers have developed first-order methods that reduce per-iteration cost (both time and memory) while maintaining global convergence. One prominent primal-dual method of this sort is due to Wen, Goldfarb, and Yin [8], which we call the WGY method.

Of course, we would like assurance that the solution an SDP solver—a nontrivial piece of software—returns to us is correct. To this end, we present a self-contained, practical Rust implementation of the WGY method along with a proof of its correctness in Verus, an automated theorem prover for Rust programs [9]. To our knowledge, this is the first verified implementation of an SDP solver, thereby showing the community a feasible way to verify such software. We first wrote the Rust program manually, i.e., without agentic AI, and then systematically guided Claude (Fable 5.1) to produce the entire Verus proof. For this project, Claude proved to be adept at engineering robust and fast proofs.

The algorithmic core of our solver consists of a few fundamental numerical linear algebra routines. In particular, the workhorse of the WGY method is the spectral decomposition of a real symmetric matrix. For this purpose, our solver offers the user a choice between two variants of the (serial) Jacobi method: one with the traditional column-cyclic ordering of pivot entries and the other with a simple caching method to select the pivot of greatest magnitude.

To verify these routines with Verus, we must decide how to reason about floating-point computations, which permeate our solver. There are good reasons to avoid reasoning about floats directly. First, Verus currently offers little support for it. Second, the benefit of staying faithful to this aspect of the Rust code is outweighed by the additional complexity of floating-point error analysis. Indeed, this analysis would obfuscate what we’re primarily after with Verus: a certified understanding of the code’s mathematical behavior, separate from artifacts of finite precision. Therefore, we decide to axiomatize a minimal set of basic floating-point operations as their exact real counterparts, for which Verus has extensive support. Within this framework, we verify the correctness of each linear algebra routine underpinning the solver.

On top of its algorithmic core, our solver provides an interface facilitating convenient formulations of SDP problems, which often involve splitting the decision variable into smaller ones. Our interface lets the user formulate the problem purely in terms of these composite variables. This decomposed problem is converted to an equivalent problem in standard form (with a single decision variable), which is fed to the WGY method. Our proof of correctness relates the computed solution of the standard-form problem to the user-supplied problem, showing that the former is feasible, i.e., satisfies the problem’s constraints, in an approximate sense for the latter.

Collectively, our Verus proofs establish that the solver as a whole is correct: if it stops upon meeting its accuracy standard, it returns a primal-dual solution with small Karush–Kuhn–Tucker (KKT) residuals relative to the standard-form problem, in which case the primal solution is approximately feasible for the user-supplied problem. Since the objective functions of both problems are equal, these criteria make up a sensible notion of correctness for a numerical solver. Indeed, it is a basic theorem of convex optimization that a primal-dual solution exactly satisfying the KKT conditions (meaning that the residuals vanish) is optimal [10 Sec. 5.5.3].

We do not try to formally verify convergence of our solver. Wen, Goldfarb, and Yin establish global convergence via convex analysis Sec. 2.2 [8], a theory for which Verus is illsuited. Sacrificing a computer-checked proof of convergence for the benefits of Verus reflects the question we sought to answer: when our Rust program stops with a claimed solution, should the user be confident in it?

Outline

We consider our SDP solver and its Verus verification in turn. We begin with a brief overview of semidefinite programming (Section II). We then discuss the WGY method for solving semidefinite programs together with its implementation in Rust (Section III). Afterward, we provide a brief overview of Verus (Section IV) before describing what we verified about our solver (Section V). The codebase on which this paper is based, including the infrastructure built to steer Claude, is available at [11].

The computer verification of numerical programs is an active research area. Its methods come in two main flavors: (a) formal proofs of correctness in a theorem prover, whether automated or interactive, and (b) certificate validation performed by a separate, trusted program. Flavor (a) has the advantage of specifying properties in an expressive formal system. It, however, involves defining the numerical program in question within this system, which may be far from the user’s preferred programming language and may lead to worse performance. For example, proving correctness in Lean would require writing the executable code as a functional program, which will typically perform worse than an imperative program written in languages like C or Rust. Flavor (b) avoids this issue but shifts the burden of verification to the separate validator. Moreover, flavor (b) just tells us how to check a given output, not whether the code behaves as intended.

Both flavors of verification have been applied to convex optimization. For example, Li et al. have developed an extensive Lean library that formalizes the convergence rates of various gradient descent algorithms [12]. Moreover, focusing on the solver interface, Bentkamp, Mir, and Avigad have built in Lean a verified translation from a user-supplied convex problem to one in conic form (which is then sent to an external solver) [13]. Both of these works, like ours, neglect floating-point reasoning by assuming exact real arithmetic—although Lean now offers more support than Verus for such reasoning [14]. Our work, however, targets a class of optimization problems not covered by gradient descent and addresses the end-to-end solver, not just the conversion step.

Meanwhile, certificate validation has had limited success in verifying SDP solvers. Primal-dual methods produce approximate solutions that can be directly checked against the KKT conditions. A validator will check each of these conditions with a trusted or, better, verified program, which ideally accounts for floating-point error. For a restricted class of SDP problems, Martin-Dorel and Roux devise a promising method for checking that the primal solution is positive semidefinite [15 Sec. 2.4.2]. They implement an efficient decision procedure in Rocq and verify its soundness. Their method, though, is not applicable to a general solver like ours.

Our project’s approach fits into flavor (a): verification amounts to specifying and proving properties in Verus’s formal system. It tries to prove that the computation of KKT residuals is correct, whereas a certificate validator merely tries to check that each particular result has small KKT residuals.

Ours appears to be the first verified implementation of an SDP solver. Surprisingly, it also appears to offer the first verified implementation of spectral decomposition for real symmetric matrices, although Lean’s mathlib includes the spectral theorem, in noncomputable form, for Hermitian matrices [16 Spectral theory of Hermitian matrices]. Thus, the present paper marks an important first step in research on verified numerical optimization.

Background on SDP

Semidefinite programming seeks to minimize a real-valued linear objective over the convex cone of positive semidefinite (real) matrices subject to finitely many linear constraints:

minimizeC∙FXX∈Sn+subject toAi∙X=bii=1,…,m\begin{aligned} \text{minimize}\quad& C \bullet_F X \\ & X \in S_n^+ \\ \text{subject to}\quad& A_i \bullet X = b_i \quad i=1,\ldots,m \end{aligned}

This presentation is the standard form of a semidefinite program (SDP). Here, Sn+S_n^+ denotes the set of positive semidefinite nn-by-nn matrices: a square matrix MM is positive semidefinite (PSD) if it is symmetric, i.e., an element of the n(n+1)2\frac{n(n+1)}{2}-dimensional vector space SnS_n, and xTMx≥0x^T M x \ge0 for all x∈Rnx \in\mathbb{R}^n. The latter condition is equivalent to requiring MM’s eigenvalues, which belong to R\mathbb{R}, to be nonnegative. The parameter matrices CC and AiA_i are assumed, without loss of generality, to be symmetric. The operation Ai∙XA_i \bullet X is defined as the ordinary dot product of AiA_i and XX viewed as vectors of size n(n+1)2\frac{n(n+1)}{2}. A variant of this operation is the Frobenius inner product C∙FXC \bullet_F X, defined by considering CC and XX as n×nn \times n matrices and taking their dot product in Rn2\mathbb{R}^{n^2}. Another way of writing the linear constraints is A(X)=b\mathcal{A}(X)=b where A\mathcal{A} has rows A1,…,AmA_1,\ldots,A_m.

A more flexible presentation lets one decompose the SDP into multiple decision variables. To describe it, we need the notion of linear matrix inequality (LMI): a relation M1⪰M2M_1 \succeq M_2 on matrices defined to hold when M1−M2M_1-M_2 is positive semidefinite—in particular, M⪰0M \succeq0 means M∈Sn+M \in S_n^+. Now, the convenient presentation of an SDP has the form

minimizeC1∙FX1+⋯+Ck∙FXkX1,…,Xksubject toXi∈Sdii=1,…,k,∑i=1kAj,i∙Xi=vjj=1,…,m,∑i=1kLt,i(Xi)⪰Mtt=1,…,ℓ\begin{aligned} \text{minimize}\quad& C_1 \bullet_F X_1+\cdots+C_k \bullet_F X_k \\ & X_1,\ldots,X_k \\ \text{subject to}\quad& X_i \in S_{d_i} \quad i=1,\ldots,k, \\ & \sum_{i=1}^{k} A_{j,i} \bullet X_i = v_j \quad j=1,\ldots,m, \\ & \sum_{i=1}^{k} \mathcal{L}_{t,i}(X_i) \succeq M_t \quad t=1,\ldots,\ell \end{aligned}

where each Lt,i\mathcal{L}_{t,i} is a linear map Sdi→Mat⁡nt(R)S_{d_i} \to\operatorname{Mat}_{n_t}(\mathbb{R}) into the space of nt×ntn_t \times n_t matrices for some nt≥0n_t \ge0, with did_i the dimension of the decision variable XiX_i. Often, it is far easier to formulate an SDP with multiple decision variables than with just one. In fact, we believe that to be useful software, an SDP solver must accommodate the convenient presentation.

Example 1. The nuclear norm of a matrix is the sum of its singular values. Minimizing it over a constraint set is an important problem in data science and can be formulated as the following SDP [17]:

minimize12(trace⁡(W1)+trace⁡(W2))X,W1,W2subject toA(X)=b,(W1XXTW2)⪰0\begin{aligned} \text{minimize}\quad& \frac{1}{2}\bigl(\operatorname{trace}(W_1)+\operatorname{trace}(W_2)\bigr)\\ & X,W_1,W_2\\ \text{subject to}\quad& A(X)=b,\\ & \begin{pmatrix} W_1 & X \\ X^{T} & W_2 \end{pmatrix}\succeq0 \end{aligned}

Every convenient presentation can be transformed into an equivalent standard-form problem. We call this process canonization, which rests on the following standard fact.

Lemma 1. Let B1,…,BkB_1,\ldots,B_k be square matrices (of possibly different sizes). The block-diagonal matrix

(B1⋱Bk)\begin{pmatrix} B_1 & & \\ & \ddots& \\ & & B_k \end{pmatrix}

is PSD if and only if each block is.

With Lemma 1, we can assemble the decision variables X1,…,XkX_1,\ldots,X_k into a big block-diagonal one as follows. Every symmetric matrix SS is the difference P1−P2P_1-P_2 of two PSD matrices: take (S+rI)−rI(S+rI)-rI with r:=∥S∥∞r:=\lVert S\rVert_\infty, which is at least the spectral radius of SS because ∥⋅∥∞\lVert\cdot\rVert_\infty is sub-multiplicative. Therefore, the set of feasible solutions for (split) corresponds to the set of X⪰0X\succeq0 such that

X=(U1⋱UℓP1,1P1,2⋱Pk,1Pk,2)X= \begin{pmatrix} U_1 & & & & & \\ & \ddots& & & & \\ & & U_\ell& & & \\ & & & P_{1,1} & & \\ & & & & P_{1,2} & \\ & & & & & \ddots\\ & & & & & & P_{k,1} \\ & & & & & & & P_{k,2} \end{pmatrix}
Lt,1(P1,1−P1,2)+⋯+Lt,k(Pk,1−Pk,2)−Ut=Mt\mathcal{L}_{t,1}(P_{1,1}-P_{1,2})+\cdots+\mathcal{L}_{t,k}(P_{k,1}-P_{k,2})-U_t=M_t
Aj,1∙(P1,1−P1,2)+⋯+Aj,k∙(Pk,1−Pk,2)=vjA_{j,1}\mathbin{\bullet}(P_{1,1}-P_{1,2})+\cdots+A_{j,k}\mathbin{\bullet}(P_{k,1}-P_{k,2})=v_j

We call this XX the lift of X1,…,XkX_1,\ldots,X_k. For each i∈{1,…,k}i\in\{1,\ldots,k\}, we recover the decision variable XiX_i as Pi,1−Pi,2P_{i,1}-P_{i,2}. The constraints imposed on XX to give it the desired shape are all linear, and the expression

C1∙F(P1,1−P1,2)+⋯+Ck∙F(Pk,1−Pk,2)C_1\mathbin{\bullet_F}(P_{1,1}-P_{1,2})+\cdots+C_k\mathbin{\bullet_F}(P_{k,1}-P_{k,2})

defines a real-valued linear function of XX. It follows that minimizing this map over all X⪰0X\succeq0 satisfying these constraints not only solves (split) but also can readily be put in standard form. We define the canonization of (split) as the resulting standard-form problem.

We now know that it suffices to solve (std), but how do we know when we have solved it? To answer this, we view (std) as the primal problem and consider its dual:

maximizeb∙yy,Zsubject toA∗(y)+Z=C,Z∈Sn+(1)\begin{aligned} \text{maximize}\quad& b\mathbin{\bullet}y\\ & y,Z\\ \text{subject to}\quad& \mathcal{A}^{*}(y)+Z=C,\\ & Z\in\mathbb{S}^{+}_{n} \tag*{(1)} \end{aligned}

Here, the map A∗:(Rm,∙)→(Sn,∙F)\mathcal{A}^{*}:(\mathbb{R}^{m},\mathbin{\bullet})\to(\mathbb{S}_{n},\mathbin{\bullet_F}) denotes the adjoint of A\mathcal{A} viewed as a map of inner product spaces, characterized by the property that A(X)∙y=X∙FA∗(y)\mathcal{A}(X)\mathbin{\bullet}y=X\mathbin{\bullet_F}\mathcal{A}^{*}(y) for all X∈SnX\in\mathbb{S}_{n} and y∈Rmy\in\mathbb{R}^{m}. Now, consider the KKT conditions on (X,y,Z)(X,y,Z):

  • XX is feasible for (std).

  • (y,Z)(y,Z) is feasible for (dual).

  • C∙FX=b∙yC\mathbin{\bullet_F}X=b\mathbin{\bullet}y.

These conditions are simply the general KKT conditions (which apply to virtually any optimization problem) specialized to the SDP setting [18 Sec. 3.1]. As the objective and constraints of (std) are convex, if (X,y,Z)(X,y,Z) satisfies the KKT conditions, then XX and (y,Z)(y,Z) are optimal solutions for the primal and dual, respectively. Conversely, the KKT conditions are necessary for a triple to be optimal provided that both the primal and the dual satisfy Slater’s condition [10 Sec. 5.2.3]: there exist feasible solutions X,y,ZX,y,Z such that both XX and ZZ are positive definite, i.e., have positive eigenvalues.

A primal-dual solver is one that computes solutions to the primal and dual simultaneously. Convergence of a plain primal-dual solver, such as the WGY method, to a triple (X,y,Z)(X,y,Z) satisfying the KKT conditions relies on Slater’s condition, which generally must be checked by hand.

Since, in practice, we must stop an SDP solver after finitely many iterations, we measure the accuracy of its returned solution (X,y,Z)(X,y,Z) by the KKT residuals: quantities measuring how close (X,y,Z)(X,y,Z) is to satisfying the KKT conditions. Small residuals correspond to high accuracy. In practice, the user may forget Slater’s condition and simply test whether the solver returns small KKT residuals. It is this realistic scenario that will shape what we want to prove about our solver.

Rust Implementation of WGY Method

In this section, we describe how we implement in Rust a complete SDP solver based on the WGY method. We do not replay the entire algorithm, which is explained in [8 Sec. 2.1]. Rather, we sketch it while focusing on those steps which, as we’ll see, play primary roles in the verification.

Canonization

The user supplies their SDP in convenient form. Its canonization is implemented like so:

fn sdp_to_standard(sdp : &SDP, check_cns : bool) ->
    (SymMatrix, (Matrix, Vec<(usize, usize)>), Vector, ...)

Here, SDP is a struct whose fields specify the parameters of a convenient presentation. For this discussion, the following are the relevant components of the output tuple, from left to right.

  • The symmetric matrix CC defining the objective map. The type of CC, SymMatrix, is an alias for Vector, which is in turn an alias for Vec<f64>. A vector stores the upper triangle of a symmetric matrix by flattening its columns.

  • The constraint matrix A\mathcal{A} represented as a pair (M,ζ)(M,\zeta). The type of MM, Matrix, is another alias for Vector, again storing a matrix by flattening its columns. The function computes MM as the matrix Σ\Sigma of the linear map

X↦col⁡(vec⁡L1(X),…,vec⁡Lℓ(X),N1(X),…,Nm(X))X \mapsto\operatorname{col}(\operatorname{vec} L_1(X),\ldots,\operatorname{vec} L_\ell(X),N_1(X),\ldots,N_m(X))

where col⁡(⋅)\operatorname{col}(\cdot) denotes vertical concatenation, vec⁡(⋅)\operatorname{vec}(\cdot) flattens a matrix column-wise, and Lt(X):=Lt,1(P1,1−P1,2)+⋯+Lt,k(Pk,1−Pk,2)−UtL_t(X) := L_{t,1}(P_{1,1}-P_{1,2})+\cdots+L_{t,k}(P_{k,1}-P_{k,2})-U_t and Nj(X):=Aj,1∙(P1,1−P1,2)+⋯+Aj,k∙(Pk,1−Pk,2)N_j(X) := A_{j,1}\bullet(P_{1,1}-P_{1,2})+\cdots+A_{j,k}\bullet(P_{k,1}-P_{k,2}), as in Section II. For efficiency, the zero constraints making XX block-diagonal are stored separately in ζ\zeta, which consists of all row-column indices where XX must be zero.

  • The right-hand side bΣb_\Sigma. The function computes it as col⁡(vec⁡M1,…,vec⁡Mℓ,v)\operatorname{col}(\operatorname{vec} M_1,\ldots,\operatorname{vec} M_\ell,v). For efficiency, the right-hand sides of the zero constraints are left implicit, but the full right-hand side for A\mathcal{A} is b:=col⁡(bΣ,0∣ζ∣)b := \operatorname{col}(b_\Sigma,0_{|\zeta|}).

The function’s second argument, check_cns, is a flag that tells the solver to check whether the augmented matrix [A∣b][\mathcal{A}\mid b] has redundant constraints (after checking that it’s consistent in the first place) and, if so, to remove them. This one-time check determines whether A\mathcal{A} has full rank and, if not, trims it so that it does. The WGY method requires A\mathcal{A} to have full rank, so that its Gram matrix AA∗\mathcal{A}\mathcal{A}^{*} is invertible. If the user knows beforehand that the constraints are non-redundant, they may forgo the check.

Rank Computation

If check_cns is turned on, then we need to compute the rank of A\mathcal{A}. To do so, we use Gaussian elimination (with partial pivoting), implemented like so:

fn gauss_elim(mat: &mut Matrix, col_dim: usize, row_dim: usize)
    -> (&mut Matrix, usize, bool)

This function mutates the input matrix to place it in row echelon form. Along the way, it tracks the number of valid pivots in A\mathcal{A} and thereby computes the matrix’s rank, returning it as the second component. It also returns a flag that indicates whether the matrix, when its final column is viewed as the right-hand side of a linear system, is consistent.

The Gaussian elimination routine illustrates the kind of numerical reasoning that we will be forced to handle. In particular, we skip pivots using the following criterion:

if pivot_abs == 0.0 || pivot_abs < TOL * coeff_scale { continue; }

Here, TOL is a small positive constant, and coeff_scale is the maximum magnitude over all entries in A\mathcal{A} so that their product is a scale-invariant threshold. With ordinary real numbers, a correct Gaussian elimination routine skips precisely those pivots equaling zero on the nose. The reality of floating-point arithmetic forces us to use a tolerance-based test instead.

Thus, we cannot hope to prove exact versions of correctness properties in Verus, even when the basic framework assumes that floating-point operations are exact.

Standard-Form Solver

Once the preprocessing is done, we run the WGY method on the data (C,A,b)(C,\mathcal{A},b). This method rests on an auxiliary function called the augmented Lagrangian:

Φμ(X,y,Z):=−b∙y+X∙FΔ+∥Δ∥F22μ\Phi_\mu(X,y,Z) := -b\bullet y+X\bullet_F\Delta+\frac{\lVert\Delta\rVert_F^2}{2\mu}
Δ:=A∗(y)+Z−C\Delta:= \mathcal{A}^{*}(y)+Z-C

for a given penalty parameter μ>0\mu>0. At each step, the WGY method minimizes Φμ\Phi_\mu over y∈Rmy\in\mathbb{R}^m and then over Z∈S+nZ\in\mathbb{S}^{n}_{+}, thereby serving as an alternating direction method (which is why the name sdp appears in our codebase). It then updates XX in terms of the computed minimizers.

In this discussion, we focus on the iterative computations of yy and ZZ. The update formula for the former follows from the stationarity condition ∇yΦμ=0\nabla_y\Phi_\mu=0 (a general KKT condition):

AA∗yk+1=μ(b−A(Xk))+A(C−Zk)\mathcal{A}\mathcal{A}^{*}y^{k+1}=\mu(b-\mathcal{A}(X^k))+\mathcal{A}(C-Z^k)

where AA∗\mathcal{A}\mathcal{A}^{*} is positive definite, hence invertible, because A\mathcal{A} has full rank. We thus need an algorithm for solving positive definite linear systems.

To this end, we implement LDLTLDL^T decomposition of an n×nn\times n symmetric matrix SS, an efficient factorization that succeeds if and only if SS is positive definite (assuming exact arithmetic):

fn ldlt_decomp(mat : &SymMatrix, dim : usize) ->
    Option<(LowTriMatrix, Vector)>

(Here, LowTriMatrix is another alias for Vector.) By decomposing SS, a system Sx=vSx=v becomes a composite of triangular solves. With the exact-real framework used by our verification, we can prove that when ldlt_decomp(S, n) returns a pair (L,D)(L,D), we have LDLT=SLDL^T=S on the nose. Nevertheless, when we use this routine to test whether a matrix is positive definite (as we’ll do in our stopping criteria), we pick up numerical error. Indeed, ldlt_decomp tests positivity of the diagonal entries with

if d[i] < TOL * max_diag_sym(mat, dim).max(1.0) { return None; }

Remark. This stage of the WGY method shows why we keep the zero constraints separate from those encoded by Σ\Sigma. The latter only involve entries within XX’s diagonal blocks, so AA∗\mathcal{A}\mathcal{A}^{*} is block-diagonal with blocks ΣΣ∗\Sigma\Sigma^{*} and 12I\frac{1}{2}I (where the factor 12\frac{1}{2} reflects how ∙F\bullet_F differs from ∙\bullet). Hence we need only run LDLTLDL^T on ΣΣ∗\Sigma\Sigma^{*}, which is typically far smaller than AA∗\mathcal{A}\mathcal{A}^{*}.

The update formula for ZZ comes from noticing that minimizing Φμ(Xk,yk+1,Z)\Phi_\mu(X^k,y^{k+1},Z) over ZZ is equivalent to the problem

minimize⁡Z∈S+n∥Z−Vk+1∥F2\underset{Z\in\mathbb{S}^{n}_{+}}{\operatorname{minimize}}\quad\lVert Z-V^{k+1}\rVert_F^2

where Vk+1V^{k+1} denotes the symmetric matrix C−A∗(yk+1)−μXkC-\mathcal{A}^{*}(y^{k+1})-\mu X^k. This problem has a known closed-form solution [19 Sec. 2]: the nonnegative part of Vk+1V^{k+1}’s spectral decomposition. Therefore, we want a spectral decomposition algorithm. To this end, we implement two variants of the Jacobi method [20 Sec. 8.5]. Let S∈SnS \in\mathcal{S}_n. The Jacobi method works by iteratively choosing a nonzero off-diagonal entry (p,q)(p,q) of SS, called the pivot, and making it zero by applying an O(n)O(n)-time orthogonal transformation Jp,qJ_{p,q}, called a Jacobi rotation. The method stops when all off-diagonal entries are small enough. Under this method, SS converges quadratically to the diagonal of its eigenvalues [21 Sec. 5.3.5].

One has a choice of how to choose the pivot on each iteration. The standard option is to employ column-cyclic ordering, which simply traverses the columns and takes the current entry as the next pivot. This approach has the advantage of making pivot selection constant time. It does, however, require calling a Jacobi rotation on every off-diagonal entry.

Another option is to dynamically select the largest entry (in magnitude) as the next pivot. Doing a brute-force search over SS for this entry is too expensive. Instead, the program maintains a cache π\pi that stores, for each column index c≥1c \ge1, the row index πc<c\pi_c < c of the largest entry above the diagonal in column cc. The transformation Jp,qJ_{p,q} only modifies entries landing either in the pp-th or qq-th row or in the pp-th or qq-th column. So, to update πc\pi_c, one just needs to check how the rotation affected rows pp and qq in column cc:

  1. If c∈{p,q}c \in\{p,q\}, then scan the cc-th column to find its new largest entry.

  2. Otherwise, check whether the current πc\pi_c equals pp or qq. If no, then just compare Sπc,cS_{\pi_c,c} with Sp,cS_{p,c} and Sq,cS_{q,c} and choose the row index of the largest entry.

  3. In the event that πc∈{p,q}\pi_c \in\{p,q\}, which occurs with probability O(1n)O\left(\frac{1}{n}\right), check whether ∣Sπc,c∣\lvert S_{\pi_c,c}\rvert fell below the magnitude of the old pivot. If no, then Sπc,cS_{\pi_c,c} is still at least as big as each untouched entry of column cc, so just compare Sp,cS_{p,c} and Sq,cS_{q,c} and choose the row index of the larger entry. If yes, then scan the cc-th column to find its new largest entry.

With this scheme, pivot selection still takes quadratic worst-case time but takes only linear time on average. This approach has the advantage of taking possibly fewer sweeps over SS—i.e., passes of n(n−1)2\frac{n(n-1)}{2} rotations—than the column-cyclic version, but pivot selection no longer takes constant time.

We have implemented both approaches:

fn jacobi_eigen_cyc(a : &mut SymMatrix, dim : usize)
    -> (Vector, Matrix)
fn jacobi_eigen_cach(a : &mut SymMatrix, dim : usize)
    -> (Vector, Matrix)

These routines store the diagonal of eigenvalues in the Vector output and the eigenvectors in the Matrix output. The user decides which one the SDP solver calls.

Stopping Criteria

While the WGY method converges on paper (assuming Slater’s condition), we need criteria for deciding when to actually stop the solver. We follow the criteria from [8 Sec. 3.4]. Essentially, the method is deemed to have converged when the KKT residuals for an iterate (Xk,yk,Zk)(X^k,y^k,Z^k) are sufficiently small. Here, the hardest condition to check is that XkX^k is nearly PSD. We use a popular heuristic for this test: choose a small value ϵ>0\epsilon> 0 and run LDLTLDL^T on Xk+ϵIX^k + \epsilon I. This approach introduces additional numerical error to our solver but is relatively fast.

Background on Verus

Why did we choose Verus? We chose Rust because it compiles programs to fast machine code, and we don’t want to sacrifice performance to formally check that our solver’s implementation is correct. Thus, Verus is the right tool for us because it enables the direct static verification of our Rust solver, without having to transpile it into a different language. Verus takes a large subset of Rust and treats it as a proof language for its own executable programs. It does so by extending the Rust compiler so that it associates exactly one of three modes to every Rust expression: executable, specification, or proof. Verus compiles only executable code to machine code, thereby keeping the runtime performance of our solver from deteriorating.

Verus augments Rust’s type system with types like Z\mathbb{Z} and R\mathbb{R} for specification and proof modes. In particular, specifications are formulas in the language of an SMT theory and are used as pre- and postconditions (marked by requires and ensures, respectively) in functions written in proof or executable mode. Within such functions, the user supplies, where appropriate, loop invariants as specifications. At compile time, Verus translates specification code to SMT queries and calls Z3 [22] on them. To aid Z3, the user supplies separate lemmas (which are assigned proof mode) as hints.

In general, the goal is to prove that an executable Rust function satisfies its postcondition under its preconditions. As is the case with Hoare-style reasoning, though, such proofs are partial: each postcondition holds when the function returns normally, but whether it necessarily does so is outside the assertion’s scope. For example, we do not analyze whether a panic! in our solver is reachable.

Verification of Rust SDP Solver

In this section, we report on how we verified the solver described in Section III. We steered Claude to generate the entire verification in Verus, finding it highly adept at engineering proofs of individual specifications. The one aspect on which we needed to provide oversight was the design of the specifications themselves (although Claude was usually proficient at it). Initial ambiguities in our prompts gave Claude too much freedom in designing them, causing some of them to be weaker than intended. We reviewed Claude’s work in stages (the nodes of a dependency graph we prompted Claude to create), sometimes with the help of a different agent, namely Codex. As we were familiar with the executable code and with what we wanted to prove about it, we had little trouble steering Claude to fix its problematic specifications.

In total, Claude wrote almost 18,000 logical lines of Verus. It is impractical to record here every important theorem in them. Rather, we sketch how this collection of guarantees comes together by walking the reader through a handful of its essential features.

Trusted Base

The trusted base establishes our approach to floating-point reasoning, namely to sidestep it. Formally, it axiomatizes floating-point arithmetic as exact real arithmetic. Importantly, this approach lets one reason about our solver’s floating-point computations via Z3’s powerful nonlinear arithmetic solver. First, we introduce the uninterpreted function rv, which gives the exact real value of an f64. We then axiomatize the behaviors of basic operations like addition, comparison, and Rust’s native absolute value method:

uninterp spec fn rv(x: f64) -> real;

broadcast axiom fn axiom_add(a: f64, b: f64, o: f64)
    requires #[trigger] add_ensures::<f64>(a, b, o),
    ensures rv(o) == rv(a) + rv(b);

broadcast axiom fn axiom_lt(a: f64, b: f64, o: bool)
    requires #[trigger] lt_ensures::<f64>(a, b, o),
    ensures o == (rv(a) < rv(b));

assume_specification[ f64::abs ](x: f64) -> (r: f64)
    ensures rv(r) == abs_r(rv(x));

Here, add_ensures and lt_ensures are uninterpreted predicates from Verus’s standard library.

Matrices

Of course, to reason about our solver, we need to handle matrix computations. Claude chose to represent a matrix as a function from index pairs to reals and to read matrices stored as packed vectors—represented as sequences of reals in Verus—as such functions:

type MatF = spec_fn(int, int) -> real;

spec fn sym_view(m: Seq<real>) -> MatF {
    |r: int, c: int| if r <= c { m[pk_idx(r, c)] }
    else { m[pk_idx(c, r)] }
}

Here, pk_idx(r, c) is the position of entry (r,c)(r,c) in the packed upper triangle mm. Thus, sym_view(m) is symmetric by construction. To handle matrices from LMI constraints, the function cm_view(m, dim), not shown, similarly reads a general column-major matrix with dim rows.

Spectral Decomposition

A correct spectral decomposition algorithm, or eigensolver, that returns (Q,B)(Q, B) on symmetric input AA ensures that A=QBQTA = QBQ^T with BB diagonal and QQ orthogonal. For our implementation of the Jacobi method, we can prove, thanks to our trusted model, that A=QBQTA = QBQ^T on the nose. We can also prove that QQ is orthogonal. But since we do not test zero off-diagonal entries exactly, we merely ask for BB to be close to its own diagonal. Such a residual is a reasonable quantity to control. Indeed, since the eigensolver keeps AA orthogonally similar to BB and B=diag⁡(B)+(B−diag⁡(B))B = \operatorname{diag}(B) + (B - \operatorname{diag}(B)), the Hoffman–Wielandt inequality [23 Thm. VI.4.1] implies that

∥λ(A)−λ(diag⁡(B))∥≤∥B−diag⁡(B)∥F\lVert\lambda(A) - \lambda(\operatorname{diag}(B)) \rVert\le\lVert B - \operatorname{diag}(B) \rVert_F

where λ(⋅)\lambda(\cdot) denotes the vector of eigenvalues in decreasing order. By bounding this Frobenius norm, we bound how much the eigenvalues returned by the solver, namely the diagonal of BB, collectively deviate from AA’s true eigenvalues.

Based on the preceding discussion, we formulate in Verus what it means for an eigensolver’s output to be correct:

spec fn eigen_decomp_inv(
    a: Seq<real>, q: Seq<real>, b: Seq<real>, dim: int)
    -> bool {
    &&& is_orthogonal(cm_view(q, dim), dim)
    &&& meq(sym_view(a),
            mmul(mmul(cm_view(q, dim), sym_view(b), dim),
                 mtr(cm_view(q, dim)), dim),
            dim, dim) }

spec fn eigen_decomp_approx(
    a: Seq<real>, q: Seq<real>, b: Seq<real>,
    dim: int, eps: real) -> bool {
    &&& eigen_decomp_inv(a, q, b, dim)
    &&& offdiag_norm_r(b, dim) <= eps }

spec fn eigensolver_ok(
    tol: real, a: Seq<real>, b: Seq<real>, q: Seq<real>,
    vals: Seq<real>, dim: int) -> bool {
    &&& q.len() == dim * dim
    &&& vals == sym_diag_r(b, dim)
    &&& eigen_decomp_approx(a, q, b, dim,
            jacobi_eps_r(tol, b, dim)) }

Here, jacobi_eps_r(tol, b, dim) is the value n(n−1)⋅tol⁡⋅max⁡(max⁡i∣Bii∣,1)\sqrt{n(n-1)} \cdot\operatorname{tol} \cdot\max(\max_i |B_{ii}|, 1) with nn the matrix dimension. This bound is derived from the explicit stopping test in the executable code: the eigensolver stops once all off-diagonal entries of BB have magnitude below tol⁡⋅max⁡(1,max⁡i∣Bii∣)\operatorname{tol} \cdot\max(1, \max_i |B_{ii}|).

We prove that both variants of the Jacobi method—the exec functions jacobi_eigen_cyc and jacobi_eigen_cach—are correct eigensolvers in this sense. Moreover, we verify the distinguishing feature of each one. For the column-cyclic variant, we prove that a sweep visits every off-diagonal entry exactly once:

spec fn visits_each_pair_once(
    visited: Seq<(int, int)>, dim: int) -> bool {
    &&& forall|i: int, k: int| 0 <= i < k < dim ==>
            0 <= #[trigger] cyc_pos(j, k) < visited.len()
            &&& visited[cyc_pos(j, k)] == (j, k)
    &&& forall|t: int| 0 <= t < dim - 1 ==>
            0 <= #[trigger] visited[t].0 < visited[t].1 < dim
            && t == cyc_pos(visited[t].0, visited[t].1) }

For the caching variant, we prove that the cache π\pi, as in Section III, stores what it’s supposed to throughout jacobi_eigen_cach’s main loop. Formally, col_max_at(b, c, i) expresses that row i<ci < c holds an entry of maximal magnitude among the entries above the diagonal in column cc, and we prove that π\pi satisfies the following predicate:

spec fn cache_ok(
    b: Seq<real>, maxima: Seq<usize>, dim: int) -> bool {
    &&& maxima.len() == dim - 1
    &&& forall|t: int| 0 <= t < dim - 1 ==>
            col_max_at(b, t + 1, maxima[t] as int)
            #[trigger] maxima[t] as int) }

KKT Residuals

Suppose that the solver returns (X,y,Z)(X, y, Z) claiming that it is a primal-dual solution to the canonical problem, the canonization of the user-supplied problem. Our verification’s central result is that the convenient-form points X1,…,XkX_1,\ldots,X_k extracted from XX make up an approximate solution to the user-supplied problem. To achieve it, we verify the following two properties:

  1. The returned triple has small KKT residuals relative to the canonical problem.

  2. Any approximately feasible point for the canonical primal problem induces approximately feasible points for the user-supplied problem.

To check property (1), we in particular want to verify that the primal solution claimed by the solver is (approximately) PSD. The primal variable keeps its block-diagonal form at each iteration, so to check that it is PSD, we check that each block is. Recall that to do so, we use the heuristic that checks the predicate psd_shifted(a, dim, eps) defined as xTAx+ϵ∥x∥2≥0x^T A x + \epsilon\lVert x\rVert^2 \ge0 for all xx. The predicate block_psd_ok applies this test to each diagonal block BB—which is symmetric by construction and specified by a starting position and a dimension—with ϵ\epsilon set to TOL⋅max⁡(max⁡i∣Bii∣,1)\mathrm{TOL}\cdot\max(\max_i\lvert B_{ii}\rvert,1):

spec fn psd_shifted(a: MatF, dim: int, eps: real)
    -> bool {
    forall|x: Seq<real>| x.len() == dim ==>
        #[trigger] quad_r(a, dim, x) + eps * dot_r(x, x)
        >= 0.0real }
spec fn block_psd_ok(
    tol: real, a: Seq<real>, start: int, dim: int) -> bool {
    psd_shifted(block_view(a, start), dim,
                psd_check_eps_r(tol, a, start, dim)) }
fn psd_block_check(
    mat: &SymMatrix, blocks: &Vec<(usize, usize)>)
    -> (result: bool)
    requires blocks_fit(blocks@, [email protected]()),
    ensures
        result ==> forall|b: int| 0 <= b < [email protected]() ==>
            #[trigger] block_psd_ok(rv(TOL), rvs(mat@),
                blocks@[b].0 as int, blocks@[b].1 as int),

The rest of property (1) is easier: the dual variable always remains PSD by construction, and all linear residuals are routine computations.

For property (2), we prove a more general relation between the user-supplied problem and the canonical one with the following soundness lemma. We just consider the case where the rank check is turned on as the other case is simpler:

proof fn lemma_approx_sound_reduced(
    sdp: &SDP, s: &SdpadSetup, z: Seq<real>)
    requires
        sdpad_input_ok(sdp, true),
        sdpad_setup_ok(sdp, true, *s),
        [email protected]() >= 1,
        z.len() == pk_len(s.var_dim as int),
    ensures (...)

Here, SdpadSetup consists of standard-form data that the solver feeds to the WGY method and sdpad_setup_ok is the predicate that this data is the canonized user-supplied problem.

As desired, this soundness lemma ensures that canonization reflects feasibility: given any point XX for the canonical problem, the convenient-form points X1,…,XkX_1,\ldots,X_k violate the user-supplied constraints by an amount partly controlled by the primal infeasibility pinf⁡\operatorname{pinf} at XX, i.e., how much A(X)\mathcal{A}(X) (after reduction) deviates from bb. In more detail, let linr⁡\operatorname{linr} be the amount by which XX violates the unreduced system [A0∣b0][A_0\mid b_0], before redundant rows were removed. Then, letting φ(X):=∥A0∥F∥X∥+∥b0∥\varphi(X):=\lVert A_0\rVert_F\lVert X\rVert+\lVert b_0\rVert, lemma_approx_sound_reduced ensures that

linr⁡≤Γ⋅TOL⋅φ(X)+∥E∥F⋅pinf⁡⋅(1+∥b∥)\operatorname{linr}\le\Gamma\cdot\mathrm{TOL}\cdot\varphi(X)+\lVert E\rVert_F\cdot\operatorname{pinf}\cdot(1+\lVert b\rVert)

where the quantities Γ\Gamma and EE depend only on [A0∣b0][A_0\mid b_0] and the row echelon form that Gaussian elimination computes from it, not on XX. Note that φ(X)\varphi(X) is the scaling factor in the classical normwise backward error for [A0∣b0][A_0\mid b_0] [24], so its appearance is expected. The bound on linr⁡\operatorname{linr} bounds each linear residual ∥∑iAj,i⋅Xi−vj∥\lVert\sum_i A_{j,i}\cdot X_i-v_j\rVert as well as each LMI residual ∥Rt:=∑iLt,i(Xi)−Mt∥−Ut∥F\lVert R_t:=\sum_i\mathcal{L}_{t,i}(X_i)-M_t\rVert-U_t\Vert_F (with notation as in Section III). Further, if the block UtU_t passes the PSD check with shift ϵt\epsilon_t, then soundness ensures that for all xx,

xT(∑iLt,i(Xi)−Mt)x≥−(ϵt+∥Rt∥F)∥x∥2x^T\left(\sum_i\mathcal{L}_{t,i}(X_i)-M_t\right)x\ge-\left(\epsilon_t+\lVert R_t\rVert_F\right)\lVert x\rVert^2

The smallest eigenvalue of a symmetric matrix SS is min⁡x≠0xTSx∥x∥2\min_{x\ne0}\frac{x^TSx}{\lVert x\rVert^2}, so this inequality implies that every eigenvalue of ∑iLt,i(Xi)−Mt\sum_i\mathcal{L}_{t,i}(X_i)-M_t (really, of its symmetric part) is at least −(ϵt+∥Rt∥F)-(\epsilon_t+\lVert R_t\rVert_F), which shrinks as the solver drives down pinf⁡\operatorname{pinf}.

Finally, for our central result to be legitimate, canonization must not introduce error in the objective function. The soundness lemma ensures that it does not: the standard-form objective at XX equals the user-supplied one at (X1,…,Xk)(X_1,\ldots,X_k).

It remains to combine, in Verus, properties (1) and (2) to get our central result. Claude does so with the lemma lemma_outcome_sound, which applies the soundness lemma to the iterate the solver claims satisfies property (1). This claim is encoded in the predicate outcome_ok. Claude verifies that the solver’s claim is true (roughly, that the KKT residuals are below TOL), thereby deducing the following contract for the executable solver:

fn sdpad_verified(sdp: &SDP, check: bool,
    var: &JacobiVariant) -> (o: SdpadOutcome)
    requires sdpad_input_ok(sdp, check),
    ensures exists|s: SdpadSetup|
        sdpad_setup_ok(sdp, check, s)
        && outcome_ok(sdp, &s, check, o)
        && user_outcome_ok(sdp, check, &s, o),

Here, user_outcome_ok, proved with lemma_outcome_sound, states that the returned convenient-form points X1,…,XkX_1,\ldots,X_k satisfy the feasibility bounds discussed above, using the pinf value maintained by the executable solver. In this sense, they make up an approximate solution to the user-supplied problem.

Claude’s Capability

To illustrate Claude’s skill at engineering Verus proofs, we outline how it proved a converse to soundness: a lifting lemma expressing that canonization preserves feasibility. Although this lemma is less important than soundness for gaining confidence in our solver, the process by which Claude proved it displays its ability to dynamically repair broken proofs.

Consider the predicate user_feasible, defined to hold on a list τ:=(X1,…,Xk)\tau:= (X_1, \ldots, X_k) of block decision variables if they are feasible (on the nose) for the user-supplied problem. The lifting lemma states that, as one would hope, if τ\tau is user-feasible, then its lift is a feasible standard-form point, with or without the rank check:

proof fn lemma_user_feasible_lifts(
    sdp: &SDP, check: bool, s: &SdpadSetup,
    xs: Seq<Seq<real>>)
requires
    sdpad_input_ok(sdp, check),
    sdpad_setup_ok(sdp, check, *s),
    [email protected]() >= 1,
    user_feasible(sdp, xs),
ensures ({
    let bd = bdims_r(sdp.lmi@);
    let vd = vdims_r(sdp.lmi@, n_vars(sdp));
    let z = lift_z(sdp.lmi@, xs, bd, vd);
    &&& is_psd(sym_view(z), s.var_dim as int)
    &&& ... })

Claude derives the ensured clause is_psd(...) from Lemma 1 combined with a separate lemma (not shown). The latter ensures that lift_z, which represents the lift of τ\tau, vanishes off the diagonal blocks and that each of its blocks is PSD. Both steps read individual entries of lift_z, an operation that depends on whether the given position is outside the blocks. That is, it involves the predicate expressing that (r,c)(r, c) is a position lying above the diagonal and outside the blocks:

spec fn in_zero_region(bs: Seq<int>, r: int, c: int)
-> bool {
    exists|j: int| 0 <= j < bs.len()
    && #[trigger] sum_upto(bs, j) <= r
       < sum_upto(bs, j + 1) <= c }

where sum_upto(bs, j) is the sum of the first jj block sizes, i.e., the offset at which block jj begins.

Reading an entry inside a block requires knowing that this predicate is false, i.e., a negated existential. But this formula becomes a universal over jj instantiated on the trigger sum_upto(bs, j). This scenario can easily cause a matching loop: an unbounded sequence of instantiations that exceeds the SMT solver’s resource limit. Still, Claude repeatedly found it useful to keep the trigger as written.

Claude showed its skill by taking advantage of this trigger while preventing the matching loop. Specifically, it made the function that computes the entries of lift_z opaque:

#[verifier::opaque]
spec fn lift_entry(..., bd: Seq<int>, vd: Seq<int>,
    r: int, c: int) -> real {
    let bs = block_sizes(bd, vd);
    if in_zero_region(bs, r, c) { 0.0real }
    else { ... }
}

Rather than remove the matching loop, the opaque attribute here confines it. Claude uses only one lemma (not shown) that reveals lift_entry’s body. This lemma’s conclusion is also a case split on in_zero_region, so Z3 handles it without looking inside the universal, thus avoiding the matching loop.

Conclusion

We gave a nontrivial example of using an autonomous agent to formally verify a human-engineered codebase, namely a Rust implementation of the Wen–Goldfarb–Yin first-order method for semidefinite programming. For all its flaws, it illustrated a feasible approach to verifying a self-contained, relatively performant SDP solver. To us, the most attractive future direction is to replace the Jacobi eigensolver with the QR algorithm [20 Sec. 8.3] as the latter, though more elaborate, is faster. Even so, the eigensolver we offered here can readily be used for other pieces of verified software that rely on spectral decomposition.

References

  1. [1]L. Lovász, “On the Shannon capacity of a graph,” IEEE Trans. Inf. Theory, vol. 25, no. 1, pp. 1–7, Jan. 1979.DOI
  2. [2]M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” J. ACM, vol. 42, no. 6, pp. 1115–1145, Nov. 1995.DOI
  3. [3]E. J. Candès and B. Recht, “Exact matrix completion via convex optimization,” Found. Comput. Math., vol. 9, no. 6, pp. 717–772, Apr. 2009.
  4. [4]P. Mironowicz, “Semi-definite programming and quantum information,” J. Phys. A: Math. Theor., vol. 57, no. 16, p. 163002, Apr. 2024.DOI
  5. [5]Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming. Philadelphia, PA: SIAM, 1994.DOI
  6. [6]J. F. Sturm, “Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones,” Optim. Methods Softw., vol. 11, no. 1–4, pp. 625–653, Jan. 1999.DOI
  7. [7]K.-C. Toh, M. J. Todd, and R. H. Tütüncü, “On the implementation and usage of SDPT3 – a Matlab software package for semidefinite-quadratic-linear programming, version 4.0,” in Handbook on Semidefinite, Conic and Polynomial Optimization. Springer US, Sep. 2011, pp. 715–754.
  8. [8]Z. Wen, D. Goldfarb, and W. Yin, “Alternating direction augmented lagrangian methods for semidefinite programming,” Math. Program. Comput., vol. 2, no. 3–4, pp. 203–230, Sep. 2010.DOI
  9. [9]L. Attuada, T. Hance, C. Cho, M. Brun, L. Subasinghe, Y. Zhou, J. Howell, B. Parno, and C. Hawblitzel, “Verus: Verifying Rust programs using linear ghost types,” Proc. ACM Program. Lang., vol. 7, no. OOPSLA1, pp. 286–315, Apr. 2023.
  10. [10]S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, UK: Cambridge University Press, 2004.
  11. [11]P. Hart, “convopt-rust: Semidefinite programming in Rust,” GitHub repository, tag verus-v1.0.0, 2026. [Online]. Available: https://github.com/PHart3/convopt-rust/tree/verus-v1.0.0
  12. [12]C. Li, Z. Wang, W. He, Y. Wu, S. Xu, and Z. Wen, “Formalization of convergence rates of four-order algorithms for convex optimization,” J. Autom. Reason., vol. 69, no. 4, p. 28, Oct. 2025.DOI
  13. [13]A. Bentkamp, R. Fernández Mir, and J. Avigad, “Verified reductions for optimization,” in Tools and Algorithms for the Construction and Analysis of Systems (TACAS), ser. LNCS, vol. 13994. Springer, Apr. 2023, pp. 74–92.arxiv.org/abs/2301.09347
  14. [14]R. J. George, W. Adkisson, and A. Anandkumar, “FloatLib: Verified floating-point arithmetic in Lean,” 2026. [Online]. Available: https://arxiv.org/abs/2609.19352
  15. [15]É. Martin-Dorel and P. Roux, “A reflexive tactic for polynomial positivity using numerical solvers and floating-point computations,” in Proc. 6th ACM SIGPLAN Conf. Certified Programs and Proofs (CPP). ACM, Jan. 2017, pp. 90–99.
  16. [16]The mathlib Community, “The Lean mathematical library,” in Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP). ACM, Jan. 2020, pp. 367–381.DOI
  17. [17]B. Recht, M. Fazel, and P. A. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,” SIAM Rev., vol. 52, no. 3, pp. 471–501, Sep. 2010.
  18. [18]L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Rev., vol. 38, no. 1, pp. 49–95, Mar. 1996.
  19. [19]N. J. Higham, “Computing a nearest symmetric positive semidefinite matrix,” Linear Algebra Appl., vol. 103, pp. 103–118, May 1988.DOI
  20. [20]G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed. Baltimore, MD: Johns Hopkins University Press, 2013.
  21. [21]J. W. Demmel, Applied Numerical Linear Algebra. Philadelphia, PA: SIAM, 1997.
  22. [22]L. de Moura and N. Bjørner, “Z3: An efficient SMT solver,” in Tools and Algorithms for the Construction and Analysis of Systems (TACAS), ser. LNCS, vol. 4963. Springer, 2008, pp. 337–340.DOI
  23. [23]R. Bhatia, Matrix Analysis, ser. Graduate Texts in Mathematics. New York, NY: Springer, 1997, vol. 169.
  24. [24]J. L. Rigal and J. Gaches, “On the compatibility of a given solution with the data of a linear system,” J. ACM, vol. 14, no. 3, pp. 543–548, Jul. 1967.DOI

Paper details

vlnc:W_84p4wt5g
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude

View statement
Looking for related papers…
Contents