In this paper we consider a block-structured convex optimization model, where in the objective the block-variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it … Read more
Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification, notwithstanding distributional ambiguity. In this work we discuss worst-case probability and conditional … Read more
An earlier paper proved the convergence of a variable stepsize Bregman operator splitting algorithm (BOSVS) for minimizing $\phi(Bu)+H(u)$ where $H$ and $\phi$ are convex functions, and $\phi$ is possibly nonsmooth. The algorithm was shown to be relatively efficient when applied to partially parallel magnetic resonance image reconstruction problems. In this paper, the convergence rate of … Read more
We investigate the convergence rates of the trajectories generated by implicit first and second order dynamical systems associated to the determination of the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space. We show that these trajectories strongly converge with exponential rate to … Read more
This paper presents an acceleration of the optimal subgradient algorithm OSGA \cite{NeuO} for solving convex optimization problems, where the objective function involves costly affine and cheap nonlinear terms. We combine OSGA with a multidimensional subspace search technique, which leads to low-dimensional problem that can be solved efficiently. Numerical results concerning some applications are reported. A … Read more
In this paper, we approach the problem of finding the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space via an implicit forward-backward-forward dynamical system with nonconstant relaxation parameters and stepsizes of the resolvents. Besides proving existence and uniqueness of strong global solutions … Read more
We propose a polynomial algorithm for a separable convex optimization problem with linear constraints. We do not make any additional assumptions about the structure of the objective function except for polynomial computability. That is, the objective function can be non-differentiable. The running time of our algorithm is polynomial in the the size of the input … Read more
We begin by considering second order dynamical systems of the from $\ddot x(t) + \Gamma (\dot x(t)) + \lambda(t)B(x(t))=0$, where $\Gamma: {\cal H}\rightarrow{\cal H}$ is an elliptic bounded self-adjoint linear operator defined on a real Hilbert space ${\cal H}$, $B: {\cal H}\rightarrow{\cal H}$ is a cocoercive operator and $\lambda:[0,+\infty)\rightarrow [0,+\infty)$ is a relaxation function depending … Read more
It has been shown in \cite{Lan13-1} that the accelerated prox-level (APL) method and its variant, the uniform smoothing level (USL) method, have optimal iteration complexity for solving black-box and structured convex programming problems without requiring the input of any smoothness information. However, these algorithms require the assumption on the boundedness of the feasible set and … Read more
We propose and analyse primal-dual interior-point algorithms for convex optimization problems in conic form. The families of algorithms we analyse are so-called short-step algorithms and they match the current best iteration complexity bounds for primal-dual symmetric interior-point algorithm of Nesterov and Todd, for symmetric cone programming problems with given self-scaled barriers. Our results apply to … Read more