First-order algorithms for robust optimization problems via convex-concave saddle-point Lagrangian reformulation

Robust optimization (RO) is one of the key paradigms for solving optimization problems affected by uncertainty. Two principal approaches for RO, the robust counterpart method and the adversarial approach, potentially lead to excessively large optimization problems. For that reason, first order approaches, based on online-convex-optimization, have been proposed (Ben-Tal et al. (2015), Kilinc-Karzan and Ho-Nguyen … Read more

An (s^r)hBcResolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems

There has been a long history of using ordinary differential equations (ODEs) to understand the dynamic of discrete-time algorithms (DTAs). Surprisingly, there are still two fundamental and unanswered questions: (i) it is unclear how to obtain a \emph{suitable} ODE from a given DTA, and (ii) it is unclear the connection between the convergence of a … Read more

Moreau envelope of supremum functions with applications to infinite and stochastic programming

In this paper, we investigate the Moreau envelope of the supremum of a family of convex, proper, and lower semicontinuous functions. Under mild assumptions, we prove that the Moreau envelope of a supremum is the supremum of Moreau envelopes, which allows us to approximate possibly nonsmooth supremum functions by smooth functions that are also the … Read more

Algorithms for Block Tridiagonal Systems: Foundations and New Results for Generalized Kalman Smoothing

Block tridiagonal systems appear in classic Kalman smoothing problems, as well in generalized Kalman smoothing, where problems may have nonsmooth terms, singular covariance, constraints, nonlinear models, and unknown parameters. In this paper, first we interpret all the classic smoothing algorithms as different approaches to solve positive definite block tridiagonal linear systems. Then, we obtain new … Read more

EFIX: Exact Fixed Point Methods for Distributed Optimization

We consider strongly convex distributed consensus optimization over connected networks. EFIX, the proposed method, is derived using quadratic penalty approach. In more detail, we use the standard reformulation – transforming the original problem into a constrained problem in a higher dimensional space – to define a sequence of suitable quadratic penalty subproblems with increasing penalty … Read more

Decentralized Failure-Tolerant Optimization of Electric Vehicle Charging

We present a decentralized failure-tolerant algorithm for optimizing electric vehicle (EV) charging, using charging stations as computing agents. The algorithm is based on the alternating direction method of multipliers (ADMM) and it has the following features: (i) It handles capacity, peak demand, and ancillary services coupling constraints. (ii) It does not require a central agent … Read more

Amenable cones are particularly nice

Amenability is a geometric property of convex cones that is stronger than facial exposedness and assists in the study of error bounds for conic feasibility problems. In this paper we establish numerous properties of amenable cones, and investigate the relationships between amenability and other properties of convex cones, such as niceness and projectional exposure. We … Read more

Faster Lagrangian-Based Methods in Convex Optimization

In this paper, we aim at unifying, simplifying, and improving the convergence rate analysis of Lagrangian-based methods for convex optimization problems. We first introduce the notion of nice primal algorithmic map, which plays a central role in the unification and in the simplification of the analysis of all Lagrangian-based methods. Equipped with a nice primal … Read more

An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone

A weakly infeasible semidefinite program (SDP) has no feasible solution, but it has nearly feasible solutions that approximate the constraint set to arbitrary precision. These SDPs are ill-posed and numerically often unsolvable. They are also closely related to “bad” linear projections that map the cone of positive semidefinite matrices to a nonclosed set. We describe … Read more

Iteration complexity analysis of a partial LQP-based alternating direction method of multipliers

In this paper, we consider a prototypical convex optimization problem with multi-block variables and separable structures. By adding the Logarithmic Quadratic Proximal (LQP) regularizer with suitable proximal parameter to each of the first grouped subproblems, we develop a partial LQP-based Alternating Direction Method of Multipliers (ADMM-LQP). The dual variable is updated twice with relatively larger … Read more