In this note, we reduce an instance of the partition problem to a dynamic lot sizing problem in polynomial time, and show that solving the latter problem solves the former problem. We further show that the instance of the partition problem can be solved using polynomial number of addition, multiplication and sort operations in input … Read more
This paper presents a game-theoretical framework for data classification and network discovery, focusing on pairwise influences in multivariate choices. The framework consists of two complementary games in which individuals, connected through a signed weighted graph, exhibit network similarity. A voting rule captures the influence of an individual’s neighbors, categorized as attractive (friend-like) or repulsive (enemy-like), … Read more
In this paper, we introduce an approach for obtaining probabilistically guaranteed upper and lower bounds on the true optimal value of stopping problems. Bounds of existing simulation-and-regression approaches, such as those based on least squares Monte Carlo and information relaxation, are stochastic in nature and therefore do not come with a finite sample guarantee. Our … Read more
Dealing with uncertainty in optimization parameters is an important and longstanding challenge. Typically, uncertain parameters are predicted accurately, and then a deterministic optimization problem is solved. However, the decisions produced by this so-called predict-then-optimize procedure can be highly sensitive to uncertain parameters. In this work, we contribute to recent efforts in producing decision-focused predictions, i.e., to … Read more
This study addresses discrete network design problems under traffic equilibrium conditions or DNDPs. Given a network and a budget, DNDPs aim to model all-or-nothing decisions such as link addition to minimize network congestion effects. Congestion is measured using traffic equilibrium theory where link travel times are modeled as convex flow-dependent functions and where users make … Read more
In this work we propose a general nonmonotone line-search method for nonconvex multi-objective optimization problems with convex constraints. At the \(k\)th iteration, the degree of nonmonotonicity is controlled by a vector \(\nu_{k}\) with nonnegative components. Different choices for \(\nu_{k}\) lead to different nonmonotone step-size rules. Assuming that the sequence \(\left\{\nu_{k}\right\}_{k\geq 0}\) is summable, and that … Read more
We introduce a framework to accelerate the convergence of gradient-based methods with online learning. The framework learns to scale the gradient at each iteration through an online learning algorithm and provably accelerates gradient-based methods asymptotically. In contrast with previous literature, where convergence is established based on worst-case analysis, our framework provides a strong convergence guarantee … Read more
Over the past two decades, descent methods have received substantial attention within the multiobjective optimization field. Nonetheless, both theoretical analyses and empirical evidence reveal that existing first-order methods for multiobjective optimization converge slowly, even for well-conditioned problems, due to the objective imbalances. To address this limitation, we incorporate curvature information to scale each objective within … Read more
We consider a two-player Nash game in which each player represents a fleet of unmanned aerial vehicles. Each fleet is supposed to distribute information among fleet members, while simultaneously trying to prevent the opposite fleet from achieving this. Using the electro-magnetic spectrum’s properties, we model each fleet’s task as a nonlinear Nash game. By reformulating … Read more
This paper develops a parameter-free adaptive proximal bundle method with two important features: 1) adaptive choice of variable prox stepsizes that “closely fits” the instance under consideration; and 2) adaptive criterion for making the occurrence of serious steps easier. Computational experiments show that our method performs substantially fewer consecutive null steps (i.e., a shorter cycle) … Read more