DSDP
dsdp.h
Go to the documentation of this file.
1 #ifndef __DSDP_H
2 #define __DSDP_H
3 
4 #include "dsdpbasictypes.h"
5 #include "dsdpvec.h"
6 #include "dsdpschurmat.h"
7 #include "dsdpcone.h"
8 #include "dsdpconverge.h"
18 typedef struct LUBounds_C* YBoundCone;
19 
24 typedef struct RDCone* RRCone;
25 
26 
27 #define MAX_DSDP_MONITORS 5
28 #define MAX_XMAKERS 4
29 
30 typedef struct {
31  DSDPVec y;
32  DSDPVec dy;
33  double mu;
34  double pstep;
35  DSDPVec rhs;
36 } XMaker;
37 
38 typedef struct { /* This information is needed to compute the step Direction */
39  DSDPVec y;
40  double zbar;
41  double mutarget;
42  double logdet;
43 } DSDPState;
44 
45 typedef struct {
46  int (*f)(void*);
47  void * ptr;
48 }DRoutine;
49 
50 typedef struct {
51  int (*monitor)(struct DSDP_C *, void*);
52  void *monitorctx;
53 } DMonitor;
54 
55 typedef struct {
56  DSDPCone cone;
57  int coneid;
58 } DCone;
59 
65 struct DSDP_C{
66 
67  DSDPCG *sles;
68  int slestype;
69 
70  double schurmu;
71  DSDPSchurMat M;
72  double Mshift;
73  double maxschurshift;
74 
75  int ncones,maxcones;
76  DCone* K;
77 
78  int keyid;
79 
80  int solvetime,cgtime,ptime,dtime,ctime;
81  int reuseM;
82  DSDPTruth goty0;
83  DSDPTruth setupcalled;
84 
85  int m; /* number of constraints */
86  double np; /* Dimension of full variable matrix */
87 
88  int itnow; /* current iterate */
89  int maxiter; /* Maximum number of iterates */
90  double pobj; /* current primal objective value - use duality gap */
91  double ppobj; /* current primal objetive value - evaluate P */
92  double dobj,ddobj; /* the current dual objective value */
93  double pstep,dstep; /* current primal and dual step lengths */
94  double dualitygap;
95  double mutarget;
96  double mu,muold,mu0; /* The current mu */
97  double rho,potential,logdet,rhon;
98  double pnorm; /* the current value of ||P|| */
99  double maxtrustradius;
100  double cnorm,anorm,bnorm;
101  double tracex,tracexs;
102  double rgap;
103  double pstepold;
104 
105  DSDPVec y; /* dual variables */
106  DSDPVec y0; /* initial dual variables */
107  DSDPVec ytemp; /* temporary dual variables */
108  DSDPVec dy1; /* search direction 1 affine direction */
109  DSDPVec dy2; /* search direction 2 centering direction */
110  DSDPVec dy; /* total search direction = constant*dy1-dy2 */
111  DSDPVec rhs1; /* objective vector b to determine step direction */
112  DSDPVec rhs2; /* barrier vector A(S^{-1}) to determine step direction */
113  DSDPVec rhs; /* right-hand side of linear system */
114  DSDPVec rhstemp;/* temporary rhs vector */
115  DSDPVec b; /* dual objective vector */
116 
117  /* Multiple of identity matrix added to dual */
118  double r;
119  int rflag;
120  DSDPPenalty UsePenalty;
121  RRCone rcone;
122 
123  DSDPTruth usefixedrho; /* True if fixed rho used. */
124 
125  XMaker xmaker[MAX_XMAKERS]; /* step direction used to create X */
126  DSDPVec xmakerrhs;
127 
128  YBoundCone ybcone;
129  double pinfeas; /* Infeasible in P indirectly -- neglect numerical errors */
130  double perror; /* Infeasible in P computed directly */
131 
132  DSDPSolutionType pdfeasible;
133  double dinfeastol; /* Parameter: Classify (D) as feasible */
134  double pinfeastol; /* Parameter: Classify (P) as feasible */
135 
136  ConvergenceMonitor conv;
137  DSDPTerminationReason reason;
138 
139  DMonitor dmonitor[MAX_DSDP_MONITORS];
140  int nmonitors;
141 
142  DRoutine droutine[10];
143  int ndroutines;
144 };
145 
146 typedef struct DSDP_C PD_DSDP;
147 
148 #define DSDPKEY 5432
149 
150 #define DSDPValid(a) {if (!(a)||((a)->keyid!=DSDPKEY)){ DSDPSETERR(101,"DSDPERROR: Invalid DSDP object\n");}}
151 
152 #include "dsdpbasictypes.h"
153 
154 
156 extern int BoundYConeSetBounds(YBoundCone, double, double);
157 extern int BoundYConeGetBounds(YBoundCone, double*, double*);
158 extern int BoundYConeAddX(YBoundCone,double,DSDPVec,DSDPVec,DSDPVec,double*);
159 extern int BoundYConeAddS(YBoundCone,DSDPVec,DSDPVec);
160 
161 #ifdef __cplusplus
162 extern "C" {
163 #endif
164 
165 extern int DSDPComputeObjective(DSDP, DSDPVec, double *);
166 extern int DSDPComputeDY(DSDP, double, DSDPVec, double*);
167 extern int DSDPComputeNewY(DSDP, double, DSDPVec);
168 extern int DSDPComputeRHS(DSDP, double, DSDPVec);
169 extern int DSDPComputePDY1(DSDP,double,DSDPVec);
170 extern int DSDPComputePDY(DSDP, double, DSDPVec, double*);
171 extern int DSDPComputePY(DSDP,double,DSDPVec);
173 extern int DSDPComputePNorm(DSDP, double,DSDPVec,double*);
174 extern int DSDPComputeDualityGap(DSDP, double, double*);
175 extern int DSDPSaveYForX(DSDP, double, double);
176 extern int DSDPSetY(DSDP,double,double,DSDPVec);
177 extern int DSDPComputePotential(DSDP, DSDPVec, double,double*);
178 extern int DSDPComputePotential2(DSDP, DSDPVec, double, double, double*);
179 extern int DSDPSetRR(DSDP,double);
180 extern int DSDPGetRR(DSDP,double*);
181 extern int DSDPGetMaxYElement(DSDP,double*);
182 
183 extern int DSDPSolveDynamicRho(DSDP);
184 extern int DSDPRefineStepDirection(DSDP,DSDPVec, DSDPVec);
185 
186 /* Cone operations */
187 extern int DSDPSetUpCones(DSDP);
189 extern int DSDPSchurSparsity(DSDP, int, int[], int);
191 extern int DSDPInvertS(DSDP);
195 extern int DSDPComputeLogSDeterminant(DSDP, double*);
196 extern int DSDPComputeANorm2(DSDP,DSDPVec);
197 extern int DSDPViewCones(DSDP);
198 extern int DSDPMonitorCones(DSDP,int);
199 extern int DSDPDestroyCones(DSDP);
200 extern int DSDPPassXVectors(DSDP,double,DSDPVec,DSDPVec);
201 extern int DSDPComputeXVariables(DSDP,double,DSDPVec,DSDPVec,DSDPVec,double*);
202 extern int DSDPGetConicDimension(DSDP,double*);
203 extern int DSDPSchurSparsity(DSDP, int, int[], int);
204 
206 extern int DSDPComputeDualStepDirection(DSDP, double, DSDPVec);
208 
209 extern int DSDPSetCone(DSDP,DSDPCone);
210 
211 extern int DSDPScaleData(DSDP);
212 extern int DSDPComputeDataNorms(DSDP);
213 
214 extern int DSDPTakeDown(DSDP);
215 extern int DSDPSetDefaultStatistics(DSDP);
216 extern int DSDPSetDefaultParameters(DSDP);
217 extern int DSDPSetDefaultMonitors(DSDP);
218 
219 /* DSDP subroutines */
220 extern int DSDPInitializeVariables(DSDP);
222 extern int DSDPCheckForUnboundedObjective(DSDP, DSDPTruth*);
223 
225 extern int DSDPMonitor(DSDP);
226 extern int DSDPPrintStats(DSDP, void*);
227 extern int DSDPPrintStatsFile(DSDP, void*);
228 
229 extern int DSDPGetSchurMatrix(DSDP,DSDPSchurMat*);
230 
231 
232 #ifdef __cplusplus
233 }
234 #endif
235 
236 extern int DSDPAddRCone(DSDP,RRCone*);
237 extern int RConeSetType(RRCone, DSDPPenalty);
238 extern int RConeGetRX(RRCone, double*);
239 
240 extern int DSDPGetConvergenceMonitor(DSDP, ConvergenceMonitor**);
241 extern int DSDPDefaultConvergence(DSDP,void *);
242 
243 extern int DSDPSetDefaultSchurMatrixStructure(DSDP);
244 extern int DSDPFixedVariablesNorm(DSDPSchurMat,DSDPVec);
245 extern int DSDPComputeFixedYX(DSDPSchurMat,DSDPVec);
246 
247 extern int DSDPAddBCone(DSDP,DSDPVec,double);
248 
249 #endif
int DSDPComputePotential2(DSDP, DSDPVec, double, double, double *)
Compute the objective function plus the barrier function.
Definition: dualimpl.c:287
int DSDPGetConvergenceMonitor(DSDP, ConvergenceMonitor **)
Get the structure containing convergence parameters.
Definition: dsdpsetup.c:268
int DSDPComputeSS(DSDP, DSDPVec, DSDPDualFactorMatrix, DSDPTruth *)
Compute the dual variables S in each cone.
Definition: dsdpcops.c:272
int DSDPSetDefaultStatistics(DSDP)
Set default statistics.
Definition: dsdpsetup.c:84
int DSDPSetRR(DSDP, double)
Set variable r.
Definition: dualimpl.c:345
int DSDPSetUpCones(DSDP)
Each cone should factor data or allocate internal data structures.
Definition: dsdpcops.c:58
int DSDPSetDefaultMonitors(DSDP)
Set convergence monitor.
Definition: dsdpsetup.c:165
int DSDPComputeG(DSDP, DSDPVec, DSDPVec, DSDPVec)
Compute the gradient of the barrier for each cone.
Definition: dsdpcops.c:215
int DSDPComputeRHS(DSDP, double, DSDPVec)
Compute the right-hand side of the linear system that determines the step direction.
Definition: dualimpl.c:177
int DSDPComputeHessian(DSDP, DSDPSchurMat, DSDPVec, DSDPVec)
Compute the Schur complement, or Gram, matrix for each cone.
Definition: dsdpcops.c:142
int DSDPScaleData(DSDP)
Scale the matrix C.
Definition: dsdpsetup.c:311
int DSDPComputeLogSDeterminant(DSDP, double *)
Compute the logarithmic barrier function for the dual varialbe S.
Definition: dsdpcops.c:495
int DSDPObjectiveGH(DSDP, DSDPSchurMat, DSDPVec)
Compute gradient of dual objective.
Definition: dualimpl.c:381
int DSDPSchurSparsity(DSDP, int, int[], int)
Each cone should print its state.
Definition: dsdpcops.c:474
int DSDPInvertS(DSDP)
Invert the S variables in each cone.
Definition: dsdpcops.c:307
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
int DSDPCGSolve(DSDP, DSDPSchurMat, DSDPVec, DSDPVec, double, DSDPTruth *)
Apply CG to solve for the step directions.
Definition: dsdpcg.c:239
int DSDPComputeANorm2(DSDP, DSDPVec)
Compute norm of A and C.
Definition: dsdpcops.c:246
int DSDPComputeNewY(DSDP, double, DSDPVec)
Update the Y variables.
Definition: dualimpl.c:125
int DSDPComputeDualityGap(DSDP, double, double *)
Compute the current duality gap.
Definition: dualimpl.c:230
int BoundYConeSetBounds(YBoundCone, double, double)
Set bounds on the variables.
Definition: allbounds.c:512
struct LUBounds_C * YBoundCone
Cone with bounds on variables y.
Definition: dsdp.h:18
int DSDPComputeObjective(DSDP, DSDPVec, double *)
Compute the objective function (DD).
Definition: dualimpl.c:21
int DSDPMonitorCones(DSDP, int)
This routine is called once per iteration.
Definition: dsdpcops.c:450
int DSDPComputePNorm(DSDP, double, DSDPVec, double *)
Compute proximity to a point on the central path.
Definition: dualimpl.c:200
int DSDPViewCones(DSDP)
Each cone should print its state.
Definition: dsdpcops.c:424
int DSDPComputeXVariables(DSDP, double, DSDPVec, DSDPVec, DSDPVec, double *)
Compute the X variables in each cone.
Definition: dsdpcops.c:654
int DSDPComputePDY(DSDP, double, DSDPVec, double *)
Compute the step direction.
Definition: dualimpl.c:77
int DSDPHessianMultiplyAdd(DSDP, DSDPVec, DSDPVec)
Add the product of Schur matrix with v.
Definition: dsdpcops.c:188
int DSDPSolveDynamicRho(DSDP)
Apply dual-scaling algorithm.
Definition: dualalg.c:121
int DSDPComputeDataNorms(DSDP)
Compute norms of A,C, and b.
Definition: dsdpsetup.c:283
int DSDPSetCone(DSDP, DSDPCone)
Pass a cone to the DSDP solver.
Definition: dsdpcops.c:522
struct RDCone * RRCone
Cone with nonnegativity on variable r.
Definition: dsdp.h:24
int DSDPCheckConvergence(DSDP, DSDPTerminationReason *)
Check for convergence and monitor solution.
Definition: dsdpsetup.c:384
int DSDPComputeDY(DSDP, double, DSDPVec, double *)
Compute the step direction.
Definition: dualimpl.c:45
int DSDPComputePDY1(DSDP, double, DSDPVec)
Compute an affine step direction dy1.
Definition: dualimpl.c:105
int DSDPComputePY(DSDP, double, DSDPVec)
Compute PY = Y - beta DY for use in computing X.
Definition: dualimpl.c:150
int DSDPSetDefaultParameters(DSDP)
Set default parameters.
Definition: dsdpsetup.c:122
int DSDPSaveYForX(DSDP, double, double)
Save the current solution for later computation of X.
Definition: dsdpx.c:149
int DSDPComputeMaxStepLength(DSDP, DSDPVec, DSDPDualFactorMatrix, double *)
Compute the maximum step length for the given step direction.
Definition: dsdpcops.c:336
int DSDPGetConicDimension(DSDP, double *)
Get the total dimension of the cones.
Definition: dsdpcops.c:401
int DSDPComputePotential(DSDP, DSDPVec, double, double *)
Compute the potential of the given point.
Definition: dualimpl.c:261
int BoundYConeGetBounds(YBoundCone, double *, double *)
Get bounds on the variables.
Definition: allbounds.c:532
int DSDPComputeDualStepDirections(DSDP)
Compute the step direction by computing a linear system and solving it.
Definition: dualalg.c:370
int DSDPDestroyCones(DSDP)
Each cone shoudl free its data structures.
Definition: dsdpcops.c:107
int DSDPInitializeVariables(DSDP)
Initialize variables and factor S.
Definition: dualalg.c:475
int DSDPCreateLUBoundsCone(DSDP, YBoundCone *)
Create bounds cone.
Definition: allbounds.c:566
int DSDPSetUpCones2(DSDP, DSDPVec, DSDPSchurMat)
Each cone should allocate its data structures .
Definition: dsdpcops.c:84
int DSDPGetRR(DSDP, double *)
Get variable r.
Definition: dualimpl.c:361
int DSDPTakeDown(DSDP)
Destroy internal data structures.
Definition: dsdpsetup.c:428
int DSDPSetY(DSDP, double, double, DSDPVec)
Update the solver with these y variables.
Definition: dualimpl.c:309
Solver, solution types, termination codes,.
DSDPTerminationReason
There are many reasons to terminate the solver.
DSDPSolutionType
Formulations (P) and (D) can be feasible and bounded, feasible and unbounded, or infeasible.
DSDPDualFactorMatrix
DSDP requires two instances of the data structures S.
DSDPTruth
Boolean variables.
The public interface between the cones and the solver.
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
Detect convergence of the solver from the duality gap and step sizes.
int DSDPAddRCone(DSDP dsdp, RCone **rrcone)
A separate cone specifies that r must be nonnegative.
Definition: dsdprescone.c:302
Methods of a Schur Matrix.
Vector operations used by the solver.
struct DSDPVec_C DSDPVec
This object hold m+2 variables: a scaling of C, the y variables, and r.
Definition: dsdpvec.h:25
int DSDPDefaultConvergence(DSDP, void *)
Check for Convergence.
Definition: dsdpconverge.c:26
int DSDPGetMaxYElement(DSDP, double *)
Copy the the infinity norm of the variables y.
Definition: dsdpsetdata.c:645
int DSDPPrintStats(DSDP, void *)
Print statistics about the current solution to standard output.
Definition: dsdpprintout.c:71
Schur complement matrix whose solution is the Newton direction.
Definition: dsdpschurmat.h:35
Internal structures for the DSDP solver.
Definition: dsdp.h:65