News

Newton-type algorithms for inverse optimization

Inverse optimization problems have long been the focus of research due to their wide applicability in both theory and practice. Since the pioneering work of Burton and Toint, countless of applications and extensions emerged.

In a series of two papers, we give min-max characterizations and simple algorithms for inverse optimization problems under various objectives. In Part I, titled Newton-type algorithms for inverse optimization I: weighted bottleneck Hamming distance and $\ell_\infty$-norm objectives, we set up the basics of a general framework that uses a Newton-type approach for finding an optimal deviation vector, and derive algorithms for the weighted bottleneck Hamming distance and weighted $\ell_\infty$-norm objectives that follow the proposed scheme.

Optimizing with respect to $\ell_\infty$-norm may not be satisfactory in situations when the goal is to modify the costs in a fair or balanced manner, and the magnitude of the individual changes is not relevant. To overcome this, in Part II, titled Newton-type algorithms for inverse optimization II: weighted span objective, we consider a novel objective function that measures the difference between the largest and the smallest weighted coordinates of the deviation vector, called the weighted span.