ISTA with constant stepsize
Input: L := L(f) - A Lipschitz constant of ∇f.
Step 0. Take x0 ∈ Rn.
Step k. (k ≥ 1) Compute
(3.1) xk = pL(xk−1).
ISTA with backtracking
Step 0. Take L0 > 0, some η > 1, and x0 ∈ Rn.
Step k. (k ≥ 1) Find the smallest nonnegative integers ik such
that with L¯ = ηikLk−1
(3.2) F(pL¯(xk−1)) ≤ QL¯(pL¯ (xk−1), xk−1).
Set Lk = ηikLk−1 and compute
(3.3) xk = pLk (xk−1).
FISTA with constant stepsize
Input: L = L(f) - A Lipschitz constant of ∇f.
Step 0. Take y1 = x0 ∈ Rn, t1 = 1.
Step k. (k ≥ 1) Compute
(4.1) xk = pL(yk), tk+1 =
1 +
1+4t2k 2 (4.2) , yk+1 = xk + tk − 1 tk+1
(4.3) (xk − xk−1).
FISTA with backtracking
Step 0. Take L0 > 0, some η > 1, and x0 ∈ Rn. Set y1 = x0, t1 = 1.
Step k. (k ≥ 1) Find the smallest nonnegative integers ik such that
with L¯ = ηikLk−1 F(pL¯(yk)) ≤ QL¯(pL¯(yk), yk).
Set Lk = ηikLk−1 and compute
xk = pLk (yk), tk+1 =
1 +
1+4t2k 2 , yk+1 = xk + tk − 1 tk+1 (xk − xk−1).