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 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