motzkin-straus

Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem

Categories Network Optimization, Nonlinear Optimization Tags , , ,

Building on a new regularized continuous formulation which avoids spurious solutions of the maximum s-plex problem, we develop a tailored block-coordinate first-order method that combines away-step Frank-Wolfe updates on the standard simplex with linear optimization over the fractional b-matching polytope. We establish finite stabilization of the auxiliary variables, convergence to stationary points, and finite support … Read more

A General Regularized Continuous Formulation for the Maximum Clique Problem

Categories Combinatorial Optimization, Network Optimization, Nonlinear Optimization Tags , , , ,

In this paper, we develop a general regularization-based continuous optimization framework for the maximum clique problem. In particular, we consider a broad class of regularization terms that can be included in the classic Motzkin-Strauss formulation and we develop conditions that guarantee the equivalence between the continuous regularized problem and the original one in both a … Read more