|
In inverse optimization problems, the goal is to modify the costs in an underlying optimization problem in such a way that a given solution becomes optimal, while the difference between the new and the original cost functions, called the deviation vector, is minimized with respect to some objective function. The $\ell_1$- and $\ell_{\infty}$-norms are standard objectives used to measure the size of the deviation. Minimizing the $\ell_1$-norm is a natural way of keeping the total change of the cost function low, while the $\ell_{\infty}$-norm achieves the same goal coordinate-wise. Nevertheless, none of these objectives is suitable to provide a balanced or fair change of the costs.
In this paper, we initiate the study of a new objective that measures the difference between the largest and the smallest weighted coordinates of the deviation vector, called the weighted span. We provide a Newton-type algorithm for finding one that runs in strongly polynomial time in the case of unit weights.
Bibtex entry:
| AUTHOR | = | {B{\'e}rczi, Krist{\'o}f and Mendoza-Cadena Mirabel, Lydia and Varga, Kitti}, |
| TITLE | = | { Newton-type algorithms for inverse optimization: weighted span objective}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2023}, |
| NUMBER | = | {TR-2023-16} |