User's Guide for rmd (rigorous MAXDET)

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 ct x - log det G(x)
s.t. G(x) = G0 + x1 G1 + ... + xn Gn is positive definite
and F(x) = F0 + x1 F1 + ... + xn Fn is positive semidefinite
for given symmetric positive definite, respectively positive semidefinite matrices Gi and Fi.

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 (non-rigorous)
 -v   be verbose
 -n   be non-verbose

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 "Z-part" of optimal dual feasible solution in homogeneous coordinates
  • with -p, dual_W_approx: conjectured "W-part" of optimal dual feasible solution in homogeneous coordinates

EXAMPLES:

  1. 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]

2e-06 -1e-06 2e-06

100

1e-09

    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.549915996e-11

* duality_gap = 1137478999/25000000000000000000 + log(20000000000000000000000000000000000000000000000000000000000000000000000000000000/19999999999999999341443869432402355206691602640158261111618189556065811235186639) ~ 4.549915996e-11


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

    

    

    3. 


    

    




  3. 
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]

2e-06 -1e-06 2e-06 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

    

    

    4. 


    

    






  4. 
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 *

    

    

    5. 


    

    











INTERPRETATION:

   

    

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

    2. 

  2. 
A lower and upper bound is attained in 
"quick-and-dirty-mode".

    3. 

  3. 
rmd can be used to rigorously solve semidefinite programming problems.

    4. 

  4. 
In "proof-mode" rmd tests for primal and dual feasibility of the last three lines 
and can so certify optimality, when the computed duality gap is zero.

    5. 









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.