We propose a distributed algorithm, named D-ADMM, for solving separable optimization problems in networks of interconnected nodes or agents. In a separable optimization problem, the cost function is the sum of all the agents’ private cost functions, and the constraint set is the intersection of all the agents’ private constraint sets. We require the private … Read more
We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when comparing to … Read more
In this paper we present a variant of the conjugate gradient (CG) algorithm in which we invoke a subspace minimization subproblem on each iteration. We call this algorithm CGSO for “conjugate gradient with subspace optimization”. It is related to earlier work by Nemirovsky and Yudin. We apply the algorithm to solve unconstrained strictly convex problems. … Read more
Finding clusters, or communities, in a graph, or network is a very important problem which arises in many domains. Several models were proposed for its solution. One of the most studied and exploited is the maximization of the so called modularity, which represents the sum over all communities of the fraction of edges within these … Read more
In this paper, we are interested in the development of efficient first-order methods for convex optimization problems in the simultaneous presence of smoothness of the objective function and stochasticity in the first-order information. First, we consider the Stochastic Primal Gradient method, which is nothing else but the Mirror Descent SA method applied to a smooth … Read more
Recently, a worst-case O(1/t) convergence rate was established for the Douglas-Rachford alternating direction method of multipliers in an ergodic sense. This note proposes a novel approach to derive the same convergence rate while in a non-ergodic sense. ArticleDownload View PDF
The contributions of the first half of this thesis are on the computational and algebraic aspects of convexity in polynomial optimization. We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves … Read more
This article uses classical notions of convex analysis over euclidean spaces, like Gale & Klee’s boundary rays and asymptotes of a convex set, or the inner aperture directions defined by Larman and Brøndsted for the same class of sets, to provide a new zero duality gap criterion for ordinary convex programs. On this ground, we … Read more
This article addresses a general criterion providing a zero duality gap for convex programs in the setting of the real locally convex spaces. The main theorem of our work is formulated only in terms of the constraints of the program, hence it holds true for any objective function fulfilling a very general qualification condition, implied … Read more
Given x, a point of a convex subset C of an Euclidean space, the two following statements are proven to be equivalent: (i) any convex function f : C → R is upper semi-continuous at x, and (ii) C is polyhedral at x. In the particular setting of closed convex mappings and Fσ domains, we … Read more