| Title: | Semi-Definite Quadratic Linear Programming Solver |
|---|---|
| Description: | Solves the general Semi-Definite Linear Programming formulation using an R implementation of SDPT3 (K.C. Toh, M.J. Todd, and R.H. Tutuncu (1999) <doi:10.1080/10556789908805762>). This includes problems such as the nearest correlation matrix problem (Higham (2002) <doi:10.1093/imanum/22.3.329>), D-optimal experimental design (Smith (1918) <doi:10.2307/2331929>), Distance Weighted Discrimination (Marron and Todd (2012) <doi:10.1198/016214507000001120>), as well as graph theory problems including the maximum cut problem. Technical details surrounding SDPT3 can be found in R.H Tutuncu, K.C. Toh, and M.J. Todd (2003) <doi:10.1007/s10107-002-0347-5>. |
| Authors: | Kim-Chuan Toh (Matlab/C), Micheal Todd (Matlab/C), Reha Tutunco (Matlab/C), Adam Rahman (R/C Headers), Timothy A. Davis (symamd C code), Stefan I. Larimore (symamd C code) |
| Maintainer: | Adam Rahman <[email protected]> |
| License: | GPL-2 | GPL-3 |
| Version: | 0.3 |
| Built: | 2024-11-27 07:47:56 UTC |
| Source: | CRAN |
An Configuration Matrix for Distance Weighted Discrimination
data(Andwd)data(Andwd)
A matrix with 50 rows and 3 columns
Ap Configuration Matrix for Distance Weighted Discrimination
data(Apdwd)data(Apdwd)
A matrix with 50 rows and 3 columns
Symmetric Matrix for Educational Testing Problem
data(Betp)data(Betp)
A matrix with 5 rows and 5 columns
Adjacency Matrix for Graph Partitioning Problem
data(Bgpp)data(Bgpp)
A matrix with 10 rows and 10 columns
B Matrix for the Log Chebyshev Approximation Problem
data(Blogcheby)data(Blogcheby)
A matrix with 10 rows and 10 columns
Adjacency Matrix for Max-Cut
data(Bmaxcut)data(Bmaxcut)
A matrix with 10 rows and 10 columns
Adjacency Matrix for Max-kCut
data(Bmaxkcut)data(Bmaxkcut)
A matrix with 10 rows and 10 columns
control_theory creates input for sqlp to solve the Control Theory Problem
control_theory(B)control_theory(B)
B |
a matrix object containing square matrices of size n |
Solves the control theory problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
B <- matrix(list(),2,1) B[[1]] <- matrix(c(-.8,1.2,-.5,-1.1,-1,-2.5,2,.2,-1),nrow=3,byrow=TRUE) B[[2]] <- matrix(c(-1.5,.5,-2,1.1,-2,.2,-1.4,1.1,-1.5),nrow=3,byrow=TRUE) out <- control_theory(B)B <- matrix(list(),2,1) B[[1]] <- matrix(c(-.8,1.2,-.5,-1.1,-1,-2.5,2,.2,-1),nrow=3,byrow=TRUE) B[[2]] <- matrix(c(-1.5,.5,-2,1.1,-2,.2,-1.4,1.1,-1.5),nrow=3,byrow=TRUE) out <- control_theory(B)
Test Vector Matrix for D-Optimal Design
data(DoptDesign)data(DoptDesign)
A matrix with 3 rows and 25 columns
doptimal creates input for sqlp to solve the D-Optimal Experimental Design problem -
given an nxp matrix with p <= n, find the portion of points that maximizes det(A'A)
doptimal(V)doptimal(V)
V |
a pxn matrix containing a set of n test vectors in dimension p (with p <= n) |
Solves the D-optimal experimental design problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(DoptDesign) out <- doptimal(DoptDesign)data(DoptDesign) out <- doptimal(DoptDesign)
dwd creates input for sqlp to solve the Distance Weighted Discrimination problem -
Given two sets of points An and Ap, find an optimal classification rule to group the points as accurately
as possible for future classification.
dwd(Ap, An, penalty)dwd(Ap, An, penalty)
Ap |
An nxp point configuration matrix |
An |
An nxp point configuration matrix |
penalty |
A real valued scalar penalty for moving points across classification rule |
Solves the distance weighted discrimination problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Andwd) data(Apdwd) penalty <- 0.5 #Not Run #out <- dwd(Apdwd,Andwd,penalty)data(Andwd) data(Apdwd) penalty <- 0.5 #Not Run #out <- dwd(Apdwd,Andwd,penalty)
etp creates input for sqlp to solve the Educational Testing Problem -
given a symmetric positive definite matrix S, how much can be subtracted from the diagonal
elements of S such that the resulting matrix is positive semidefinite definite.
etp(B)etp(B)
B |
A symmetric positive definite matrix |
Solves the education testing problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Betp) out <- etp(Betp)data(Betp) out <- etp(Betp)
f vector for the Log Chebyshev Approximation Problem
data(flogcheby)data(flogcheby)
A vector with length 20
Symmetric Matrix for the Toeplitz Approximatin Problem
data(Ftoep)data(Ftoep)
A matrix with 10 rows and 10 columns
Adjacency Matrix on which to find the Lovasz Number
data(Glovasz)data(Glovasz)
A matrix with 10 rows and 10 columns
gpp creates input for sqlp to solve the graph partitioning problem.
gpp(B, alpha)gpp(B, alpha)
B |
A weighted adjacency matrix |
alpha |
Any real value in (0,n^2) |
Solves the graph partitioning problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Bgpp) alpha <- nrow(Bgpp) out <- gpp(Bgpp, alpha)data(Bgpp) alpha <- nrow(Bgpp) out <- gpp(Bgpp, alpha)
Approximate Correlation Matrix for Nearest Correlation Matrix Problem
data(Hnearcorr)data(Hnearcorr)
A matrix with 5 rows and 5 columns
lmi1 creates input for sqlp to solve a linear matrix inequality problem
lmi1(B)lmi1(B)
B |
An mxn real valued matrix |
Solves the type-1 linear matrix inequality problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
B <- matrix(c(-1,5,1,0,-2,1,0,0,-1), nrow=3) #Not Run #out <- lmi1(B)B <- matrix(c(-1,5,1,0,-2,1,0,0,-1), nrow=3) #Not Run #out <- lmi1(B)
lmi2 creates input for sqlp to solve a linear matrix inequality problem
lmi2(A1, A2, B)lmi2(A1, A2, B)
A1 |
An nxm real valued matrix |
A2 |
An nxm real valued matrix |
B |
An nxp real valued matrix |
Solves the type-2 linear matrix inequality problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
A1 <- matrix(c(-1,0,1,0,-2,1,0,0,-1),3,3) A2 <- A1 + 0.1*t(A1) B <- matrix(c(1,3,5,2,4,6),3,2) out <- lmi2(A1,A2,B)A1 <- matrix(c(-1,0,1,0,-2,1,0,0,-1),3,3) A2 <- A1 + 0.1*t(A1) B <- matrix(c(1,3,5,2,4,6),3,2) out <- lmi2(A1,A2,B)
lmi3 creates input for sqlp to solve a linear matrix inequality problem
lmi3(A, B, G)lmi3(A, B, G)
A |
An nxn real valued matrix |
B |
An mxn real valued matrix |
G |
An nxn real valued matrix |
Solves the type-3 linear matrix inequality problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
A <- matrix(c(-1,0,1,0,-2,1,0,0,-1),3,3) B <- matrix(c(1,2,3,4,5,6), 2, 3) G <- matrix(1,3,3) out <- lmi3(A,B,G)A <- matrix(c(-1,0,1,0,-2,1,0,0,-1),3,3) B <- matrix(c(1,2,3,4,5,6), 2, 3) G <- matrix(1,3,3) out <- lmi3(A,B,G)
logcheby creates input for sqlp to solve the Chebyshev Approximation Problem
logcheby(B, f)logcheby(B, f)
B |
A pxm real valued matrix with p > m |
f |
A vector of length p |
Solves the log Chebyshev approximation problem. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Blogcheby) data(flogcheby) #Not Run #out <- logcheby(Blogcheby, flogcheby)data(Blogcheby) data(flogcheby) #Not Run #out <- logcheby(Blogcheby, flogcheby)
lovasz creates input for sqlp to find the Lovasz Number of a graph
lovasz(G)lovasz(G)
G |
An adjacency matrix corresponding to a graph |
Finds the maximum Shannon entropy of a graph, more commonly known as the Lovasz number. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Glovasz) out <- lovasz(Glovasz)data(Glovasz) out <- lovasz(Glovasz)
maxcut creates input for sqlp to solve the Max-Cut problem -
given a graph B, find the maximum cut of the graph
maxcut(B)maxcut(B)
B |
A (weighted) adjacency matrix corresponding to a graph |
Determines the maximum cut for a graph B. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Bmaxcut) out <- maxcut(Bmaxcut)data(Bmaxcut) out <- maxcut(Bmaxcut)
maxkcut creates input for sqlp to solve the Max-kCut Problem -
given a graph object B, determine if a cut of at least size k exists.
maxkcut(B, K)maxkcut(B, K)
B |
A (weighted) adjacency matrix |
K |
An integer value, the minimum number of cuts in B |
Determines if a cut of at least size k exists for a graph B. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Bmaxkcut) out <- maxkcut(Bmaxkcut,2)data(Bmaxkcut) out <- maxkcut(Bmaxkcut,2)
minelips creates input for sqlp to solve the minimum ellipsoid problem -
given a set of n points, find the minimum volume ellipsoid that contains all the points
minelips(V)minelips(V)
V |
An nxp matrix consisting of the points to be contained in the ellipsoid |
for a set of points (x1,...,xn) determines the ellipse of minimum volume that contains all points. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Vminelips) #Not Run #out <- minelips(Vminelips)data(Vminelips) #Not Run #out <- minelips(Vminelips)
nearcorr creates input for sqlp to solve the nearest correlation matrix problem -
given a approximate correlation matrix H, find the nearest correlation matrix X.
nearcorr(H)nearcorr(H)
H |
A symmetric matrix |
For a given approximate correlation matrix H, determines the nearest correlation matrix X. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Hnearcorr) out <- nearcorr(Hnearcorr)data(Hnearcorr) out <- nearcorr(Hnearcorr)
smat takes a vector and creates a symmetrix matrix
smat(blk, p, At, isspM = NULL)smat(blk, p, At, isspM = NULL)
blk |
Lx2 matrix detailing the type of matrices ("s", "q", "l", "u"), and the size of each matrix |
p |
Row of blk to be used during matrix creation |
At |
vector to be turned into a symmetric matrix |
isspM |
if At is sparse, isspx = 1, 0 otherwise. Default is to assume M is dense. |
M |
A Symmetric Matrix |
y <- c(1,0.00000279, 3.245, 2.140, 2.44, 2.321, 4.566) blk <- matrix(list(),1,2) blk[[1,1]] <- "s" blk[[1,2]] <- 3 P <- smat(blk,1, y)y <- c(1,0.00000279, 3.245, 2.140, 2.44, 2.321, 4.566) blk <- matrix(list(),1,2) blk[[1,1]] <- "s" blk[[1,2]] <- 3 P <- smat(blk,1, y)
sqlp solves a semidefinite quadratic linear programming problem using the SDPT3 algorithm of Toh et. al. (1999)
returning both the primal solution X and dual solution Z.
sqlp(blk = NULL, At = NULL, C = NULL, b = NULL, control = NULL, X0 = NULL, y0 = NULL, Z0 = NULL)sqlp(blk = NULL, At = NULL, C = NULL, b = NULL, control = NULL, X0 = NULL, y0 = NULL, Z0 = NULL)
blk |
A named-list object describing the block diagonal structure of the SQLP data |
At |
A list object containing constraint matrices for the primal-dual problem |
C |
A list object containing the constant $c$ matrices in the primal objective function |
b |
A vector containing the right hand side of the equality constraints in the primal problem |
control |
A list object specifying the values of certain parameters. If not provided, default values are used |
X0 |
An initial iterate for the primal solution variable X. If not provided, an initial iterate is computed internally. |
y0 |
An initial iterate for the dual solution variable y. If not provided, an initial iterate is computed internally. |
Z0 |
An initial iterate for the dual solution variable Z. If not provided, an initial iterate is computed internally. |
A full mathematical description of the problem to be solved, details surrounding the input variables, and discussion regarding the output variables can be found in the accompanying vignette.
X |
A list containing the solution matrix to the primal problem |
y |
The solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
K.C. Toh, M.J. Todd, and R.H. Tutuncu, SDPT3 — a Matlab software package for semidefinite programming, Optimization Methods and Software, 11 (1999), pp. 545–581. R.H Tutuncu, K.C. Toh, and M.J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming Ser. B, 95 (2003), pp. 189–217.
blk = c("l" = 2) C = matrix(c(1,1),nrow=1) A = matrix(c(1,3,4,-1), nrow=2) At = t(A) b = c(12,10) out = sqlp(blk,list(At),list(C),b)blk = c("l" = 2) C = matrix(c(1,1),nrow=1) A = matrix(c(1,3,4,-1), nrow=2) At = t(A) b = c(12,10) out = sqlp(blk,list(At),list(C),b)
svec takes the upper triangular matrix (including the diagonal) and vectorizes
it column-wise.
svec(blk, M, isspx = NULL)svec(blk, M, isspx = NULL)
blk |
1x2 matrix detailing the type of matrix ("s", "q", "l", "u"), and the size of the matrix |
M |
matrix which is to be vectorized |
isspx |
if M is sparse, isspx = 1, 0 otherwise. Default is to assume M is dense. |
x |
vector of upper triangular components of x |
data(Hnearcorr) blk <- matrix(list(),1,2) blk[[1]] <- "s" blk[[2]] <- nrow(Hnearcorr) svec(blk,Hnearcorr)data(Hnearcorr) blk <- matrix(list(),1,2) blk[[1]] <- "s" blk[[2]] <- nrow(Hnearcorr) svec(blk,Hnearcorr)
toep creates input for sqlp to solve the Toeplitz approximation problem -
given a symmetric matrix F, find the nearest symmetric positive definite Toeplitz matrix.
toep(A)toep(A)
A |
A symmetric matrix |
For a symmetric matrix A, determines the closest Toeplitz matrix. Mathematical and implementation details can be found in the vignette
X |
A list containing the solution matrix to the primal problem |
y |
A list containing the solution vector to the dual problem |
Z |
A list containing the solution matrix to the dual problem |
pobj |
The achieved value of the primary objective function |
dobj |
The achieved value of the dual objective function |
data(Ftoep) #Not Run #out <- toep(Ftoep)data(Ftoep) #Not Run #out <- toep(Ftoep)
Configuration Matrix for Minimum Ellipse Problem
data(Vminelips)data(Vminelips)
A matrix with 2 rows and 2 columns