一类逆度规最优值问题的可解性和复杂性研究

On Solvability and Complexity for a Class of Inverse Gauge Optimal Value Problems

摘要: 逆优化作为优化理论的重要分支，近年来在多个领域展现出广泛的应用前景。本文研究一类新型逆优化问题——逆度规最优值问题，其目标是在给定最优目标值估计的条件下，反推成本向量参数，使得对应的度规优化问题的最优值与之匹配。本文首先在适当的假设下，利用度规对偶理论分析了该问题的可解性，证明了最优解的存在性。进一步，通过构造与二元整数可行性问题的等价性，证明了逆度规最优值问题属于NP难问题。最后，基于度规函数的极函数表示与对偶理论，将原问题转化为两类带有双线性约束的优化模型，为后续算法设计提供了理论基础。

Abstract: Inverse optimization has emerged as a pivotal subfield with broad applications across various disciplines. This paper investigates a novel class of inverse problems—the inverse gauge optimal value problem—which aims to recover the cost vector parameters such that the optimal value of the corresponding gauge optimization problem matches a given estimate. Under mild assumptions, we establish the solvability of the problem by leveraging gauge duality theory, proving the existence of optimal solutions. Furthermore, we demonstrate the NP-hardness of the problem by constructing an equivalence to the binary integer feasibility problem. Finally, by exploiting the polar representation of gauge functions and duality results, we reformulate the original problem as two types of optimization models with bilinear constraints, paving the way for future algorithmic developments.

1. 引言

逆优化问题的研究涵盖多个学科领域，例如医学成像[1]、地球物理研究[2]、光学工程[3]、声学建模[4]以及机器学习[5]。在优化领域内，逆优化已逐渐成为一个重要的子领域，近年来受到越来越多学者的关注[6]。传统的数学优化将目标函数和约束函数作为输入以产生决策，这通常被称为“正向”优化模型。与之相反，逆优化接受一个决策作为输入，并试图重建目标函数或约束参数。更准确地说，其目标是确定正向模型的参数值，使得所给出的决策成为精确或近似最优解。这一参数推断任务本身就是一个优化问题，被称为逆优化模型。

逆优化的早期系统性工作可追溯至Burton和Toint [7]，他们研究了最短路径问题的逆形式。他们的研究成果推动了后续关于网络逆问题的研究[8]-[13]。随后，根据正向模型目标函数和约束函数的形式，发展出了逆线性优化、逆二次优化、逆二阶锥优化、逆半定优化、逆半定二次优化、逆锥优化等多种专门的连续逆优化模型[14]-[23]。

区别于上述逆优化问题，Ahmed和Guan [24]提出了一类独特的逆优化问题——逆最优值问题。与早期以解作为输入的逆优化模型不同，逆最优值问题使用最优目标值估计$\widehat{z}$ 以及参数估计$\widehat{c}$ 作为输入。该模型表述为：

$\underset{c}{\min }\left\{\Vert c-\widehat{c}\Vert :\underset{x}{\min }\left\{c^{\text{T}}x:Ax\ge b\right\}=\widehat{z},c\in C\right\},$

其中$\Vert \cdot \Vert$ 是某一向量范数，$c\in {ℝ}^n$ ，$A\in {ℝ}^{m\times n}$ ，$b\in {ℝ}^m$ ，$C$ 是参数估计集合。上述问题的结构表明逆最优值问题是一种特殊的双层优化问题。在特定条件下，它可以重构为单层优化问题。此外，其他逆最优值问题的变体也得到了研究。例如，Mostafaee [25]与Cerny和Hladik [26]分析了一种仅提供最优值估计$\widehat{z}$ 的版本：

$\underset{c}{\min }\left\{d\left(z,\widehat{z}\right):\underset{x}{\min }\left\{c^{\text{T}}x:Ax\ge b\right\}=z,c\in C\right\},$

其中$d\left(z,\widehat{z}\right)$ 表示正向问题的最优值与最优值估计$\widehat{z}$ 之间的凸距离度量。除上述研究之外，其他文献利用精确罚函数技术讨论正向问题为带有非负决策变量约束的线性规划[27] [28]和二阶锥规划[29]的逆最优值问题的求解。逆最优值问题也被应用于建模组合问题，如最小生成树和最短路径问题[30]-[34]。

度规优化问题作为一类新型优化问题模型，最近引起了广泛的关注与讨论。最早涉及此类问题的研究是Frenud [35]讨论带有线性约束的度规优化问题，该问题可以用来建模一系列重要的应用，包括锥优化以及在机器学习和信号处理等领域中出现的相关问题。通过扩展约束的形式，进而得到了相应的非线性度规优化的弱对偶定理和强对偶定理并应用于线性规划问题和p范数优化问题的讨论。Van den Berg [36]描述了一个基于度规函数的稀疏优化框架。Teuber、Steidl和Chan [37]考虑模型与观测之间的误差通过Kullback-Leibler散度进行度量的度规优化问题。Jaggi [38]整理了生成常见度规函数的原子集，它们被广泛地应用于机器学习相关问题的研究。Friedlander等人[39]研究了一般度规优化的对偶理论和变分性质。

基于上述度规优化的发展，在本文中我们考虑下述形式的逆最优值问题

$\underset{N,d}{\min }\left\{\left|z-\widehat{z}\right|:\underset{x}{\min }\left\{f\left(Nx+d\right):Ax\ge b\right\}=z,\left(N,d\right)\in \Omega \right\},$(1)

其中$f:{ℝ}^m\to ℝ$ 是正常连续度规函数，$N,A\in {ℝ}^{m\times n}$ ，$b,d\in {ℝ}^m$ ，$\widehat{z}>0$ 。$\left(N,d\right)$ 可以看作成本向量，$\Omega :={\Omega }_N\times {\Omega }_d$ 是目标成本向量集。为了便于叙述，称上述问题(1)为逆度规最优值问题。

本文针对上述逆度规最优值问题，分析了该问题的可解性条件。通过将度规优化的对偶理论应用于对应的正向问题，证明了该问题在一般情况下是NP难的。在一定的假设条件下，讨论了如何将上述逆度规优化问题重述为两类带有双线性约束的优化模型，为后续算法设计提供了理论基础。

2. 预备知识

本节介绍度规函数的定义及其相关性质[40]及度规对偶的重要结果[35] [39]，这些结论将用于后文的证明。

2.1. 度规函数

定义2.1 [40] 凸函数$\kappa :{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ 称为度规函数，如果它满足非负性和正齐次性，并且在原点处的函数值为零。

范数和伪范数是度规函数的具体实例，而度规函数也极大地推广了范数的概念。所有度规函数都可以被某个凸集$D$ 的Minkowski函数$\gamma \left(\cdot |D\right)$ 所表示，即

$\kappa \left(x\right)=\gamma \left(x|D\right):=\inf \left\{\lambda \ge 0|x\in \lambda D\right\}.$

特别地，总可以选择$D=\left\{x|\kappa \left(x\right)\le 1\right\}$ 使得上述结论成立。

定义2.2 [40] 度规函数$\kappa$ 的极函数${\kappa }^{\circ }$ 定义为

${\kappa }^{\circ }\left(y\right):=\inf \left\{\mu \ge 0|\langle x,y\rangle \le \mu \kappa \left(x\right),\forall x\in {ℝ}^n\right\}.$

如果$\kappa$ 是范数，那么${\kappa }^{\circ }$ 是对应的对偶范数。

引理2.1 [40] 如果$\kappa$ 为度规函数，则$\kappa$ 的极${\kappa }^{\circ }$ 为闭度规函数且${\kappa }^{\circ }=\text{cl}\kappa$ 。事实上，如果$\kappa =\gamma \left(\cdot |D\right)$ ，其中$D$ 为非空凸集，则${\kappa }^{\circ }=\gamma \left(\cdot |D^{\circ }\right)$ ，其中集合$D^{\circ }:=\left\{x^{\ast }|\langle x,x^{\ast }\rangle \le 1,\forall x\in D\right\}$ 表示集合$D$ 的极。

由引理2.1可知，集合$D^{\circ }$ 是包含原点的闭凸集。

引理2.2 [40] 设$D$ 为${ℝ}^n$ 中含有原点的闭凸集，$D$ 的度规函数$\gamma \left(\cdot |D\right)$ 为闭的，则对任意$\lambda >0$ 有

$\left\{x|\gamma \left(x|D\right)\le \lambda \right\}=\lambda D.$

2.2. 度规对偶

下面给出度规对偶的重要结果，相关结论出自文献[35] [39]。

Frenud在[35]中讨论下述带有线性约束的度规优化问题

$\begin{array}{l}\underset{x}{\min }f\left(Nx+d\right)\\ \text{ s}\text{.t}\text{. }Ax\ge b\end{array}$ (2)

其中$f:{ℝ}^m\to ℝ$ 是正常连续度规函数，$N,A\in {ℝ}^{m\times n}$ ，$b,d\in {ℝ}^m$ 。问题(2)可以等价表示为

$\begin{array}{l}\underset{x,s}{\min }g\left(x,s\right)\\ \text{ s}\text{.t}\text{. }Ax\ge b,\\ -Nx+s=d,\end{array}$ (3)

其中$g\left(x,s\right)=f\left(s\right)$ 。此外，$f$ 是闭度规函数当且仅当$g$ 是闭度规函数，且有$\text{dom }g={ℝ}^n\times \text{dom }f$ 。利用[1]中定义的度规对偶对应关系，得到问题(3)的度规对偶问题

$\begin{array}{l}\underset{\lambda ,\mu }{\min }{g}^{\circ }\left(A^{\text{T}}\lambda -N^{\text{T}}\mu ,\mu \right)\\ \text{ s}\text{.t}\text{. }{b}^{\text{T}}\lambda +d^{\text{T}}\mu =1,\\ \lambda \ge 0.\end{array}$

当$y=0$ 时，$g^{\circ }\left(y,t\right)=f^{\circ }\left(t\right)$ ；当$y\ne 0$ 时，$g^{\circ }\left(y,t\right)=+\infty$ 。因此上述问题可简化为：

$\begin{array}{l}\underset{\lambda ,\mu }{\min }{f}^{\circ }\left(\mu \right)\\ \text{ s}\text{.t}\text{. }{b}^{\text{T}}\lambda +d^{\text{T}}\mu =1,\\ A^{\text{T}}\lambda -N^{\text{T}}\mu =0,\\ \lambda \ge 0.\end{array}$ (4)

且有$\text{dom }{g}^{\circ }=\left\{0\right\}\times \text{dom }{f}^{\circ }$ 。除了上述度规对偶的结论，在[39]中讨论一般度规优化问题

$\begin{array}{l}\left(\text{P}\right)\underset{x}{\min }\kappa \left(x\right)\\ \text{ s}\text{.t}\text{. }x\in C,\end{array}$

其中$C$ 是闭凸集，$\kappa$ 是度规函数。上述问题的度规对偶定义如下：

$\begin{array}{l}\left(\text{D}\right)\underset{x}{\min }{\kappa }^{\circ }\left(x\right)\\ \text{ s}\text{.t}\text{. }x\in C^{\prime },\end{array}$

其中集合$C^{\prime }:=\left\{y|\langle y,x\rangle \ge 1,\forall x\in C\right\}$ 表示$C$ 的反极。

基于文献[35]的分析，下述定理给出了度规优化问题(P)和(D)的弱对偶和强对偶结论。

命题2.1 [35] 假设$\text{dom }{\kappa }^{\circ }\cap C^{\prime }\ne \varnothing$ ，则$v_p\ge v_g^{-1}>0$ ，其中$v_p$ 和$v_g$ 分别表示原问题(P)和度规对偶问题(D)的最优值。进一步，假设度规函数$\kappa$ 是闭的，且有$\text{ri}\text{dom }\kappa \cap \text{ ri}C\ne \varnothing$ 和$\text{ri}\text{dom }{\kappa }^{\circ }\cap \text{ ri}{C}^{\prime }\ne \varnothing$ ，则$v_p{v}_g=1$ 且原问题(P)和度规对偶问题(D)的最优值都可达。

3. 可解性

本章讨论逆度规最优值问题的可解性。为了便于叙述，定义下述符号

$\begin{array}{l}P\left(N,d\right):=\underset{x}{\min }\left\{f\left(Nx+d\right):Ax\ge b\right\},\\ {\Omega }_0:=\left\{\left(N,d\right)|P\left(N,d\right)>0\right\},\\ {\Omega }_{\widehat{z}}:=\left\{\left(N,d\right)|P\left(N,d\right)\ge \widehat{z}\right\},\end{array}$

和下述假设条件

(A1) 对于任意$\left(N,d\right)\in \Omega$ 满足

$\text{ri}\text{dom }g\cap \text{ ri}C\ne \varnothing ,\text{ ri}\text{dom }{g}^{\circ }\cap \text{ ri}{C}^{\prime }\ne \varnothing ,$

其中$g\left(x,s\right)=f\left(s\right)$ ，$\text{ri}\text{dom }g={ℝ}^n\times \text{ri}\text{dom }f$ ，$\text{ri}\text{dom }{g}^{\circ }=\left\{0\right\}\times \text{ri}\text{dom }{f}^{\circ }$ 且有

$C=\left\{\left(x,s\right)|Ax\ge b,-Nx+s=d\right\},C^{\prime }=\left\{\left(y,\mu \right)|存在\lambda \ge 0使得b^{\text{T}}\lambda +d^{\text{T}}\mu =1,y=A^{\text{T}}\lambda -N^{\text{T}}\mu \right\}.$

(A2) 成本向量集合$\Omega$ 是非空、紧且凸的；$\text{ri}\text{dom}$

(A3) 问题(1)的可行域$S:=\left\{x|Ax\ge b\right\}$ 是紧集。

注3.1 由上述假设(A1)和命题2.1可知，对于任意$\left(N,d\right)\in \Omega$ ，度规优化问题(2)和度规对偶问题(4)的强对偶性成立且两个问题的最优值都是大于0的有限值，即

$0<P\left(N,d\right)<+\infty ,\forall \left(N,d\right)\in \Omega ,$

从而有$\Omega \cap {\Omega }_0=\Omega \ne \varnothing$ 。因此可以得到

$P\left(N,d\right)=\min \left\{{\left(f^{\circ }\left(\mu \right)\right)}^{-1}|b^{\text{T}}\lambda +d^{\text{T}}\mu =1,A^{\text{T}}\lambda -N^{\text{T}}\mu =0,\lambda \ge 0\right\},$

${\Omega }_0=\left\{\left(N,d\right)|存在\left(\lambda ,\mu \right)使得b^{\text{T}}\lambda +d^{\text{T}}\mu =1,A^{\text{T}}\lambda -N^{\text{T}}\mu =0,\lambda \ge 0\right\},$

${\Omega }_{\widehat{z}}=\left\{\left(N,d\right)|存在\left(\lambda ,\mu \right)使得f^{\circ }\left(\mu \right)\widehat{z}\le 1,b^{\text{T}}\lambda +d^{\text{T}}\mu =1,A^{\text{T}}\lambda -N^{\text{T}}\mu =0,\lambda \ge 0\right\}.$

基于注3.1和上面的假设条件，可以得到下面的性质。

命题3.1 (i)函数$P\left(\cdot ,\cdot \right)$ 关于成本向量$\left(N,d\right)$ 的可行集$\Omega$ 上是连续的。

(ii) 集合${\Omega }_0$ 和${\Omega }_{\widehat{z}}$ 都是闭凸集。

证明 (ii)的结果可由注3.1得到。下面只对(i)进行证明。

先证明下半连续性，即给定$\left(N_0,d_0\right)\in \Omega$ 和任意序列$\left(N_k,d_k\right)\to \left(N_0,d_0\right)$ ，有

$\underset{k\to \infty }{\lim \inf }P\left(N_k,d_k\right)\ge P\left(N_0,d_0\right).$

对每个k，由S的紧性和f的连续性，可以得到$P\left(N_k,d_k\right)$ 存在，且存在$x_k\in S$ ，使$P\left(N_k,d_k\right)=f\left(N_k{x}_k+d_k\right)$ 。由于假设(A3)成立，则序列$\left\{x_k\right\}$ 至少存在一个收敛子列，记为$x_{k_j}\to x^{*}\in S$ 。根据$\left(N_k,d_k\right)\to \left(N_0,d_0\right)$ ，可知$N_{k_j}{x}_{k_j}+d_{k_j}\to N_0{x}^{*}+d_0$ ，进而由f的连续性得到

$\underset{j\to \infty }{\lim \inf }P\left(N_{k_j},d_{k_j}\right)=\underset{j\to \infty }{\lim \inf }f\left(N_{k_j}{x}_{k_j}+d_{k_j}\right)\ge f\left(N_0{x}^{\ast }+d_0\right).$

由于$x^{\ast }\in S$ 是可行点，则有

$f\left(N_0{x}^{*}+d_0\right)\ge \underset{x\in S}{\min }f\left(N_{0}x+d_0\right)=P\left(N_0,d_0\right).$

基于上述分析，对于任意子列$\left\{P\left(N_{k_j},d_{k_j}\right)\right\}$ ，均有$\underset{j\to \infty }{\lim \inf }P\left(N_{k_j},d_{k_j}\right)\ge P\left(N_0,d_0\right)$ 。因此有

$\underset{k\to \infty }{\lim \inf }P\left(N_k,d_k\right)\ge P\left(N_0,d_0\right).$

接下来证明上半连续性。设$x_0\in S$ 是使得$P\left(N_0,d_0\right)=f\left(N_0{x}_0+d_0\right)$ 的最优解。对任意$k$ ，有

$P\left(N_k,d_k\right)\le f\left(N_k{x}_0+d_k\right).$

而由于$N_k\to N_0$ 且$d_k\to d_0$ ，可得$f\left(N_k{x}_0+d_k\right)\to f\left(N_0{x}_0+d_0\right)=P\left(N_0,d_0\right)$ 。对上述不等式两侧同时取上极限，则

$\underset{k\to \infty }{\lim \sup }P\left(N_k,d_k\right)\le \underset{k\to \infty }{\lim \sup }f\left(N_k{x}_0+d_k\right)=P\left(N_0,d_0\right).$

综上所述，$P\left(N_k,d_k\right)$ 的下极限与上极限均收敛于$P\left(N_0,d_0\right)$ ，从而函数$P$ 在$\Omega$ 上连续。

基于命题3.1可知函数$\left|P\left(N,d\right)-\widehat{z}\right|$ 在成本向量集合$\Omega$ 上连续。进一步，利用假设(A2)可以得到下述定理：

定理3.1 逆度规最优值问题(1)至少存在一个最优解且对应的最优值是有限的。

证明 由$P\left(N,d\right)$ 的定义可知，逆度规最优值问题(1)可以重述为

$\begin{array}{l}\underset{N,d}{\min }\left|P\left(N,d\right)-\widehat{z}\right|\\ \text{ s}\text{.t}\text{. }\left(N,d\right)\in \Omega .\end{array}$(5)

由魏尔斯特斯拉定理可知，上述问题至少存在一个最优解。进一步，由注3.1可知该最优解对应的最优值是有限的。

4. 复杂性

本章讨论逆度规最优值问题的复杂性，证明过程依赖于建立逆最优值问题(5)与下述二元整数可行性问题之间的等价性。

二元整数可行性问题：给定整数矩阵$B\in {\mathbb{Z}}^{m\times n}$ 和整数向量$h\in {\mathbb{Z}}^m$ ，是否存在一个向量$y\in {\left\{0,1\right\}}^n$ ，使得$By\le h$ ？

通过观察上述定义和问题(5)的形式，二元整数可行性问题和逆度规最优值问题的实例分别由矩阵向量对$\left(B,h\right)$ 及函数$P\left(N,d\right)$ 、集合$\Omega$ 和标量$\widehat{z}$ 指定。为了方便叙述，将这样的实例分别表示为$ℬ\left(B,h\right)$ 和。

引理4.1 给定实例$ℬ\left(B,h\right)$ ，可以构造逆度规最优值问题(1)的实例，使得$ℬ\left(B,h\right)$ 的答案为“是”当且仅当的最优目标值为0。

证明 给定实例$ℬ\left(B,h\right)$ ，其中$B\in {\mathbb{Z}}^{m\times n}$ ，$h\in {\mathbb{Z}}^m$ 。可以按下述步骤构造对应的逆度规最优值问题(1)的实例：

• 定义连续度规函数

$f\left(u\right)=\max \left\{u,0\right\},u\in ℝ$

和紧多面体集合

$\widehat{\Omega }={\widehat{\Omega }}_C\times {\widehat{\Omega }}_s,$

其中

${\widehat{\Omega }}_C=\left\{\left(c_1^{\text{T}},c_2^{\text{T}},c_3^{\text{T}}\right)\in {ℝ}^{1\times 3n}:B{c}_1\le h,c_1=c_2,c_3=e,0\le c_1\le e,0\le c_2\le e\right\},{\widehat{\Omega }}_s=\left\{n\right\},$

这里$e\in {ℝ}^n$ 表示全1向量。

• 取$w={\left(u^{\text{T}},-v^{\text{T}},v^{\text{T}}\right)}^{\text{T}}\in {ℝ}^{3n}$ ，$u\in {ℝ}^n$ ，$v\in {ℝ}^n$ ，$C=\left(c_1^{\text{T}},c_2^{\text{T}},c_3^{\text{T}}\right)\in {\widehat{\Omega }}_C$，$s\in {\widehat{\Omega }}_s$ ，则

$f\left(Cw+s\right)=\max \left\{c_1^{\text{T}}u-c_2^{\text{T}}v+c_3^{\text{T}}v+n,0\right\}.$

• 定义函数$Q:{ℝ}^{1\times 3n}\times ℝ\mapsto ℝ$ 为下述优化问题的最优值

$\begin{array}{ll}\underset{w}{\min }\hfill & f\left(Cw+s\right)\hfill \\ \text{ s}\text{.t}\text{.}\hfill & Aw\ge b,\hfill \end{array}$

其中

$A=\left(\begin{array}{l}{I}_n{0}_{n\times n}{I}_n\\ -I_n{0}_{n\times n}-I_n\\ I_n{0}_{n\times n}{0}_{n\times n}\\ 0_{n\times n}{0}_{n\times n}{I}_n\end{array}\right),b=\left(\begin{array}{c}e\\ -2e\\ 0_n\\ 0_n\end{array}\right),$

这里$I_n$ 表示$n$ 阶单位矩阵，$0_{n\times n}$ 表示$n$ 阶零矩阵，$0_n\in {ℝ}^n$ 表示全0向量。

• 取${\widehat{z}}^{*}=n$ ，则逆度规最优值问题(1)有实例。

假设$ℬ\left(B,h\right)$ 答案为“是”，即存在$\widehat{y}\in {\left\{0,1\right\}}^n$ ，使得$B\widehat{y}\le h$ 。定义成本向量$\left(\widehat{C},\widehat{s}\right)=\left(\left({\widehat{c}}_1^{\text{T}},{\widehat{c}}_2^{\text{T}},{\widehat{c}}_3^{\text{T}}\right),n\right)$，其中${\widehat{c}}_1={\widehat{c}}_2=\widehat{y}$ ，${\widehat{c}}_3=e$ 。显然$\left(\widehat{C},\widehat{s}\right)\in \widehat{\Omega }$ 。令$Q_j\left(\widehat{C},\widehat{s}\right)$ 是下述问题的最优值

$\begin{array}{l}\underset{u_j,v_j}{\min }\text{ max}\left\{{\widehat{y}}_j{u}_j+\left(1-{\widehat{y}}_j\right)v_j+1,0\right\}\\ \text{ s}\text{.t}\text{. }1\le u_j+v_j\le 2,\\ u_j\ge 0,v_j\ge 0.\end{array}$

由函数$Q$ 的定义，则$Q\left(\widehat{C},\widehat{s}\right)={\displaystyle \sum _{j=1}^n{Q}_j\left(\widehat{C},\widehat{s}\right)}$ 。由于${\widehat{y}}_j\in \left\{0,1\right\}$ ，有

$\begin{array}{l}{\widehat{y}}_j=0\Rightarrow v_j=0,\\ {\widehat{y}}_j=1\Rightarrow u_j=0.\end{array}$

则$Q_j\left(\widehat{C},\widehat{s}\right)=1$ ，$Q\left(\widehat{C},\widehat{s}\right)=n={\widehat{z}}^{*}$ 。因此最优值为0。

假设的最优值为0，即存在$\left(\overline{C},\overline{s}\right)\in \widehat{\Omega }$ ，使得$\widehat{Q}\left(\overline{C},\overline{s}\right)=n$ 。令$\overline{C}:=\left({\widehat{c}}^{\text{T}},{\widehat{c}}^{\text{T}},e^{\text{T}}\right)$， $\overline{s}=n$ ，其中$0\le \widehat{c}\le e$ 且$B\widehat{c}\le h$ 。注意$\widehat{Q}\left(\overline{C},\overline{s}\right)$ 可以写为下述形式

$\widehat{Q}\left(\overline{C},\overline{s}\right)={\displaystyle \sum _{j=1}^n{\widehat{Q}}_j\left(\overline{C},\overline{s}\right)},$ (6)

其中${\widehat{Q}}_j\left(\overline{C},\overline{s}\right)$ 是下述问题的最优值

$\begin{array}{l}\underset{u_j,v_j}{\min }\text{ max}\left\{{\widehat{c}}_j{u}_j+\left(1-{\widehat{c}}_j\right)v_j+1,0\right\}\\ \text{ s}\text{.t}\text{. }1\le u_j+v_j\le 2,\\ u_j\ge 0,v_j\ge 0.\end{array}$

因为$0\le {\widehat{c}}_j\le 1$ ，则对于所有$j$ 有${\widehat{Q}}_j\left(\overline{C},\overline{s}\right)=\min \left\{{\widehat{c}}_j,1-{\widehat{c}}_j\right\}+1\ge 1$ 。进一步，由(6)可知

$n=\widehat{Q}\left(\overline{C},\overline{s}\right)={\displaystyle \sum _{j=1}^n{\widehat{Q}}_j}\left(\overline{C},\overline{s}\right)\ge n.$

因此对于所有$j$ ，有${\widehat{Q}}_j\left(\overline{C},\overline{s}\right)=1$ ，所以${\widehat{c}}_j\in \left\{0,1\right\}$ 。由于$B\widehat{c}\le h$ ，取$y=\widehat{c}\in {\left\{0,1\right\}}^n$ ，则二元整数可行性问题的实例$ℬ\left(B,h\right)$ 答案为“是”。

定理4.1 逆度规最优值问题(1)是NP-难的。

证明 引理4.1证明了我们可以通过构造并求解等价的逆度规最优值问题(1)的实例来回答任何二元整数可行性问题。由于二元整数可行性问题是NP-难的，因此逆度规最优值问题(1)也是NP-难的。

5. 模型转化

本章将度规对偶的结果应用于逆度规最优值问题。通过问题的结构特征，将其转化为两类带有双线性约束的优化模型。

在假设(A1)、(A2)和(A3)成立的条件下，由注3.1中$P\left(N,d\right)$ 的对偶表达，逆度规最优值问题(1)可以等价转化为下述形式

$\begin{array}{l}\underset{z,\lambda ,\mu ,N,d}{\min }\left|z-\widehat{z}\right|\\ \text{ s}\text{.t}\text{. }z{f}^{°}\left(\mu \right)\le 1,\\ b^{\text{T}}\lambda +d^{\text{T}}\mu =1,A^{\text{T}}\lambda -N^{\text{T}}\mu =0,\\ \lambda \ge 0,z\ge 0,\left(N,d\right)\in \Omega .\end{array}$(7)

根据引理2.1，对于闭度规函数$f(\cdot )=\gamma \left(\cdot |\mathcal{D}\right)$ ，其中$\mathcal{D}=\left\{x|f\left(x\right)\le 1\right\}$ 是包含原点的凸集。其极函数$f^{°}(\cdot )=\gamma \left(\cdot |{\mathcal{D}}^{°}\right)$ ，显然${\mathcal{D}}^{°}$ 是包含原点的闭凸集。进一步，由引理2.2可得${\mathrm{lev}}_{\le \mu }{f}^{°}=\mu {\mathcal{D}}^{°}$ ，因此约束条件$z{f}^{°}\left(\mu \right)\le 1$ 等价于$z\mu \in {\mathcal{D}}^{°}$ 。最后，对问题(7)进行参数化处理，即令$t=z\lambda$ ，$s=z\mu$ ，可以得到下述问题

$\begin{array}{l}\underset{z,t,s,N,d}{\min }\left|z-\widehat{z}\right|\\ \text{ s}\text{.t}\text{. }{b}^{\text{T}}t+d^{\text{T}}s=z,A^{\text{T}}t-N^{\text{T}}s=0,\\ t\ge 0,z\ge 0,s\in {\mathcal{D}}^{°},\left(N,d\right)\in \Omega .\end{array}$(8)

由集合${\Omega }_{\widehat{z}}$ 的定义和注3.1中集合${\Omega }_{\widehat{z}}$ 的等价刻画，逆度规最优值问题(1)也可以重述为

$\begin{array}{l}\underset{z,t,s,\widehat{s},N,d}{\min }z-\widehat{z}\\ \text{ s}\text{.t}\text{. }{b}^{\text{T}}t+d^{\text{T}}s=z,A^{\text{T}}t-N^{\text{T}}s=0,\widehat{s}=\widehat{z}\mu ,\\ t\ge 0,z\ge 0,s,\widehat{s}\in {\mathcal{D}}^{°},\left(N,d\right)\in \Omega \cap {\Omega }_{\widehat{z}}.\end{array}$(9)

显然，问题(8)和问题(9)都是带有双线性约束的优化模型。

双线性约束是非凸优化问题中常见的难点之一，它破坏了问题的凸性，不能直接使用凸优化算法。因此，问题(8)和问题(9)的计算难度主要来自这些双线性约束，且常伴随多个局部极值点、可行域不规则、对初值敏感等数值挑战。鉴于上述结构特性，可以考虑下述潜在的算法框架来求解或近似求解上述问题：

• 若可为变量$N,d,s$ 等推导出合理的上下界，可采用McCormick包络对双线性项进行凸松弛，将原问题转化为凸松弛问题。结合空间分支定界框架，通过对变量区间进行细分并逐步收紧松弛，设计相应的全局优化算法求解。相关思路可参考关于混合整数线性规划与双线性规划的研究[41] [42]。

• 若集合${\mathcal{D}}^{°}$ 性质良好时，不难发现：固定$\left(N,d\right)$ ，上述问题关于$\left(t,s,z\right)$ 为线性规划或锥规划；固定$\left(t,s,z\right)$ ，上述问题关于$\left(N,d\right)$ 为凸可行性问题。鉴于上述分析，可采用交替极小化策略[43]。该方法每步迭代仅需求解两个凸子问题，计算效率高，且易于嵌入现有凸优化求解器(如MOSEK、CVX)。

综上，由于双线性约束带来的固有非凸性，问题(8)和(9)在求解上具有一定难度。但可结合全局优化方法(例如McCormick松弛 + 分支定界)与高效启发式策略(如交替极小化)构建可行的求解框架，为后续数值实验与算法设计提供理论基础。

极集${\mathcal{D}}^{°}$ 的计算

本小节讨论计算极集${\mathcal{D}}^{°}$ 的可行性，这一步骤的难易程度直接决定了上述统一框架的实用价值。由于${\mathcal{D}}^{°}$ 的定义，它与问题(2)中函数$f$ 的选择有关。下面讨论两种极集${\mathcal{D}}^{°}$ 具有显式表达形式的情况：

• 函数$f$ 为$l_p$ 范数，即$f\left(x\right)={\left|\left|x\right|\right|}_p\left(p>1且p为正整数\right)$ ，此时

$\mathcal{D}=\left\{x|f\left(x\right)\le 1\right\}=\left\{x|{\Vert x\Vert }_p\le 1\right\}$

是单位$p$ 范数球，集合$\mathcal{D}$ 的极

${\mathcal{D}}^{°}=\left\{y|{\Vert y\Vert }_q\le 1\right\}$

是单位$q$ 范数球，其中$p^{-1}+q^{-1}=1$ 。

• 函数$f$ 为形如$\max \left\{{\eta }^{\text{T}}x,0\right\}$ 的度规函数，其中$\eta \in {ℝ}^n$ 。由定义2.2，可直接计算得到

$f^{°}\left(y\right)=\{\begin{array}{ll}v\hfill & 如果y=v\eta 对于某个v\ge 0成立,\hfill \\ +\infty \hfill & 其他.\hfill \end{array}$

此时，集合${\mathcal{D}}^{°}=\left\{v\eta |0\le v\le 1\right\}$ 。

NOTES

^*通讯作者。