Scholarlink

<p>In inverse optimization problems, we are given a feasible solution to an underlying optimization problem, and the goal is to modify the problem parameters so that the given input solution becomes optimal. In the minimum-cost setting, the underlying optimization problem is endowed with a linear cost function, and the goal is to modify the costs by a small deviation vector so that the input solution becomes optimal. The difference between the new and the original cost functions can be measured in several ways. In this paper, we focus on two objectives: the weighted bottleneck Hamming distance and the weighted <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11590_2024_2183_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell _{\infty }\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mi>∞</mi> </msub> </math></EquationSource> </InlineEquation>-norm. We consider a general model in which the coordinates of the deviation vector are required to fall within given lower and upper bounds. For the weighted bottleneck Hamming distance objective, we present a simple, purely combinatorial algorithm that determines an optimal deviation vector in strongly polynomial time. For the weighted <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11590_2024_2183_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell _{\infty }\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mi>∞</mi> </msub> </math></EquationSource> </InlineEquation>-norm objective, we give a min-max characterization for the optimal solution, and provide a pseudo-polynomial algorithm for finding an optimal deviation vector that runs in strongly polynomial time in the case of unit weights. For both objectives, we assume that an algorithm with the same time complexity for solving the underlying combinatorial optimization problem is available.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Newton-type algorithms for inverse optimization: weighted bottleneck Hamming distance and \(\ell _\infty\)-norm objectives

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年1月21日

查看全文
  • Kristóf Bérczi,
  • Lydia Mirabel Mendoza-Cadena,
  • Kitti Varga

摘要

In inverse optimization problems, we are given a feasible solution to an underlying optimization problem, and the goal is to modify the problem parameters so that the given input solution becomes optimal. In the minimum-cost setting, the underlying optimization problem is endowed with a linear cost function, and the goal is to modify the costs by a small deviation vector so that the input solution becomes optimal. The difference between the new and the original cost functions can be measured in several ways. In this paper, we focus on two objectives: the weighted bottleneck Hamming distance and the weighted \(\ell _{\infty }\) ℓ ∞ -norm. We consider a general model in which the coordinates of the deviation vector are required to fall within given lower and upper bounds. For the weighted bottleneck Hamming distance objective, we present a simple, purely combinatorial algorithm that determines an optimal deviation vector in strongly polynomial time. For the weighted \(\ell _{\infty }\) ℓ ∞ -norm objective, we give a min-max characterization for the optimal solution, and provide a pseudo-polynomial algorithm for finding an optimal deviation vector that runs in strongly polynomial time in the case of unit weights. For both objectives, we assume that an algorithm with the same time complexity for solving the underlying combinatorial optimization problem is available.