n <- 10
set.seed(1)
A <- matrix(rnorm(n * n), n, n)
x_star <- rnorm(n)
b <- A %*% x_star
epsilon <- 1e-2Minimum-Length Least Squares
Introduction
This example shows how to solve a minimum-length least squares problem, which finds a minimum-length vector \(x \in \mathbf{R}^n\) achieving small mean-square error (MSE) for a particular least-squares problem:
\[ \begin{array}{ll} \mbox{minimize} & \mathrm{len}(x) \\ \mbox{subject to} & \frac{1}{n}\|Ax - b\|_2^2 \leq \epsilon, \end{array} \]
where the variable is \(x\) and the problem data are \(n\), \(A\), \(b\), and \(\epsilon\).
Here, \(\mathrm{len}(x)\) denotes the index of the last nonzero element in \(x\). This is a quasiconvex function, and the overall problem is a quasiconvex program (QCP). It can be specified using disciplined quasiconvex programming (DQCP) and therefore solved using CVXR.
Problem Data
We first construct the problem data. We generate a random \(n \times n\) matrix \(A\) and a “true” solution \(x^*\), then compute \(b = Ax^*\).
Solving the QCP
Now we construct and solve the QCP using DQCP. The objective length_expr(x) computes the index of the last nonzero element in \(x\), and the constraint requires the MSE to be at most \(\epsilon\).
x <- Variable(n)
mse <- sum_squares(A %*% x - b) / n
problem <- Problem(Minimize(length_expr(x)), list(mse <= epsilon))
cat("Is problem DQCP?", is_dqcp(problem), "\n")
result <- psolve(problem, qcp = TRUE)
check_solver_status(problem)
cat("Found a solution, with length:", result, "\n")Is problem DQCP? TRUE
Found a solution, with length: 9 The result tells us that the optimizer found a solution whose last nonzero element is at a position less than \(n\), meaning some trailing entries of \(x\) are (approximately) zero. Let us inspect the MSE and the solution:
cat("MSE:", value(mse), "\n")MSE: 0.008573609 cat("x:", value(x), "\n")x: 6.380624 -3.836223 2.554995 -3.388525 -6.414025 0.6027364 5.530766 4.008516 5.174304 -8.629955e-17 For comparison, here is the “true” solution \(x^*\) from which the data was generated:
cat("x_star:", as.numeric(x_star), "\n")x_star: -0.6203667 0.04211587 -0.9109216 0.1580288 -0.6545846 1.767287 0.7167075 0.9101742 0.3841854 1.682176 The minimum-length solution achieves the MSE bound while setting some trailing components to zero, effectively finding a sparser representation. This demonstrates how quasiconvex optimization can be used to find solutions with structural properties (here, sparsity in a specific sense) that go beyond what standard convex optimization provides.
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., Boyd, S. (2020). Disciplined Quasiconvex Programming. Optimization Letters, 14, 1643–1657.