Complexity theory – Optimization Online

prunAdag: an adaptive pruning-aware gradient method

Published: 2025/02/12

Data Science Algorithms, Nonlinear Optimization adaptive first-order methods, Complexity theory, Model pruning, objective-function-free optimization (OFFO)

A pruning-aware adaptive gradient method is proposed which classifies the variables in two sets before updating them using different strategies. This technique extends the “relevant/irrelevant” approach of Ding (2019) and Zimmer et al. (2022) and allows a posteriori sparsification of the solution of model parameter fitting problems. The new method is proved to be convergent … Read more

On the Complexity of Separation From the Knapsack Polytope

Published: 2021/11/11

Alberto Del Pia

Jeff Linderoth

Haoran Zhu

0-1 Programming Complexity theory, knapsack polytope, separation problem

We close three open problems in the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1,k)-configuration inequalities, and weight inequalities are all NP-complete. We also give a number of special cases where the separation problem can be solved in polynomial time. ArticleDownload View … Read more