        ==========================================================
                    Supplementary Code for the Paper
        "Polynomial Time Guarantees for the Burer-Monteiro Method"
        ==========================================================


This folder contains the code necessary to reproduce the experiments from Section 6.

The main part of the code is implemented in Julia, in the file "exp.jl".
The Julia code generates random input data, solves the optimization problems,
and then saves the input and output to the "data/" folder.
We use Matlab for generating the figures. The files "fig1.m", "fig2a.m", "fig2b.m"
read the data produced by Julia, and generate Figures 1, 2a, 2b.
The Julia code takes several hours to complete, while the Matlab code takes seconds.

The Julia code relies on two optimization libraries:
-- NLopt: used for solving nonlinear programs using the ALM method
-- MosekTools: used for solving semidefinite programs
We also use the libraries LinearAlgebra, JuMP, Random, Printf, DelimitedFiles, MATLAB.
The user must install these libraries before running the code.

We rely on random data for the experiments, so the results obtained by the
user might differ from ours, but the qualitative behavior should be similar.
For completeness, we have included the data files that we obtained when we ran the code
(see the "data/" folder). The Matlab functions "fig1.m", "fig2a.m", "fig2b.m" produce
the figures from the paper when using these data files.

We now provide concrete instructions for reproducing the results from each of the figures.


Figure 1
========

Load the script "exp.jl" in Julia, and call the function experiment1(p0)
for each of the values p0 = 4, 7, 12, as follows:

julia> include("exp.jl")
julia> experiment1(4)
julia> experiment1(7)
julia> experiment1(12)

The code generates the files "data/exp_p4.mat", "data/exp_p7.mat", "data/exp_p12.mat".

Afterwards, run the script "fig1.m" in Matlab:

matlab> fig1


Figure 2a
=========

After Figure 1 is produced, identify an index k0 for which the optimality gap is large.
To do so, run the following command in Matlab:

matlab> load('data/exp1_p7.mat','Gap','ErrX','p')

and look for an index k0 such that entries of Gap(:,k0) are large (particularly
the last entries).
From now on, we assume that k0=43 (which works for the sample data provided).

Once the value of k0 is identified, we load the script "exp.jl" in Julia, and call the
function experiment2(p0,k0,SigmaRange) with p0=7, k0=43, SigmaRange=(0:.02:.2).

julia> include("exp.jl")
julia> experiment2(7,43,0:.02:.2)

The code generates the file "data/exp2.mat".

Afterwards, run the script "fig2a.m" in Matlab:

matlab> fig2a


Figure 2b
=========

This figure concerns the same experiment as the one from Figure 2a.
The main difference is that Figure 2a shows the error of the final point produced by
the ALM algorithm, while Figure 2b shows the error of *all* the intermediate points
computed by ALM.

We use the optimization library NLopt for ALM. However, this library only gives access
to the final point produced by ALM. The user has to modify the source code of the NLopt
library to get access to the intermediate points. More precisely, the user needs to expose
the value of the variable "xcur" (the current point). 

After modifying the NLopt library, rerun the Julia function experiment2()

julia> include("exp.jl")
julia> experiment2(7,43,[0,.2])

This generates several files named as "data/exp2-full/in_i%d_j%d.mat". We assume that
the user saves all values of "xcur" into a file formatted as "data/exp2-full/out.txt".

Afterwards, run the script "fig2b.m" in Matlab:

matlab> fig2b
