dsdp.h
Go to the documentation of this file.
#ifndef __DSDP_H
#define __DSDP_H
#include "dsdpbasictypes.h"
#include "dsdpvec.h"
#include "dsdpschurmat.h"
#include "dsdpcone.h"
#include "dsdpconverge.h"
typedef struct LUBounds_C* YBoundCone;
typedef struct RDCone* RRCone;
#define MAX_DSDP_MONITORS 5
#define MAX_XMAKERS 4
typedef struct {
DSDPVec y;
DSDPVec dy;
double mu;
double pstep;
DSDPVec rhs;
} XMaker;
typedef struct { /* This information is needed to compute the step Direction */
DSDPVec y;
double zbar;
double mutarget;
double logdet;
} DSDPState;
typedef struct {
int (*f)(void*);
void * ptr;
}DRoutine;
typedef struct {
int (*monitor)(struct DSDP_C *, void*);
void *monitorctx;
} DMonitor;
typedef struct {
DSDPCone cone;
int coneid;
} DCone;
struct DSDP_C{
DSDPCG *sles;
int slestype;
double schurmu;
DSDPSchurMat M;
double Mshift;
double maxschurshift;
int ncones,maxcones;
DCone* K;
int keyid;
int solvetime,cgtime,ptime,dtime,ctime;
int reuseM;
DSDPTruth goty0;
DSDPTruth setupcalled;
int m; /* number of constraints */
double np; /* Dimension of full variable matrix */
int itnow; /* current iterate */
int maxiter; /* Maximum number of iterates */
double pobj; /* current primal objective value - use duality gap */
double ppobj; /* current primal objetive value - evaluate P */
double dobj,ddobj; /* the current dual objective value */
double pstep,dstep; /* current primal and dual step lengths */
double dualitygap;
double mutarget;
double mu,muold,mu0; /* The current mu */
double rho,potential,logdet,rhon;
double pnorm; /* the current value of ||P|| */
double maxtrustradius;
double cnorm,anorm,bnorm;
double tracex,tracexs;
double rgap;
double pstepold;
DSDPVec y; /* dual variables */
DSDPVec y0; /* initial dual variables */
DSDPVec ytemp; /* temporary dual variables */
DSDPVec dy1; /* search direction 1 affine direction */
DSDPVec dy2; /* search direction 2 centering direction */
DSDPVec dy; /* total search direction = constant*dy1-dy2 */
DSDPVec rhs1; /* objective vector b to determine step direction */
DSDPVec rhs2; /* barrier vector A(S^{-1}) to determine step direction */
DSDPVec rhs; /* right-hand side of linear system */
DSDPVec rhstemp;/* temporary rhs vector */
DSDPVec b; /* dual objective vector */
/* Multiple of identity matrix added to dual */
double r;
int rflag;
DSDPPenalty UsePenalty;
RRCone rcone;
DSDPTruth usefixedrho; /* True if fixed rho used. */
XMaker xmaker[MAX_XMAKERS]; /* step direction used to create X */
DSDPVec xmakerrhs;
YBoundCone ybcone;
double pinfeas; /* Infeasible in P indirectly -- neglect numerical errors */
double perror; /* Infeasible in P computed directly */
DSDPSolutionType pdfeasible;
double dinfeastol; /* Parameter: Classify (D) as feasible */
double pinfeastol; /* Parameter: Classify (P) as feasible */
ConvergenceMonitor conv;
DSDPTerminationReason reason;
DMonitor dmonitor[MAX_DSDP_MONITORS];
int nmonitors;
DRoutine droutine[10];
int ndroutines;
};
typedef struct DSDP_C PD_DSDP;
#define DSDPKEY 5432
#define DSDPValid(a) {if (!(a)||((a)->keyid!=DSDPKEY)){ DSDPSETERR(101,"DSDPERROR: Invalid DSDP object\n");}}
#include "dsdpbasictypes.h"
extern int DSDPCreateLUBoundsCone(DSDP, YBoundCone*);
extern int BoundYConeSetBounds(YBoundCone, double, double);
extern int BoundYConeGetBounds(YBoundCone, double*, double*);
extern int BoundYConeAddX(YBoundCone,double,DSDPVec,DSDPVec,DSDPVec,double*);
extern int BoundYConeAddS(YBoundCone,DSDPVec,DSDPVec);
#ifdef __cplusplus
extern "C" {
#endif
extern int DSDPComputeObjective(DSDP, DSDPVec, double *);
extern int DSDPComputeDY(DSDP, double, DSDPVec, double*);
extern int DSDPComputeNewY(DSDP, double, DSDPVec);
extern int DSDPComputeRHS(DSDP, double, DSDPVec);
extern int DSDPComputePDY1(DSDP,double,DSDPVec);
extern int DSDPComputePDY(DSDP, double, DSDPVec, double*);
extern int DSDPComputePY(DSDP,double,DSDPVec);
extern int DSDPComputeG(DSDP, DSDPVec,DSDPVec,DSDPVec);
extern int DSDPComputePNorm(DSDP, double,DSDPVec,double*);
extern int DSDPComputeDualityGap(DSDP, double, double*);
extern int DSDPSaveYForX(DSDP, double, double);
extern int DSDPSetY(DSDP,double,double,DSDPVec);
extern int DSDPComputePotential(DSDP, DSDPVec, double,double*);
extern int DSDPComputePotential2(DSDP, DSDPVec, double, double, double*);
extern int DSDPSetRR(DSDP,double);
extern int DSDPGetRR(DSDP,double*);
extern int DSDPGetMaxYElement(DSDP,double*);
extern int DSDPSolveDynamicRho(DSDP);
extern int DSDPRefineStepDirection(DSDP,DSDPVec, DSDPVec);
/* Cone operations */
extern int DSDPSetUpCones(DSDP);
extern int DSDPSetUpCones2(DSDP, DSDPVec, DSDPSchurMat);
extern int DSDPSchurSparsity(DSDP, int, int[], int);
extern int DSDPComputeSS(DSDP, DSDPVec, DSDPDualFactorMatrix, DSDPTruth*);
extern int DSDPInvertS(DSDP);
extern int DSDPComputeHessian( DSDP, DSDPSchurMat, DSDPVec, DSDPVec);
extern int DSDPHessianMultiplyAdd( DSDP, DSDPVec, DSDPVec);
extern int DSDPComputeMaxStepLength(DSDP, DSDPVec, DSDPDualFactorMatrix, double*);
extern int DSDPComputeLogSDeterminant(DSDP, double*);
extern int DSDPComputeANorm2(DSDP,DSDPVec);
extern int DSDPViewCones(DSDP);
extern int DSDPMonitorCones(DSDP,int);
extern int DSDPDestroyCones(DSDP);
extern int DSDPPassXVectors(DSDP,double,DSDPVec,DSDPVec);
extern int DSDPComputeXVariables(DSDP,double,DSDPVec,DSDPVec,DSDPVec,double*);
extern int DSDPGetConicDimension(DSDP,double*);
extern int DSDPSchurSparsity(DSDP, int, int[], int);
extern int DSDPCGSolve(DSDP,DSDPSchurMat,DSDPVec,DSDPVec,double,DSDPTruth*);
extern int DSDPComputeDualStepDirection(DSDP, double, DSDPVec);
extern int DSDPComputeDualStepDirections(DSDP);
extern int DSDPSetCone(DSDP,DSDPCone);
extern int DSDPScaleData(DSDP);
extern int DSDPComputeDataNorms(DSDP);
extern int DSDPTakeDown(DSDP);
extern int DSDPSetDefaultStatistics(DSDP);
extern int DSDPSetDefaultParameters(DSDP);
extern int DSDPSetDefaultMonitors(DSDP);
/* DSDP subroutines */
extern int DSDPInitializeVariables(DSDP);
extern int DSDPObjectiveGH( DSDP, DSDPSchurMat, DSDPVec);
extern int DSDPCheckForUnboundedObjective(DSDP, DSDPTruth*);
extern int DSDPCheckConvergence(DSDP,DSDPTerminationReason *);
extern int DSDPMonitor(DSDP);
extern int DSDPPrintStats(DSDP, void*);
extern int DSDPPrintStatsFile(DSDP, void*);
extern int DSDPGetSchurMatrix(DSDP,DSDPSchurMat*);
#ifdef __cplusplus
}
#endif
extern int DSDPAddRCone(DSDP,RRCone*);
extern int RConeSetType(RRCone, DSDPPenalty);
extern int RConeGetRX(RRCone, double*);
extern int DSDPGetConvergenceMonitor(DSDP, ConvergenceMonitor**);
extern int DSDPDefaultConvergence(DSDP,void *);
extern int DSDPSetDefaultSchurMatrixStructure(DSDP);
extern int DSDPFixedVariablesNorm(DSDPSchurMat,DSDPVec);
extern int DSDPComputeFixedYX(DSDPSchurMat,DSDPVec);
extern int DSDPAddBCone(DSDP,DSDPVec,double);
#endif
DSDPComputePotential2
int DSDPComputePotential2(DSDP, DSDPVec, double, double, double *)
Compute the objective function plus the barrier function.
Definition dualimpl.c:287
DSDPComputeSS
int DSDPComputeSS(DSDP, DSDPVec, DSDPDualFactorMatrix, DSDPTruth *)
Compute the dual variables S in each cone.
Definition dsdpcops.c:272
DSDPSetDefaultStatistics
int DSDPSetDefaultStatistics(DSDP)
Set default statistics.
Definition dsdpsetup.c:84
DSDPSetRR
int DSDPSetRR(DSDP, double)
Set variable r.
Definition dualimpl.c:345
DSDPSetUpCones
int DSDPSetUpCones(DSDP)
Each cone should factor data or allocate internal data structures.
Definition dsdpcops.c:58
DSDPSetDefaultMonitors
int DSDPSetDefaultMonitors(DSDP)
Set convergence monitor.
Definition dsdpsetup.c:165
DSDPComputeG
int DSDPComputeG(DSDP, DSDPVec, DSDPVec, DSDPVec)
Compute the gradient of the barrier for each cone.
Definition dsdpcops.c:215
DSDPComputeRHS
int DSDPComputeRHS(DSDP, double, DSDPVec)
Compute the right-hand side of the linear system that determines the step direction.
Definition dualimpl.c:177
DSDPComputeHessian
int DSDPComputeHessian(DSDP, DSDPSchurMat, DSDPVec, DSDPVec)
Compute the Schur complement, or Gram, matrix for each cone.
Definition dsdpcops.c:142
DSDPScaleData
int DSDPScaleData(DSDP)
Scale the matrix C.
Definition dsdpsetup.c:311
DSDPComputeLogSDeterminant
int DSDPComputeLogSDeterminant(DSDP, double *)
Compute the logarithmic barrier function for the dual varialbe S.
Definition dsdpcops.c:495
DSDPObjectiveGH
int DSDPObjectiveGH(DSDP, DSDPSchurMat, DSDPVec)
Compute gradient of dual objective.
Definition dualimpl.c:381
DSDPSchurSparsity
int DSDPSchurSparsity(DSDP, int, int[], int)
Each cone should print its state.
Definition dsdpcops.c:474
DSDPInvertS
int DSDPInvertS(DSDP)
Invert the S variables in each cone.
Definition dsdpcops.c:307
DSDPPassXVectors
int DSDPPassXVectors(DSDP, double, DSDPVec, DSDPVec)
Pass the information needed to compute the variables X in each cone but do not compute X.
Definition dsdpcops.c:378
DSDPCGSolve
int DSDPCGSolve(DSDP, DSDPSchurMat, DSDPVec, DSDPVec, double, DSDPTruth *)
Apply CG to solve for the step directions.
Definition dsdpcg.c:239
DSDPComputeANorm2
int DSDPComputeANorm2(DSDP, DSDPVec)
Compute norm of A and C.
Definition dsdpcops.c:246
DSDPComputeNewY
int DSDPComputeNewY(DSDP, double, DSDPVec)
Update the Y variables.
Definition dualimpl.c:125
DSDPComputeDualityGap
int DSDPComputeDualityGap(DSDP, double, double *)
Compute the current duality gap.
Definition dualimpl.c:230
BoundYConeSetBounds
int BoundYConeSetBounds(YBoundCone, double, double)
Set bounds on the variables.
Definition allbounds.c:512
YBoundCone
struct LUBounds_C * YBoundCone
Cone with bounds on variables y.
Definition dsdp.h:18
DSDPComputeObjective
int DSDPComputeObjective(DSDP, DSDPVec, double *)
Compute the objective function (DD).
Definition dualimpl.c:21
DSDPMonitorCones
int DSDPMonitorCones(DSDP, int)
This routine is called once per iteration.
Definition dsdpcops.c:450
DSDPComputePNorm
int DSDPComputePNorm(DSDP, double, DSDPVec, double *)
Compute proximity to a point on the central path.
Definition dualimpl.c:200
DSDPViewCones
int DSDPViewCones(DSDP)
Each cone should print its state.
Definition dsdpcops.c:424
DSDPComputeXVariables
int DSDPComputeXVariables(DSDP, double, DSDPVec, DSDPVec, DSDPVec, double *)
Compute the X variables in each cone.
Definition dsdpcops.c:654
DSDPComputePDY
int DSDPComputePDY(DSDP, double, DSDPVec, double *)
Compute the step direction.
Definition dualimpl.c:77
DSDPHessianMultiplyAdd
int DSDPHessianMultiplyAdd(DSDP, DSDPVec, DSDPVec)
Add the product of Schur matrix with v.
Definition dsdpcops.c:188
DSDPSolveDynamicRho
int DSDPSolveDynamicRho(DSDP)
Apply dual-scaling algorithm.
Definition dualalg.c:121
DSDPComputeDataNorms
int DSDPComputeDataNorms(DSDP)
Compute norms of A,C, and b.
Definition dsdpsetup.c:283
DSDPSetCone
int DSDPSetCone(DSDP, DSDPCone)
Pass a cone to the DSDP solver.
Definition dsdpcops.c:522
RRCone
struct RDCone * RRCone
Cone with nonnegativity on variable r.
Definition dsdp.h:24
DSDPCheckConvergence
int DSDPCheckConvergence(DSDP, DSDPTerminationReason *)
Check for convergence and monitor solution.
Definition dsdpsetup.c:384
DSDPComputeDY
int DSDPComputeDY(DSDP, double, DSDPVec, double *)
Compute the step direction.
Definition dualimpl.c:45
DSDPComputePDY1
int DSDPComputePDY1(DSDP, double, DSDPVec)
Compute an affine step direction dy1.
Definition dualimpl.c:105
DSDPComputePY
int DSDPComputePY(DSDP, double, DSDPVec)
Compute PY = Y - beta DY for use in computing X.
Definition dualimpl.c:150
DSDPSetDefaultParameters
int DSDPSetDefaultParameters(DSDP)
Set default parameters.
Definition dsdpsetup.c:122
DSDPSaveYForX
int DSDPSaveYForX(DSDP, double, double)
Save the current solution for later computation of X.
Definition dsdpx.c:149
DSDPComputeMaxStepLength
int DSDPComputeMaxStepLength(DSDP, DSDPVec, DSDPDualFactorMatrix, double *)
Compute the maximum step length for the given step direction.
Definition dsdpcops.c:336
DSDPGetConicDimension
int DSDPGetConicDimension(DSDP, double *)
Get the total dimension of the cones.
Definition dsdpcops.c:401
DSDPComputePotential
int DSDPComputePotential(DSDP, DSDPVec, double, double *)
Compute the potential of the given point.
Definition dualimpl.c:261
BoundYConeGetBounds
int BoundYConeGetBounds(YBoundCone, double *, double *)
Get bounds on the variables.
Definition allbounds.c:532
DSDPComputeDualStepDirections
int DSDPComputeDualStepDirections(DSDP)
Compute the step direction by computing a linear system and solving it.
Definition dualalg.c:370
DSDPDestroyCones
int DSDPDestroyCones(DSDP)
Each cone shoudl free its data structures.
Definition dsdpcops.c:107
DSDPInitializeVariables
int DSDPInitializeVariables(DSDP)
Initialize variables and factor S.
Definition dualalg.c:475
DSDPCreateLUBoundsCone
int DSDPCreateLUBoundsCone(DSDP, YBoundCone *)
Create bounds cone.
Definition allbounds.c:566
DSDPSetUpCones2
int DSDPSetUpCones2(DSDP, DSDPVec, DSDPSchurMat)
Each cone should allocate its data structures .
Definition dsdpcops.c:84
DSDPGetRR
int DSDPGetRR(DSDP, double *)
Get variable r.
Definition dualimpl.c:361
DSDPTakeDown
int DSDPTakeDown(DSDP)
Destroy internal data structures.
Definition dsdpsetup.c:428
DSDPSetY
int DSDPSetY(DSDP, double, double, DSDPVec)
Update the solver with these y variables.
Definition dualimpl.c:309
dsdpbasictypes.h
Solver, solution types, termination codes,.
DSDPTerminationReason
DSDPTerminationReason
There are many reasons to terminate the solver.
Definition dsdpbasictypes.h:50
DSDPSolutionType
DSDPSolutionType
Formulations (P) and (D) can be feasible and bounded, feasible and unbounded, or infeasible.
Definition dsdpbasictypes.h:38
DSDPDualFactorMatrix
DSDPDualFactorMatrix
DSDP requires two instances of the data structures S.
Definition dsdpbasictypes.h:25
DSDPTruth
DSDPTruth
Boolean variables.
Definition dsdpbasictypes.h:19
dsdpcone.h
The public interface between the cones and the solver.
DSDPCone
struct DSDPCone_C DSDPCone
This object holds the data of a SDP, LP, or other cone. Its structure is opaque to the DSDP Solver,...
Definition dsdpcone.h:27
dsdpconverge.h
Detect convergence of the solver from the duality gap and step sizes.
dsdpschurmat.h
Methods of a Schur Matrix.
dsdpvec.h
Vector operations used by the solver.
DSDPVec
struct DSDPVec_C DSDPVec
This object hold m+2 variables: a scaling of C, the y variables, and r.
Definition dsdpvec.h:25
DSDPSchurMat_C
Schur complement matrix whose solution is the Newton direction.
Definition dsdpschurmat.h:35
DSDP_C
Internal structures for the DSDP solver.
Definition dsdp.h:65