Multistage stochastic programs are a viable modeling tool for sequential decisions conditional on information revealed at different points in time (stages). However, as the number of stages increases their applicability is soon halted by the curse of dimensionality. A typical, sometimes forced, alternative is to approximate stages by their expected values thus considering fewer stages … Read more
For binary polynomial optimization problems (POPs) of degree $d$ with $n$ variables, we prove that the $\lceil(n+d-1)/2\rceil$th semidefinite (SDP) relaxation in Lasserre’s hierarchy of the SDP relaxations provides the exact optimal value. If binary POPs involve only even-degree monomials, we show that it can be further reduced to $\lceil(n+d-2)/2\rceil$. This bound on the relaxation order … Read more
We consider graph three-partitions with the objective of minimizing the number of edges between the first two partition sets while keeping the size of the third block small. We review most of the existing relaxations for this min-cut problem and focus on a new class of semidefinite relaxations, based on matrices of order $2n$ which … Read more
We present three new approximate versions of alternating direction method of multipliers (ADMM), all of which require only knowledge of subgradients of the subproblem objectives, rather than bounds on the distance to the exact subproblem solution. One version, which applies only to certain common special cases, is based on combining the operator-splitting analysis of the … Read more
Let $\F$ be a quadratically constrained, possibly nonconvex, bounded set, and let $\E_1, \ldots, \E_l$ denote ellipsoids contained in $\F$ with non-intersecting interiors. We prove that minimizing an arbitrary quadratic $q(\cdot)$ over $\G := \F \setminus \cup_{k=1}^\ell \myint(\E_k)$ is no more difficult than minimizing $q(\cdot)$ over $\F$ in the following sense: if a given semidefinite-programming … Read more
This paper describes a regularized variant of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex programs. It is shown that the pointwise iteration-complexity of the new method is better than the corresponding one for the standard ADMM method and that, up to a logarithmic term, is identical to the ergodic iteration-complexity … Read more
Stochastic approximation techniques play an important role in solving many problems encountered in machine learning or adaptive signal processing. In these contexts, the statistics of the data are often unknown a priori or their direct computation is too intensive, and they have thus to be estimated online from the observed signals. For batch optimization of … Read more
In this article we present a version of the proximal alternating direction method for a convex problem with linear constraints and a separable objective function, in which the standard quadratic regularizing term is replaced with an interior proximal metric for those variables that are required to satisfy some additional convex constraints. Moreover, the proposed method … Read more
In this paper, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. Given a MILP instance of one of these three … Read more
In this paper, we present a conditional gradient type (CGT) method for solving a class of composite optimization problems where the objective function consists of a (weakly) smooth term and a (strongly) convex regularization term. While including a strongly convex term in the subproblems of the classical conditional gradient (CG) method improves its rate of … Read more