CQ-free optimality conditions and strong dual formulations for a special conic optimization problem
Abstract
In this paper, we consider a special class of conic optimization problems, consisting of set-semidefinite(or K-semidefinite) programming problems, where the set K is a polyhedral convex cone. For these problems, we introduce the concept of immobile indices and study the properties of the set of normalized immobile indices and the feasible set. This study provides the main result of the paper, which is to formulate and prove the new first-order optimality conditions in the form of a criterion. The optimality conditions are explicit and do not use any constraint qualifications. For the case of a linear cost function, we reformulate the K-semidefinite problem in a regularized form and construct its dual. We show that the pair of the primal and dual regularized problems satisfies the strong duality relation which means that the duality gap is vanishing.References
Ahmed F., Dür M., Still G. Copositive Programming via Semi-Infinite Optimization, J. Optim. Theory Appl., 159, pp. 322–340, 2013.
Anjos M.F., Lasserre J.B. Eds. Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, International Series in Operational Research and Management Science, 166 p., Springer,2012
Asprey S.P., Maccietto S. Eds. Dynamic model development: methods, theory and applications, In: Proceedings of the Workshop on the Life af a Process Model-From Conception to Action, Imperial Colledge, London, UK, October 25-26, 2000.
Berman A., Shaked-Monderer N. PCompletely Positive Matrices, World Scientific, 2003, 216 p.
Bomze I.M. Copositive optimization - Recent developments and applications, EJOR 216(3), pp. 509–520, 2012.
Bomze I.M., Dür M., de Klerk E., Roos C., Quist A.J., Terlaky T. On copositive programming and standard quadratic optimization problems, Journal Global Optim. 18, pp. 301–320, 2000.
Bonnans J.F., Shapiro A. Perturbation analysis of optimization problems, Springer-Verlag, New-York, 2000.
Boyd S. P., Vandenberghe L. Convex Optimization, Cambridge University Press, 2004.
de Klerk E., Pasechnik D.V. Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, pp. 875–892, 2002.
Dür M. Copositive Programming – a Survey, In: Diehl M, Glineur F, Jarlebring E, Michielis W., editors. Recent advances in Optimization and its applications in Engineering; Springer-Verlag Berlin Heidelberg X1: 535 p., 2010.
Eichfelder G., Jahn J. Foundations of Set-Semidefinite Optimization., In: Pardalos P., Rassias T., Khan A. (eds) Nonlinear Analysis and Variational Problems. Springer Optimization and Its Applications, vol 35. pp. 259-284. Springer, New York, NY, 2010.
Eichfelder G., Jahn J. Set-semidefinite optimization, Journal of Convex Analysis, 15, pp. 767-801, 2008.
Glineur F. Conic optimization: an elegant framework for convex optimization, Belgian Journal of Operations Research, Statistics and Computer Science, 41, pp. 5?8,2001.
Kliemann L., Shirazi Sheykhdarabadi E., and Srivastav A. Price of anarchy for graph coloring games with concave payoff, JDG (by AIMS) 4(1), pp. 41-58, 2017.
Kostyukova O.I., Tchemisova T.V. Implicit optimality criterion for convex SIP problem with box constrained index set, TOP, 20 (2), pp. 475–502, 2012.
Kostyukova O.I., Tchemisova T.V. Optimality conditions for convex semi-infinite programming problems with finitely representable compact index sets, J. Optim. Theory Appl. 175(1), pp. 76-103, 2017.
Kostyukova O.I., Tchemisova T.V. Optimality conditions for linear copositive programming problems with isolated immobile indices, Optimization, vol. 69, issue 1, pp. 145-164, 2020.
Kostyukova O.I., Tchemisova T.V. Optimality criteria without constraint qualification for linear semidefinite problems, JMS-Journal of Mathematical Sciences, 182 (2), pp. 126-143, 2012.
Kostyukova O.I., Tchemisova T.V. Sufficient optimality conditions for convex semi-infinite programming, Optimization Methods and Software, 25 (2), pp. 279-297, 2010.
Kostyukova O.I., TchemisovaT.V.,Dudina O.S. Immobile indices and CQ-freeoptimality criteria for linear copositive programming problems, Set-Valued Var. Anal., 28, pp. 89-107, 2020.
Laraki, R., Lasserre, J.B. Semidefinite programming for min-max problems and games, Math. Program. 131, 305-332, 2012.
Motzkin, T. Copositive quadratic forms, National Bureau of Standards,Report 1818, pp. 11-12 , 1952.
Özögür-Akyüz S., Akteke-Öztürk B., Tchemisova T., Weber G.-W. New optimization methods in Data Mining, In: Fleischmann B., Borgwardt KH., Klein R., Tuma A. (eds) Operations Research Proceedings. Springer, Berlin, Heidelberg, pp. 527-532, 2009.
Ramana, M. V., Tuncel, L., Wolkowicz H. Strong duality for semidefinite programming, SIAM J. Optimization, 7 (3), pp. 641-662, 1997.
Rockafellar R.T. Convex Analysis, Princeton Univ. Press, Vol.28, Princeton Univ. Pres, NJ, 470 p., 1970.
Shapiro A. Semi-infinite programming, duality, discretization and optimality conditions, Optimization, 58:2, pp. 133-161, 2009.
Sra S., Novozin S., and Wright S. J. Optimization for machine learning, Neural information processing series. Cambridge, MIT Press, 2012.
Stein O. How to solve a semi-infinite optimization problem, EJOR, vol. 223, Issue 2, pp. 312-320, 2012.
Stein O., Still G. On Optimality Conditions for Generalized Semi-Infinite Programming Problems, J. Optim. Theory Appl. 104, pp. 443-458, 2000.
Tunc¸el L., Wolkowicz H. Strong duality and minimal representations for cone optimization, Comput. Optim. Appl. 53, pp. 619–648, 2013.
Vasant P. , Alparslan-Gök S.Z., and Weber G.-W. Handbook of Research on Emergent Applications of Optimization Algorithms, Volumes 1-2, IGI Global, Hershey PA, USA, 2017.
Weber G.-W., Kropat E., Alparslan Gök S.Z. Semi-Infinite and Conic Optimization in Modern Human Life and Financial Sciences under Uncertainty, In: ISI Proceedings of 20th Mini-EURO conference, pp. 180–185, 2008.
Wolkowicz H., Saigal R., Vandenberghe L. Eds. Handbook of semidefinite programming: theory, algorithms, and applications, Kluwer Academic Publishers, Boston, MA, 2000, 654 p.
Zaslavski A. Structure of approximate solutions of dynamic continuous time zero-sum games, JDG (by AIMS), 2014, 1(1): 153-179.
Zhang H., Bai Y., Fang C. Linear conic optimization models for robust credit risk optimization, Operations Research Transactions, v. 17 (1), 86-97, 2013.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
