Convex Optimization

Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case

Categories Convex Optimization Tags ,

We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let \(p_{\mathrm{sil}}=\log_2(1+\sqrt2)\) and \(\kappa\) be the condition number. We prove the iteration lower bound \(\Omega\left(\kappa^{\frac{1}{p_{\mathrm{sil}}}-o(1)}\log\frac1\delta\right)\)for both relative squared distance and relative function error, uniformly over \(0<\delta<1\) and sufficiently large \(\kappa\). This matches the polynomial exponent of \(\kappa\) for the Silver stepsize schedule … Read more

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

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 , , , , , ,

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, for the first time, the ability to consider more than two sets, a task which has been in the mind of researchers for many years … 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

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:\ \mathrm{there\ exists}\ x\in S\ \mathrm{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 that 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

Solving Quasi-Variational Inequalities Using the Progressive Decoupling of Linkages

Categories Complementarity and Variational Inequalities, Convex Optimization, Game Theory Tags

Inspired by the progressive decoupling of linkages methodology for optimization and variational inequalities, we propose an algorithm for solving quasi-variational inequalities as a sequence of variational inequalities. Our method is shown to converge locally under some regularity conditions and globally when such conditions hold throughout the entire domain. Separately, under other type of assumptions, global … Read more

Sharp Singularity-Degree Bounds for Equality-Generated SDP–RLT Relaxations of Binary Programs

Categories Convex Optimization, Semi-definite Programming

Singularity degree is an important measure of semidefinite programming (SDP) degeneracy, but it is generally unavailable a priori from the problem data. We augment the Shor relaxation of binary sets \(\{x\in\{0,1\}^n:Ax=b\}\) with the first-level Reformulation–Linearization Technique (RLT) equations generated by the defining linear equalities. For the resulting equality-generated SDP–RLT relaxation, we determine the exact worst-case … Read more

Two Spectral Gaps: Decentralized Optimization over Intersections of Local Convex Sets

Categories Convex Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

We study decentralized minimization of an average of strongly convex, smooth local objectives over an intersection of agent-private closed convex sets, where each agent knows only its own objective and its own set and agents communicate over a gossip network. We show that the complexity is controlled by a single geometric scalar, which we call … Read more

Implicit Primal-Dual Guarantees in Unconstrained First-Order Minimization

Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

This work considers the design of first-order convex optimization algorithms and convergence proofs. In particular, we consider nonsmooth Lipschitz and smooth problems accessed through a subgradient or gradient oracle, respectively. For the general class of fixed-step first-order methods, prior work on Performance Estimation Problems (PEPs) has shown that structured, tight convergence proofs typically exist. Under … Read more