Thesis (Ph. D.)--Lehigh University, 1997. / Includes vita. Bibliography: leaves 119-120.

published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

No description available.

No description available.

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.

Cheung, Ho Yee. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 91-96). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- Matroids and Matrices --- p.5 / Chapter 2.1.1 --- Examples --- p.6 / Chapter 2.1.2 --- Constructions --- p.7 / Chapter 2.1.3 --- Matroid Intersection --- p.8 / Chapter 2.1.4 --- Matroid Parity --- p.9 / Chapter 2.2 --- Matrix Formulations --- p.14 / Chapter 2.2.1 --- Graph Matching --- p.15 / Chapter 2.2.2 --- Skew-Symmetric Matrix --- p.16 / Chapter 2.2.3 --- Linear Matroid Parity --- p.21 / Chapter 2.2.4 --- Weighted Problems --- p.25 / Chapter 2.3 --- Algebraic Tools --- p.26 / Chapter 2.3.1 --- Matrix Algorithms --- p.26 / Chapter 2.3.2 --- Computing Matrix Inverse --- p.28 / Chapter 2.3.3 --- Matrix of Indeterminates --- p.32 / Chapter 2.3.4 --- Mixed Skew-symmetric Matrix --- p.34 / Chapter 2.4 --- Algebraic Algorithms for Graph Matching --- p.35 / Chapter 2.4.1 --- Matching in O{nw+1) time --- p.36 / Chapter 2.4.2 --- Matching in O(n3) time --- p.37 / Chapter 2.4.3 --- Matching in O(nw) time --- p.38 / Chapter 2.4.4 --- Weighted Algorithms --- p.39 / Chapter 2.4.5 --- Parallel Algorithms --- p.40 / Chapter 2.5 --- Algebraic Algorithms for Graph Connectivity --- p.41 / Chapter 2.5.1 --- Previous Approach --- p.41 / Chapter 2.5.2 --- Matrix Formulation Using Network Coding --- p.42 / Chapter 3 --- Linear Matroid Parity --- p.49 / Chapter 3.1 --- Introduction --- p.49 / Chapter 3.1.1 --- Problem Formulation and Previous Work --- p.50 / Chapter 3.1.2 --- Our Results --- p.52 / Chapter 3.1.3 --- Techniques --- p.55 / Chapter 3.2 --- Preliminaries --- p.56 / Chapter 3.3 --- A Simple Algebraic Algorithm for Linear Matroid Parity --- p.56 / Chapter 3.3.1 --- An 0(mr2) Algorithm --- p.56 / Chapter 3.4 --- Graph Algorithms --- p.59 / Chapter 3.4.1 --- Mader's S-Path --- p.59 / Chapter 3.4.2 --- Graphic Matroid Parity --- p.64 / Chapter 3.4.3 --- Colorful Spanning Tree --- p.66 / Chapter 3.5 --- Weighted Linear Matroid Parity --- p.69 / Chapter 3.6 --- A Faster Linear Matroid Parity Algorithm --- p.71 / Chapter 3.6.1 --- Matrix Formulation --- p.71 / Chapter 3.6.2 --- An O(mw) Algorithm --- p.74 / Chapter 3.6.3 --- An O(mrw - 1 ) Algorithm --- p.76 / Chapter 3.7 --- Maximum Cardinality Matroid Parity --- p.79 / Chapter 3.8 --- Open Problems --- p.80 / Chapter 4 --- Graph Connectivities --- p.81 / Chapter 4.1 --- Introduction --- p.81 / Chapter 4.2 --- Inverse of Well-Separable Matrix --- p.83 / Chapter 4.3 --- Directed Graphs with Good Separators --- p.86 / Chapter 4.4 --- Open Problems --- p.89

Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

Thesis (Ph. D.)--University of Florida, 2005. / Title from title page of source document. Document formatted into pages; contains 105 pages. Includes vita. Includes bibliographical references.