SIAM Journal on Optimization

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, which utilize the particular structure of ...

We study distributed multiagent optimization over graphs. We consider the minimization of $F+G$ subject to convex constraints, where $F$ is the smooth strongly convex sum of the agent's losses and $G$ is a nonsmooth convex function. We build on ...

We present ${\it Free-MESSAGE}^{,p}$, the first zeroth-order algorithm for (weakly) convex mean-semideviation-based risk-aware learning, which is also the first-ever three-level zeroth-order compositional stochastic optimization algorithm. Using a nontrivial ...

Nonconvex derivative-free time-consuming objectives are often optimized using “black-box” optimization. These approaches assume very little about the objective. While broadly applicable, they typically require more evaluations than methods exploiting ...

We study numerical optimization algorithms that use zeroth-order information to minimize time-varying geodesically convex cost functions on Riemannian manifolds. In the Euclidean setting, zeroth-order algorithms have received a lot of attention in both ...

A successful computational approach for solving large-scale positive semidefinite (PSD) programs is to enforce PSD-ness on only a collection of submatrices. For our study, we let $\mathcal{S}^{n,k}$ be the convex cone of $n\times n$ symmetric matrices ...

We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $\alpha(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim., 12 (2002), pp. 875--892], ...

In this paper, we study smooth stochastic multilevel composition optimization problems, where the objective function is a nested composition of $T$ functions. We assume access to noisy evaluations of the functions and their gradients, through a stochastic ...

We consider the problem of minimizing an objective function that is the sum of a convex function and a group sparsity-inducing regularizer. Problems that integrate such regularizers arise in modern machine learning applications, often for the purpose of ...

This paper considers an $n$-player stochastic Nash equilibrium problem (NEP) in which the $i$th player minimizes a composite objective $f_i( \bullet ,x_{-i}) + r_i( \bullet )$, where $f_i$ is an expectation-valued smooth function, $x_{-i}$ is a tuple ...

Let $b$ be a nonnegative vector in a Euclidean Jordan algebra $\mathbb{E}$. Its condition number $\kappa(b)$ is assumed to be high, possibly infinite. The condition number of a nonnegative vector is defined as the ratio between the largest and the ...

A classical approach for obtaining valid inequalities for a set involves the analysis of relaxations constructed using aggregations of the inequalities that describe such a set. When the set is described by linear inequalities, thanks to the Farkas lemma,...

We consider the problem of minimizing a high-dimensional objective function, which may include a regularization term, using only (possibly noisy) evaluations of the function. Such optimization is also called derivative-free, zeroth-order, or black-box ...

We consider a distributionally robust second-order stochastic dominance constrained optimization problem. We require the dominance constraints to hold with respect to all probability distributions in a Wasserstein ball centered at the empirical ...

This paper establishes finite active-set identification of an almost cyclic 2-coordinate descent method for problems with one linear coupling constraint and simple bounds. First, general active-set identification results are stated for nonconvex objective ...

The arithmetic mean/geometric mean inequality (AM/GM inequality) facilitates classes of nonnegativity certificates and of relaxation techniques for polynomials and, more generally, for exponential sums. Here, we present a first systematic study of the AM/...

The aim of this note is to give an elementary proof of linear convergence of the Sinkhorn algorithm for the entropic regularization of multimarginal optimal transport in the setting of general probability spaces. The proof simply relies on (i) the fact ...

We present two classes of differentially private optimization algorithms derived from the well-known accelerated first-order methods. The first algorithm is inspired by Polyak's heavy ball method and employs a smoothing approach to decrease the ...

We consider optimization problems on Riemannian manifolds with equality and inequality constraints, which we call Riemannian nonlinear optimization (RNLO) problems. Although they have numerous applications, the existing studies on them are limited ...

In this paper, we introduce a definition of Fenchel conjugate and Fenchel biconjugate on Hadamard manifolds based on the tangent bundle. Our definition overcomes the inconvenience that the conjugate depends on the choice of a certain point on the manifold, ...

Random projection techniques based on the Johnson--Lindenstrauss lemma are used for randomly aggregating the constraints or variables of optimization problems while approximately preserving their optimal values, which leads to smaller-scale optimization ...

We develop a trust-region method for minimizing the sum of a smooth term (f) and a nonsmooth term (h), both of which can be nonconvex. Each iteration of our method minimizes a possibly nonconvex model of (f + h) in a trust region. The model coincides with (...

Chance constraints provide a principled framework to mitigate the risk of high-impact extreme events by modifying the controllable properties of a system. The low probability and rare occurrence of such events, however, impose severe sampling and ...

This paper is concerned with the column $\ell_{2,0}$-regularized factorization model of low-rank matrix recovery problems and its computation. The column $\ell_{2,0}$-norm of factor matrices is introduced to promote column sparsity of factors and low-rank ...

We consider finite- and infinite-horizon Markov decision processes (MDPs) with unknown state-transition probabilities. They are assumed to belong to certain ambiguity sets, and the goal is to maximize the worst-case expected total discounted reward over all ...

Given the noisy pairwise measurements among a set of unknown group elements, how does one recover them efficiently and robustly? This problem, known as group synchronization, has drawn tremendous attention in the scientific community. In this work, we ...

Numerical continuation in the context of optimization can be used to mitigate convergence issues due to a poor initial guess. In this work, we extend this idea to Riemannian optimization problems, that is, the minimization of a target function on a ...

We consider the popular and classical method of alternating projections for finding a point in the intersection of two closed sets. By situating the algorithm in a metric space, equipped only with well-behaved geodesics and angles (in the sense of ...

The focus of this paper is on stochastic variational inequalities (VI) under Markovian noise. A prominent application of our algorithmic developments is the stochastic policy evaluation problem in reinforcement learning. Prior investigations in the ...

We study solution sensitivity for nonlinear programs (NLPs) whose structures are induced by graphs. These NLPs arise in many applications such as dynamic optimization, stochastic optimization, optimization with partial differential equations, and network ...