Top

Published in:

2013 | OriginalPaper | Chapter

28. Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals

Author : Gábor Pataki

Published in: Computational and Analytical Mathematics

Publisher: Springer New York

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The facial reduction algorithm (FRA) of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program

$$\displaystyle{ \sup \,\{\,\langle c,x\rangle \,\vert \,Ax \leq _{K}b\,\} }$$

(P)

in the absence of any constraint qualification. The FRA solves a sequence of auxiliary optimization problems to obtain such a dual. Ramana’s dual is applicable when (P) is a semidefinite program (SDP) and is an explicit SDP itself. Ramana, Tunçel, and Wolkowicz showed that these approaches are closely related; in particular, they proved the correctness of Ramana’s dual using certificates from a facial reduction algorithm. Here we give a simple and self-contained exposition of facial reduction, of extended duals, and generalize Ramana’s dual:

We state a simple FRA and prove its correctness.
Building on this algorithm we construct a family of extended duals when K is a nice cone. This class of cones includes the semidefinite cone and other important cones.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Convergence of Linesearch and Trust-Region Methods Using the Kurdyka–Łojasiewicz Inequality

next chapter Towards a New Era in Subdifferential Analysis?

Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. Ser. B 95 3–51 (2003)MathSciNetCrossRefMATH

Andersen, E.D., Roos, C., Terlaky, T.: Notes on duality in second order and p-order cone optimization. Optimization 51, 627–643 (2002)MathSciNetCrossRefMATH

Ben-Tal, A., Nemirovskii, A.: Lectures on Modern Convex Optimization. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2001)MATH

Bonnans, F.J., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Series in Operations Research. Springer, New York (2000)MATH

Borwein, J.M., Wolkowicz, H.: Facial reduction for a cone-convex programming problem. J. Aust. Math. Soc. 30, 369–380 (1981)MathSciNetCrossRefMATH

Borwein, J.M., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. App. 83, 495–530 (1981)MathSciNetCrossRefMATH

Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)CrossRefMATH

Cheung, V., Wolkowicz, H., Schurr, S.: Preprocessing and regularization for degenerate semidefinite programs. Technical Report, University of Waterloo (2012)

Chua, C.-B.: Relating homogeneous cones and positive definite cones via T-algebras. SIAM J. Optim. 14, 500–506 (2003)MathSciNetCrossRefMATH

10.

Chua, C.-B., Tunçel, L.: Invariance and efficiency of convex representations. Math. Program. B 111, 113–140 (2008)CrossRefMATH

11.

Faybusovich, L.: On Nesterov’s approach to semi-definite programming. Acta Appl. Math. 74, 195–215 (2002)MathSciNetCrossRefMATH

12.

Freund, R.M.: Talk at the University of Waterloo (1994)

13.

Freund, R.M., Roundy, R., Todd, M.J.: Identifying the set of always-active constraints in a system of linear inequalities by a single linear program. Technical Report Sloan W.P. No. 1674–1685, Sloan School of Business, MIT (1985)

14.

Gouveia, J., Parrilo, P., Thomas, R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. (2013) (to appear)

15.

G$\ddot{\mathrm{u}}$ler, O.: Foundations of Optimization. Graduate Texts in Mathematics. Springer, New York (2010)

16.

Helmberg, C.: The semidefinite programming webpage. http://www-user.tu-chemnitz.de/~semidef.html

17.

Klep, I., Schweighofer, M.: An exact duality theory for semidefinite programming based on sums of squares. Technical Report, Universität Konstanz. http://arxiv.org/abs/1207.1691 (2012)

18.

Lewis, A.S.: Facial reduction in partially finite convex programming. Math. Program. B 65, 123–138 (1994)CrossRefMATH

19.

Luo, Z.-Q., Sturm, J.: Error analysis. In: Saigal, R., Vandenberghe, L., Wolkowicz, H. (eds.) Handbook of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht (2000)

20.

Luo, Z.-Q., Sturm, J., Zhang, S.: Duality results for conic convex programming. Technical Report 9719/A, Econometric Institute, Erasmus University, Rotterdam (1997)

21.

Pataki, G.: A simple derivation of a facial reduction algorithm and extended dual systems. Technical Report, Columbia University (2000)

22.

Pataki, G.: On the closedness of the linear image of a closed convex cone. Math. Oper. Res. 32, 395–412 (2007)MathSciNetCrossRefMATH

23.

Pataki, G.: Bad semidefinite programs: they all look the same. Technical Report, University of North Carolina at Chapel Hill (2010). Available from http://arxiv.org/abs/1112.1436 (under review)

24.

Pataki, G.: On the connection of facially exposed and nice cones. J. Math. Anal. App. 400, 211–221 (2013)MathSciNetCrossRefMATH

25.

Pólik, I., Terlaky, T.: Exact duality for optimization over symmetric cones. Technical Report, Lehigh University (2009)

26.

Ramana, M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Program. Ser. B 77, 129–162 (1997)MathSciNetMATH

27.

Ramana, M.V., Tunçel, L., Wolkowicz, H.: Strong duality for semidefinite programming. SIAM J. Opt. 7, 641–662 (1997)CrossRefMATH

28.

Rockafellar, T.R.: Convex Analysis. Princeton University Press, Princeton (1970)MATH

29.

Schurr, S.P., Tits, A.L., O’Leary, D.P.: Universal duality in conic convex optimization. Math. Program. 109, 69–88 (2007)MathSciNetCrossRefMATH

30.

Tunçel, L., Wolkowicz, H.: Strong duality and minimal representations for cone optimization. Comput. Optim. Appl. 53, 619–648

31.

Roshchina, V.: Facially exposed cones are not nice in general. Technical Report, University of Ballarat (2013). http://arxiv.org/abs/1301.1000

32.

Saigal, R., Vandenberghe, L., Wolkowicz, H. (eds.): Handbook of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht (2000)

33.

Jos Sturm: Error bounds for linear matrix inequalities. SIAM J. Optim. 10, 1228–1248 (2000)

34.

Todd, M.J.: Semidefinite Optimization. Acta Numer. 10, 515–560 (2001)MathSciNetMATH

35.

Tunçel, L.: Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization. Fields Institute Monographs. American Mathematical Society, Providence (2011)

36.

Waki, H., Muramatsu, M.: Facial reduction algorithms for conic optimization problems. Technical Report CS-09-01, Department of Computer Science, The University of Electro-Communications (2009)

37.

Wang, Y., Xiu, N., Luo, Z.: A regularized strong duality for nonsymmetric semidefinite least squares problem. Optim. Lett. 5, 665–682 (2011)MathSciNetCrossRefMATH

Title: Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals
Author: Gábor Pataki
Publisher: Springer New York
Book: Computational and Analytical Mathematics
Print ISBN: 978-1-4614-7620-7

Electronic ISBN: 978-1-4614-7621-4

Copyright Year: 2013
DOI: https://doi.org/10.1007/978-1-4614-7621-4_28

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner