Warm Starts

A new feature in 1.0 is warm starts for one of our solvers in OSQP. Having warm starts allows the user to retain data of a particular problem and change parameters of the problem without repeating any of the calculations.

Lasso Example

We will demonstrate this in a simple lasso problem:

\[ \begin{array}{ll} \underset{x, \lambda}{\mbox{minimize}} & \frac{1}{2}||Ax - b||_2^2 + \lambda ||x||_1\\ \mbox{subject to} & \lambda > 0 \end{array} \]

#Problem data
set.seed(1)
m <- 2000
n <- 1000
A <- Matrix(rnorm(m*n), nrow = m, ncol = n)
b <- rnorm(m)

#Construct problem
gamma <- Parameter(pos = TRUE)
x <- Variable(n)
obj <- Minimize(.5 * sum_squares(A%*%x - b) + gamma * norm1(x))
constraint <- list(x >= 0)
prob <- Problem(obj, constraint)

#Solve first time
value(gamma) <- 1
result <- solve(prob, solver = "OSQP", warm_start = TRUE) #warm_start = T is not necessary for the first time
cat(sprintf("First solve time is %f\n", result$solve_time))
## First solve time is 29.043055
#Solve second time
value(gamma) <- 2
result <- solve(prob, solver = "OSQP", warm_start = TRUE)
cat(sprintf("Second solve time is %f\n", result$solve_time))
## Second solve time is 1.042841

As you can see, there is a very significant speed up with warm starts than without.

Session Info

sessionInfo()
## R version 4.0.2 (2020-06-22)
## Platform: x86_64-apple-darwin19.5.0 (64-bit)
## Running under: macOS Catalina 10.15.7
## 
## Matrix products: default
## BLAS/LAPACK: /usr/local/Cellar/openblas/0.3.10_1/lib/libopenblasp-r0.3.10.dylib
## 
## locale:
## [1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8
## 
## attached base packages:
## [1] stats     graphics  grDevices datasets  utils     methods   base     
## 
## other attached packages:
## [1] Matrix_1.2-18 CVXR_1.0-9   
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_1.0.5       knitr_1.28       magrittr_1.5     bit_1.1-15.2    
##  [5] lattice_0.20-41  R6_2.4.1         rlang_0.4.7      stringr_1.4.0   
##  [9] tools_4.0.2      grid_4.0.2       xfun_0.15        osqp_0.6.0.3    
## [13] htmltools_0.5.0  yaml_2.2.1       bit64_0.9-7      digest_0.6.25   
## [17] assertthat_0.2.1 bookdown_0.19    cccp_0.2-4       gmp_0.6-0       
## [21] Rglpk_0.6-4      codetools_0.2-16 slam_0.1-47      evaluate_0.14   
## [25] rmarkdown_2.3    blogdown_0.19    Rcplex_0.3-3     gurobi_9.0.3.1  
## [29] stringi_1.4.6    compiler_4.0.2   Rmpfr_0.8-1      Rmosek_9.2.3    
## [33] rcbc_0.1.0.9001

Source

R Markdown

References