convex optimization

Linearized Alternating Direction Method of Multipliers via Positive-Indefinite Proximal Regularization for Convex Programming

Categories Convex Optimization Tags , , , ,

The alternating direction method of multipliers (ADMM) is being widely used for various convex minimization models with separable structures arising in a variety of areas. In the literature, the proximalversion of ADMM which allows ADMM’s subproblems to be proximally regularized has been well studied. Particularly the linearized version of ADMM can be yielded when the … Read more

Faster Alternating Direction Method of Multipliers with a Worst-case O(1/n^2) Convergence Rate

Categories Convex Optimization Tags , , , ,

The alternating direction method of multipliers (ADMM) is being widely used for various convex programming models with separable structures arising in specifically many scientific computing areas. The ADMM’s worst-case O(1/n) convergence rate measured by the iteration complexity has been established in the literature when its penalty parameter is a constant, where n is the iteration … Read more

Complexity bounds for primal-dual methods minimizing the model of objective function

Categories Convex and Nonsmooth Optimization Tags , , , ,

We provide Frank-Wolfe ($\equiv$ Conditional Gradients) method with a convergence analysis allowing to approach a primal-dual solution of convex optimization problem with composite objective function. Additional properties of complementary part of the objective (strong convexity) significantly accelerate the scheme. We also justify a new variant of this method, which can be seen as a trust-region … Read more

Multiple cuts in separating plane algorithms

Categories Convex Optimization Tags , , , ,

This paper presents an extended version of the separation plane algorithms for subgradient-based finite-dimensional nondifferentiable convex blackbox optimization. The extension introduces additional cuts for epigraph of the conjugate of objective function which improve the convergence of the algorithm. The case of affine cuts is considered in more details and it is shown that it requires … Read more

Frechet inequalities via convex optimization

Categories Convex Optimization, Infinite Dimensional Optimization, Robust Optimization Tags , ,

Quantifying the risk carried by an aggregate position $S_d\defn\sum_{i=1}^d X_i$ comprising many risk factors $X_i$ is fundamental to both insurance and financial risk management. Frechet inequalities quantify the worst-case risk carried by the aggregate position given distributional information concerning its composing factors but without assuming independence. This marginal factor modeling of the aggregate position in … Read more

A Simplified Form of Block-Iterative Operator Splitting, and an Asynchronous Algorithm Resembling the Multi-Block ADMM

Categories Convex Optimization Tags , , ,

This paper develops what is essentially a simplified version of the block-iterative operator splitting method already proposed by the author and P. Combettes, but with more general initialization conditions. It then describes one way of implementing this algorithm asynchronously under a computing model inspired by modern HPC environments, which consist of interconnected nodes each having … Read more

Efficient Subgradient Methods for General Convex Optimization

Categories Convex Optimization Tags ,

A subgradient method is presented for solving general convex optimization problems, the main requirement being that a strictly-feasible point is known. A feasible sequence of iterates is generated, which converges to within user-specified error of optimality. Feasibility is maintained with a line-search at each iteration, avoiding the need for orthogonal projections onto the feasible region … Read more

Chebyshev Inequalities for Products of Random Variables

Categories Convex Optimization, Semi-definite Programming Tags , , ,

We derive sharp probability bounds on the tails of a product of symmetric non-negative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed numerically using semidefinite programming. If only an upper bound on the covariance matrix is available, … Read more

Algorithms for stochastic optimization with expectation constraints

Categories Bound-constrained Optimization, Convex and Nonsmooth Optimization, Stochastic Programming Tags , , , ,

This paper considers the problem of minimizing an expectation function over a closed convex set, coupled with an expectation constraint on either decision variables or problem parameters. We first present a new stochastic approximation (SA) type algorithm, namely the cooperative SA (CSA), to handle problems with the expectation constraint on devision variables. We show that … Read more

Iteration-complexity of a Rockafellar’s proximal method of multipliers for convex programming based on second-order approximations

Categories Constrained Nonlinear Optimization, Convex Optimization, Global Optimization Tags , , , ,

This paper studies the iteration-complexity of a new primal-dual algorithm based on Rockafellar’s proximal method of multipliers (PMM) for solving smooth convex programming problems with inequality constraints. In each step, either a step of Rockafellar’s PMM for a second-order model of the problem is computed or a relaxed extragradient step is performed. The resulting algorithm … Read more