Semidefinite Blocks (Operational Routines)


Detailed Description

Additional routines that operate on the data.

#include dsdp5.h 

In DSDP Standard Form a semidefinite program is given by the pair of problems

\[ \begin{array}{llllllllll} (P) \ \ \ & \mbox{minimize} & {\displaystyle \sum_{j=0}^{n_b-1} C_j \bullet X_j } &\mbox{subject to}& {\displaystyle \sum_{j=0}^{n_b-1} A_{i,j} \bullet X_{j} = b_i } ,& i=1,\ldots, m, & & X_j \succeq 0, \\ \end{array} \]

\[ \begin{array}{lllllllll} (D) \ \ \ & \mbox{maximize} & {\displaystyle \sum_{i=1}^m b_i \ y_i } &\mbox{subject to}&{\displaystyle \sum_{i=1}^m A_{i,j}y_i + S_{j} } = C_{j}, & j=0, \ldots, n_b-1, & S_j \succeq 0 \\ \end{array} \]

where the data $A_{i,j}$ and $C_j$ are symmetric matrices of the same dimension and the inner product of two $n \times n$ matrices $C=(c_{k,l})$ and $X=(x_{k,l})$ is defined by $ C \bullet X := trace (C^T X) = \sum_{k,l}c_{k,l} x_{k,l} $.

Blocks are labelled from 0 to nblocks, where nblocks is the total number of blocks in the SDPCone object.

Variables y are numbered 1 through m. Variable 0 designates the C matrices, which are also denoted $ A_{0,j}$.

Return values:
0 if successful


Functions

int SDPConeAddADotX (SDPCone sdpcone, int blockj, double alpha, double x[], int nn, double adotx[], int m)
 Compute the inner products of a dense matrix X with the data matrices.
int SDPConeAddXVAV (SDPCone sdpcone, int blockj, double vin[], int n, double sum[], int mm)
 Compute $ v^T A_{i,j} v $ for i = 0 through m.
int SDPConeComputeS (SDPCone sdpcone, int blockj, double cc, double y[], int nvars, double r, int n, double s[], int nn)
 Compute the dual matrix S.
int SDPConeComputeX (SDPCone sdpcone, int blockj, int n, double x[], int nn)
 Compute the matrix X.
int SDPConeComputeXV (SDPCone sdpcone, int blockj, int *derror)
 Compute a factor V such that $ V V^T= X $.
int SDPConeGetBlockSize (SDPCone sdpcone, int blockj, int *n)
 Get the dimension of one block in the semidefinite cone.
int SDPConeGetNumberOfBlocks (SDPCone sdpcone, int *nblocks)
 Get the number of blocks in the semidefinite cone.
int SDPConeMatrixView (SDPCone sdpcone, int blockj)
 Print the dense array to the screen.
int SDPConeRestoreXArray (SDPCone sdpcone, int blockj, double *xx[], int *nn)
 Restore the dense array and set these pointers to null.
int SDPConeSetBlockSize (SDPCone sdpcone, int blockj, int n)
 Set the dimension of one block in the semidefinite cone.
int SDPConeSetSparsity (SDPCone sdpcone, int blockj, int nnz)
 Set the number of nonzero matrices in a block of the semidefinite cone.
int SDPConeSetXArray (SDPCone sdpcone, int blockj, int n, double xx[], int nn)
 Provide an array for the SDPCone object can use to store dense matrices.
int SDPConeXVMultiply (SDPCone sdpcone, int blockj, double vin[], double vout[], int n)
 Multiply an array by a factor V such that $ V V^T= X $.


Function Documentation

int SDPConeAddADotX ( SDPCone  sdpcone,
int  blockj,
double  alpha,
double  x[],
int  nn,
double  adotx[],
int  m 
)

Compute the inner products of a dense matrix X with the data matrices.

Parameters:
sdpcone semidefinite cone
blockj block number
alpha multiply inner product be this multiple
x the dense array representing a matrix X.
nn length of the array
adotx array.
m the length of the array and the number of variables y, plus two.

Definition at line 75 of file sdpcone.c.

int SDPConeAddXVAV ( SDPCone  sdpcone,
int  blockj,
double  vin[],
int  n,
double  sum[],
int  mm 
)

Compute $ v^T A_{i,j} v $ for i = 0 through m.

Parameters:
sdpcone the SDP cone
blockj block number
vin array
n dimension of the block and the length of the two arrays.
sum input array
mm the number of variables plus 2
See also:
SDPConeAddADotX()

Definition at line 292 of file sdpcone.c.

Referenced by MaxCutRandomized(), and StableRandomized().

int SDPConeComputeS ( SDPCone  sdpcone,
int  blockj,
double  cc,
double  y[],
int  nvars,
double  r,
int  n,
double  s[],
int  nn 
)

Compute the dual matrix S.

Parameters:
sdpcone semidefinite cone object
blockj block number
cc the multiple of the matrix C (or A_0)
y an array of containing the variables y
nvars the length of the array and the number of variables y
r the multiple of the identity matrix to add
n the dimension of the block
s array to where the matrix S will be copied.
nn length of the array s

Definition at line 42 of file sdpcone.c.

Referenced by DSDPPrintData(), and DSDPPrintSolution().

int SDPConeComputeX ( SDPCone  sdpcone,
int  blockj,
int  n,
double  x[],
int  nn 
)

Compute the matrix X.

Parameters:
sdpcone semidefinite cone
n di
blockj block number
n the dimension of the block
x array to where the matrix X will be copied.
nn length of the array x
See also:
DSDPComputeX()

Definition at line 191 of file sdpcone.c.

int SDPConeComputeXV ( SDPCone  sdpcone,
int  blockj,
int *  derror 
)

Compute a factor V such that $ V V^T= X $.

Parameters:
sdpcone the SDP cone
blockj block number
derror nonzero if no such factor could be computed.
See also:
SDPConeXVMultiply()
This routine is helpful in semidefinite relaxations of combinatorial problems.

Definition at line 325 of file sdpcone.c.

Referenced by MaxCutRandomized(), and StableRandomized().

int SDPConeGetBlockSize ( SDPCone  sdpcone,
int  blockj,
int *  n 
)

Get the dimension of one block in the semidefinite cone.

Parameters:
sdpcone semidefinite cone object
blockj block number
*n set to the dimension of the block
See also:
SDPConeSetBlockSize()

Definition at line 560 of file dsdpadddata.c.

Referenced by DSDPPrintData(), DSDPPrintSolution(), and SDPConeAddADotX().

int SDPConeGetNumberOfBlocks ( SDPCone  sdpcone,
int *  nblocks 
)

Get the number of blocks in the semidefinite cone.

Parameters:
sdpcone semidefinite cone object
*nblocks set to the dimension of the block
See also:
DSDPCreateSDPCone()

Definition at line 578 of file dsdpadddata.c.

Referenced by DSDPPrintData(), and DSDPPrintSolution().

int SDPConeMatrixView ( SDPCone  sdpcone,
int  blockj 
)

Print the dense array to the screen.

Parameters:
sdpcone semidefinite cone object
blockj block number
See also:
SDPConeGetXArray()

Definition at line 372 of file dsdpadddata.c.

int SDPConeRestoreXArray ( SDPCone  sdpcone,
int  blockj,
double *  xx[],
int *  nn 
)

Restore the dense array and set these pointers to null.

Parameters:
sdpcone semidefinite cone object
blockj block number
xx address of an array for dense matrices
*nn the length of the array
See also:
SDPConeGetXArray()

Definition at line 351 of file dsdpadddata.c.

Referenced by DSDPPrintSolution().

int SDPConeSetBlockSize ( SDPCone  sdpcone,
int  blockj,
int  n 
)

Set the dimension of one block in the semidefinite cone.

Parameters:
sdpcone semidefinite cone object
blockj block number
n dimension of the block
Note:
This routine is optional, but its use can help the object detect input errors.

Definition at line 535 of file dsdpadddata.c.

Referenced by LovaszTheta(), MaxCut(), mexFunction(), MinColoring(), ReadSDPAFile(), SDPConeCheckN(), and StableSet().

int SDPConeSetSparsity ( SDPCone  sdpcone,
int  blockj,
int  nnz 
)

Set the number of nonzero matrices in a block of the semidefinite cone.

Parameters:
sdpcone semidefinite cone object
blockj block number
nnz number of nonzero matrices in the block
Note:
This routine is optional, but its use can improve the memory allocation within the SDPCone object.

Definition at line 596 of file dsdpadddata.c.

Referenced by LovaszTheta(), mexFunction(), MinColoring(), ReadSDPAFile(), and StableSet().

int SDPConeSetXArray ( SDPCone  sdpcone,
int  blockj,
int  n,
double  xx[],
int  nn 
)

Provide an array for the SDPCone object can use to store dense matrices.

Parameters:
sdpcone semidefinite cone object
blockj block number
n dimension of the block
xx array for dense matrices
nn length of array
This routine elimates the need to copy the solution X into a separate array.

See also:
SDPConeGetXArray()

Definition at line 278 of file dsdpadddata.c.

Referenced by mexFunction(), and ReadSDPAFile().

int SDPConeXVMultiply ( SDPCone  sdpcone,
int  blockj,
double  vin[],
double  vout[],
int  n 
)

Multiply an array by a factor V such that $ V V^T= X $.

Parameters:
sdpcone the SDP cone
blockj block number
vin input array
vout the product V vin
n dimension of the block and the length of the two arrays.
See also:
SDPConeComputeXV()

SDPConeAddXVAV()

Definition at line 251 of file sdpcone.c.

Referenced by MaxCutRandomized(), and StableRandomized().


Generated on Wed May 21 19:31:20 2008 for DSDP by  doxygen 1.5.5