Minimum-Length Least Squares

Author

CVXPY Developers and Balasubramanian Narasimhan

Introduction

This example shows how to solve a minimum-length least squares problem, which finds a minimum-length vector $x \in R^{n}$ achieving small mean-square error (MSE) for a particular least-squares problem:

$\begin{array}{ll} minimize & len (x) \\ subject to & \frac{1}{n} ∥ A x - b ∥_{2}^{2} \leq ϵ, \end{array}$

where the variable is $x$ and the problem data are $n$ , $A$ , $b$ , and $ϵ$ .

Here, $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 = A x^{*}$ .

n <- 10
set.seed(1)
A <- matrix(rnorm(n * n), n, n)
x_star <- rnorm(n)
b <- A %*% x_star
epsilon <- 1e-2

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 $ϵ$ .

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.2 (2025-10-31)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3

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    Rcplex_0.3-8     
[17] backports_1.5.0   rprojroot_2.1.1   htmltools_0.5.9   Rmosek_11.1.1    
[21] gmp_0.7-5.1       piqp_0.6.2        rmarkdown_2.30    grid_4.5.2       
[25] evaluate_1.0.5    fastmap_1.2.0     yaml_2.3.12       compiler_4.5.2   
[29] codetools_0.2-20  htmlwidgets_1.6.4 Rcpp_1.1.1        here_1.0.2       
[33] osqp_1.0.0        lattice_0.22-9    digest_0.6.39     checkmate_2.3.4  
[37] Matrix_1.7-4      tools_4.5.2

References

Agrawal, A., Boyd, S. (2020). Disciplined Quasiconvex Programming. Optimization Letters, 14, 1643–1657.