给出ILP逆优化精确求解的显式迭代次数公式，可直接预测所需计算量。
Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs
- 基于投影子梯度下降法，通过子最优损失函数求解逆优化问题。
- 首次得到迭代次数与样本数、特征维度、约束矩阵结构的显式关系。
- 适用于需要精确解释观测最优解的工业建模与决策分析场景。
数据驱动的逆优化问题（DDIOP）旨在估计能解释已观测最优解数据的目标函数参数（权重），在整数线性规划（ILP）中广泛应用。已知通过梯度优化方法求解子最优损失，可有限步内精确求解ILP的逆优化，且迭代次数满足 $T=O(1/γ( au_{ ext{sub}})^2)$，其中 $γ( au_{ ext{sub}})$ 为依赖于问题的几何常数。然而，此前缺乏对 $γ( au_{ ext{sub}})$ 随问题规模下界的估计，导致无法将迭代次数表示为问题规模的显式函数。本文针对前向问题为整数线性规划的情形，给出了投影子梯度下降法在子最优损失上达到与观测数据精确一致所需的迭代次数，其表达式为样本数、特征维度、特征范围及约束系数矩阵结构的显式函数（仅含基本常数的多项式因子，如权重集直径、步长参数、子最优损失的Lipschitz常数）。
原文摘要 · Abstract (English)
A data-driven inverse optimization problem (DDIOP) is the problem of estimating the objective-function parameters (weights) that explain observed optimal-solution data, and it arises in many applications, including integer linear programming (ILP). It is known that, by applying gradient-based optimization methods to the suboptimality loss, the inverse optimization of ILPs can be solved exactly within finitely many oracle iterations, and that the required number of iterations is bounded as $T=O(1/γ(\ell_{\mathrm{sub}})^2)$ in terms of a problem-dependent geometric constant $γ(\ell_{\mathrm{sub}})$. However, no means of bounding $γ(\ell_{\mathrm{sub}})$ from below as a function of the problem size has been available, and hence the number of iterations could not be given as an explicit function of the problem size. We therefore give, when the forward problem is an integer linear program (ILP), the number of iterations sufficient for projected subgradient descent applied to the suboptimality loss to achieve exact consistency with the observed data, as a fully explicit function of the number of samples, the dimension of the features, the ranges of the features, and the structure of the constraint coefficient matrix, up to polynomial factors in the basic constants (the diameter of the weight set, the step-size parameter, and the Lipschitz constant of the suboptimality loss).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。