Conditional Gradient Augmented Lagrangian method with Inequalities (CGALI)

This repository contains the numerical work related to the article,

A conditional-gradient-based single-loop augmented Lagrangian method for inequality constrained optimization, by Xiaozhou Wang, Ting Kei Pong, and Zev Woodstock. Preprint will be announced soon.

The main algorithm proposed is a single-loop conditional gradient-based Augmented Lagrangian method designed to handle additional convex inequality constraints. This repository includes Julia implementations of:

• Our new algorithm, with capability to be ran with both open-loop and short-step stepsizes, and

• CoexDurCG algorithm from: Conditional gradient methods for convex optimization with general affine and nonlinear constraints, G. Lan, E. Romeijn, and Z. Zhou, SIAM Journal on Optimization, 31(3), 2307-2339, 2021. Preprint: https://arxiv.org/pdf/2007.00153

Both algorithms are written to rely on a Linear Minimization Oracle coming from FrankWolfe.jl. For a reference solution, this code is also drafted to use an out-of-the-box solver from JuMP.jl (current options are "cvx" and "Gurobi").

In the article, both algorithms are benchmarked on a high-dimensional problem with a quadratic objective function, quadratic inequality constraints, and a Birkhoff polytope constraint. This specific problem is described in the generate_problem_instance function within problem_setup.jl, as well as our article.

To run the main experiment, please run the following command from within Julia.

include("run_test.jl")

Below, we describe a (non-exhaustive) list of modifiable parameters within run_test.jl:

• n (positive Integer) the sidelength of the matrix variable; problem will have $n^2$ variables. Our experiments involve $n=500$.
• run_coex (Bool) toggles whether or not CoexDurCG will be ran on the main problem -use_shortstep (Bool) toggles the stepsize used by CGALI; if false, CGALI uses Open Loop stepsizes (see function alph_func later within the script)
• plot_results and plot_results_pdf (Bools) generate plots of relevant optimality criterion for the problem; the _pdf suffix indicates that a PDF contianing the plots will be generated.
• write_data_to_txt (Bool) writes a .txt file to make the results plottable in LaTeX.
• debug_mode (Bool) runs both algorithms with extra checks to verify that mathematically-proven inequalities actually hold during the run. Warning: setting this flag to true can significantly slow down performance.
• estim_fopt_with_solver (Bool) tells the code whether or not to use a solver to estimate the solution to the problem.
• solver (String), either "cvx" or "Gurobi" - describes which solver to use if estim_fopt_with_solver is true. Both solvers run into memory problems if n gets too large, although usually Gurobi tends to do better than cvx.

This repository also contains the raw data currently plotted in our article, within the paper_data folder.

The work of ZW was supported by NSF DMS-2532423