DSDP
Data Structures | Typedefs | Functions
dsdp.h File Reference

Internal data structure for the DSDP solver. More...

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 DSDPDestroyCones (DSDP)
 Each cone shoudl free its data structures.
 
int DSDPGetConicDimension (DSDP, double *)
 Get the total dimension of the cones.
 
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 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.
 

Detailed Description

Internal data structure for the DSDP solver.

Definition in file dsdp.h.

Typedef Documentation

◆ RRCone

typedef struct RDCone * RRCone

Cone with nonnegativity on variable r.

Definition at line 24 of file dsdp.h.

◆ YBoundCone

struct LUBounds_C * YBoundCone

Cone with bounds on variables y.

Definition at line 18 of file dsdp.h.

Function Documentation

◆ BoundYConeGetBounds()

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

Get bounds on the variables.

Parameters
luconecone of bounds.
lblower bound on variables.
ubupper bound

Definition at line 532 of file allbounds.c.

◆ BoundYConeSetBounds()

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

Set bounds on the variables.

Parameters
luconecone of bounds.
lblower bound on variables.
ubupper bound

Definition at line 512 of file allbounds.c.

Referenced by DSDPCreateLUBoundsCone().

◆ DSDPCGSolve()

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

Apply CG to solve for the step directions.

Parameters
dsdpthe solver
MMmatrix
RHSright-hand side
Xsolution
cgtolaccuracy
successoutput whether a solution of suitable accuracy was found

Definition at line 239 of file dsdpcg.c.

Referenced by DSDPComputeDualStepDirections(), and DSDPSolveDynamicRho().

◆ DSDPCheckConvergence()

int DSDPCheckConvergence ( DSDP  dsdp,
DSDPTerminationReason reason 
)

Check for convergence and monitor solution.

Parameters
dsdpsolver
reasontermination reason

Definition at line 384 of file dsdpsetup.c.

Referenced by DSDPSolveDynamicRho().

◆ DSDPComputeANorm2()

int DSDPComputeANorm2 ( DSDP  dsdp,
DSDPVec  Anorm2 
)

Compute norm of A and C.

Parameters
dsdpthe solver
Anorm2norm of data corresponding to each variable y.

Definition at line 246 of file dsdpcops.c.

Referenced by DSDPComputeDataNorms().

◆ DSDPComputeDataNorms()

int DSDPComputeDataNorms ( DSDP  dsdp)

Compute norms of A,C, and b.

Parameters
dsdpthe solver

Definition at line 283 of file dsdpsetup.c.

◆ DSDPComputeDualityGap()

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

Compute the current duality gap.

Parameters
dsdpthe solver
mubarrier parameter
gapthe duality gap
See also
DSDPGetDualityGap()
DSDPGetPPObjective()

Definition at line 230 of file dualimpl.c.

Referenced by DSDPSaveYForX().

◆ DSDPComputeDualStepDirections()

int DSDPComputeDualStepDirections ( DSDP  dsdp)

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

Parameters
dsdpthe 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().

◆ DSDPComputeDY()

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

Compute the step direction.

Parameters
dsdpthe solver
mubarrier parameter
DYStep direction
pnormdistance 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().

◆ DSDPComputeG()

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

Compute the gradient of the barrier for each cone.

Parameters
dsdpthe solver
vtscaling for each element in the next two vectors
vrhs1scaled gradient of the objective function
vrhs2scaled gradient of the barrier function

Definition at line 215 of file dsdpcops.c.

Referenced by DSDPComputeDualStepDirections(), and DSDPSolveDynamicRho().

◆ DSDPComputeHessian()

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

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

Parameters
dsdpthe solver
Mmatrix
vrhs1gradient of objective (b)
vrhs2gradient of barrier

Definition at line 142 of file dsdpcops.c.

Referenced by DSDPComputeDualStepDirections().

◆ DSDPComputeLogSDeterminant()

int DSDPComputeLogSDeterminant ( DSDP  dsdp,
double *  logdet 
)

Compute the logarithmic barrier function for the dual varialbe S.

Parameters
dsdpthe solver
logdetevaluated barrier function
See also
DSDPComputeSS()

Definition at line 495 of file dsdpcops.c.

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

◆ DSDPComputeMaxStepLength()

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

Compute the maximum step length for the given step direction.

Parameters
dsdpthe solver
DYstep direction
flagprimal or dual structure
maxsteplengththe minumum of maximums on each cone.
See also
DSDPComputeSS()

Definition at line 336 of file dsdpcops.c.

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

◆ DSDPComputeNewY()

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

Update the Y variables.

Parameters
dsdpthe solver
betastep length
Ythe 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().

◆ DSDPComputeObjective()

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

Compute the objective function (DD).

Parameters
dsdpis the solver
YCurrent variables
ddobjobjective value
See also
DSDPComputeNewY()
DSDPGetDDObjective()

Definition at line 21 of file dualimpl.c.

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

◆ DSDPComputePDY()

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

Compute the step direction.

Parameters
dsdpthe solver
mubarrier parameter
DYStep direction
pnormdistance 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().

◆ DSDPComputePDY1()

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

Compute an affine step direction dy1.

Parameters
dsdpthe solver
murreciprocal of barrier parameter
DY1Step 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().

◆ DSDPComputePNorm()

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

Compute proximity to a point on the central path.

Parameters
dsdpthe solver
mubarrier parameter
DYNewton step direction
pnormthe norm
See also
DSDPComputeDY()

Definition at line 200 of file dualimpl.c.

Referenced by DSDPComputeDY(), and DSDPComputePDY().

◆ DSDPComputePotential()

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

Compute the potential of the given point.

Parameters
dsdpthe solver
yvariables
logdetlogarithmic barrier function of the given point
potentialreturn the potential of the given point.
See also
DSDPSetPotentialParameter()

Definition at line 261 of file dualimpl.c.

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

◆ DSDPComputePotential2()

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

Compute the objective function plus the barrier function.

Parameters
dsdpthe solver
yvariables
mubarrier function
logdetlogarithmic barrier function of the given point
potentialreturn the potential of the given point.\
See also
DSDPGetBarrierParameter()

Definition at line 287 of file dualimpl.c.

Referenced by DSDPYStepLineSearch2().

◆ DSDPComputePY()

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

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

Parameters
dsdpthe solver
betastep length
PYthe new value
See also
DSDPComputeNewY()

Definition at line 150 of file dualimpl.c.

Referenced by DSDPChooseBarrierParameter(), and DSDPSolveDynamicRho().

◆ DSDPComputeRHS()

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

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

Parameters
dsdpthe solver
mubarrier parameter
RHSright-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().

◆ DSDPComputeSS()

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

Compute the dual variables S in each cone.

Parameters
dsdpthe solver
Yvariables
flagprimal or dual structure
ispsdefiniteDSDP_TRUE if a member of the cone, DSDP_FALSE otherwise.

Definition at line 272 of file dsdpcops.c.

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

◆ DSDPComputeXVariables()

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

Compute the X variables in each cone.

Parameters
dsdpthe solver
xmakermubarrier parameter
xmakeryinput y variables
xmakerdyinput step direction
AXoutput product of X and the data
tracexsouput inner product of X and S.

Definition at line 654 of file dsdpcops.c.

◆ DSDPCreateLUBoundsCone()

int DSDPCreateLUBoundsCone ( DSDP  dsdp,
LUBounds *  dspcone 
)

Create bounds cone.

Parameters
dsdpthe solver
dspconecone of bounds.

Definition at line 566 of file allbounds.c.

◆ DSDPDestroyCones()

int DSDPDestroyCones ( DSDP  dsdp)

Each cone shoudl free its data structures.

Parameters
dsdpthe solver

Definition at line 107 of file dsdpcops.c.

Referenced by DSDPTakeDown().

◆ DSDPGetConicDimension()

int DSDPGetConicDimension ( DSDP  dsdp,
double *  n 
)

Get the total dimension of the cones.

Parameters
dsdpthe solver
ndimension

Definition at line 401 of file dsdpcops.c.

Referenced by DSDPCheckConvergence(), and DSDPTakeDown().

◆ DSDPGetRR()

int DSDPGetRR ( DSDP  dsdp,
double *  res 
)

Get variable r.

Parameters
dsdpsolver
*resset variable r

Definition at line 361 of file dualimpl.c.

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

◆ DSDPHessianMultiplyAdd()

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

Add the product of Schur matrix with v.

Parameters
dsdpthe solver
vinput vector.
vvproduct gradient of barrier

Definition at line 188 of file dsdpcops.c.

◆ DSDPInitializeVariables()

int DSDPInitializeVariables ( DSDP  dsdp)

Initialize variables and factor S.

Parameters
dsdpthe solver

Definition at line 475 of file dualalg.c.

◆ DSDPInvertS()

int DSDPInvertS ( DSDP  dsdp)

Invert the S variables in each cone.

Parameters
dsdpthe solver
See also
DSDPComputeSS()

Definition at line 307 of file dsdpcops.c.

Referenced by DSDPComputeDualStepDirections(), and DSDPSolveDynamicRho().

◆ DSDPMonitorCones()

int DSDPMonitorCones ( DSDP  dsdp,
int  tag 
)

This routine is called once per iteration.

Parameters
dsdpthe solver
tagallow 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().

◆ DSDPObjectiveGH()

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

Compute gradient of dual objective.

Parameters
dsdpsolver
MSchur matrix.
vrhs1gradient vector

Definition at line 381 of file dualimpl.c.

Referenced by DSDPComputeG(), and DSDPComputeHessian().

◆ DSDPPassXVectors()

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
dsdpthe solver
mubarrier parameter
Yinput y variables
DYinput step direction
See also
DSDPComputeXVariables()

Definition at line 378 of file dsdpcops.c.

Referenced by DSDPSaveYForX().

◆ DSDPSaveYForX()

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

Save the current solution for later computation of X.

Parameters
dsdpthe solver
mubarrier function
pstepprimal step length, hopefully equals 1

Definition at line 149 of file dsdpx.c.

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

◆ DSDPScaleData()

int DSDPScaleData ( DSDP  dsdp)

Scale the matrix C.

Parameters
dsdpthe solver

Definition at line 311 of file dsdpsetup.c.

◆ DSDPSchurSparsity()

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

Each cone should print its state.

Parameters
dsdpthe solver
rowcorresponding to the variable y.
rnnznonzeros indicate a nonzero in the Shur matrix at that column.
msize of Schur matrix and the arrow.

Definition at line 474 of file dsdpcops.c.

Referenced by DSDPSparsityInSchurMat().

◆ DSDPSetCone()

int DSDPSetCone ( DSDP  dsdp,
DSDPCone  tcone 
)

Pass a cone to the DSDP solver.

Parameters
dsdpthe solver
tconea cone object.

Definition at line 522 of file dsdpcops.c.

Referenced by DSDPAddCone().

◆ DSDPSetDefaultMonitors()

int DSDPSetDefaultMonitors ( DSDP  dsdp)

Set convergence monitor.

Parameters
dsdpthe solver

Definition at line 165 of file dsdpsetup.c.

◆ DSDPSetDefaultParameters()

int DSDPSetDefaultParameters ( DSDP  dsdp)

Set default parameters.

Parameters
dsdpthe solver

Definition at line 122 of file dsdpsetup.c.

◆ DSDPSetDefaultStatistics()

int DSDPSetDefaultStatistics ( DSDP  dsdp)

Set default statistics.

Parameters
dsdpthe solver

Definition at line 84 of file dsdpsetup.c.

◆ DSDPSetRR()

int DSDPSetRR ( DSDP  dsdp,
double  res 
)

Set variable r.

Parameters
dsdpsolver
resvariable r

Definition at line 345 of file dualimpl.c.

Referenced by DSDPInitializeVariables(), and DSDPResetY0().

◆ DSDPSetUpCones()

int DSDPSetUpCones ( DSDP  dsdp)

Each cone should factor data or allocate internal data structures.

Parameters
dsdpthe solver

Definition at line 58 of file dsdpcops.c.

◆ DSDPSetUpCones2()

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

Each cone should allocate its data structures .

Parameters
dsdpthe solver
yy0variable vector
MShur Matrix

Definition at line 84 of file dsdpcops.c.

◆ DSDPSetY()

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

Update the solver with these y variables.

Parameters
dsdpthe solver
betamost recent step length
logdetlogarithmic barrier function of the given point
ynewcurrent solution.

Definition at line 309 of file dualimpl.c.

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

◆ DSDPSolveDynamicRho()

int DSDPSolveDynamicRho ( DSDP  dsdp)

Apply dual-scaling algorithm.

Parameters
dsdpthe solver

Definition at line 121 of file dualalg.c.

◆ DSDPTakeDown()

int DSDPTakeDown ( DSDP  dsdp)

Destroy internal data structures.

Parameters
dsdpsolver

Definition at line 428 of file dsdpsetup.c.

◆ DSDPViewCones()

int DSDPViewCones ( DSDP  dsdp)

Each cone should print its state.

Parameters
dsdpthe solver

Definition at line 424 of file dsdpcops.c.