38 results
Showing 1–20 · 0.74 seconds · RSS
Open Journal of Mathematical Optimization
Scopus
ISSN 2777-5860 · Université de Montpellier · 38 articles in the index
-
Journal Article
Iterative Linear Quadratic Optimization for Nonlinear Control: Differentiable Programming Algorithmic Templates
Iterative optimization algorithms depend on access to information about the objective function. In a differentiable programming framework, this information, such as gradients, can be automatically derived from the computational graph. We explore how nonlinear control algorithms, often employing…
-
Journal Article
Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizes
In this work, we propose an adaptive variation on the classical Heavy-ball method for convex quadratic minimization. The adaptivity crucially relies on so-called “Polyak step-sizes”, which consists of using the knowledge of the optimal value of the optimization problem at hand instead of problem…
-
Journal Article
Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions
We consider the problem of linearizing a pseudo-Boolean function $f : \lbrace 0,1\rbrace ^n \rightarrow \mathbb{R}$ by means of $k$ Boolean functions. Such a linearization yields an integer linear programming formulation with only $k$ auxiliary variables. This motivates the definition of the…
-
Journal Article
First order algorithms for computing linear and polyhedral estimates
It was recently shown [6, 8] that “properly built” linear and polyhedral estimates nearly attain minimax accuracy bounds in the problem of recovery of unknown signal from noisy observations of linear images of the signal when the signal set is an ellitope. However, design of nearly optimal…
-
Journal Article
Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics
Optimizing the transient control of gas networks is a highly challenging task. The corresponding model incorporates the combinatorial complexity of determining the settings for the many active elements as well as the non-linear and non-convex nature of the physical and technical principles of gas…
-
Journal Article
Cardinality-constrained structured data-fitting problems
A memory-efficient solution framework is proposed for the cardinality-constrained structured data-fitting problem. Dual-based atom-identification rules reveal the structure of the optimal primal solution from near-optimal dual solutions, which allows for a simple and computationally efficient…
-
Journal Article
Tight analyses for subgradient descent I: Lower bounds
Consider the problem of minimizing functions that are Lipschitz and convex, but not necessarily differentiable. We construct a function from this class for which the $Tþ$ iterate of subgradient descent has error $\Omega (\log (T)/\sqrt{T})$. This matches a known upper bound of $O(\log…
-
Journal Article
An interior proximal gradient method for nonconvex optimization
We consider structured minimization problems subject to smooth inequality constraints and present a flexible algorithm that combines interior point (IP) and proximal gradient schemes. While traditional IP methods cannot cope with nonsmooth objective functions and proximal algorithms cannot handle…
-
Journal Article
Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty
Given a nominal combinatorial optimization problem, we consider a robust two-stages variant with polyhedral cost uncertainty, called Decision-Dependent Information Discovery (DDID). In the first stage, DDID selects a subset of uncertain cost coefficients to be observed, and in the second-stage…
-
Journal Article
Adaptive Cut Selection in Mixed-Integer Linear Programming
Cutting plane selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter…
-
Journal Article
Short Paper - A Note on Robust Combinatorial Optimization with Generalized Interval Uncertainty
In this paper, we consider a robust combinatorial optimization problem with uncertain weights and propose an uncertainty set that generalizes interval uncertainty by imposing lower and upper bounds on deviations of subsets of items. We prove that if the number of such subsets is fixed and the…
-
Journal Article
Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
We study the linear convergence of the primal-dual hybrid gradient method. After a review of current analyses, we show that they do not explain properly the behavior of the algorithm, even on the most simple problems. We thus introduce the quadratic error bound of the smoothed gap, a new regularity…
-
Journal Article
Convergence Rates of Gradient Methods for Convex Optimization in the Space of Measures
We study the convergence rate of Bregman gradient methods for convex optimization in the space of measures on a $d$-dimensional manifold. Under basic regularity assumptions, we show that the suboptimality gap at iteration $k$ is in $O(\log (k)k^{-1})$ for multiplicative updates, while it is in…
-
Journal Article
Inertial-relaxed splitting for composite monotone inclusions
In a similar spirit of the extension of the proximal point method developed by Alves et al. [2], we propose in this work an Inertial-Relaxed primal-dual splitting method to address the problem of decomposing the minimization of the sum of three convex functions, one of them being smooth, and…
-
Journal Article
The continuous quadrant penalty formulation of logical constraints
Could continuous optimization address efficiently logical constraints? We propose a continuous-optimization alternative to the usual discrete-optimization (big-M and complementary) formulations of logical constraints, that can lead to effective practical methods. Based on the simple idea of guiding…
-
Journal Article
The backtrack Hölder gradient method with application to min-max and min-min problems
We present a new algorithm to solve min-max or min-min problems out of the convex world. We use rigidity assumptions, ubiquitous in learning, making our method – the backtrack Hölder algorithm applicable to many optimization problems. Our approach takes advantage of hidden regularity properties and…
-
Journal Article
Cycle-based formulations in Distance Geometry
The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension $K$, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a…
-
Journal Article
Short Paper - A note on the Frank–Wolfe algorithm for a class of nonconvex and nonsmooth optimization problems
Frank and Wolfe’s celebrated conditional gradient method is a well-known tool for solving smooth optimization problems for which minimizing a linear function over the feasible set is computationally cheap. However, when the objective function is nonsmooth, the method may fail to compute a…
-
Journal Article
A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives
In this short note, we provide a simple version of an accelerated forward-backward method (a.k.a. Nesterov’s accelerated proximal gradient method) possibly relying on approximate proximal operators and allowing to exploit strong convexity of the objective function. The method supports both relative…
-
Journal Article
Screening for a Reweighted Penalized Conditional Gradient Method
The conditional gradient method (CGM) is widely used in large-scale sparse convex optimization, having a low per iteration computational cost for structured sparse regularizers and a greedy approach for collecting nonzeros. We explore the sparsity acquiring properties of a general penalized CGM…