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"
18typedef struct LUBounds_C* YBoundCone;
19
24typedef struct RDCone* RRCone;
25
26
27#define MAX_DSDP_MONITORS 5
28#define MAX_XMAKERS 4
29
30typedef struct {
31 DSDPVec y;
32 DSDPVec dy;
33 double mu;
34 double pstep;
35 DSDPVec rhs;
36} XMaker;
37
38typedef 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
45typedef struct {
46 int (*f)(void*);
47 void * ptr;
48}DRoutine;
49
50typedef struct {
51 int (*monitor)(struct DSDP_C *, void*);
52 void *monitorctx;
53} DMonitor;
54
55typedef struct {
56 DSDPCone cone;
57 int coneid;
58} DCone;
59
65struct DSDP_C{
66
67 DSDPCG *sles;
68 int slestype;
69
70 double schurmu;
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;
138
139 DMonitor dmonitor[MAX_DSDP_MONITORS];
140 int nmonitors;
141
142 DRoutine droutine[10];
143 int ndroutines;
144};
145
146typedef 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
156extern int BoundYConeSetBounds(YBoundCone, double, double);
157extern int BoundYConeGetBounds(YBoundCone, double*, double*);
158extern int BoundYConeAddX(YBoundCone,double,DSDPVec,DSDPVec,DSDPVec,double*);
159extern int BoundYConeAddS(YBoundCone,DSDPVec,DSDPVec);
160
161#ifdef __cplusplus
162extern "C" {
163#endif
164
165extern int DSDPComputeObjective(DSDP, DSDPVec, double *);
166extern int DSDPComputeDY(DSDP, double, DSDPVec, double*);
167extern int DSDPComputeNewY(DSDP, double, DSDPVec);
168extern int DSDPComputeRHS(DSDP, double, DSDPVec);
169extern int DSDPComputePDY1(DSDP,double,DSDPVec);
170extern int DSDPComputePDY(DSDP, double, DSDPVec, double*);
171extern int DSDPComputePY(DSDP,double,DSDPVec);
173extern int DSDPComputePNorm(DSDP, double,DSDPVec,double*);
174extern int DSDPComputeDualityGap(DSDP, double, double*);
175extern int DSDPSaveYForX(DSDP, double, double);
176extern int DSDPSetY(DSDP,double,double,DSDPVec);
177extern int DSDPComputePotential(DSDP, DSDPVec, double,double*);
178extern int DSDPComputePotential2(DSDP, DSDPVec, double, double, double*);
179extern int DSDPSetRR(DSDP,double);
180extern int DSDPGetRR(DSDP,double*);
181extern int DSDPGetMaxYElement(DSDP,double*);
182
183extern int DSDPSolveDynamicRho(DSDP);
184extern int DSDPRefineStepDirection(DSDP,DSDPVec, DSDPVec);
185
186/* Cone operations */
187extern int DSDPSetUpCones(DSDP);
189extern int DSDPSchurSparsity(DSDP, int, int[], int);
191extern int DSDPInvertS(DSDP);
195extern int DSDPComputeLogSDeterminant(DSDP, double*);
196extern int DSDPComputeANorm2(DSDP,DSDPVec);
197extern int DSDPViewCones(DSDP);
198extern int DSDPMonitorCones(DSDP,int);
199extern int DSDPDestroyCones(DSDP);
200extern int DSDPPassXVectors(DSDP,double,DSDPVec,DSDPVec);
201extern int DSDPComputeXVariables(DSDP,double,DSDPVec,DSDPVec,DSDPVec,double*);
202extern int DSDPGetConicDimension(DSDP,double*);
203extern int DSDPSchurSparsity(DSDP, int, int[], int);
204
206extern int DSDPComputeDualStepDirection(DSDP, double, DSDPVec);
208
209extern int DSDPSetCone(DSDP,DSDPCone);
210
211extern int DSDPScaleData(DSDP);
212extern int DSDPComputeDataNorms(DSDP);
213
214extern int DSDPTakeDown(DSDP);
217extern int DSDPSetDefaultMonitors(DSDP);
218
219/* DSDP subroutines */
220extern int DSDPInitializeVariables(DSDP);
222extern int DSDPCheckForUnboundedObjective(DSDP, DSDPTruth*);
223
225extern int DSDPMonitor(DSDP);
226extern int DSDPPrintStats(DSDP, void*);
227extern int DSDPPrintStatsFile(DSDP, void*);
228
229extern int DSDPGetSchurMatrix(DSDP,DSDPSchurMat*);
230
231
232#ifdef __cplusplus
233}
234#endif
235
236extern int DSDPAddRCone(DSDP,RRCone*);
237extern int RConeSetType(RRCone, DSDPPenalty);
238extern int RConeGetRX(RRCone, double*);
239
240extern int DSDPGetConvergenceMonitor(DSDP, ConvergenceMonitor**);
241extern int DSDPDefaultConvergence(DSDP,void *);
242
243extern int DSDPSetDefaultSchurMatrixStructure(DSDP);
244extern int DSDPFixedVariablesNorm(DSDPSchurMat,DSDPVec);
245extern int DSDPComputeFixedYX(DSDPSchurMat,DSDPVec);
246
247extern 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 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.
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
Schur complement matrix whose solution is the Newton direction.
Internal structures for the DSDP solver.
Definition dsdp.h:65