The Computational Complexity of Avoiding Strict Saddle Points in Non-Convex Constrained Optimization

The authors provide the Wolfram Mathematica files containing all the queries used for proving the non-existence of approximate SOSPs in Groups A-G and 1-4. To run these queries, one must simply run each one of the following files. Specifically inside the directory ./Groups you can find:

• Group-A.nb
• Group-B.nb
• Group-C.nb
• Group-D.nb
• Group-E.nb
• Group-F.nb
• Group-G.nb
• Group-1.nb
• Group-2.nb
• Group-3.nb
• Group-4.nb

Moreover, the authors provide the hardness_analysis.ipynb (Jupyter notebook, python3), within the same folder, where one can find python code that generates the polynomial expressions of the biquintic interpolation for Gx, Gy and lambda, for each one of the above groups. In the same file, one can also find code for plotting the landscapes of the function, the partial derivatives and the lambda for each one of the above groups.

You can find the full paper here