MPC 2024 - Issue 3
Refine
Year of publication
- 2024 (6)
Document Type
- Article (6)
Language
- English (6)
Has Fulltext
- yes (6)
We study a primal-dual interior point method specialized to clustered low-rank semidefinite programs requiring high precision numerics, which arise from certain multivariate polynomial (matrix) programs through sums-of-squares characterizations and sampling. We consider the interplay of sampling and symmetry reduction as well as a greedy method to obtain numerically good bases and sample points. We apply this to the computation of three-point bounds for the kissing number problem, for which we show a significant speedup. This allows for the computation of improved kissing number bounds in dimensions 11 through 23. The approach performs well for problems with bad numerical conditioning, which we show through new computations for the binary sphere packing problem.
In this paper, we introduce a new effective matrix adaptation evolution strategy
(MADFO) for noisy derivative-free optimization problems. Like every MAES solver,
MADFO consists of three phases: mutation, selection and recombination. MADFO
improves the mutation phase by generating good step sizes, neither too small not
too large, that increase the probability of selecting mutation points with small inexact
function values in the selection phase. In the recombination phase, a recombination
point with lowest inexact function value found among all evaluated points so far may
be found by a new randomized non-monotone line search method and accepted as
the best point. If no best point is found, a heuristic point may be accepted as the best
point. We compare MADFO with state-of-the-art DFO solvers on noisy test problems
obtained by adding various kinds and levels of noise to all unconstrained CUTEst
test problems with dimensions n ≤ 20, and find that MADFO has the highest number
of solved problems
Model training algorithms which observe a small portion of the training set in each
computational step are ubiquitous in practical machine learning, and include both
stochastic and online optimization methods. In the vast majority of cases, such algo-
rithms typically observe the training samples via the gradients of the cost functions
the samples incur. Thus, these methods exploit are the slope of the cost functions via
their first-order approximations. To address limitations of gradient-based methods,
such as sensitivity to step-size choice in the stochastic setting, or inability to exploit
small function variability in the online setting, several streams of research attempt
to exploit more information about the cost functions than just their gradients via the
well-known proximal operators. However, implementing such methods in practice
poses a challenge, since each iteration step boils down to computing the proximal
operator, which may not be as easy as computing a gradient. In this work we devise
a novel algorithmic framework, which exploits convex duality theory to achieve both
algorithmic efficiency and software modularity of proximal operator implementations,
in order to make experimentation with incremental proximal optimization algorithms
accessible to a larger audience of researchers and practitioners, by reducing the gap
between their theoretical description in research papers and their use in practice.
We provide a reference Python implementation for the framework developed in this
paper as an open source library at on GitHub (https://github.com/alexshtf/inc_prox_
pt/releases/tag/prox_pt_paper) Shtoff (Efficient implementation of incremental proxi-
mal point methods arXiv:2205.01457, 2024), along with examples which demonstrate
our implementation on a variety of problems, and reproduce the numerical experiments
in this paper. The pure Python reference implementation is not necessarily the most
efficient, but is a basis for creating efficient implementations by combining Python
with a native backend.
PEPit is a python package aiming at simplifying the access to worst-case analy-
ses of a large family of first-order optimization methods possibly involving gradient,
projection, proximal, or linear optimization oracles, along with their approximate, or
Bregman variants. In short, PEPit is a package enabling computer-assisted worst-
case analyses of first-order optimization methods. The key underlying idea is to
cast the problem of performing a worst-case analysis, often referred to as a perfor-
mance estimation problem (PEP), as a semidefinite program (SDP) which can be
solved numerically. To do that, the package users are only required to write first-order
methods nearly as they would have implemented them. The package then takes care
of the SDP modeling parts, and the worst-case analysis is performed numerically
via standard solvers.
PyEPO: a PyTorch-based end-to-end predict-then-optimize library for linear and integer programming
(2024)
In deterministic optimization, it is typically assumed that all problem parameters are
fixed and known. In practice, however, some parameters may be a priori unknown
but can be estimated from contextual information. A typical predict-then-optimize
approach separates predictions and optimization into two distinct stages. Recently,
end-to-end predict-then-optimize has emerged as an attractive alternative. This work
introduces the
PyEPO package, a
PyTorch-based end-to-end predict-then-optimize
library in Python. To the best of our knowledge,
PyEPO (pronounced like pineapple
with a silent “n") is the first such generic tool for linear and integer programming
with predicted objective function coefficients. It includes various algorithms such as
surrogate decision losses, black-box solvers, and perturbated methods.
PyEPO offers
a user-friendly interface for defining new optimization problems, applying state-of-
the-art algorithms, and using custom neural network architectures. We conducted
experiments comparing various methods on problems such as the Shortest Path, the
Multiple Knapsack, and the Traveling Salesperson Problem, discussing empirical
insights that may guide future research.
PyEPO and its documentation are available
at https://github.com/khalil-research/PyEPO.