Newton-type algorithms for inverse optimization: weighted bottleneck Hamming distance and ℓ ∞ -norm objectives

Area of Science:

• Optimization Theory
• Combinatorial Optimization
• Algorithm Design

Background:

• Inverse optimization problems involve adjusting parameters so a given solution becomes optimal.
• This research focuses on the minimum-cost setting with linear cost functions.
• The study considers modifying costs using a deviation vector within specified bounds.

Purpose of the Study:

• To develop algorithms for inverse optimization problems under two specific objectives: weighted bottleneck Hamming distance and weighted L-infinity norm.
• To analyze the computational complexity of finding optimal deviation vectors for these objectives.
• To explore a general model with bounded coordinates for the deviation vector.

Main Methods:

• For the weighted bottleneck Hamming distance: A purely combinatorial algorithm is presented.
• For the weighted L-infinity norm: A min-max characterization is derived, and a pseudo-polynomial algorithm is provided for unit weights.
• Both methods assume the availability of an algorithm for the underlying combinatorial optimization problem.

Main Results:

• A strongly polynomial time algorithm for the weighted bottleneck Hamming distance objective.
• A pseudo-polynomial time algorithm for the weighted L-infinity norm objective, which is strongly polynomial for unit weights.
• The algorithms are designed for a general model with bounded deviation vector coordinates.

Conclusions:

• Efficient algorithms are provided for solving inverse minimum-cost optimization problems with specific distance metrics.
• The research contributes to the understanding of computational complexity in inverse optimization.
• The findings offer practical methods for adjusting problem parameters to achieve desired optimal solutions.