Full Convergence of Regularized Methods for Unconstrained Optimization

Typically, the sequence of points generated by an optimization algorithm may have multiple limit points. Under convexity assumptions, however, (sub)gradient methods are known to generate a convergent sequence of points. In this paper, we extend the latter property to a broader class of algorithms. Specifically, we study unconstrained optimization methods that use local quadratic models … Read more

Dual certificates of primal cone membership

We discuss easily verifiable cone membership certificates, that is, certificates proving relations of the form \( b\in K \) for convex cones \(K\) that consist of vectors in the dual cone \(K^*\). Vectors in the dual cone are usually associated with separating hyperplanes, and so they are interpreted as certificates of non-membership in the standard … Read more

Algorithmic Approaches for Identifying the Trade-off between Pessimism and Optimism in a Stochastic Fixed Charge Facility Location Problem

We introduce new algorithms to identify the trade-off (TRO) between adopting a distributional belief and hedging against ambiguity when modeling uncertainty in a capacitated fixed charge facility location problem (CFLP). We first formulate a TRO model for the CFLP (TRO-CFLP), which determines the number of facilities to open by minimizing the fixed establishment cost and … Read more

Worst-Case Complexity of High-Order Algorithms for Pareto-Front Reconstruction

In this paper, we are concerned with a worst-case complexity analysis of a-posteriori algorithms for unconstrained multiobjective optimization. Specifically, we propose an algorithmic framework that generates sets of points by means of $p$th-order models regularized with a power $p+1$ of the norm of the step. Through a tailored search procedure, several trial points are generated … Read more

ASMOP: Additional sampling stochastic trust region method for multi-objective problems

We consider an unconstrained multi-criteria optimization problem with finite sum objective functions. The proposed algorithm belongs to a non-monotone trust-region framework where additional sampling approach is used to govern the sample size and the acceptance of a candidate point. Depending on the problem, the method can result in a mini-batch or an increasing sample size … Read more

A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

Relaxations of KKT Conditions do not Strengthen Finite RLT and SDP-RLT Bounds for Nonconvex Quadratic Programs

We consider linear and semidefinite programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality … Read more

SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy

We consider the Lasserre hierarchy for computing bounds on the stability number of graphs. The semidefinite programs (SDPs) arising from this hierarchy involve large matrix variables and many linear constraints, which makes them difficult to solve using interior-point methods. We propose solving these SDPs using the alternating direction method of multipliers (ADMM). When the second … Read more

On Local Search in Bilevel Mixed-Integer Linear Programming

Two-level hierarchical decision-making problems, where a leader’s choice influences a follower’s action, arise across key business and public-sector domains, from market design and pricing to defense. These problems are typically modeled as bilevel programs and are known to be notoriously hard to solve at scale. In single-level combinatorial optimization, especially for challenging instances, local search … Read more

Statistical Inference for Distributed Contextual Multi-armed Bandit

In this paper, we study the online statistical inference of distributed contextual multi-armed bandit problems, where the agents collaboratively learn an optimal policy by exchanging their local estimates of the global parameters with neighbors over a communication network. We propose a distributed online decision making algorithm, which balances the exploration and exploitation dilemma via the … Read more