gforce.FORCE: FORCE \(K\)-means solver.

Description

Solves the Peng-Wei K-means SDP Relaxation using the FORCE algorithm.

Usage

gforce.FORCE(D, K, force_opts = NULL, D_Kmeans = NULL, X0 = NULL,
  E = NULL, R_only = FALSE)

Arguments

a matrix \(D\) as defined above.

number of clusters.

force_opts

tuning parameters. NULL signifies defaults will be used.

D_Kmeans

matrix to be used for initial integer solution. NULL signifies that D will be used.

initial iterate. NULL signifies that it will be generated randomly from D_Kmeans. If supplied, E must be supplied as well.

strictly feasible solutions. NULL signifies that it will be generated randomly. If supplied, X0 must be supplied as well.

R_only

logical expression. If R_only == FALSE, then the included native code implementation will be used. Otherwise, an R implementation is used.

Value

An object with following components

Z_T: Final iterate of the projected gradient descent algorithm run on the smoothed eigenvalue problem.
B_Z_T: Projection of Z_T to the border of the positive semi-definite cone.
B_Z_T_opt_val: Objective value of the \(K\)-means SDP relaxation at B_Z_T.
Z_best: Iterate with best objective value found during projected gradient descent on the smoothed eigenvalue problem.
B_Z_best: Projection of Z_best to the border of the positive semi-definite cone.
B_Z_best_opt_val: Objective value of the \(K\)-means SDP relaxation at B_Z_T.
km_best: Best clustering in terms of objective value of the SDP relaxation. This is found by running Lloyd's algorithm on the rows of D_kmeans_matrix.
B_km: Partnership matrix corresponding to km_best.
km_opt_val: Objective value of the \(K\)-means SDP relaxation at B_km.
km_best_time: Time elapsed (in seconds) until km_best was found.
km_iter_best: Number of times a \(K\)-means algorithm was run before km_best was found.
km_iter_total: Total number of calls to a \(K\)-means solver (such as Lloyd's algorithm).
dual_certified: 1 if a dual certificate was found, and 0 otherwise.
dual_certified_grad_iter: Number of gradient updates performed before a dual certificate was found.
dual_certified_time: Time elapsed (in seconds) until dual certificate was found for B_km.
grad_iter_best: Gradient iteration where Z_best was computed.
grad_iter_best_time: Time elapsed (in seconds) when the update grad_iter_best was performed.
total_time: Total time elapsed (in seconds) during call to gforce.FORCE.

References

C. Eisenach and H. Liu. Efficient, Certifiably Optimal High-Dimensional Clustering. arXiv:1806.00530, 2018.

J. Peng and Y. Wei. Approximating K-means-type Clustering via Semidefinite Programming. SIAM Journal on Optimization, 2007.

J. Renegar. Efficient first-order methods for linear programming and semidefinite programming. arXiv:1409.5832, 2014.

Examples

Run this code

# NOT RUN {
K <- 5
n <- 50
d <- 50
dat <- gforce.generator(K,d,n,3,graph='scalefree')
sig_hat <- (1/n)*t(dat$X)%*%dat$X
gam_hat <- gforce.Gamma(dat$X)
D <- diag(gam_hat) - sig_hat
res <- gforce.FORCE(D,K)

# }