Finally, as combinatorial applications of complex quadratic optimization; we consider Max 3-Cut with fixed nodes constraints, Max 3-Dicut with weight constraints, Max 3-XOR, and so on, and present corresponding bounds on the approximation ratios. / Quadratic optimization problems with complex-valued decision variables, in short called complex quadratic optimization problems, find many applications in engineering. In this dissertation, we study several instructive models of complex quadratic optimization, as well as its applications in combinatorial optimization. The tool that we use is a combination of semidefinite programming (SDP) relaxation and randomization technique, which has been well exploited in the last decade. Since most of the optimization models are NP-hard in nature, we shall design polynomial time approximation algorithms for a general model, or polynomial time exact algorithms for some restricted instances of a general model. / To enable the analysis, we first develop two basic theoretical results: one is the probability formula for a bivariate complex normal distribution vector to be in a prescribed angular region, and the other one is the rank-one decomposition theorem for complex positive semidefinite matrices. The probability formula enables us to compute the expected value of a randomized (with a specific rounding rule) solution based on an optimal solution of the SDP relaxation problem, while the rank-one decomposition theorem provides a new proof of the complex S -lemma and leads to novel deterministic rounding procedures. / With the above results in hand, we then investigate the models and applications of complex quadratic optimization via semidefinite programming in detail. We present an approximation algorithm for a convex quadratic maximization problem with discrete complex decision variables, where the approximation analysis is based on the probability formula. Besides, an approximation algorithm is proposed for a non-convex quadratic maximization problem with discrete complex decision variables. Then we study a limit of the model, i.e., a quadratic maximization problem with continuous unit module decision variables. The problem is shown to be strongly NP-hard. Approximation algorithms are described for the problem, including both convex case and non-convex case. Furthermore, if the objective matrix has a sign structure, then a stronger approximation result is shown to hold. In addition, we use the complex matrix decomposition theorem to solve complex quadratically constrained complex quadratic programming. We consider several interesting cases for which the corresponding SDP relaxation admits no gap with the true optimal value, and consequently, this yields polynomial time procedures for solving those special cases of complex quadratic optimization. / Huang Yongwei. / "August 2005." / Adviser: Shuzhong Zhang. / Source: Dissertation Abstracts International, Volume: 67-07, Section: B, page: 4033. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (p. 142-155). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_343664 |
| Date | January 2005 |
| Contributors | Huang, Yongwei., Chinese University of Hong Kong Graduate School. Division of Systems Engineering and Engineering Management. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, theses |
| Format | electronic resource, microform, microfiche, 1 online resource (ix, 155 p. : ill.) |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0022 seconds