一类逆度规最优值问题的可解性和复杂性研究
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.
文章引用：薛涵文, 卢越. 一类逆度规最优值问题的可解性和复杂性研究[J]. 应用数学进展, 2026, 15(1): 122-132. https://doi.org/10.12677/aam.2026.151013

参考文献

[1] Parker, D.J. (1999) Introduction to Inverse Problems in Imaging. Computer Physics Communications, 120, 269-270. [Google Scholar] [CrossRef] 
[2] Kim, Y. and Nakata, N. (2018) Geophysical Inversion versus Machine Learning in Inverse Problems. The Leading Edge, 37, 894-901. [Google Scholar] [CrossRef] 
[3] Pilozzi, L., Farrelly, F.A., Marcucci, G. and Conti, C. (2018) Machine Learning Inverse Problem for Topological Photonics. Communications Physics, 1, Article No. 57. [Google Scholar] [CrossRef] 
[4] Colton, D., Coyle, J. and Monk, P. (2000) Recent Developments in Inverse Acoustic Scattering Theory. SIAM Review, 42, 369-414. [Google Scholar] [CrossRef] 
[5] Cheon, M.S. (2021) An Outer-Approximation Guided Optimization Approach for Constrained Neural Network Inverse Problems. Mathematical Programming, 196, 173-202. [Google Scholar] [CrossRef] 
[6] Chan, T.C.Y., Mahmood, R. and Zhu, I.Y. (2025) Inverse Optimization: Theory and Applications. Operations Research, 73, 1046-1074. [Google Scholar] [CrossRef] 
[7] Burton, D. and Toint, P.L. (1992) On an Instance of the Inverse Shortest Paths Problem. Mathematical Programming, 53, 45-61. [Google Scholar] [CrossRef] 
[8] Ahuja, R.K. and Orlin, J.B. (2001) Inverse Optimization. Operations Research, 49, 771-783. [Google Scholar] [CrossRef] 
[9] Ahuja, R.K. and Orlin, J.B. (2002) Combinatorial Algorithms for Inverse Network Flow Problems. Networks, 40, 181-187. [Google Scholar] [CrossRef] 
[10] Cai, M.C., Yang, X.G. and Zhang, J.Z. (1999) The Complexity Analysis of the Inverse Center Location Problem. Journal of Global Optimization, 15, 213-218. [Google Scholar] [CrossRef] 
[11] Heuberger, C. (2004) Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results. Journal of Combinatorial Optimization, 8, 329-361. [Google Scholar] [CrossRef] 
[12] Zhang, J. and Ma, Z. (1999) Solution Structure of Some Inverse Combinatorial Optimization Problems. Journal of Combinatorial Optimization, 3, 127-139. [Google Scholar] [CrossRef] 
[13] Zhang, J., Liu, Z. and Ma, Z. (2000) Some Reverse Location Problems. European Journal of Operational Research, 124, 77-88. [Google Scholar] [CrossRef] 
[14] Iyengar, G. and Kang, W. (2005) Inverse Conic Programming with Applications. Operations Research Letters, 33, 319-330. [Google Scholar] [CrossRef] 
[15] Zhang, L., Ge, Y. and Lu, Y. (2015) An Alternating Direction Method for Solving a Class of Inverse Semi-Definite Quadratic Programming Problems. Journal of Industrial and Management Optimization, 12, 317-336. [Google Scholar] [CrossRef] 
[16] Lu, Y., Huang, M., Zhang, Y. and Gu, J. (2019) A Nonconvex ADMM for a Class of Sparse Inverse Semidefinite Quadratic Programming Problems. Optimization, 68, 1075-1105. [Google Scholar] [CrossRef] 
[17] Wu, J., Zhang, Y., Zhang, L. and Lu, Y. (2016) A Sequential Convex Program Approach to an Inverse Linear Semidefinite Programming Problem. Asia-Pacific Journal of Operational Research, 33, Article ID: 1650025. [Google Scholar] [CrossRef] 
[18] Xiao, X., Zhang, L. and Zhang, J. (2009) A Smoothing Newton Method for a Type of Inverse Semi-Definite Quadratic Programming Problem. Journal of Computational and Applied Mathematics, 223, 485-498. [Google Scholar] [CrossRef] 
[19] Xiao, X., Zhang, L. and Zhang, J. (2009) On Convergence of Augmented Lagrangian Method for Inverse Semi-Definite Quadratic Programming Problems. Journal of Industrial & Management Optimization, 5, 319-339. [Google Scholar] [CrossRef] 
[20] Zhang, J.Z. and Liu, Z.H. (1996) Calculating Some Inverse Linear Programming Problems. Journal of Computational and Applied Mathematics, 72, 261-273. [Google Scholar] [CrossRef] 
[21] Zhang, J. and Liu, Z. (1999) A Further Study on Inverse Linear Programming Problems. Journal of Computational and Applied Mathematics, 106, 345-359. [Google Scholar] [CrossRef] 
[22] Zhang, J. and Zhang, L. (2009) An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems. Applied Mathematics and Optimization, 61, 57-83. [Google Scholar] [CrossRef] 
[23] Zhang, Y., Jiang, Y., Zhang, L. and Zhang, J. (2013) A Perturbation Approach for an Inverse Linear Second-Order Cone Programming. Journal of Industrial & Management Optimization, 9, 171-189. [Google Scholar] [CrossRef] 
[24] Ahmed, S. and Guan, Y. (2004) The Inverse Optimal Value Problem. Mathematical Programming, 102, 91-110. [Google Scholar] [CrossRef] 
[25] Mostafaee, A., Hladík, M. and Černý, M. (2016) Inverse Linear Programming with Interval Coefficients. Journal of Computational and Applied Mathematics, 292, 591-608. [Google Scholar] [CrossRef] 
[26] Černý, M. and Hladík, M. (2015) Inverse Optimization: Towards the Optimal Parameter Set of Inverse LP with Interval Coefficients. Central European Journal of Operations Research, 24, 747-762. [Google Scholar] [CrossRef] 
[27] Lv, Y., Hu, T. and Wan, Z. (2008) A Penalty Function Method for Solving Inverse Optimal Value Problem. Journal of Computational and Applied Mathematics, 220, 175-180. [Google Scholar] [CrossRef] 
[28] Lv, Y., Chen, Z. and Wan, Z. (2010) A Penalty Function Method Based on Bilevel Programming for Solving Inverse Optimal Value Problems. Applied Mathematics Letters, 23, 170-175. [Google Scholar] [CrossRef] 
[29] Lu, Y., Dong, Z., Hu, Z., Ma, H. and Xue, D. (2024) A Penalty-Type Method for Solving Inverse Optimal Value Problem in Second-Order Conic Programming. Applied Numerical Mathematics, 198, 419-427. [Google Scholar] [CrossRef] 
[30] Jia, J., Guan, X., Wang, H., Zhang, B. and Pardalos, P.M. (2023) Combinatorial Algorithms for Solving the Restricted Bounded Inverse Optimal Value Problem on Minimum Spanning Tree under Weighted l∞ Norm. Journal of Computational and Applied Mathematics, 419, 114754. [Google Scholar] [CrossRef] 
[31] Wang, H., Guan, X., Zhang, Q. and Zhang, B. (2021) Capacitated Inverse Optimal Value Problem on Minimum Spanning Tree under Bottleneck Hamming Distance. Journal of Combinatorial Optimization, 41, 861-887. [Google Scholar] [CrossRef] 
[32] Zhang, B., Guan, X. and Zhang, Q. (2020) Inverse Optimal Value Problem on Minimum Spanning Tree under Unit l∞ Norm. Optimization Letters, 14, 2301-2322. [Google Scholar] [CrossRef] 
[33] Zhang, B., Guan, X., Pardalos, P.M., Wang, H., Zhang, Q., Liu, Y., et al. (2020) The Lower Bounded Inverse Optimal Value Problem on Minimum Spanning Tree under Unit l∞ Norm. Journal of Global Optimization, 79, 757-777. [Google Scholar] [CrossRef] 
[34] Zhang, Q., Guan, X., Jia, J., Qian, X. and Pardalos, P.M. (2022) The Restricted Inverse Optimal Value Problem on Shortest Path under l∞ Norm on Trees. Journal of Global Optimization, 86, 251-284. [Google Scholar] [CrossRef] 
[35] Freund, R.M. (1987) Dual Gauge Programs, with Applications to Quadratic Programming and the Minimum-Norm Problem. Mathematical Programming, 38, 47-67. [Google Scholar] [CrossRef] 
[36] van den Berg, E. and Friedlander, M.P. (2011) Sparse Optimization with Least-Squares Constraints. SIAM Journal on Optimization, 21, 1201-1229. [Google Scholar] [CrossRef] 
[37] Teuber, T., Steidl, G. and Chan, R.H. (2013) Minimization and Parameter Estimation for Seminorm Regularization Models with i-Divergence Constraints. Inverse Problems, 29, Article ID: 035007. [Google Scholar] [CrossRef] 
[38] Jaggi, M. (2013) Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. International Conference on Machine Learning. PMLR, Atlanta, 17-19 June 2013, 427-435.
[39] Friedlander, M.P., Macêdo, I. and Pong, T.K. (2014) Gauge Optimization and Duality. SIAM Journal on Optimization, 24, 1999-2022. [Google Scholar] [CrossRef] 
[40] Rockafellar, R. (1972) Convex Analysis. Princeton University Press.
[41] Kumar Vatsa, A. and Chandra, S. (2024) Exact and Approximation Methods for Mixed-Integer Nonlinear Programming Problem. In: Hamid, F., Ed., Optimization Essentials: Theory, Tools, and Applications, Springer, 393-415. [Google Scholar] [CrossRef] 
[42] Castro, P.M. (2015) Tightening Piecewise McCormick Relaxations for Bilinear Problems. Computers & Chemical Engineering, 72, 300-311. [Google Scholar] [CrossRef] 
[43] Byrne, C.L. (2012) Alternating Minimization as Sequential Unconstrained Minimization: A Survey. Journal of Optimization Theory and Applications, 156, 554-566. [Google Scholar] [CrossRef] 

为你推荐