Abstract
In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an \({(k\,sin(\frac{\pi}{k}))^2/(4\pi)}\) -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon, N., Makarychev, K., Makarychev, Y., Naor, A.: Quadratic forms on graphs. In: Proceedings of the 37th annual ACM symposium on theory of computing, pp. 486–493 (2005)
Alon, N., Naor, A.: Approximating the Cut–Norm via Grothendieck’s inequality. In: Proceedings of the 36th annual ACM symposium on theory of computing, pp. 72–80 (2004)
Ben-Tal A., Nemirovski A. and Roos C. (2003). Extended matrix cube theorems with applications to μ–theory in control. Math. Oper. Res. 28(3): 497–523
Charikar, M., Wirth, A.: Maximizing quadratic programs: extending Grothendieck’s inequality. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science, pp. 54–60 (2004)
Frieze A. and Jerrum M. (1997). Improved approximation algorithms for Max k–Cut and Max bisection. Algorithmica 18: 67–81
Goemans M.X. and Rendl F. (2000). Combinatorial optimization. In: Wolkowicz, H., Saigal, R. and Vandenberghe, L. (eds) Handbook of semidefinite programming: theory, algorithms and applications, pp 343–360. Kluwer, Dordrecht
Goemans M.X. and Williamson D.P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6): 1115–1145
Goemans M.X. and Williamson D.P. (2004). Approximation algorithms for Max–3–Cut and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68(2): 442–470
Hochbaum, D.S. (ed): Approximation Algorithms for NP-hard problems. PWS Publishing Company, (1997)
Nemirovski A., Roos C. and Terlaky T. (1999). On maximization of quadratic form over intersection of ellipsoids with common center. Math. Prog. Ser. A 86: 463–473
Nesterov, Y.: Global quadratic optimization via conic relaxation, CORE Discussion Paper 9860. Université Catholique de Louvain (1998)
Rietz R.E. (1974). A proof of the Grothendieck inequality. Israel J. Math. 19: 271–276
Toker O. and Özbay H. (1998). On the complexity of purely complex μ computation and related problems in multidimensional systems. IEEE Trans Automat Control 43(3): 409–414
Vandenberghe L. and Boyd S. (1996). Semidefinite programming. SIAM Rev 38(1): 49–95
Ye Y. (1999). Approximating quadratic programming with bound and quadratic constraints. Math. Prog. 84: 219–226
Zhang, S., Huang, Y.: Complex quadratic optimization and semidefinite programming. Technical Report SEEM 2004–03, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, 2004. SIAM J. Optim. 16(3), 871–890 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper has appeared in the Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization (IPCO XI), 2005.
This research was supported in part by NSF grant DMS-0306611.
Rights and permissions
About this article
Cite this article
So, A.MC., Zhang, J. & Ye, Y. On approximating complex quadratic optimization problems via semidefinite programming relaxations. Math. Program. 110, 93–110 (2007). https://doi.org/10.1007/s10107-006-0064-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0064-6