convex optimization

On the Optimal Proximal Parameter of an ADMM-like Splitting Method for Separable Convex Programming

Categories Convex Optimization Tags , , ,

An ADMM-based splitting method is proposed in [11] for solving convex minimization problems with linear constraints and multi-block separable objective functions; while a relatively large proximal parameter is required for theoretically ensuring the convergence. In this paper, we further study this method and find its optimal (smallest) proximal parameter. For succinctness, we focus on the … Read more

Optimal Linearized Alternating Direction Method of Multipliers for Convex Programming

Categories Convex Optimization Tags , , , , ,

The alternating direction method of multipliers (ADMM) is being widely used in a variety of areas; its different variants tailored for different application scenarios have also been deeply researched in the literature. Among them, the linearized ADMM has received particularly wide attention from many areas because of its efficiency and easy implementation. To theoretically guarantee … Read more

Randomized Similar Triangles Method: A Unifying Framework for Accelerated Randomized Optimization Methods (Coordinate Descent, Directional Search, Derivative-Free Method)

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

In this paper, we consider smooth convex optimization problems with simple constraints and inexactness in the oracle information such as value, partial or directional derivatives of the objective function. We introduce a unifying framework, which allows to construct different types of accelerated randomized methods for such problems and to prove convergence rate theorems for them. … Read more

On the behavior of Lagrange multipliers in convex and non-convex infeasible interior point methods

Categories Nonlinear Optimization Tags , , , ,

This paper analyzes sequences generated by infeasible interior point methods. In convex and non-convex settings, we prove that moving the primal feasibility at the same rate as complementarity will ensure that the Lagrange multiplier sequence will remain bounded, provided the limit point of the primal sequence has a Lagrange multiplier, without constraint qualification assumptions. We … Read more

Invex Optimization Revisited

Categories Applications - Science and Engineering, Global Optimization Theory, Nonlinear Optimization Tags , , ,

Given a non-convex optimization problem, we study conditions under which every Karush-Kuhn-Tucker (KKT) point is a global optimizer. This property is known as KT-invexity and allows to identify the subset of problems where an interior point method always converges to a global optimizer. In this work, we provide necessary conditions for KT-invexity in n-dimensions and … Read more

Infeasibility detection in the alternating direction method of multipliers for convex optimization

Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

The alternating direction method of multipliers is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well-known that the algorithm generates iterates that converge to a solution, provided that it exists. If a solution does not exist, then the iterates diverge. Nevertheless, we show that they yield conclusive … Read more

Distributionally Robust Markovian Traffic Equilibrium

Categories Robust Optimization, Transportation Tags , ,

Stochastic user equilibrium models are fundamental to the analysis of transportation systems. Such models are typically developed under the assumption of route based choice models for the users. A class of link based models under a Markovian assumption on the route choice behavior of the users has been proposed to deal with the drawbacks of … Read more

On the pointwise iteration-complexity of a dynamic regularized ADMM with over-relaxation stepsize

Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

In this paper, we extend the improved pointwise iteration-complexity result of a dynamic regularized alternating direction method of multipliers (ADMM) for a new stepsize domain. In this complexity analysis, the stepsize parameter can even be chosen in the interval $(0,2)$ instead of interval $(0,(1+\sqrt{5})/2)$. As usual, our analysis is established by interpreting this ADMM variant … Read more

ADMM for monotone operators: convergence analysis and rates

Categories Convex Optimization Tags , , , , ,

We propose in this paper a unifying scheme for several algorithms from the literature dedicated to the solving of monotone inclusion problems involving compositions with linear continuous operators in infinite dimensional Hilbert spaces. We show that a number of primal-dual algorithms for monotone inclusions and also the classical ADMM numerical scheme for convex optimization problems, … Read more

From Data to Decisions: Distributionally Robust Optimization is Optimal

Categories Robust Optimization, Second-Order Cone Programming, Stochastic Programming Tags , , , , ,

We study stochastic programs where the decision-maker cannot observe the distribution of the exogenous uncertainties but has access to a finite set of independent samples from this distribution. In this setting, the goal is to find a procedure that transforms the data to an estimate of the expected cost function under the unknown data-generating distribution, … Read more