In a Hilbert setting, we introduce a new dynamic system and associated algorithms aimed at solving by rapid methods, monotone inclusions. Given a maximal monotone operator $A$, the evolution is governed by the time dependent operator $I -(I + \lambda(t) {A})^{-1}$, where, in the resolvent, the positive control parameter $\lambda(t)$ tends to infinity as $t … Read more
In this paper we study the convex problem of optimizing the sum of a smooth function and a compactly supported non-smooth term with a specific separable form. We analyze the block version of the generalized conditional gradient method when the blocks are chosen in a cyclic order. A global sublinear rate of convergence is established … Read more
In this paper we propose a corrected semi-proximal ADMM (alternating direction method of multipliers) for the general $p$-block $(p\!\ge 3)$ convex optimization problems with linear constraints, aiming to resolve the dilemma that almost all the existing modified versions of the directly extended ADMM, although with convergent guarantee, often perform substantially worse than the directly extended … Read more
In this paper we underline the importance of the parametric subregularity property of set-valued mappings, defined with respect to fixed sets. We show that this property appears naturally for some very simple mappings which play an important role in the theory of metric regularity. We prove a result concerning the preservation of metric subregularity at … Read more
We consider the alternating proximal gradient method (APGM) proposed to solve a convex minimization model with linear constraints and separable objective function which is the sum of two functions without coupled variables. Inspired by Peaceman-Rachford splitting method (PRSM), a nature idea is to extend APGM to the symmetric alternating proximal gradient method (SAPGM), which can … Read more
Trust-region methods are a broad class of methods for continuous optimization that found application in a variety of problems and contexts. In particular, they have been studied and applied for problems without using derivatives. The analysis of trust-region derivative-free methods has focused on global convergence, and they have been proved to generate a sequence of … Read more
We present polynomial-time algorithms for constrained optimization problems overwhere the intersection graph of the constraint set has bounded tree-width. In the case of binary variables we obtain exact, polynomial-size linear programming formulations for the problem. In the mixed-integer case with bounded variables we obtain polynomial-size linear programming representations that attain guaranteed optimality and feasibility bounds. … Read more
We study the usage of regularity properties of collections of sets in convergence analysis of alternating projection methods for solving feasibility problems. Several equivalent characterizations of these properties are provided. Two settings of inexact alternating projections are considered and the corresponding convergence estimates are established and discussed. ArticleDownload View PDF
In this paper, we analyze the convergence of Alternating Direction Method of Multipliers (ADMM) on convex quadratic programs (QPs) with linear equality and bound constraints. The ADMM formulation alternates between an equality constrained QP and a projection on the bounds. Under the assumptions of: (i) positive definiteness of the Hessian of the objective projected on … Read more
Until now it has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm with its combinatorial nature does not even offer a polynomial bound, whereas the complexity of the polynomial algorithms by Khachiyan and Karmarkar is based on the number of variables n, and … Read more