Time- and memory-inefficient construction of large objectives

[alexrwatson]

Describe the bug
An objective constructed iteratively (by adding to previous objectives) is dramatically slower and uses much more memory than an apparently-equivalent expression using matrix operations.

To Reproduce

library(CVXR)

A = matrix(rnorm(80*4), nrow=80, ncol=4)
x = Variable(4)

# Naive implementation of sum-of-squares objective
print("Naive problem construction")
print(system.time({ 
  objective = 0
  for (i in 1:nrow(A)) {
    objective = objective + (t(A[i,]) %*% x)**2
  }
  prob = Problem(Minimize(objective), list())
}))
print("Naive problem solution")
print(system.time({
  res = solve(prob)
  print(res$status)
}))

# Slightly more efficient implementation of sum-of-squares objective
print("More efficient problem construction")
print(system.time({
  objective_eff = sum((A %*% x)**2)
  prob_eff = Problem(Minimize(objective_eff), list())
}))
print("More efficient problem solution")
print(system.time({
  res_eff = solve(prob_eff)
  print(res_eff$status)
}))

Expected behavior
I would expect the more efficient problem construction to run a little faster, but not dramatically so. I would expect the problem solution to be identical, since the semantics of the two problem constructions should be identical.

Output

[1] "Naive problem construction"
   user  system elapsed 
  1.245   0.000   1.245 
[1] "Naive problem solution"
[1] "optimal"
   user  system elapsed 
  4.482   0.000   4.480 
[1] "More efficient problem construction"
   user  system elapsed 
  0.013   0.000   0.014 
[1] "More efficient problem solution"
[1] "optimal"
   user  system elapsed 
  0.096   0.000   0.095 

The solution takes more 46 times as long with the naive construction compared to the more efficient one, even though both of them are the same sum-of-squares objective. The construction takes 89 times as long. It's very surprising that constructing a vector and summing it does not end up compile to the same problem as summing the elements of the vector step by step.

Moreover, the (nominal...?) memory usage is different by a factor of 1400. RStudio reports prob to be a Large Problem (890.3 MB) and prob_eff to be a Large Problem (636.9 kB). This doesn't reflect the actual memory usage - I guess there is some sparse implementation behind the scenes - but if any objects are serialised (using save or knitr caching) then they do not seem to be stored efficiently and it becomes a big problem.

Version

R version 4.4.2 (2024-10-31)
Platform: x86_64-pc-linux-gnu
Running under: Ubuntu 22.04.5 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/openblas-pthread/libblas.so.3 
LAPACK: /usr/lib/x86_64-linux-gnu/openblas-pthread/libopenblasp-r0.3.20.so;  LAPACK version 3.10.0

locale:
 [1] LC_CTYPE=en_GB.UTF-8       LC_NUMERIC=C               LC_TIME=en_GB.UTF-8        LC_COLLATE=en_GB.UTF-8    
 [5] LC_MONETARY=en_GB.UTF-8    LC_MESSAGES=en_GB.UTF-8    LC_PAPER=en_GB.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C             LC_MEASUREMENT=en_GB.UTF-8 LC_IDENTIFICATION=C       

time zone: Europe/London
tzcode source: system (glibc)

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

other attached packages:
[1] CVXR_1.0-14

loaded via a namespace (and not attached):
 [1] R6_2.5.1          Matrix_1.7-1      bit_4.5.0         lattice_0.22-5    osqp_0.6.3.3      gmp_0.7-5        
 [7] bit64_4.5.2       grid_4.4.2        Rglpk_0.6-5.1     renv_1.0.7        Rmpfr_0.9-5       slam_0.1-54      
[13] compiler_4.4.2    rstudioapi_0.17.1 tools_4.4.2       Rcpp_1.0.13       yaml_2.3.10 

Additional context
Obviously the easy response to this 'bug' is to say 'Well, write your problems efficiently then.' Fair enough. R expressions are also more efficient when vectorised (but the disparity is, I think, less than here). I'm mostly interested in this from a pedagogical point of view - when a class first sees a data-driven problem (which is probably more complicated than least-squares) it's easier to explain the for loop than the vectorised version.

It might be that my hope that these expressions should be 'equivalent' is naive, and this is just too hard - CVXR has to convert these into the solvers' representations, and maybe this is way easier with the second construction than the first? But maybe there is a missed opportunity for efficiency which would at least bring the memory usage down to reasonable levels?