Perron-Frobenius Matrix Completion

Introduction

The DGP atom library has several functions of positive matrices, including the trace, (matrix) product, sum, Perron-Frobenius eigenvalue, and \((I - X)^{-1}\) (eye-minus-inverse). In this example, we use some of these atoms to formulate and solve an interesting matrix completion problem.

In this problem, we are given some entries of an elementwise positive matrix \(A\), and the goal is to choose the missing entries so as to minimize the Perron-Frobenius eigenvalue or spectral radius. Letting \(\Omega\) denote the set of indices \((i, j)\) for which \(A_{ij}\) is known, the optimization problem is

\[ \begin{array}{ll} \mbox{minimize} & \lambda_{\text{pf}}(X) \\ \mbox{subject to} & \prod_{(i, j) \not\in \Omega} X_{ij} = 1 \\ & X_{ij} = A_{ij}, \, (i, j) \in \Omega, \end{array} \]

which is a log-log convex program.

Problem Data

We consider the partially known matrix

\[ A = \begin{bmatrix} 1.0 & ? & 1.9 \\ ? & 0.8 & ? \\ 3.2 & 5.9& ? \end{bmatrix}, \]

where the question marks denote the missing entries.

Problem Formulation and Solution

n <- 3

# Known entries: (row, col) pairs (1-indexed in R)
known_rows <- c(1, 1, 2, 3, 3)
known_cols <- c(1, 3, 2, 1, 2)
known_values <- c(1.0, 1.9, 0.8, 3.2, 5.9)

X <- Variable(c(n, n), pos = TRUE)
objective_fn <- pf_eigenvalue(X)

constraints <- lapply(seq_along(known_values), function(k) {
    X[known_rows[k], known_cols[k]] == known_values[k]
})

# Constraint on the product of unknown entries
# Unknown entries are: (1,2), (2,1), (2,3), (3,3)
constraints <- c(constraints, list(
  X[1, 2] * X[2, 1] * X[2, 3] * X[3, 3] == 1.0
))

problem <- Problem(Minimize(objective_fn), constraints)
result <- psolve(problem, gp = TRUE)
check_solver_status(problem)
cat("Optimal value (spectral radius):", result, "\n")
cat("X:\n")
print(value(X))

Optimal value (spectral radius): 4.702374 
X:
          [,1]     [,2]      [,3]
[1,] 1.0000000 4.636241 1.9000000
[2,] 0.4999191 0.800000 0.3777418
[3,] 3.2000000 5.900000 1.1421922

The optimal spectral radius is approximately 4.70. The solver finds values for the unknown entries that minimize this spectral radius while satisfying the constraint that the product of the unknown entries equals 1.

Session Info

R version 4.5.3 (2026-03-11)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3.1

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/Los_Angeles
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] CVXR_1.8.1

loaded via a namespace (and not attached):
 [1] slam_0.1-55       cli_3.6.5         knitr_1.51        ECOSolveR_0.6.1  
 [5] rlang_1.1.7       xfun_0.56         clarabel_0.11.2   otel_0.2.0       
 [9] gurobi_13.0-1     Rglpk_0.6-5.1     highs_1.12.0-3    cccp_0.3-3       
[13] scs_3.2.7         S7_0.2.1          jsonlite_2.0.0    backports_1.5.0  
[17] rprojroot_2.1.1   htmltools_0.5.9   Rmosek_11.1.1     gmp_0.7-5.1      
[21] piqp_0.6.2        rmarkdown_2.30    grid_4.5.3        evaluate_1.0.5   
[25] fastmap_1.2.0     yaml_2.3.12       compiler_4.5.3    codetools_0.2-20 
[29] htmlwidgets_1.6.4 Rcpp_1.1.1        here_1.0.2        osqp_1.0.0       
[33] lattice_0.22-9    digest_0.6.39     checkmate_2.3.4   Matrix_1.7-4     
[37] tools_4.5.3      

References

• Agrawal, A., Diamond, S., Boyd, S. (2019). Disciplined Geometric Programming. Optimization Letters, 13(5), 961–976.