gforce.FORCE: FORCE K-means solver.

In GFORCE: Clustering and Inference Procedures for High-Dimensional Latent Variable Models

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

D	a matrix D as defined above.
K	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.
X0	initial iterate. NULL signifies that it will be generated randomly from D_Kmeans. If supplied, E must be supplied as well.
E	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.

See Also

gforce.defaults

Examples

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)

GFORCE documentation built on May 2, 2019, 3:44 a.m.