R - Optimize X, such that min(sum(X_i)) for all n, where X_n + X_(n-1) + X_(n-2) >= Y_n, where Y is known for all n

Question

I have a unknown vector X with length=50, and a known vector Y (length 50) of constants.

I wish to find X, such that for X_i>=0, sum(X_i) is minimized, with the constraint:

X_n + X_{n-1} >= Y_n

I am not sure where to start with R.

Answer 1

I guess you can try CVXR to solve the optimization problem.

1. First of all, let's define a matrix M like below

M <- matrix(0,nrow = 10,ncol = 11)
for (i in 1:nrow(M)) {
  for (j in 1:ncol(M)) {
    if (j %in% (i+(0:1))) M[i,j] <- 1
  }
}

which looks like

> M
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
 [1,]    1    1    0    0    0    0    0    0    0     0     0
 [2,]    0    1    1    0    0    0    0    0    0     0     0
 [3,]    0    0    1    1    0    0    0    0    0     0     0
 [4,]    0    0    0    1    1    0    0    0    0     0     0
 [5,]    0    0    0    0    1    1    0    0    0     0     0
 [6,]    0    0    0    0    0    1    1    0    0     0     0
 [7,]    0    0    0    0    0    0    1    1    0     0     0
 [8,]    0    0    0    0    0    0    0    1    1     0     0
 [9,]    0    0    0    0    0    0    0    0    1     1     0
[10,]    0    0    0    0    0    0    0    0    0     1     1

2. Then, we construct the objective function as well as the constraints

library(CVXR)
X <- Variable(11)
objective <- Minimize(sum(X))
constraints <- list( X>=0, M%*%X >= Y)
problem <- Problem(objective,constraints)
res <- solve(problem)

3. Finally, we can see values of X via res$getValue(X)

---

Example Given Y as below

set.seed(1)
Y <- runif(10)

we can get

Xopt <- res$getValue(X)

> Xopt
              [,1]
 [1,] 1.667850e-07
 [2,] 3.072356e-01
 [3,] 6.488860e-02
 [4,] 6.214644e-01
 [5,] 2.867441e-01
 [6,] 1.486883e-02
 [7,] 8.835218e-01
 [8,] 7.476340e-02
 [9,] 5.860353e-01
[10,] 5.264372e-02
[11,] 9.142897e-03

---

Another possible option might be pracma::fmincon, e.g.,

pracma:: fmincon(rep(0, 11),
  function(x) sum(x),
  A = -M,
  b = -Y,
  lb = 0,
)