dsdp.h File Reference

Detailed Description

Internal data structure for the DSDP solver.

Definition in file dsdp.h.

Go to the source code of this file.

Data Structures

struct  DSDP_C
 Internal structures for the DSDP solver. More...

Typedefs

typedef struct RDCone * RRCone
 Cone with nonnegativity on variable r.
typedef struct LUBounds_C * YBoundCone
 Cone with bounds on variables y.

Functions

int BoundYConeGetBounds (YBoundCone, double *, double *)
 Get bounds on the variables.
int BoundYConeSetBounds (YBoundCone, double, double)
 Set bounds on the variables.
int DSDPCGSolve (DSDP, DSDPSchurMat, DSDPVec, DSDPVec, double, DSDPTruth *)
 Apply CG to solve for the step directions.
int DSDPCheckConvergence (DSDP, DSDPTerminationReason *)
 Check for convergence and monitor solution.
int DSDPComputeANorm2 (DSDP, DSDPVec)
 Compute norm of A and C.
int DSDPComputeDataNorms (DSDP)
 Compute norms of A,C, and b.
int DSDPComputeDualityGap (DSDP, double, double *)
 Compute the current duality gap.
int DSDPComputeDualStepDirections (DSDP)
 Compute the step direction by computing a linear system and solving it.
int DSDPComputeDY (DSDP, double, DSDPVec, double *)
 Compute the step direction.
int DSDPComputeG (DSDP, DSDPVec, DSDPVec, DSDPVec)
 Compute the gradient of the barrier for each cone.
int DSDPComputeHessian (DSDP, DSDPSchurMat, DSDPVec, DSDPVec)
 Compute the Schur complement, or Gram, matrix for each cone.
int DSDPComputeLogSDeterminant (DSDP, double *)
 Compute the logarithmic barrier function for the dual varialbe S.
int DSDPComputeMaxStepLength (DSDP, DSDPVec, DSDPDualFactorMatrix, double *)
 Compute the maximum step length for the given step direction.
int DSDPComputeNewY (DSDP, double, DSDPVec)
 Update the Y variables.
int DSDPComputeObjective (DSDP, DSDPVec, double *)
 Compute the objective function (DD).
int DSDPComputePDY (DSDP, double, DSDPVec, double *)
 Compute the step direction.
int DSDPComputePDY1 (DSDP, double, DSDPVec)
 Compute an affine step direction dy1.
int DSDPComputePNorm (DSDP, double, DSDPVec, double *)
 Compute proximity to a point on the central path.
int DSDPComputePotential (DSDP, DSDPVec, double, double *)
 Compute the potential of the given point.
int DSDPComputePotential2 (DSDP, DSDPVec, double, double, double *)
 Compute the objective function plus the barrier function.
int DSDPComputePY (DSDP, double, DSDPVec)
 Compute PY = Y - beta DY for use in computing X.
int DSDPComputeRHS (DSDP, double, DSDPVec)
 Compute the right-hand side of the linear system that determines the step direction.
int DSDPComputeSS (DSDP, DSDPVec, DSDPDualFactorMatrix, DSDPTruth *)
 Compute the dual variables S in each cone.
int DSDPComputeXVariables (DSDP, double, DSDPVec, DSDPVec, DSDPVec, double *)
 Compute the X variables in each cone.
int DSDPCreateLUBoundsCone (DSDP, YBoundCone *)
 Create bounds cone.
int DSDPDefaultConvergence (DSDP, void *)
 Check for Convergence.
int DSDPDestroyCones (DSDP)
 Each cone shoudl free its data structures.
int DSDPGetConicDimension (DSDP, double *)
 Get the total dimension of the cones.
int DSDPGetConvergenceMonitor (DSDP, ConvergenceMonitor **)
 Get the structure containing convergence parameters.
int DSDPGetMaxYElement (DSDP, double *)
 Copy the the infinity norm of the variables y.
int DSDPGetRR (DSDP, double *)
 Get variable r.
int DSDPHessianMultiplyAdd (DSDP, DSDPVec, DSDPVec)
 Add the product of Schur matrix with v.
int DSDPInitializeVariables (DSDP)
 Initialize variables and factor S.
int DSDPInvertS (DSDP)
 Invert the S variables in each cone.
int DSDPMonitorCones (DSDP, int)
 This routine is called once per iteration.
int DSDPObjectiveGH (DSDP, DSDPSchurMat, DSDPVec)
 Compute gradient of dual objective.
int DSDPPassXVectors (DSDP, double, DSDPVec, DSDPVec)
 Pass the information needed to compute the variables X in each cone but do not compute X.
int DSDPPrintStats (DSDP, void *)
 Print statistics about the current solution to standard output.
int DSDPSaveYForX (DSDP, double, double)
 Save the current solution for later computation of X.
int DSDPScaleData (DSDP)
 Scale the matrix C.
int DSDPSchurSparsity (DSDP, int, int[], int)
 Each cone should print its state.
int DSDPSetCone (DSDP, DSDPCone)
 Pass a cone to the DSDP solver.
int DSDPSetDefaultMonitors (DSDP)
 Set convergence monitor.
int DSDPSetDefaultParameters (DSDP)
 Set default parameters.
int DSDPSetDefaultStatistics (DSDP)
 Set default statistics.
int DSDPSetRR (DSDP, double)
 Set variable r.
int DSDPSetUpCones (DSDP)
 Each cone should factor data or allocate internal data structures.
int DSDPSetUpCones2 (DSDP, DSDPVec, DSDPSchurMat)
 Each cone should allocate its data structures .
int DSDPSetY (DSDP, double, double, DSDPVec)
 Update the solver with these y variables.
int DSDPSolveDynamicRho (DSDP)
 Apply dual-scaling algorithm.
int DSDPTakeDown (DSDP)
 Destroy internal data structures.
int DSDPViewCones (DSDP)
 Each cone should print its state.

Typedef Documentation

typedef struct RDCone * RRCone

Cone with nonnegativity on variable r.

Definition at line 24 of file dsdp.h.

struct LUBounds_C * YBoundCone

Cone with bounds on variables y.

Definition at line 18 of file dsdp.h.

Function Documentation

int BoundYConeGetBounds ( LUBounds  lucone,
double *  lb,
double *  ub 
)

Get bounds on the variables.

Parameters:
lucone cone of bounds.
lb lower bound on variables.
ub upper bound

Definition at line 532 of file allbounds.c.

Referenced by DSDPGetYBounds().

int BoundYConeSetBounds ( LUBounds  lucone,
double  lb,
double  ub 
)

Set bounds on the variables.

Parameters:
lucone cone of bounds.
lb lower bound on variables.
ub upper bound

Definition at line 512 of file allbounds.c.

Referenced by DSDPCreateLUBoundsCone(), and DSDPSetYBounds().

int DSDPCGSolve ( DSDP  dsdp,
DSDPSchurMat  MM,
DSDPVec  RHS,
DSDPVec  X,
double  cgtol,
DSDPTruth *  success 
)

Apply CG to solve for the step directions.

Parameters:
dsdp the solver
MM matrix
RHS right-hand side
X solution
cgtol accuracy
success output whether a solution of suitable accuracy was found

Definition at line 239 of file dsdpcg.c.

Referenced by DSDPComputeDualStepDirections(), and DSDPSolveDynamicRho().

int DSDPCheckConvergence ( DSDP  dsdp,
DSDPTerminationReason *  reason 
)

Check for convergence and monitor solution.

Parameters:
dsdp solver
reason termination reason

Definition at line 384 of file dsdpsetup.c.

Referenced by DSDPSolveDynamicRho().

int DSDPComputeANorm2 ( DSDP  dsdp,
DSDPVec  Anorm2 
)

Compute norm of A and C.

Parameters:
dsdp the solver
Anorm2 norm of data corresponding to each variable y.

Definition at line 246 of file dsdpcops.c.

Referenced by DSDPComputeDataNorms().

int DSDPComputeDataNorms ( DSDP  dsdp  ) 

Compute norms of A,C, and b.

Parameters:
dsdp the solver

Definition at line 283 of file dsdpsetup.c.

Referenced by DSDPGetDataNorms(), and DSDPSetup().

int DSDPComputeDualityGap ( DSDP  dsdp,
double  mu,
double *  gap 
)

Compute the current duality gap.

Parameters:
dsdp the solver
mu barrier parameter
gap the duality gap
See also:
DSDPGetDualityGap()

DSDPGetPPObjective()

Definition at line 230 of file dualimpl.c.

Referenced by DSDPSaveYForX().

int DSDPComputeDualStepDirections ( DSDP  dsdp  ) 

Compute the step direction by computing a linear system and solving it.

Parameters:
dsdp the solver
DSDP first attempts unpreconditioned CG to the matrix. Once the number of iterations becomes too large, it swithes a CG preconditioned by the Cholesky factorization. Usually only one iteration of the preconditioned CG is necessary, but solutions with large norms and very precise solutions may require additional iterations.

Definition at line 370 of file dualalg.c.

Referenced by DSDPSolveDynamicRho().

int DSDPComputeDY ( DSDP  dsdp,
double  mu,
DSDPVec  DY,
double *  pnorm 
)

Compute the step direction.

Parameters:
dsdp the solver
mu barrier parameter
DY Step direction
pnorm distance to the target
Assuming the affine direction and centering direction have alread been computed, combine them with the appropriate barrier parameter.

See also:
DSDPComputeRHS()

Definition at line 45 of file dualimpl.c.

Referenced by DSDPComputeDualityGap(), DSDPResetY0(), DSDPSaveYForX(), and DSDPSolveDynamicRho().

int DSDPComputeG ( DSDP  dsdp,
DSDPVec  vt,
DSDPVec  vrhs1,
DSDPVec  vrhs2 
)

Compute the gradient of the barrier for each cone.

Parameters:
dsdp the solver
vt scaling for each element in the next two vectors
vrhs1 scaled gradient of the objective function
vrhs2 scaled gradient of the barrier function

Definition at line 215 of file dsdpcops.c.

Referenced by DSDPComputeDualStepDirections(), and DSDPSolveDynamicRho().

int DSDPComputeHessian ( DSDP  dsdp,
DSDPSchurMat  M,
DSDPVec  vrhs1,
DSDPVec  vrhs2 
)

Compute the Schur complement, or Gram, matrix for each cone.

Parameters:
dsdp the solver
M matrix
vrhs1 gradient of objective (b)
vrhs2 gradient of barrier

Definition at line 142 of file dsdpcops.c.

Referenced by DSDPComputeDualStepDirections().

int DSDPComputeLogSDeterminant ( DSDP  dsdp,
double *  logdet 
)

Compute the logarithmic barrier function for the dual varialbe S.

Parameters:
dsdp the solver
logdet evaluated barrier function
See also:
DSDPComputeSS()

Definition at line 495 of file dsdpcops.c.

Referenced by DSDPInitializeVariables(), DSDPResetY0(), DSDPYStepLineSearch(), and DSDPYStepLineSearch2().

int DSDPComputeMaxStepLength ( DSDP  dsdp,
DSDPVec  DY,
DSDPDualFactorMatrix  flag,
double *  maxsteplength 
)

Compute the maximum step length for the given step direction.

Parameters:
dsdp the solver
DY step direction
flag primal or dual structure
maxsteplength the minumum of maximums on each cone.
See also:
DSDPComputeSS()

Definition at line 336 of file dsdpcops.c.

Referenced by DSDPChooseBarrierParameter(), DSDPYStepLineSearch(), and DSDPYStepLineSearch2().

int DSDPComputeNewY ( DSDP  dsdp,
double  beta,
DSDPVec  Y 
)

Update the Y variables.

Parameters:
dsdp the solver
beta step length
Y the new solution
Add a multiple of the step direction to the current solution.

Definition at line 125 of file dualimpl.c.

Referenced by DSDPYStepLineSearch(), and DSDPYStepLineSearch2().

int DSDPComputeObjective ( DSDP  dsdp,
DSDPVec  Y,
double *  ddobj 
)

Compute the objective function (DD).

Parameters:
dsdp is the solver
Y Current variables
ddobj objective value
See also:
DSDPComputeNewY()

DSDPGetDDObjective()

Definition at line 21 of file dualimpl.c.

Referenced by DSDPComputePotential(), DSDPComputePotential2(), DSDPInitializeVariables(), and DSDPSetY().

int DSDPComputePDY ( DSDP  dsdp,
double  mu,
DSDPVec  DY,
double *  pnorm 
)

Compute the step direction.

Parameters:
dsdp the solver
mu barrier parameter
DY Step direction
pnorm distance to the target
Assuming the affine direction and centering direction have alread been computed, combine them with the appropriate barrier parameter.

See also:
DSDPComputeRHS()

DSDPComputeDY()

Definition at line 77 of file dualimpl.c.

Referenced by DSDPChooseBarrierParameter(), and DSDPSolveDynamicRho().

int DSDPComputePDY1 ( DSDP  dsdp,
double  mur,
DSDPVec  DY1 
)

Compute an affine step direction dy1.

Parameters:
dsdp the solver
mur reciprocal of barrier parameter
DY1 Step direction
Assuming the affine direction has alread been computed, scale it.
See also:
DSDPComputeDY()

Definition at line 105 of file dualimpl.c.

Referenced by DSDPChooseBarrierParameter().

int DSDPComputePNorm ( DSDP  dsdp,
double  mu,
DSDPVec  DY,
double *  pnorm 
)

Compute proximity to a point on the central path.

Parameters:
dsdp the solver
mu barrier parameter
DY Newton step direction
pnorm the norm
See also:
DSDPComputeDY()

Definition at line 200 of file dualimpl.c.

Referenced by DSDPComputeDY(), and DSDPComputePDY().

int DSDPComputePotential ( DSDP  dsdp,
DSDPVec  y,
double  logdet,
double *  potential 
)

Compute the potential of the given point.

Parameters:
dsdp the solver
y variables
logdet logarithmic barrier function of the given point
potential return the potential of the given point.
See also:
DSDPSetPotentialParameter()

Definition at line 261 of file dualimpl.c.

Referenced by DSDPInitializeVariables(), DSDPSetY(), and DSDPYStepLineSearch().

int DSDPComputePotential2 ( DSDP  dsdp,
DSDPVec  y,
double  mu,
double  logdet,
double *  potential 
)

Compute the objective function plus the barrier function.

Parameters:
dsdp the solver
y variables
mu barrier function
logdet logarithmic barrier function of the given point
potential return the potential of the given point.\
See also:
DSDPGetBarrierParameter()

Definition at line 287 of file dualimpl.c.

Referenced by DSDPYStepLineSearch2().

int DSDPComputePY ( DSDP  dsdp,
double  beta,
DSDPVec  PY 
)

Compute PY = Y - beta DY for use in computing X.

Parameters:
dsdp the solver
beta step length
PY the new value
See also:
DSDPComputeNewY()

Definition at line 150 of file dualimpl.c.

Referenced by DSDPChooseBarrierParameter(), and DSDPSolveDynamicRho().

int DSDPComputeRHS ( DSDP  dsdp,
double  mu,
DSDPVec  RHS 
)

Compute the right-hand side of the linear system that determines the step direction.

Parameters:
dsdp the solver
mu barrier parameter
RHS right-hand side direction
Assuming that the gradient of the objective and the gradient of the barrier have already been computed, combine them with the appropriate barrier parameter.

This vector is basically $ b - mu * A(S^{-1}) $

See also:
DSDPComputeDY()

Definition at line 177 of file dualimpl.c.

Referenced by DSDPComputeDY(), DSDPComputePDY(), DSDPComputePNorm(), and DSDPSaveYForX().

int DSDPComputeSS ( DSDP  dsdp,
DSDPVec  Y,
DSDPDualFactorMatrix  flag,
DSDPTruth *  ispsdefinite 
)

Compute the dual variables S in each cone.

Parameters:
dsdp the solver
Y variables
flag primal or dual structure
ispsdefinite DSDP_TRUE if a member of the cone, DSDP_FALSE otherwise.

Definition at line 272 of file dsdpcops.c.

Referenced by DSDPChooseBarrierParameter(), DSDPComputeAndFactorS(), DSDPInitializeVariables(), DSDPResetY0(), DSDPSolveDynamicRho(), DSDPYStepLineSearch(), and DSDPYStepLineSearch2().

int DSDPComputeXVariables ( DSDP  dsdp,
double  xmakermu,
DSDPVec  xmakery,
DSDPVec  xmakerdy,
DSDPVec  AX,
double *  tracexs 
)

Compute the X variables in each cone.

Parameters:
dsdp the solver
xmakermu barrier parameter
xmakery input y variables
xmakerdy input step direction
AX output product of X and the data
tracexs ouput inner product of X and S.

Definition at line 654 of file dsdpcops.c.

Referenced by DSDPComputeX().

int DSDPCreateLUBoundsCone ( DSDP  dsdp,
LUBounds *  dspcone 
)

Create bounds cone.

Parameters:
dsdp the solver
dspcone cone of bounds.

Definition at line 566 of file allbounds.c.

Referenced by DSDPCreate().

int DSDPDestroyCones ( DSDP  dsdp  ) 

Each cone shoudl free its data structures.

Parameters:
dsdp the solver

Definition at line 107 of file dsdpcops.c.

Referenced by DSDPTakeDown().

int DSDPGetConicDimension ( DSDP  dsdp,
double *  n 
)

Get the total dimension of the cones.

Parameters:
dsdp the solver
n dimension

Definition at line 401 of file dsdpcops.c.

Referenced by DSDPCheckConvergence(), DSDPGetDimension(), DSDPSetup(), and DSDPTakeDown().

int DSDPGetConvergenceMonitor ( DSDP  dsdp,
ConvergenceMonitor **  ctx 
)

Get the structure containing convergence parameters.

Parameters:
dsdp the solver
*ctx will point to the structure.
Note:
This structure part of the DSDP structure.

Definition at line 268 of file dsdpsetup.c.

Referenced by DSDPGetDualBound(), DSDPGetGapHistory(), DSDPGetGapTolerance(), DSDPGetPNormTolerance(), DSDPGetRHistory(), DSDPGetStepTolerance(), DSDPSetDualBound(), DSDPSetGapTolerance(), DSDPSetPNormTolerance(), and DSDPSetStepTolerance().

int DSDPGetRR ( DSDP  dsdp,
double *  res 
)

Get variable r.

Parameters:
dsdp solver
*res set variable r

Definition at line 361 of file dualimpl.c.

Referenced by DSDPGetR(), DSDPInitializeVariables(), DSDPResetY0(), DSDPSaveYForX(), and DSDPSolveDynamicRho().

int DSDPHessianMultiplyAdd ( DSDP  dsdp,
DSDPVec  v,
DSDPVec  vv 
)

Add the product of Schur matrix with v.

Parameters:
dsdp the solver
v input vector.
vv product gradient of barrier

Definition at line 188 of file dsdpcops.c.

int DSDPInitializeVariables ( DSDP  dsdp  ) 

Initialize variables and factor S.

Parameters:
dsdp the solver

Definition at line 475 of file dualalg.c.

Referenced by DSDPSolve().

int DSDPInvertS ( DSDP  dsdp  ) 

Invert the S variables in each cone.

Parameters:
dsdp the solver
See also:
DSDPComputeSS()

Definition at line 307 of file dsdpcops.c.

Referenced by DSDPComputeDualStepDirections(), and DSDPSolveDynamicRho().

int DSDPMonitorCones ( DSDP  dsdp,
int  tag 
)

This routine is called once per iteration.

Parameters:
dsdp the solver
tag allow for multiple monitors
The cone can print statistics, visualize data, terminate solver, or whatever it wants.

Definition at line 450 of file dsdpcops.c.

Referenced by DSDPCheckConvergence().

int DSDPObjectiveGH ( DSDP  dsdp,
DSDPSchurMat  M,
DSDPVec  vrhs1 
)

Compute gradient of dual objective.

Parameters:
dsdp solver
M Schur matrix.
vrhs1 gradient vector

Definition at line 381 of file dualimpl.c.

Referenced by DSDPComputeG(), and DSDPComputeHessian().

int DSDPPassXVectors ( DSDP  dsdp,
double  mu,
DSDPVec  Y,
DSDPVec  DY 
)

Pass the information needed to compute the variables X in each cone but do not compute X.

Parameters:
dsdp the solver
mu barrier parameter
Y input y variables
DY input step direction
See also:
DSDPComputeXVariables()

Definition at line 378 of file dsdpcops.c.

Referenced by DSDPSaveYForX().

int DSDPSaveYForX ( DSDP  dsdp,
double  mu,
double  pstep 
)

Save the current solution for later computation of X.

Parameters:
dsdp the solver
mu barrier function
pstep primal step length, hopefully equals 1

Definition at line 149 of file dsdpx.c.

Referenced by DSDPChooseBarrierParameter(), DSDPInitializeVariables(), and DSDPSolveDynamicRho().

int DSDPScaleData ( DSDP  dsdp  ) 

Scale the matrix C.

Parameters:
dsdp the solver

Definition at line 311 of file dsdpsetup.c.

Referenced by DSDPSetup().

int DSDPSchurSparsity ( DSDP  dsdp,
int  row,
int  rnnz[],
int  m 
)

Each cone should print its state.

Parameters:
dsdp the solver
row corresponding to the variable y.
rnnz nonzeros indicate a nonzero in the Shur matrix at that column.
m size of Schur matrix and the arrow.

Definition at line 474 of file dsdpcops.c.

Referenced by DSDPSparsityInSchurMat().

int DSDPSetCone ( DSDP  dsdp,
DSDPCone  tcone 
)

Pass a cone to the DSDP solver.

Parameters:
dsdp the solver
tcone a cone object.

Definition at line 522 of file dsdpcops.c.

Referenced by DSDPAddCone().

int DSDPSetDefaultMonitors ( DSDP  dsdp  ) 

Set convergence monitor.

Parameters:
dsdp the solver

Definition at line 165 of file dsdpsetup.c.

Referenced by DSDPCreate().

int DSDPSetDefaultParameters ( DSDP  dsdp  ) 

Set default parameters.

Parameters:
dsdp the solver

Definition at line 122 of file dsdpsetup.c.

Referenced by DSDPCreate().

int DSDPSetDefaultStatistics ( DSDP  dsdp  ) 

Set default statistics.

Parameters:
dsdp the solver

Definition at line 84 of file dsdpsetup.c.

Referenced by DSDPCreate().

int DSDPSetRR ( DSDP  dsdp,
double  res 
)

Set variable r.

Parameters:
dsdp solver
res variable r

Definition at line 345 of file dualimpl.c.

Referenced by DSDPInitializeVariables(), DSDPResetY0(), and DSDPSetR0().

int DSDPSetUpCones ( DSDP  dsdp  ) 

Each cone should factor data or allocate internal data structures.

Parameters:
dsdp the solver

Definition at line 58 of file dsdpcops.c.

Referenced by DSDPSetup().

int DSDPSetUpCones2 ( DSDP  dsdp,
DSDPVec  yy0,
DSDPSchurMat  M 
)

Each cone should allocate its data structures .

Parameters:
dsdp the solver
yy0 variable vector
M Shur Matrix

Definition at line 84 of file dsdpcops.c.

Referenced by DSDPSetup().

int DSDPSetY ( DSDP  dsdp,
double  beta,
double  logdet,
DSDPVec  ynew 
)

Update the solver with these y variables.

Parameters:
dsdp the solver
beta most recent step length
logdet logarithmic barrier function of the given point
ynew current solution.

Definition at line 309 of file dualimpl.c.

Referenced by DSDPInitializeVariables(), DSDPResetY0(), DSDPYStepLineSearch(), and DSDPYStepLineSearch2().

int DSDPSolveDynamicRho ( DSDP  dsdp  ) 

Apply dual-scaling algorithm.

Parameters:
dsdp the solver

Definition at line 121 of file dualalg.c.

Referenced by DSDPSolve().

int DSDPTakeDown ( DSDP  dsdp  ) 

Destroy internal data structures.

Parameters:
dsdp solver

Definition at line 428 of file dsdpsetup.c.

Referenced by DSDPDestroy().

int DSDPViewCones ( DSDP  dsdp  ) 

Each cone should print its state.

Parameters:
dsdp the solver

Definition at line 424 of file dsdpcops.c.

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