SDPJSolver
SDPJ is a native Julia semidefinite program (SDP) solver.
- Motivated by the eft/modular bootstrap programs, SDPJ is a parallelized, arbitrary precision SDP solver based on the primal-dual interior-point method.
- SDPJ is largely inspired by SDPA and SDPB, with slightly different parallelization architecture.
- The solver is still in a development stage, which is far from fully optimized and might contain bugs. Corrections and suggestions are welcome and will get serious attention : )
The optimization problem
The function
sdp(c, A, C, B, b; β = 0.1, Ωp = 1, Ωd = 1, ϵ_gap = 1e-10, ϵ_primal = 1e-10, ϵ_dual = 1e-10, iterMax = 200, prec = 300)
solves the following SDP:
Primal
Dual
Domain
Interior-point method
In each iteration, the program solves the following deformed KKT conditions to determine the Newton step:
- Primal feasibility
- Dual feasibility
- Complementarity
Mehrotra's predictor-corrector method is used to accelerate convergence.
After a search direction is obtained, the step size is determined by requiring that
The feasibility problem
The function
findFeasible(A, C, B, b; β = 0.1, Ωp = 1, Ωd = 1, ϵ_gap = 1e-10, ϵ_primal = 1e-10, ϵ_dual = 1e-10, iterMax = 200, prec = 300)
determines whether the SDP above is feasible. Note that the arguments are basically the same as sdp()
except no vector c
for the objective function is needed. The function converts the feasibility problem to the following optimization problem:
If
findFeasible()
will fail if the feasible set is unbounded but works fine when the problem is infeasible.
Inputs
prec
: arithemetic precision in base-10, which is equivalent to
setprecision(prec, base = 10)
The default value of the global variable T
is BigFloat
, which supports arbitrary precision arithmetic.
If accuracy is not a concern, the user can manually set T
to other arithmetic types for improved performance, say Float64
:
setArithmeticType(Float64)
c
: Vector{T}
A
: Vector{Array{T, 3}}
C
: Vector{Matrix{T}}
B
: Matrix{T}
b
: Vector{T}
β
: factor of reduction in μ in each step
Ωp
and Ωd
are initial values for the matrices X and Y:
mode
: can be either "opt"
or "feas"
.
The iteration terminates if any of the following occurs:
- The function
sdp()
is used, and the duality gap, primal infeasibility, and dual infeasibility are belowϵ_gap
,ϵ_primal
, andϵ_dual
, respectively. - The function
findFeasible()
is used, and the primal/dual infeasibilities reach their thresholds, with a certificate of$t^* > 0$ or$t^* < 0$ found. - The number of iteration exceeds
iterMax
.
Outputs
The function sdp()
returns a dictionary with the following keys:
- "x": value of the variable
x
- "X": value of the variable
X
- "y": value of the variable
y
- "Y": value of the variable
Y
- "pObj": value of the primal objective function
- "dObj": value of the dual objective fucntion
- "status": reports the status of optimization. Can be either
- "Optimal"
- "Feasible"
- "Infeasible"
- "Cannot reach optimality (feasibility) within
iterMax
iterations."