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
DSDPTruth
Boolean variables.
int DSDPViewCones(DSDP)
Each cone should print its state.
Definition: dsdpcops.c:424
int DSDPComputeLogSDeterminant(DSDP, double *)
Compute the logarithmic barrier function for the dual varialbe S.
Definition: dsdpcops.c:495
int DSDPTakeDown(DSDP)
Destroy internal data structures.
Definition: dsdpsetup.c:428
struct DSDPVec_C DSDPVec
This object hold m+2 variables: a scaling of C, the y variables, and r.
Definition: dsdpvec.h:25
struct RDCone * RRCone
Cone with nonnegativity on variable r.
Definition: dsdp.h:24
int DSDPInvertS(DSDP)
Invert the S variables in each cone.
Definition: dsdpcops.c:307
int DSDPComputeDualStepDirections(DSDP)
Compute the step direction by computing a linear system and solving it.
Definition: dualalg.c:370
Schur complement matrix whose solution is the Newton direction.
Definition: dsdpschurmat.h:35
int DSDPComputeSS(DSDP, DSDPVec, DSDPDualFactorMatrix, DSDPTruth *)
Compute the dual variables S in each cone.
Definition: dsdpcops.c:272
int DSDPComputePDY1(DSDP, double, DSDPVec)
Compute an affine step direction dy1.
Definition: dualimpl.c:105
int DSDPComputeNewY(DSDP, double, DSDPVec)
Update the Y variables.
Definition: dualimpl.c:125
Detect convergence of the solver from the duality gap and step sizes.
int DSDPObjectiveGH(DSDP, DSDPSchurMat, DSDPVec)
Compute gradient of dual objective.
Definition: dualimpl.c:381
int DSDPMonitorCones(DSDP, int)
This routine is called once per iteration.
Definition: dsdpcops.c:450
int DSDPSetCone(DSDP, DSDPCone)
Pass a cone to the DSDP solver.
Definition: dsdpcops.c:522
Internal structures for the DSDP solver.
Definition: dsdp.h:65
int DSDPPrintStats(DSDP, void *)
Print statistics about the current solution to standard output.
Definition: dsdpprintout.c:71
DSDPTerminationReason
There are many reasons to terminate the solver.
int DSDPCheckConvergence(DSDP, DSDPTerminationReason *)
Check for convergence and monitor solution.
Definition: dsdpsetup.c:384
int DSDPSetRR(DSDP, double)
Set variable r.
Definition: dualimpl.c:345
int DSDPScaleData(DSDP)
Scale the matrix C.
Definition: dsdpsetup.c:311
int DSDPSetDefaultParameters(DSDP)
Set default parameters.
Definition: dsdpsetup.c:122
int DSDPComputeDualityGap(DSDP, double, double *)
Compute the current duality gap.
Definition: dualimpl.c:230
int DSDPComputePY(DSDP, double, DSDPVec)
Compute PY = Y - beta DY for use in computing X.
Definition: dualimpl.c:150
int DSDPComputeDataNorms(DSDP)
Compute norms of A,C, and b.
Definition: dsdpsetup.c:283
Solver, solution types, termination codes,.
int DSDPInitializeVariables(DSDP)
Initialize variables and factor S.
Definition: dualalg.c:475
int DSDPSaveYForX(DSDP, double, double)
Save the current solution for later computation of X.
Definition: dsdpx.c:149
int DSDPSetY(DSDP, double, double, DSDPVec)
Update the solver with these y variables.
Definition: dualimpl.c:309
int DSDPGetConicDimension(DSDP, double *)
Get the total dimension of the cones.
Definition: dsdpcops.c:401
int DSDPDefaultConvergence(DSDP, void *)
Check for Convergence.
Definition: dsdpconverge.c:26
int DSDPComputeRHS(DSDP, double, DSDPVec)
Compute the right-hand side of the linear system that determines the step direction.
Definition: dualimpl.c:177
int DSDPSetDefaultStatistics(DSDP)
Set default statistics.
Definition: dsdpsetup.c:84
int DSDPAddRCone(DSDP dsdp, RCone **rrcone)
A separate cone specifies that r must be nonnegative.
Definition: dsdprescone.c:302
int DSDPSolveDynamicRho(DSDP)
Apply dual-scaling algorithm.
Definition: dualalg.c:121
int DSDPCreateLUBoundsCone(DSDP, YBoundCone *)
Create bounds cone.
Definition: allbounds.c:566
Methods of a Schur Matrix.
Vector operations used by the solver.
int DSDPHessianMultiplyAdd(DSDP, DSDPVec, DSDPVec)
Add the product of Schur matrix with v.
Definition: dsdpcops.c:188
int DSDPSetUpCones(DSDP)
Each cone should factor data or allocate internal data structures.
Definition: dsdpcops.c:58
int DSDPComputeDY(DSDP, double, DSDPVec, double *)
Compute the step direction.
Definition: dualimpl.c:45
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
int DSDPComputeHessian(DSDP, DSDPSchurMat, DSDPVec, DSDPVec)
Compute the Schur complement, or Gram, matrix for each cone.
Definition: dsdpcops.c:142
int DSDPComputeXVariables(DSDP, double, DSDPVec, DSDPVec, DSDPVec, double *)
Compute the X variables in each cone.
Definition: dsdpcops.c:654
The public interface between the cones and the solver.
int DSDPComputePotential(DSDP, DSDPVec, double, double *)
Compute the potential of the given point.
Definition: dualimpl.c:261
int DSDPGetConvergenceMonitor(DSDP, ConvergenceMonitor **)
Get the structure containing convergence parameters.
Definition: dsdpsetup.c:268
int DSDPComputeANorm2(DSDP, DSDPVec)
Compute norm of A and C.
Definition: dsdpcops.c:246
int DSDPComputeObjective(DSDP, DSDPVec, double *)
Compute the objective function (DD).
Definition: dualimpl.c:21
int DSDPGetRR(DSDP, double *)
Get variable r.
Definition: dualimpl.c:361
int DSDPComputeG(DSDP, DSDPVec, DSDPVec, DSDPVec)
Compute the gradient of the barrier for each cone.
Definition: dsdpcops.c:215
int DSDPComputeMaxStepLength(DSDP, DSDPVec, DSDPDualFactorMatrix, double *)
Compute the maximum step length for the given step direction.
Definition: dsdpcops.c:336
DSDPDualFactorMatrix
DSDP requires two instances of the data structures S.
int DSDPComputePNorm(DSDP, double, DSDPVec, double *)
Compute proximity to a point on the central path.
Definition: dualimpl.c:200
int DSDPDestroyCones(DSDP)
Each cone shoudl free its data structures.
Definition: dsdpcops.c:107
struct LUBounds_C * YBoundCone
Cone with bounds on variables y.
Definition: dsdp.h:18
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 BoundYConeSetBounds(YBoundCone, double, double)
Set bounds on the variables.
Definition: allbounds.c:512
int DSDPSchurSparsity(DSDP, int, int[], int)
Each cone should print its state.
Definition: dsdpcops.c:474
int DSDPComputePDY(DSDP, double, DSDPVec, double *)
Compute the step direction.
Definition: dualimpl.c:77
int DSDPSetUpCones2(DSDP, DSDPVec, DSDPSchurMat)
Each cone should allocate its data structures .
Definition: dsdpcops.c:84
int BoundYConeGetBounds(YBoundCone, double *, double *)
Get bounds on the variables.
Definition: allbounds.c:532
int DSDPComputePotential2(DSDP, DSDPVec, double, double, double *)
Compute the objective function plus the barrier function.
Definition: dualimpl.c:287
int DSDPCGSolve(DSDP, DSDPSchurMat, DSDPVec, DSDPVec, double, DSDPTruth *)
Apply CG to solve for the step directions.
Definition: dsdpcg.c:239
int DSDPSetDefaultMonitors(DSDP)
Set convergence monitor.
Definition: dsdpsetup.c:165
DSDPSolutionType
Formulations (P) and (D) can be feasible and bounded, feasible and unbounded, or infeasible.
int DSDPGetMaxYElement(DSDP, double *)
Copy the the infinity norm of the variables y.
Definition: dsdpsetdata.c:645