The boosted Frank-Wolfe algorithm accelerates the classical Frank-Wolfe algorithm by better aligning the update direction with the negative gradient. Its analysis, however, has been limited to deterministic convex problems, with step sizes that require either line search or knowledge of the Lipschitz constant of the gradient. We develop a novel step size strategy that does … Read more
We study a class of constrained nonconvex-nonconcave minimax optimization problems in which the inner maximization involves potentially complex constraints. Under the assumption that the inner problem of a novel lifted minimax reformulation satisfies a local Kurdyka-Łojasiewicz (KL) condition, we show that the maximal function of the original problem enjoys a local generalized Hölder smoothness property. … Read more
Direct search is one of the most popular derivative-free optimization paradigms, that relies on exploring the variable space using polling directions. To analyze and implement direct search, one typically relies on positive spanning sets. This concept is somewhat decorrelated from interpolation-based sets used in model-based algorithms, another class of derivative-free optimization methods. This discrepancy is … Read more
We introduce a sequential version of the minimum $s$-$t$ cut problem, defined by a directed graph with source $s$ and sink $t$, and nonnegative random variables for each arc representing arc weights. We start with a working set $S = \{s\}$ and observe weight realizations for outgoing arcs from $S$ only. We choose to either … Read more
Lagrangian relaxation is a well-established technique for deriving strong bounds in single-objective discrete optimization. Its generalization to the multiobjective setting is not straightforward, as preserving the multiobjective structure leads to bound sets rather than scalar bounds. Recent studies show the existence of Lagrange multipliers that can yield tighter bound sets than those obtained from convex … Read more
The binary reflected Gray code orders the vertices of the unit hypercube along a Hamiltonian path in which consecutive vertices differ in exactly one coordinate. While Gray codes have been extensively studied from a combinatorial perspective, much less is known about the polyhedral structure of convex hulls of contiguous subpaths of this order. This paper … Read more
In this paper, we study nonsmooth composite optimization problems under heavy-tailed noise, with the objective being a summation of a nested function and a nonsmooth convex regularizer. We propose stochastic proximal approximation methods incorporating a normalization technique to handle the potential challenges caused by the nonsmooth regularizer and heavy-tailed noise. For the case where the … Read more
In this work, we study optimization specified only through a comparison oracle: given two points, it reports which one is preferred. We call it function-free optimization because we do not assume access to, nor the existence of, a canonical application-given objective function. Instead, our goal is to find a most-preferred feasible point, which we call … Read more
This paper resolves an open problem posed in the literature by proving that, in dual-sourcing inventory systems, the optimality gap of tailored base-surge (TBS) policies decays exponentially with the regular source lead time, with the express-source lead time fixed. In contrast to the existing approach, which relies on conditional Jensen inequalities and a vanishing-discount argument … Read more
This work introduces an inexact cubic regularization method with adaptive reuse of Hessian approximations to solve general non-convex optimization problems. In the proposed approach, the gradient is computed inexactly and updated at every iteration, whereas the Hessian approximation is updated at a specific iteration and then reused for $m$ subsequent iterations (a lazy strategy), where … Read more