一种用于解决线性规划中逆最优值问题的精确凸差分惩罚方法

《Journal of Computational and Applied Mathematics》：An exact penalty difference-of-convex approach for solving inverse optimal value problems in linear programming

　　摘要
本文提出了一种精确的惩罚型差分凸（DC）算法，用于解决线性规划中的逆最优值问题（IOVP）。与现有的基于惩罚的方法不同，这些方法通常会受到非凸子问题的影响，并且缺乏收敛性保证。我们利用KKT条件和前向线性规划的强对偶性，将原始的双层问题重新表述为具有互补约束的单层问题。通过一个精确的?1型惩罚项将互补条件纳入目标函数，该惩罚项仅在违反互补性的点上生效，从而得到一个DC分解，其子问题是在固定的多面体可行集上的凸程序。我们证明了由所提算法生成的序列的每一个极限点都是惩罚问题的一个静止点（当目标函数通过近端项变得强凸时，序列的每一个累积点也是静止点），而无需依赖任何约束条件。我们还证明了惩罚项的精确性：在标准条件下，惩罚问题的全局最小化解与IOVP的全局最小化解是一致的，并且该惩罚项通常是渐进精确的。通过对合成问题和高维实例进行的大量数值实验，包括与双线性惩罚重构方法（Lv, Chen & Wan, Applied Mathematics Letters, 2010）和最近的基于DC的方法（Li & Cui, Mathematics of Operations Research, 2026）的比较，以及对惩罚参数的敏感性分析，证明了我们方法的有效性、鲁棒性和可扩展性。

引言
逆问题的研究涵盖了多种学科，如医学成像[1]、地球物理研究[2]、光学工程[3]、声学建模[4]和机器学习[5]。在优化领域，逆优化作为一个显著的研究子领域，在近年来受到了越来越多的关注[6]。传统的数学优化以目标和约束函数作为输入来产生解，这通常被称为“前向”优化问题。相比之下，逆优化以决策作为输入，试图重构目标或约束参数。更准确地说，其目标是确定前向模型的参数值，使得给定的决策成为精确或近似的最优解。这种参数推断任务本身也是一个优化问题，被称为“逆”模型。
早期关于逆优化的系统研究可以追溯到Burton和Toint[7]，他们研究了最短路径问题的逆版本。他们的发现引发了对网络逆问题的后续研究[8], [9], [10], [11], [12], [13]。随后，逆线性规划（LP）的研究可以追溯到Zhang和Liu[14], [15]的开创性工作，他们首次从参数估计的角度出发，对逆LP问题进行了形式化和求解。他们的工作为后来各种专门的连续逆优化模型的发展奠定了基础[16], [17], [18], [19], [20], [21], [22], [23]及其中的参考文献。
本文关注一类特殊的逆优化问题——逆最优值问题（IOVP）。在这个问题中，我们寻求一个成本向量??∈???，使得前向线性程序的最优值与给定的估计值???∈?相匹配。形式上，IOVP可以表述为
min???{???(??,???)：min???{???????∣?????≥??}=??, ??∈??},
其中???(??,???)表示v和???之间的距离度量，??∈???是成本向量，??∈???是决策变量，??∈???×??是约束矩阵，??∈???是右侧向量，??????表示允许的成本向量多面体集。问题（1）由Ahmed和Guan[24]首次提出，并且此后在各种形式下进行了研究[25], [26], [27], [28]。

现有的IOVP方法通常依赖于惩罚方法或基于对偶性的重构，但在惩罚参数调整和收敛性保证方面面临挑战。最接近的前辈方法[27], [28]使用惩罚函数来处理从前向LP的KKT条件派生的互补约束。然而，它们存在两个主要限制：
1. [27], [28]中的惩罚项涉及对偶变量和松弛变量的乘积yisi，这破坏了结果子问题的凸性，使其难以全局求解。
2. 没有提供收敛到静止点的保证，且算法纯是启发式的。

相比之下，我们的工作通过一个精确的?1型惩罚项将互补约束纳入目标函数，并利用其自然的DC分解（见第2节中的（7））。生成的DC程序的可行域是一个多面体，因此我们算法生成的每一个子问题都是可以通过现成的求解器（如IPOPT[29]）求解的凸程序。此外，我们证明了由所提算法生成的序列的每一个极限点都是惩罚问题的一个静止点（当目标函数通过近端项变得强凸时，每一个累积点也是静止点），并且我们证明了惩罚项的精确性：在标准条件下，惩罚问题的全局最小化解与IOVP的全局最小化解是一致的。表1总结了主要的理论和数值差异。

最近，Li和Cui[30]提出了一个变分框架和一种针对渐进可解非凸问题的DC型算法，该算法也可以应用于IOVP。他们的工作依赖于epi-收敛性，并在某些条件下提供了收敛性保证。在本文中，我们还包括了与他们方法的数值比较，以进一步突出我们精确惩罚DC分解的优势。

为了克服上述困难，我们提出了一种惩罚型差分凸算法（DCA）。我们的主要贡献有三方面：
• 使用精确惩罚的DC重构。我们利用KKT条件和下层问题的强对偶性，将双层IOVP重构为具有互补约束的单层问题（1）。然后通过一个精确的?1型惩罚项将互补条件纳入目标函数，得到以下惩罚型模型：
min??,??,??,?????(???????,???)+???????(???Π???+?(?????))s.t.??????????=0,??∈??,????????=??,??∈???+,??∈???+,
其中??:=(1,1,?,1)??∈???, ρ?>?0是惩罚参数，Π???+表示映射到???+（即，(Π???+?(??))??=max?{????,0}）。惩罚项????????(???Π???+?(?????))=???∑????=1min?{????,????}在互补集{(??,??)∈???+×???+:???????=0}上消失，并且在违反互补性的每个点上为正，因此在公式中它是真正需要的。根据定理2.1中建立的精确性条件，ρ的一个有限值就足够了。在本文中，我们做出以下假设：
（AS1）集合??????是非空的、凸的、紧凑的且多面体的；
（AS2）对于固定的???，距离函数???(??,???)在v上是凸的、有约束性的且连续的；
（AS3）IOVP下层的强对偶性成立。
• 收敛性保证。我们证明了由所提DCA生成的序列的每一个极限点都是惩罚问题的一个静止点（定理3.1），并且当目标函数变得强凸时，每一个累积点也是静止的。我们还证明了惩罚项的精确性（定理2.1），因此在标准条件下，惩罚模型的解解决了逆最优值问题（1）。
• 数值验证。我们通过大量的合成问题和高维实验证明了我们方法的有效性，包括与双线性惩罚重构方法[27], [28]以及Li和Cui[30]的最新方法的比较。

本文的结构如下。第2节介绍了惩罚型变体的DC算法（4）。第3节建立了收敛性结果。第4节报告了在合成问题和高维问题上的数值实验。最后，第5节给出了结论性评论。

算法
本节旨在提出一种差分凸算法（DCA），用于解决逆最优值问题（1）的单层重构。根据前向问题（1）的KKT条件和假设（AS3），IOVP等价于以下具有互补约束的单层问题：
min??,??,??,?????(???????,???)??.??.??????????=0,??∈??,????????=??,??∈???+,??∈???+,???????=0。
实际上，点(c, x, y, s)对于（3）是可行的当且仅当x对于前向问题是可行的，y对于其

收敛性分析
本节分析了问题（10）的最优解与问题（6）的静止点之间的关系，然后提出了算法1的相应收敛性结果。

定义 1
如果满足0∈????1?(??*)????1?(??*)+?????(??*)，
则点z*?∈?D被称为问题（6）（等价于惩罚问题（4）的静止点，
其中g1, h1如（7）中定义，D如（5）中定义，?????(??*)表示凸集D在z*处的法锥。
由于D是多面体的，其法锥允许一个

实验设置
本节提出了在合成问题和高维实例上对算法1的数值实验，并与双线性惩罚重构方法[27], [28]和最近的基于DC的方法[30]进行了比较。所有代码都是用Python 3.14、NumPy 2.5和SciPy 1.18[36]实现的。下层的前向线性程序和变量x中的线性子问题是用HiGHS求解器[37]求解的；变量（y, t）中的凸二次子问题也使用该求解器求解。

结论性评论
在本文中，我们开发了一种精确的惩罚型差分凸（DC）算法，用于解决线性规划中的逆最优值问题。通过结合前向LP的KKT条件和强对偶性，我们将原始的双层问题重构为具有互补约束的单层问题。通过一个精确的?1型惩罚项将互补条件纳入目标函数，其DC分解产生的子问题是在固定的多面体上的凸程序。

Yue Lu | Zheng-Peng Dong | Zi-Jun Hao | Ming Huang
天津师范大学数学科学学院，天津，300387，中国