|
|
一类逆度规最优值问题的可解性和复杂性研究
|
Abstract:
逆优化作为优化理论的重要分支，近年来在多个领域展现出广泛的应用前景。本文研究一类新型逆优化问题——逆度规最优值问题，其目标是在给定最优目标值估计的条件下，反推成本向量参数，使得对应的度规优化问题的最优值与之匹配。本文首先在适当的假设下，利用度规对偶理论分析了该问题的可解性，证明了最优解的存在性。进一步，通过构造与二元整数可行性问题的等价性，证明了逆度规最优值问题属于NP难问题。最后，基于度规函数的极函数表示与对偶理论，将原问题转化为两类带有双线性约束的优化模型，为后续算法设计提供了理论基础。
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] | Parker, D.J. (1999) Introduction to Inverse Problems in Imaging. Computer Physics Communications, 120, 269-270. https://doi.org/10.1016/s0010-4655(99)00257-x |
| [2] | Kim, Y. and Nakata, N. (2018) Geophysical Inversion versus Machine Learning in Inverse Problems. The Leading Edge, 37, 894-901. https://doi.org/10.1190/tle37120894.1 |
| [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. https://doi.org/10.1038/s42005-018-0058-8 |
| [4] | Colton, D., Coyle, J. and Monk, P. (2000) Recent Developments in Inverse Acoustic Scattering Theory. SIAM Review, 42, 369-414. https://doi.org/10.1137/s0036144500367337 |
| [5] | Cheon, M.S. (2021) An Outer-Approximation Guided Optimization Approach for Constrained Neural Network Inverse Problems. Mathematical Programming, 196, 173-202. https://doi.org/10.1007/s10107-021-01653-y |
| [6] | Chan, T.C.Y., Mahmood, R. and Zhu, I.Y. (2025) Inverse Optimization: Theory and Applications. Operations Research, 73, 1046-1074. https://doi.org/10.1287/opre.2022.0382 |
| [7] | Burton, D. and Toint, P.L. (1992) On an Instance of the Inverse Shortest Paths Problem. Mathematical Programming, 53, 45-61. https://doi.org/10.1007/bf01585693 |
| [8] | Ahuja, R.K. and Orlin, J.B. (2001) Inverse Optimization. Operations Research, 49, 771-783. https://doi.org/10.1287/opre.49.5.771.10607 |
| [9] | Ahuja, R.K. and Orlin, J.B. (2002) Combinatorial Algorithms for Inverse Network Flow Problems. Networks, 40, 181-187. https://doi.org/10.1002/net.10048 |
| [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. https://doi.org/10.1023/a:1008360312607 |
| [11] | Heuberger, C. (2004) Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results. Journal of Combinatorial Optimization, 8, 329-361. https://doi.org/10.1023/b:joco.0000038914.26975.9b |
| [12] | Zhang, J. and Ma, Z. (1999) Solution Structure of Some Inverse Combinatorial Optimization Problems. Journal of Combinatorial Optimization, 3, 127-139. https://doi.org/10.1023/a:1009829525096 |
| [13] | Zhang, J., Liu, Z. and Ma, Z. (2000) Some Reverse Location Problems. European Journal of Operational Research, 124, 77-88. https://doi.org/10.1016/s0377-2217(99)00122-8 |
| [14] | Iyengar, G. and Kang, W. (2005) Inverse Conic Programming with Applications. Operations Research Letters, 33, 319-330. https://doi.org/10.1016/j.orl.2004.04.007 |
| [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. https://doi.org/10.3934/jimo.2016.12.317 |
| [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. https://doi.org/10.1080/02331934.2019.1576663 |
| [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. https://doi.org/10.1142/s0217595916500251 |
| [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. https://doi.org/10.1016/j.cam.2008.01.028 |
| [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. https://doi.org/10.3934/jimo.2009.5.319 |
| [20] | Zhang, J.Z. and Liu, Z.H. (1996) Calculating Some Inverse Linear Programming Problems. Journal of Computational and Applied Mathematics, 72, 261-273. https://doi.org/10.1016/0377-0427(95)00277-4 |
| [21] | Zhang, J. and Liu, Z. (1999) A Further Study on Inverse Linear Programming Problems. Journal of Computational and Applied Mathematics, 106, 345-359. https://doi.org/10.1016/s0377-0427(99)00080-1 |
| [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. https://doi.org/10.1007/s00245-009-9075-z |
| [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. https://doi.org/10.3934/jimo.2013.9.171 |
| [24] | Ahmed, S. and Guan, Y. (2004) The Inverse Optimal Value Problem. Mathematical Programming, 102, 91-110. https://doi.org/10.1007/s10107-004-0515-x |
| [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. https://doi.org/10.1016/j.cam.2015.07.034 |
| [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. https://doi.org/10.1007/s10100-015-0402-y |
| [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. https://doi.org/10.1016/j.cam.2007.08.005 |
| [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. https://doi.org/10.1016/j.aml.2009.09.007 |
| [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. https://doi.org/10.1016/j.apnum.2024.02.004 |
| [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. https://doi.org/10.1016/j.cam.2022.114754 |
| [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. https://doi.org/10.1007/s10878-021-00721-5 |
| [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. https://doi.org/10.1007/s11590-020-01553-8 |
| [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. https://doi.org/10.1007/s10898-020-00947-3 |
| [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. https://doi.org/10.1007/s10898-022-01256-7 |
| [35] | Freund, R.M. (1987) Dual Gauge Programs, with Applications to Quadratic Programming and the Minimum-Norm Problem. Mathematical Programming, 38, 47-67. https://doi.org/10.1007/bf02591851 |
| [36] | van den Berg, E. and Friedlander, M.P. (2011) Sparse Optimization with Least-Squares Constraints. SIAM Journal on Optimization, 21, 1201-1229. https://doi.org/10.1137/100785028 |
| [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. https://doi.org/10.1088/0266-5611/29/3/035007 |
| [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. https://doi.org/10.1137/130940785 |
| [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. https://doi.org/10.1007/978-981-99-5491-9_13 |
| [42] | Castro, P.M. (2015) Tightening Piecewise McCormick Relaxations for Bilinear Problems. Computers & Chemical Engineering, 72, 300-311. https://doi.org/10.1016/j.compchemeng.2014.03.025 |
| [43] | Byrne, C.L. (2012) Alternating Minimization as Sequential Unconstrained Minimization: A Survey. Journal of Optimization Theory and Applications, 156, 554-566. https://doi.org/10.1007/s10957-012-0134-2 |
