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 30.594040
#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.071613

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

Session Info

sessionInfo()
## R version 3.6.3 (2020-02-29)
## Platform: x86_64-apple-darwin19.3.0 (64-bit)
## Running under: macOS Catalina 10.15.4
## 
## Matrix products: default
## BLAS:   /System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libBLAS.dylib
## LAPACK: /System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libLAPACK.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-1   
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_1.0.4.3     knitr_1.28       magrittr_1.5     bit_1.1-15.2    
##  [5] lattice_0.20-40  R6_2.4.1         rlang_0.4.5      stringr_1.4.0   
##  [9] tools_3.6.3      grid_3.6.3       xfun_0.12        osqp_0.6.0.3    
## [13] htmltools_0.4.0  yaml_2.2.1       bit64_0.9-7      digest_0.6.25   
## [17] assertthat_0.2.1 bookdown_0.18    gmp_0.5-13.6     Rglpk_0.6-4     
## [21] slam_0.1-47      evaluate_0.14    rmarkdown_2.1    blogdown_0.18   
## [25] Rcplex_0.3-3     gurobi_9.0-1     stringi_1.4.6    compiler_3.6.3  
## [29] Rmpfr_0.8-1      Rmosek_9.1.0     rcbc_0.1.0.9001

Source

R Markdown

References