Cyclic block coordinate descent, exact minimisation per block

Tseng result is that cyclic block descent converges on a smooth plus separable non-smooth function; separability is what saves it. For the convex quadratic each block subproblem has a closed form, so the sweep is exact and the objective decreases monotonically.

Usage

Bcdblk(Q, b, blocks, x0 = NULL, n_iter = 20)

Arguments

Q: Symmetric positive definite Hessian.
b: Linear term.
blocks: List of zero-based coordinate index vectors.
x0: Starting point; zeros by default.
n_iter: Number of full sweeps.

Value

List with estimate, x, obj_trace, n_iter.

Details

Determinism: fixed sweep count, fixed block order, no tolerance test. The callable-objective form is not representable across both arms, so the quadratic case is what is provided.

Formula: minimise f(x) = 0.5 x'Qx - b'x; exact block minimiser x_B = Q_BB^{-1} (b_B - Q_{B,Bc} x_{Bc}).

References

Tseng, P. (2001). Convergence of a block coordinate descent method for nondifferentiable minimization. JOTA 109:475-494.

Examples

Q <- matrix(c(4, 1, 0, 1, 3, 0, 0, 0, 2), 3)
Bcdblk(Q, b = c(1, 2, 3), blocks = list(c(0, 1), 2), n_iter = 10)
#> $estimate
#> [1] -2.931818
#> 
#> $x
#> [1] 0.09090909 0.63636364 1.50000000
#> 
#> $obj_trace
#>  [1]  0.000000 -2.931818 -2.931818 -2.931818 -2.931818 -2.931818 -2.931818
#>  [8] -2.931818 -2.931818 -2.931818 -2.931818
#> 
#> $n_iter
#> [1] 10
#> 
#> $method
#> [1] "Block coordinate descent, exact quadratic blocks"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"