An algorithm for generating Lagrangian bound sets in Multiobjective Integer Programming

Categories Integer Programming, Multi-Criteria Optimization Tags , , ,

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

Convex Hulls of Binary Reflected Gray Code Intervals

Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra Tags , ,

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

Normalized stochastic proximal approximation methods for nonsmooth composite optimization under heavy-tailed noise

Categories Nonlinear Optimization, Nonsmooth Optimization

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

Function-free Optimization via Comparison Oracles

Categories Convex Optimization, Nonlinear Optimization Tags , , ,

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

Optimality Gap of Tailored Base-Surge Policies Decays Exponentially in Regular-Source Lead Times for Dual-Sourcing Models

Categories Dynamic Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

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

Inexact Cubic Regularization Method with Adaptive Reuse of Hessian Approximations

Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

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

Stochastic block coordinate and function alternation for multi-objective optimization and learning

Categories Multi-Criteria Optimization Tags , , ,

Multi-objective optimization is central to many engineering and machine learning applications, where multiple objectives must be optimized in balance. While multi-gradient based optimization methods combine these objectives in each step, such methods require computing gradients with respect to all variables at every iteration, resulting in high computational costs in large-scale settings. In this work, we … Read more

Betweenness Central Nodes Under Uncertainty: An Absorbing Markov Chain Approach

Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Robust Optimization Tags , , , , , , ,

We propose a betweenness centrality measure and algorithms for stochastic networks, where edges can fail and weights vary across realizations, making the most central node random. Our approach models the sequence of reported central nodes as an absorbing Markov chain and measures node importance by the share of pre-absorption time spent at each node. This … Read more

Accuracy and Relationships of Quadratic Models in Derivative-free Optimization

Categories Nonlinear Optimization Tags , ,

We study three quadratic models in model-based derivative-free optimization: the minimum norm (MN), minimum Frobenius norm (MFN), and quadratic generalized simplex derivative (QS) models. Despite their widespread use, their approximation accuracy and relationships have not been systematically explored. We establish fully linear error bounds for all three models, removing the uniformly bounded model Hessian assumption … Read more

Inexact proximal point method for piecewise-star-convex function

Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , ,

We propose and analyze an inexact proximal point method for minimizing locally Lipschitz functions on Euclidean spaces with a piecewise star-convex structure. More precisely, the space is covered by finitely many closed convex sets, and on each set the objective function satisfies a star-convex inequality with respect to the minimizers of its restriction. This class … Read more