rmd is a wrapper for the package MAXDET of Wu, Vandenberghe and Boyd.
It invokes
MAXDET to compute an approximation
of a solution to a general determinant maximization problem. Then the primal
and dual solution is approximated by rationals and tested for feasibility.
This part of the computation uses the package
NTL (A Library for doing Number Theory)
of Victor Shoup with rational
arithmetic only and it is mathematically rigorous.
Determinant maximization problems are convex optimization problems of the form:
minimize c
^{t} x  log det G(x)
s.t. G(x) = G
_{0} + x
_{1} G
_{1} + ... + x
_{n} G
_{n} is positive definite
and F(x) = F
_{0} + x
_{1} F
_{1} + ... + x
_{n} F
_{n} is positive semidefinite
for given symmetric positive definite, respectively positive semidefinite matrices
G
_{i} and F
_{i}.
For more information on the underlying theory, notation and terminology see the paper
"Determinant maximization with linear matrix inequality constraints" of
Vandenberghe, Boyd and Wu.
USAGE:
rmd [options] < file
Options:
h show this help
d x set duality gap to x
p proof mode
m N set maximum iterations to N
q quick and dirty (nonrigorous)
v be verbose
n be nonverbose
INPUT:
input files (preferably with extension
.rmd)
are plain text files containing the following information in the following
order:
 number of variables: m
 number of blocks in F: L
 Sizes of blocks in F: F_blkszs[1] .. F_blkszs[L]
 F in homogeneous coordinates: [ common_denominator F_0 .. F_m "in upper triangular block notation" ]
 Number of blocks in G: K
 Sizes of blocks in G: G_blkszs[1] .. G_blkszs[K]
 G in homogeneous coordinates: [ common_denominator G_0 .. G_m "in upper triangular block notation" ]
 c in homogeneous coordinates: [ common_denominator c_1 .. c_m ]
 without p, interior point: x=(x_1, ..., x_m) a point with G(x) = G_0 + x_1G_1 + ... + x_mG_m positive definite and F(x) = F_0 + x_1F_1 + ... + x_mF_m positive semidefinite
 without p and m, maximum number of iterations: how many iterations should MAXDET perform
 without p and d, absolute gap (convergence criterion): stop MAXDET when the gap between primal and dual solution is less then absolute gap
 with p, minimizer_approx: conjectured optimal primal feasible solution in homogeneous coordinates
 with p, dual_Z_approx: conjectured "Zpart" of optimal dual feasible solution in homogeneous coordinates
 with p, dual_W_approx: conjectured "Wpart" of optimal dual feasible solution in homogeneous coordinates
EXAMPLES:

Input:
Create a file input.rmd containing (in that order) dimension, data for F, G, c, interior point, maximum number of iterations and duality gap:
3
4
3 1 1 1
[1
4 0 0
0 0
0
0
0
0
0 1 1
1 1
1
0
0
1
0 0 2
0 1
2
1
1
1
0 0 1
0 0
1
0
1
0]
1
2
[1
0 0
0
1 0
0
0 1
0
0 0
1]
[1 0 0 0]
2e06 1e06 2e06
100
1e09
Call:
rmd < input.rmd
Output:
***********
*** rmd ***
***********
 SOLVING MAXDET PROBLEM
 starting MAXDET (workspace = 535)
iters primal dual
4 1.642528 7.638472
6 1.909503 1.909738
8 1.909543 1.909543
11 1.909543 1.909543
 MAXDET stopped because duality_gap reached.
 primal value = 1.909542505
 dual value = 1.909542505
 minimizer = 3 1.5 3
 minimizer_approx = [100000000000000000000 299999999998862554306 149999999999431232745 299999999998862509897]
 CHECKING PRIMAL SOLUTION
 G(x) is positive definite.
 F(x) is positive semidefinite.
 upper_bound ~ 1.909542505
 CHECKING DUAL SOLUTION
 Tr G_i W + Tr F_i Z = c_i.
 W is positive definite.
 Z is positive semidefinite.
 lower_bound ~ 1.909542505
 duality_gap ~ 4.549915996e11
* duality_gap = 1137478999/25000000000000000000 + log(20000000000000000000000000000000000000000000000000000000000000000000000000000000/19999999999999999341443869432402355206691602640158261111618189556065811235186639) ~ 4.549915996e11

Input:
Take same input as in the previous example, but possibly without
number of maximum iterations and duality gap.
Call:
rmd d 0.000001 m 50 q < input.rmd
Output:
***********
*** rmd ***
***********
* lower_bound ~ 3.000000091
* upper_bound ~ 2.999999927

Input:
The following input file input.rmd, gives data of a semidefinite programming problem (SDP).
For SDPs the data for G is just a "dummy" of the form "1 1 [1 1 0 .. 0]" with m (number of variables)
zeros.
4
7
3 1 1 1 1 1 1
[1 4 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 2 1 1 0 0 0 2 0 1 2 2 2 2 0 2 0 0 0 1 0 0 1 0 2 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1]
1
1
[1 1 0 0 0 0]
[1 0 0 0 1]
2e06 1e06 2e06 0.0
Call:
rmd d 0.01 m 10 < input.rmd
Output:
***********
*** rmd ***
***********
 SOLVING MAXDET PROBLEM
 starting MAXDET (workspace = 609)
iters primal dual
5 0.223323 7.582806
10 2.999001 3.001249
 MAXDET stopped because duality_gap reached.
 primal value = 2.999000909
 dual value = 3.001249103
 minimizer = 2.999750304 1.499875152 2.999750304 2.999000909
 minimizer_approx = [100000000000000000000 299975030424994759671 149987515212497405094 299975030424994759671 299900090852727174705]
 CHECKING PRIMAL SOLUTION
 G(x) is positive definite.
 F(x) is positive semidefinite.
 upper_bound ~ 2.999000909
 CHECKING DUAL SOLUTION
 Tr G_i W + Tr F_i Z = c_i.
 W is positive definite.
 Z is positive semidefinite.
 lower_bound ~ 3.001249103
 duality_gap ~ 0.002248194014
* duality_gap = 224819401418182171/100000000000000000000 + log(1) ~ 0.002248194014

Input:
The following input file input.rmd contains the data from the previous example without an
interior point in doubles, but with three additional lines containing a (conjectured) primal feasible and a dual
feasible solution (last two lines).
4
7
3 1 1 1 1 1 1
[1 4 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 2 1 1 0 0 0 2 0 1 2 2 2 2 0 2 0 0 0 1 0 0 1 0 2 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1]
1
1
[1 1 0 0 0 0]
[1 0 0 0 1]
[2 6 3 6 6]
[12 9 6 6 4 4 4 0 0 0 4 4 4]
[1 1]
Call:
rmd p < input.rmd
Output:
***********
*** rmd ***
***********
 duality_gap = 0 + log(1)
* CERTIFIED OPTIMUM *
INTERPRETATION:

A primal feasible minimizer_approx is computed,
together with a certified duality gap.

A lower and upper bound is attained in
"quickanddirtymode".

rmd can be used to rigorously solve semidefinite programming problems.

In "proofmode" rmd tests for primal and dual feasibility of the last three lines
and can so certify optimality, when the computed duality gap is zero.
INSTALLATION:
To install
rmd
(together with
coop and
pacoop)
you have to install
NTL
(A Library for doing Number Theory) of Victor Shoup before.
Then download the
complete
rmd package and run
make. You may have to
edit the variable
CXXFlags in the
Makefile so that it finds NTL.
If you have trouble to install our software,
please feel free to contact us.