Exploring constraint qualification-free optimality conditions for linear second-order cone programming
DOI:
https://doi.org/10.11121/ijocta.1421Keywords:
Second-order Cone Programming, constraint qualification, optimality conditions, immobile indicesAbstract
Linear second-order cone programming (SOCP) deals with optimization problems characterized by a linear objective function and a feasible region defined by linear equalities and second-order cone constraints. These constraints involve the norm of a linear combination of variables, enabling the representation of a wide range of convex sets. The SOCP serves as a potent tool for addressing optimization challenges across engineering, finance, machine learning, and various other domains. In this paper, we introduce new optimality conditions tailored for {SOCP} problems. These conditions have the form of two optimality criteria that are obtained without the requirement of any constraint qualifications and are defined explicitly. The first criterion utilizes the concept of immobile indices of constraints. The second criterion, without relying explicitly on immobile indices, introduces a special finite vector set for assessing optimality. To demonstrate the effectiveness of these criteria, we present two illustrative examples highlighting their applicability. We compare the obtained criteria with other known optimality conditions and show the advantage of the former ones.
Downloads
References
Nesterov, Y., & Nemirovski, A.S. (1992). Conic formulation of a convex programming problem and duality. Optimization Methods & Software, 1(2), 95-115. https://doi.org/10.1080/10556789208805510
Glineur, F. (2001). Conic optimization: an elegant framework for convex optimization. Belgian Journal of Operations Research, Statistics and Computer Science, 41(1-2), 5-28.
Dur, M. & Rendl, F. (2021). Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems. EURO Journal on Computational Optimization, v.9, 100021. https://doi.org/10.1016/j.ejco.2021.100021
Hanasusanto, G. A., & Kuhn, D. (2018). Conic programming reformulations of two stage distributionally robust linear programs over Wasserstein balls. Operations Research, 66(3), 849-869. https://doi.org/10.1287/opre.2017.1698
Kocuk, B. (2021) Conic reformulations for Kullback-Leibler divergence constrained distributionally robust optimization and applications. An International Journal of Optimization and Control: Theories and Applications, 11(2), pp.139-151. https://doi.org/10.11121/ijocta.01.2021.001001
Pataki, G. (2000). The geometry of semidefinite programming. In: H. Wolkowicz, R. Saigal, & L. Vandenberghe (eds.) Handbook of Semidefinite Programming. International Series in Operations Research & Management Science, vol 27. Springer, Boston, MA, 29-65. https://doi.org/10.1007/978-1-4615-4381-7_3
Vandenberghe, L. & Boyd, S. (1996). Semidefinite programming. SIAM Review, 38(1), 49-95. https://doi.org/10.1137/1038003
Anjos, M.F. & Lasserre, J.B. (2012) Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research & Management Science, Springer New York, NY. https://doi.org/10.1007/978-1-4614-0769-0
Alizadeh, F. & Goldfarb, D. (2003). Second-order cone programming. Mathematical Programming, Ser. B, 95, 3-51. https://doi.org/10.1007/s10107-002-0339-5
Lobo, M.S., Vandenberghe, L., Boyd, S., & Lebret, H. (1998). Applications of second order cone programming. Linear Algebra and Its Applications, 284, 193-228. https://doi.org/10.1016/S0024-3795(98)10032-0
Luo, Z.-Q. & Sturm, J. F. (2000). Error analysis. In: H. Wolkowicz, R. Saigal, L. Vandenberghe (eds) Handbook of Semidefinite Programming. International Series in Operations Research & Management Science, vol 27. Springer, Boston, MA, 163-190.
Meng, J., Cao, P., Huang, J., Lin, H., Chen, Y., & Cao, R. (2019) Second-order cone programming formulation of discontinuous deformation analysis. IJNME- International Journal for Numerical Methods in Engineering. 118(5), 243-57. https://doi.org/10.1002/nme.6006
Wang, D., Chen, X., Lyu, Y., & Tang, C. (2019) Geotechnical localization analysis based on Cosserat continuum theory and second-order cone programming optimized finite element method. Computers and Geotechnics. 114, 103-118. https://doi.org/10.1016/j.compgeo.2019.103118
Zhang, Y., & Zhang, L. (2019). New constraint qualifications and optimality conditions for second order cone programs. Set-Valued and Variational Analysis. 27, 693-712. https://doi.org/10.1007/s11228-018-0487-2
Bonnans, J.F., & Shapiro, A. (2000). Perturbation analysis of optimization problems. Springer, New York.
Kostyukova, O. I., Tchemisova, T. V., & Dudina, O. S. (2020). Immobile indices and CQ-free optimality criteria for linear copositive programming problems. Set-Valued and Variational Analysis. 28, 89-107. https://doi.org/10.1007/s11228-019-00527-y
Kapoor, M., Suneja, S. K., & Sharma, S. (2016). Generalized (?, ?)-convexity in nonsmooth vector optimization over cones. An International Journal of Optimization and Control: Theories & Applications, 6(1), 1-7. https://doi.org/10.11121/ijocta.01.2016.00247
Andreani, R., Martinez, J.M., Silva, P.S., & Ramos, A.( 2018). Strict constraint qualifications and sequential optimality conditions for constrained optimization. Mathematics of Operations Research online, 43, 693-717. https://doi.org/10.1287/moor.2017.0879
Jeyakumar, V. (2008). Constraint qualifications characterizing Lagrangian duality in convex optimization. Journal of Optimization Theory and Applications, 136, 31-41. https://doi.org/10.1007/s10957-007-9294-x
Andreani, R., Fukuda, E. H., Haeser, G., Santos, D.O., & Secchin, L.D. (2024) Optimality conditions for nonlinear second-order cone programming and symmetric cone programming. Journal of Optimization Theory and Applications, 200, 1-13. https://doi.org/10.1007/s10957-023-02338-6
Gorokhovik, V.V. (2021). Step-affine functions, halfspaces, and separation of convex sets with applications to convex optimization problems. In: Proceedings of the Steklov Institute of Mathematics, 313(1), S83-S99. https://doi.org/10.1134/S008154382103010X
Kortanek, K. O., Yu, G., & Zhang, Q. (2021). Strong duality for standard convex programs. Mathematical Methods of Operations Research, 94(3), 413-436. https://doi.org/10.1007/s00186-021-00761-x
Cochran, J.J., Cox, L.A., Jr., Keskinocak, P., Kharoufeh, J.P., Smith, J.C., & Solodov, M.V. (2011). Constraint qualifications. In: J.J. Cochran, L.A. Cox, P. Keskinocak,J.P. Kharoufeh, & J.C. Smith (eds.) Wiley Encyclopedia of Operations Research and Management Science. Wiley. https://doi.org/10.1002/9780470400531
Bonnans, J.F., & Ramirez, H. (2005) Perturbation analysis of second-order cone programming problems. Mathematical Programming, 104(2), 205-227. https://doi.org/10.1007/s10107-005-0613-4
Kruger, A.Y., Minchenko, L., Outrata, J.V. (2013) On relaxing the Mangasarian-Fromovitz constraint qualification. Positivity, 18, 171-189. https://doi.org/10.1007/s11117-013-0238-4
Andreani, R., Haeser, G., Mito, L.M., Ramirez, H., Santos, D.O., & Silveira, T.P. (2022) Naive constant rank-type constraint qualifications for multifold second-order cone programming and semidefinite programming. Optimization Letters, 16, 589-610. https://doi.org/10.1007/s11590-021-01737-w
Andersen, E. D., Roos, C., & Terlaky, T. (2002). Notes on duality in second order and p-order cone optimization. Optimization, 51(4), 627-643. https://doi.org/10.1080/0233193021000030751
Kostyukova, O., & Tchemisova, T. (2015). Convex SIP problems with finitely representable compact index sets: immobile indices and the properties of the auxiliary NLP problem, Set-Valued and Variational Analysis, 23(3), 519-546. https://doi.org/10.1007/s11228-015-0320-0
Tuncel, L., & Wolkowicz, H. (2013). Strong duality and minimal representations for cone optimization. Computational Optimization and Applications. 53, 619-648. https://doi.org/10.1007/s10589-012-9480-0
Kostyukova, O., & Tchemisova, T. (2021). Structural properties of faces of the cone of copositive matrices. Mathematics, 9(21), 2698. https://doi.org/10.3390/math9212698
Golshtein, E. G. (1971). Theory of duality in mathematical programming and its applications. Nauka. Moscow. (in Russian)
Liu, M., & Pataki, G. (2018). Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming. Mathematical Programming, 167, 435-480. https://doi.org/10.1007/s10107-017-1136-5
Ramana, M. V., Tuncel, L., & Wolkowicz, H. (1997). Strong duality for semidefinite programming. SIAM Journal on Optimization, 7(3), 641-662. https://doi.org/10.1137/S1052623495288350
Kostyukova, O. I., & Tchemisova, T. V. (2022). On strong duality in linear copositive programming. Journal of Global Optimization, 83(3), 457-480. https://doi.org/10.1007/s10898-021-00995-3
Kostyukova, O.I. & Tchemisova,T.V. (2023) An exact explicit dual for the linear copositive programming problem. Optimization Letters, 17, 107-120. https://doi.org/10.1007/s11590-022-01870-0
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Olga Kostyukova, Tatiana Tchemisova
This work is licensed under a Creative Commons Attribution 4.0 International License.
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.