Convex and Nonsmooth Optimization

A sufficient convergence condition for generalized Benders decomposition with general dual functions

Categories (Mixed) Integer Linear Programming, Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , ,

We revisit the framework of generalized Benders decomposition over a compact but non-finite master domain. We show by counterexample that strong general dual functions alone may fail to guarantee convergence. We then define a condition of uniform local strongness and prove that strong general dual functions satisfying this condition guarantee finite \(\epsilon\)-termination. Finally, we show … Read more

New adaptive proximal gradient algorithms for solving multiobjective composite optimization problems

Categories Nonlinear Optimization, Nonsmooth Optimization, Robust Optimization Tags , , , ,

In this paper, we propose new adaptive proximal gradient algorithms to solve multiobjective optimization problems, where each objective function is the sum of a differentiable function and a proper, closed, convex function. Utilizing the local behavior of the differentiable terms we propose new adaptive ways to select stepsizes used in proximal gradient scheme. In particular, … Read more

The best approximation tuple: an extension of the Cheney-Goldstein algorithm and results to the multiple sets case

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

In this paper we extend the algorithm and several results published in the celebrated 1959 paper of Cheney and Goldstein about the best approximation pair (BAP) problem in two separate directions. One is the consideration of more than two sets. The other is the ability to handle each set as an intersections of a finite … Read more

An exact algorithm for the probabilistic TSP via a new tractable convex representation of recourse

Categories (Mixed) Integer Linear Programming, Convex Optimization, Stochastic Programming Tags , , , ,

We consider the probabilistic traveling salesman problem (PTSP) in which customer presences are Bernoulli random variables, and the objective is to determine an a priori tour minimizing the expected traveling cost of the a posteriori tour obtained by skipping absent customers after customer presence is revealed. The existing literature has established that, given an a … Read more

A Proximal Approach for Nonsmooth Composite-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , ,

We propose a proximal-type algorithm for nonsmooth and nonconvex optimization problems with composite constraints. The constraint is defined by the composition of a locally upper-\(C^2\) outer function with a locally Lipschitz continuous inner mapping. The method is based on an improvement function that balances objective decrease and constraint satisfaction, and on a surrogate model obtained … Read more

Calculus of the facial distance

Categories Convex and Nonsmooth Optimization, Polyhedra Tags , ,

We develop a few calculus rules to compute or lower bound the facial distance of a polytope. We illustrate our calculus rules on various popular polytopes. In particular, we provide a lower bound on the facial distance of the Birkhoff polytope. CitationWorking paper. Tepper School of Business. Carnegie Mellon UniversityArticleDownload View PDF

On the Equivalence of Monge and Kantarovich Problems in Discrete Optimal Transport

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization of Systems modeled by PDEs

Consider a discrete optimal transport problem that has at least two consumers. We show that the Monge and Kantorovich versions of such a discrete optimal transport problem are equivalent for all cost functions if and only if the supply from all the suppliers are equal, and the demand from every consumer is an integral multiple … Read more

Symmetry-dependence in Rounding of a Convex Body

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

The symmetry measure of a convex body \(S\subset\mathbb{R}^n\) is given by: \[ \mathrm{sym}(S):=\max\{\alpha\ge0:\text{ there exists }x\in S\text{ such that } -\alpha(S-x)\subseteq S-x\}\,, \]where such an \(x\) is called a Minkowski center. We prove that every convex body \(S\) admits a \(\sqrt{\frac{n}{\mathrm{sym}(S)}}\)-rounding of \(S\), namely, there exists an origin-centered ellipsoid \(E\) and a center \(c\) such … Read more

Radial-type error bounds for semidefinite feasibility problems without strict feasibility: qualitative estimates and asymptotic tightness

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

In this paper, we develop a systematic framework for deriving explicit error bounds for semidefinite feasibility problems without assuming strict feasibility (Slater’s condition), a setting in which existing results are limited. Our main technical contribution is the introduction of radial-type H\”{o}lder error bounds, where the error bound constant depends explicitly on the norm of the … Read more

UGM: A Unified Framework and New Perspectives for Accelerated Gradient Methods in Smooth and Strongly Convex Optimization

Categories Convex Optimization Tags ,

In this paper, we propose a unified framework for accelerated gradient methods, dubbed UGM, which subsumes a wide range of accelerated and conventional gradient-type methods designed for minimizing $L$-smooth and $\mu$-strongly convex functions. We demonstrate that the iteration update of the proposed framework can be intrinsically interpreted as a hybrid combination of the heavy-ball method … Read more