clique relaxations

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

Fast cluster detection in networks by first-order optimization

Categories Network Optimization, Nonlinear Optimization Tags , , ,

Cluster detection plays a fundamental role in the analysis of data. In this paper, we focus on the use of s-defective clique models for network-based cluster detection and propose a nonlinear optimization approach that efficiently handles those models in practice. In particular, we introduce an equivalent continuous formulation for the problem under analysis, and we … Read more

Continuous Cubic Formulations for Cluster Detection Problems in Networks

Categories Combinatorial Optimization, Global Optimization, Integer Programming Tags , , , , , ,

The celebrated Motzkin-Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Tur\'{a}n’s theorem in graph theory, but was later used to develop … Read more