Window constraints are mechanisms to bound the tuples processed by continuous queries specified over unbounded data streams. While sliding window queries move the constraint window upon the arrival of each individual tuple, hopping window queries instead move the window by a fixed amount after some period, thus periodically refreshing their results. We observe that for large hops, techniques liked delta result updating may not be efficient -- as large portions of the tuples in the current window will be different from the previous window and thus must be maintained. On the other hand, the complete result updating technique, which has been found to be less suitable for sliding windows queries. Compute the next result based on the complete current window now can be shown to be superior in performance for some hopping windows queries. A trade-off emerges between the complete result method which has a lower per tuple processes cost but potentially processing redundant results versus the delta result method which has no redundant processing but pays a higher per tuple processing cost. On top of that, strict non-monotonic operators such as difference operator, cause premature expiration due to operator semantics. Negative tuples are needed for this kind of special expiration. Such negative tuples added extra burden to the stream engine. Thus, in streaming processing, the difference operator is typically suggested to be placed on top of the query plan despite its potential ability to reduce cardinality of the stream. With this thesis, we introduce a whole solution for hopping window query processing which includes an optimizer for generalized hopping window query optimization that exploits both processing techniques within one integrated query plan alone with query plan rewriting. First, we design the query operators to be multi-mode, that is, to be able to take either a delta or a complete result as input, and produce either a delta result or complete result as output. Then we design a cost model to be able to chose the optimal mode for each operator. Thirdly, our optimizer targets to configure each operator within a query plan to work in the suitable mode to achieve minimum overall processing costs. Last but not least, two query optimization techniques have been adopted. One explores all possibilities of pushing the difference down past joins using dynamic programming and assigning optimal mode at the same time, the other applies heuristic difference push down rule. The proposed techniques has been implemented within the WPI stream query engine, called CAPE. Finally, we show the benefit of our solution with a vast number of experimental results.

Implemented robust regressio technology in portfolio optimization. Constructed optimized portfolio based on robust regression estimations. Compared the portfolio performance with optimized portfolio which is based on ordinary least square estimation.

Database federation is one approach to data integration, in which a middleware, called mediator, provides uniform access to a number of heterogeneous data sources. In this thesis, we focus on the query optimization for distributed joins over database federation. One important observation in query optimization over distributed database system is that run-time conditions (namely available buffer size, CPU utilization in machine and network environment) can significantly affect the execution cost of a query plan. However, in existing database federation systems, very few studies have addressed run-time conditions. It is a challenging problem, because usually the mediator is not able to know the run-time conditions of remote sites and considering run-time conditions will bring about extra complexity to the optimizer. This thesis proposes the Cluster-and-Conquer algorithm for query optimization over database federation while efficiently considering run-time conditions. This algorithm has three-fold benefits. Firstly, the run-time conditions of machines are now available for cluster mediator. Secondly, each cluster mediator can deal with its own sub query concurrently, so the complexity of processing query plan is decreased. Thirdly, the algorithm outperforms other related approaches in terms of“cost of costing", because it removes unnecessary inter-cluster operations in the early stage. I have implemented a prototype data federation system with Cluster-and-Conquer algorithm. The experimental results showed the capabilities and efficiency of our algorithm and described the target scenarios where the algorithm performs better than other related approaches.

Accurate needle placement is critical to the success of needle-based interventions. Needle deflection due to tissue non-homogeneity and dynamic forces results in targeting error, potentially requiring repeated insertions. Real-time imaging enables closed-loop control of the needle during insertion, improving insertion accuracy. The needle localization algorithm proposed in this thesis models the needle as a parametric polynomial equation optimized to minimize beam bending energy relative to a set of observed needle coordinates. Simulated insertions using an MRI dataset show that the minimum bending energy model allows planning of subsequent imaging planes to capture the moving needle while estimating the shape of the needle with low error.

Scheduling problems are common in a wide range of real-world industries and strategies for tackling them can impact on profits significantly. The careful planning and precise timing of industrial events and processes can maximize the utilization of resources, improve efficiency and reduce costs. One important type of scheduling problem from the domain of maintenance planning is the Generator Maintenance Scheduling Problem (GMSP) in the power industry. This thesis makes three broad contributions. First, we introduce a set of 23 real-world instances of the problem of different characteristics and sizes, based on data collected from industry in Saudi Arabia. We show that the fitness landscapes of these instances are rugged and full of relatively poor local optima. Our initial experiments to optimize the instances using a simple evolutionary algorithm and some hill-climbers reveal the dominance of local search for this problem, and suggest that effort be concentrated on the development of more advanced local search algorithms. Secondly, we turn our attention to ensemble problem solving, another promising direction, and propose the use of selection methods (selectors) to evaluate and choose the constituent algorithms of algorithm portfolios. These selectors range in intricacy and the computational effort they require. We show that a selector based on "racing" methods from the metaheuristic tuning literature appears to offer the best trade-off between performance and cost of selection. Finally, we propose several operators for an Iterated Local Search (ILS) algorithm for GMSP taking close account of the problem constraints. To improve performance, we propose extensions to the basic ILS design. These include an ILS with restart strategy, an ILS with delta evaluation implementation, an ILS hybrid with a variable neighbourhood descent algorithm, and a portfolio of ILSs. Results show a superior and consistent performance of the portfolios in a smaller number of evaluations (especially when using communication between constituent components) compared to the performance of individual constituent algorithms.

by Cheng Tak Wai, Johnny. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 59-62). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Self-dual embedding --- p.7 / Chapter 2.2 --- Conic optimization --- p.8 / Chapter 2.3 --- Self-dual embedded conic optimization --- p.9 / Chapter 2.4 --- Connection with convex programming --- p.11 / Chapter 2.5 --- Chapter summary --- p.15 / Chapter 3 --- Implementation of the algorithm --- p.17 / Chapter 3.1 --- The new search direction --- p.17 / Chapter 3.2 --- Select the step-length --- p.23 / Chapter 3.3 --- The multi-constraint case --- p.25 / Chapter 3.4 --- Chapter summary --- p.32 / Chapter 4 --- Numerical results on randomly generated problem --- p.34 / Chapter 4.1 --- Single-constraint problems --- p.35 / Chapter 4.2 --- Multi-constraint problems --- p.36 / Chapter 4.3 --- Running time and the size of the problem --- p.39 / Chapter 4.4 --- Chapter summary --- p.42 / Chapter 5 --- Geometric optimization --- p.45 / Chapter 5.1 --- Geometric programming --- p.45 / Chapter 5.1.1 --- Monomials and posynomials --- p.45 / Chapter 5.1.2 --- Geometric programming --- p.46 / Chapter 5.1.3 --- Geometric program in convex form --- p.47 / Chapter 5.2 --- Conic transformation --- p.48 / Chapter 5.3 --- Computational results of geometric optimization problem --- p.50 / Chapter 5.4 --- Chapter summary --- p.55 / Chapter 6 --- Conclusion --- p.57

Lee Sum Wai = 應用多目標基因演算法於合併三維破裂物件 / 李芯慧. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references. / Text in English; abstracts in English and Chinese. / Lee Sum Wai = Ying yong duo mu biao ji yin yan suan fa yu he bing san wei po lie wu jian / Li Xinhui. / Contents --- p.VI / List of Figures --- p.IX / List of Tables --- p.XIII / Chapter Chapter 1 --- Introduction --- p.1-1 / Chapter 1.1. --- A review of assembling objects --- p.1-3 / Chapter 1.1.1. --- Two-Dimensional matching --- p.1-3 / Chapter 1.1.2. --- Three-Dimensional matching --- p.1-4 / Chapter 1.1.3. --- 2.5-Dimensional matching --- p.1-5 / Chapter 1.2. --- Objectives of this research work --- p.1-7 / Chapter 1.2.1. --- Local Matching of fragments --- p.1-7 / Chapter 1.2.2. --- Global Matching fragments --- p.1-8 / Chapter 1.3. --- Thesis Outline --- p.1-9 / Chapter Chapter 2 --- Background Information --- p.2-1 / Chapter 2.1. --- Three-Dimensional Objects Representation --- p.2-1 / Chapter 2.2. --- Three-Dimensional Objects Geometric Transformation --- p.2-3 / Chapter 2.1.1. --- Translation --- p.2-4 / Chapter 2.1.2. --- Rotation --- p.2-5 / Chapter 2.3. --- Orientated Bounding Box (OBB) --- p.2-6 / Chapter 2.4. --- Scan-Line Method --- p.2-7 / Chapter 2.5. --- Mesh Simplification --- p.2-10 / Chapter 2.6. --- Review of the Surface Matching Method --- p.2-12 / Chapter 2.6.1. --- G. Papaioannou et al ´بs method --- p.2-13 / Chapter Chapter 3 --- Genetic Algorithm --- p.3-1 / General introduction --- p.3-1 / Chapter 3.1. --- Characteristics of Genetic Algorithms --- p.3-3 / Chapter 3.2. --- Mechanism of Genetic Algorithms --- p.3-4 / Chapter 3.2.1. --- Coding --- p.3-4 / Chapter 3.2.2. --- Reproduction --- p.3-5 / Chapter 3.2.3. --- Selection --- p.3-8 / Chapter 3.2.4. --- Stopping Criteria --- p.3-9 / Chapter 3.3. --- Convergence of Genetic Algorithms --- p.3-10 / Chapter 3.4. --- Comparison with Traditional Optimization Methods --- p.3-13 / Chapter 3.4.1. --- Test Function - Sphere --- p.3-14 / Chapter 3.4.2. --- Test Function - Rosenbrock's Saddle --- p.3-19 / Chapter 3.4.3. --- Test Function 一 Step --- p.3-22 / Chapter 3.4.4. --- Test Function -Quartic --- p.3-25 / Chapter 3.4.5. --- Test Function - Shekel's Foxholes --- p.3-28 / Chapter 3.5. --- Multi-Objective Genetic Algorithms --- p.3-29 / Chapter 3.5.1. --- Non-Pareto Approach --- p.3-31 / Chapter 3.5.2. --- Pareto-Ranking --- p.3-32 / Chapter 3.5.3. --- Comparison --- p.3-35 / Chapter Chapter 4 --- Assembling broken objects (I) --- p.4-1 / Chapter 4.1. --- System Flow of Single Pair Assemblage --- p.4-2 / Chapter 4.2. --- Parameterization --- p.4-3 / Chapter 4.2.1. --- Degree of Freedom --- p.4-3 / Chapter 4.2.2. --- Reference Plane and Sampling Points --- p.4-4 / Chapter 4.3. --- Matching Error --- p.4-5 / Chapter 4.3.1. --- Counterpart Surface Matching Error --- p.4-5 / Chapter 4.3.2. --- Border Matching Error --- p.4-7 / Chapter 4.4. --- Correlation-Based Matching Method --- p.4-14 / Chapter Chapter 5 --- Assembling Broken Objects (II)- Global Matching --- p.5-1 / Chapter 5.1. --- Arrangement Strategy --- p.5-2 / Chapter 5.1.1. --- Introduction to Packing --- p.5-2 / Chapter 5.1.2. --- Proposed Architecture --- p.5-6 / Chapter 5.2. --- Relational Multi-Objective Genetic Algorithm --- p.5-13 / Chapter 5.2.1. --- Existing Problem --- p.5-13 / Chapter 5.2.2. --- A New Operator --- p.5-14 / Chapter 5.2.3. --- Relationship Function --- p.5-16 / Chapter 5.3. --- Conclusion and summary --- p.5-20 / Chapter Chapter 6 --- Optimization Approach by Genetic Algorithm --- p.6-1 / Chapter 6.1. --- Solution Space --- p.6-1 / Chapter 6.2. --- Formulation of Gene and Chromosome --- p.6-3 / Chapter 6.2.1. --- Matching Three or More Fragments --- p.6-4 / Chapter 6.2.2. --- Matching Two Fragments --- p.6-5 / Chapter 6.3. --- Fitness Function --- p.6-5 / Chapter 6.3.1. --- Matching Two Fragments --- p.6-5 / Chapter 6.3.2. --- Matching Three or More Fragments --- p.6-6 / Chapter 6.4. --- Reproduction --- p.6-7 / Chapter 6.4.1. --- Crossover --- p.6-8 / Chapter 6.4.2. --- Mutation --- p.6-9 / Chapter 6.4.3. --- Inheritance --- p.6-9 / Chapter 6.5. --- Selection --- p.6-9 / Chapter Chapter 7 --- Experimental Results --- p.7-1 / Chapter 7.1 --- Data Acquisition --- p.7-1 / Chapter 7.2 --- Experiment for Mesh Simplification --- p.7-4 / Chapter 7.3 --- Experiment for Correlation-Based Matching Method --- p.7-5 / Chapter 7.4 --- Experiment One: Two Fragments --- p.7-6 / Chapter 7.5 --- Experiment Two: Several Fragments --- p.7-10 / Chapter 7.5.1 --- Constraint Direction Matching --- p.7-10 / Chapter 7.5.2 --- Unconstraint Direction Matching --- p.7-14 / Chapter Chapter 8 --- Conclusion --- p.8-1 / Appendix Reference --- p.1

基於計算機仿真的優化設計方法如今已成為產品設計的重要工具之一。其最主要特點包括縮短產品開發週期，降低物理實驗成本，保證產品質量以及利用科學方法推動設計創新等。與此同時，計算機輔助設計，仿真，優化的一體化策略也得到了學術界和工業界的廣泛關注。許多新的研究成果都致力於提高以往算法的效率和適用性。 / 基於水平集的形狀和拓撲優化算法是設計輕量化連續結構體的強有力的工具之一。相比於基於有限單元網格的材分佈算法，前者能夠更清楚地表a達所設計結構的幾何邊界和特徵。這個優勢使得該算法能更好的與計算機輔助幾何設計方法相結合，例如構造立體幾何法 (Constructive Solid Geometry)。另外，最新的研究表明，基於水平集的幾何表達方法能夠很好地與擴展有限元分析(Extended Finite ElementAnalysis) 相結合，實現高效的仿真優化計算。這種結合的主要特點包括統一的數據表達，高精度的結構分析和優化計算，以及優化過程中無需重新劃分有限單元網格等。 / 近年來，儘管水平集結構優化算法得到了廣泛的發展，許多基於該方法的應用也層出不窮，但仍有一些相對實際的問題亟待解決。例如，如何提高水平集優化效率，如何增強該方法的設計能力以及適用性等。本論文致力於研究上述問題并提出了一些實用的新方法。 / 首先，我們結合semi-Lagrangian 數值方法和最優化線搜索算法，提出了一種新的水平集結構優化方法。在求解水平集方程的過程中，semi-Lagrangian 方法允許相對較大的時間步長並且無需受CFL(Courant-Friedrichs-Lewy) 條件的限制。基於這個特點，本文提出的最優化線搜索策略能夠自適應地計算出每一步的最佳時間步長，并充分考慮拓撲優化過程中的實際特徵。實驗表明，本算法能夠有效地減少優化迭代次數，同時降低整體優化計算的時間。另外，我們還提出了一種新的敏度計算方法。其思想與有限維度問題中的共軛梯度法相似。實驗表明該方法能夠替代廣泛運用于水平集優化的最速下降法，得到滿意的優化結果。 / 其次，我們提出了一種在水平集結構優化過程中設計幾何特徵的方法。幾何特徵指模型中包含加工、組裝或者特定功能信息的簡單幾何形狀。在優化設計中加入特徵設計功能有顯著的實際意義。本文中，我們結合水平集方法和構造立體幾何法的優勢，首先在建模時分離出具有特徵的幾何元素體（特徵體）和包含自由邊界的幾何元素體（自由體），然後分別在各自的設計策略下實現同步的優化計算。對於特徵體的設計，我們利用仿射變換驅動幾何形狀的改變并時刻保持關鍵的幾何特徵。其中，仿射變換的速度場通過擬合連續體設計的速度場得到，實際變換則採用粒子水平集方法。另一方面，自由體的形狀和拓撲通過標準的水平集方法進行優化設計。實驗表明，該方法能夠在結構形狀及拓撲優化過程中，保持並設計包含不用實際工程信息的幾何特徵，實現了真正意義上的含有幾何特徵的最優結構設計。本文中，我們將用數個二維和三維的算例來說明該方法的設計潛力和適用性。 / 最後，我們討論并實現了基於自適應水平集方法的三維結構優化算法。該方法在計算過程中結合了顯示和隱式幾何表達的雙重優點。首先，我們用八叉樹網格來表示隱式水平集模型以及其對應的二維流型三角片網格模型。在優化迭代過程中，隱式水平集模型的邊界演化採用semi-Lagrangian 方法。其中，有向距離函數通過直接計算當前顯示模型得到，而非插值。之後，新的三角片網格模型從更新的距離場中提取出來，作為下一步的輸入。這種混合表達和自適應的網格策略不僅實現了窄帶計算，而且能夠很好跟擴展有限元分析方法相結合。此外，我們在計算過程中還提出并加入了一種能夠保持幾何特徵和模型表面拓撲的網格簡化算法以提高計算效率。值得注意的是，這種自適應水平集方法成功地在結構優化過程中植入了幾何模型處理方法。這為進一步發展水平集結構優化提供了一個新的方向。 / In modern product design practice, adopting simulation based optimization has become a standard procedure to reduce experimental cost, shorten development time, assure product quality and promote innovation. Both industries and academics have put great efforts in exploring new approaches to integrate computer aided design (CAD), simulation and optimization processes in an effective and truly applicable way. / For general lightweight structural design of continuum, the level set method is a promising tool for shape and topology optimization. Compared to traditional approaches such as Finite Element (FE) mesh based shape optimization and material based topology optimization, the level set based method excels in its flexibility in handling both shape and topological change as well as the capability in representing a clear structural geometry. The later advantage allows for a intuitive integration of computer aided design and engineering (CAD/CAE), because the level set model can be easily extended to constructive solid geometry, which is a fundamental geometry description of CAD. Meanwhile, recent research progress indicates that coupling level set method with extended finite element (XFEM) analysis for simulation based design possesses tremendous values, such as data compatibility, free of re-meshing and good accuracy. / Although the basic theory of level set based structural optimization has been well established and many applications have been reported in the last decade, the realm is still under investigation for a number of practical issues, such as to improve computational efficiency, optimal search effectiveness, design capability and industrial applicability. This thesis presents some recent research progress and novel techniques towards these common goals. / Firstly, an efficient and numerically stable semi-Lagrangian level set method is proposed for structural optimization with a line search algorithm and a sensitivity modulation scheme. The semi-Lagrange method has an advantage to allow for a large time step without the limitation of Courant- Friedrichs-Lewy (CFL) condition. The line search attempts to adaptively determine an appropriate time step in each iteration of optimization. With consideration of some practical characteristics during topology optimization process, incorporating the line search into semi-Lagrange optimization method can yield fewer design iterations and thus improve the overall computational efficiency. The sensitivity modulation is inspired from the conjugate gradient method in finite-dimensions, and provides an alternative to the standard steepest descent search in level set based optimization. Two benchmark examples are presented to compare the sensitivity modulation and the steepest descent techniques with and without the line search respectively. / Secondly, a generic method to design engineering features for level set based structural optimization is presented. Engineering features are regular and simple shape units containing specific engineering significance for manufacture and assembly consideration. It is practically useful to combine feature design with structural optimization. In this thesis, a Constructive Solid Geometry (CSG) based Level Sets description is proposed to represent a structure based on two basic entities: a level set model containing either a feature shape or a freeform boundary. By treating both entities implicitly and homogeneously, optimal feature design and freeform boundary design are unified under the level set framework. For feature models, a constrained motion of affine transformations is utilized, where the design velocity is obtained through a least square approximation of continuous shape variation. An accurate particle level set updating scheme is employed for the transformation. Meanwhile, freeform models undergo a standard level set updating process using a semi-Lagrange scheme. With this method, various feature characteristics are identified through carefully constructing a CSG model tree with flexible entities and preserved by imposing motion constraints to different stages of the tree. Moreover, because a free shape and topology optimization is enabled over non-feature regions, a truly optimal structural configuration with engineering features can be designed in a convenient way. Several 2D and 3D generative feature design examples are provided to show the applicability of this approach. / Finally, a 3D implementation using adaptive level set method is discussed. This method utilizes both explicit and implicit geometric representations for computation. An octree grid is adopted to accommodate the free structural interface of an implicit level set model and a corresponding 2-manifold triangle mesh model. Within each iteration of optimization, the interface evolves implicitly using a semi-Lagrange level set method, during which the signed distance field is evaluated directly and accurately from the current surface model other than interpolation. After that, another mesh model is extracted from the updated field and serves as the input of subsequent process. This hybrid and adaptive representation scheme not only achieves "narrow band computation", but also facilitates the structural analysis by using a geometry-aware mesh-free approach. Moreover, a feature preserving and topological errorless mesh simplification algorithm is proposed to enhance the computational efficiency. Remarkably, the adaptive level set scheme opens up a gate to incorporate geometric editing into structural optimization in an effective way, which creates a new dimension of opportunity to further develop level set based structural optimization in this direction. A three dimensional benchmark example and possible extensions are presented to demonstrate the capability and potential of this method. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Zhou, Mingdong. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 123-135). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background of Structural Optimization --- p.2 / Chapter 1.2 --- Research Issues and Contributions --- p.7 / Chapter 1.3 --- Content Outline --- p.11 / Chapter 2 --- Structural Optimization with Level Set Method --- p.13 / Chapter 2.1 --- Dynamic Level Set Method --- p.14 / Chapter 2.1.1 --- Implicit Model Description and Hamilton-Jacobi Equation --- p.15 / Chapter 2.1.2 --- Model Update and Re-Initialization --- p.16 / Chapter 2.2 --- Application in Structural Optimization Problem --- p.19 / Chapter 2.2.1 --- Problem Formulation of Linear Elastic Continuum --- p.19 / Chapter 2.2.2 --- Design Sensitivity Analysis --- p.21 / Chapter 2.2.3 --- Optimization Strategy --- p.24 / Chapter 2.3 --- Couple with Extended Finite Element Method --- p.26 / Chapter 2.3.1 --- X-FEM for Structural Analysis --- p.28 / Chapter 2.3.2 --- Numerical Integration --- p.30 / Chapter 2.3.3 --- Imposing Boundary Conditions --- p.31 / Chapter 2.4 --- Summary --- p.33 / Chapter 3 --- A semi-Lagrangian level set method for structural optimization --- p.34 / Chapter 3.1 --- Introduction --- p.35 / Chapter 3.2 --- Semi-Lagrangian Level Set Method --- p.37 / Chapter 3.3 --- A Line Search Algorithm --- p.38 / Chapter 3.4 --- A Sensitivity Modulation Scheme --- p.41 / Chapter 3.5 --- Numerical Examples --- p.43 / Chapter 3.5.1 --- Cantilever beam --- p.44 / Chapter 3.5.2 --- Bridge-type structure --- p.48 / Chapter 3.6 --- Summary --- p.54 / Chapter 4 --- Engineering Feature Design in Structural Optimization --- p.58 / Chapter 4.1 --- Introduction --- p.59 / Chapter 4.2 --- CSG based Level Sets --- p.64 / Chapter 4.3 --- Structural Optimization with CSGLS --- p.67 / Chapter 4.4 --- Constrained Motion with Affine Transformation --- p.71 / Chapter 4.4.1 --- 2D Algorithm --- p.71 / Chapter 4.4.2 --- 3D Algorithm --- p.74 / Chapter 4.5 --- Design Sharp Characteristics --- p.79 / Chapter 4.6 --- Numerical Examples --- p.79 / Chapter 4.6.1 --- Moment of Inertia (MOI) Maximization --- p.79 / Chapter 4.6.2 --- Feature Design in Structural Topology Optimization --- p.81 / Chapter 4.6.3 --- Generative Feature Design --- p.85 / Chapter 4.6.4 --- A 3D Feature Based Optimal Design --- p.92 / Chapter 4.7 --- Summary --- p.93 / Chapter 5 --- Adaptive level set implementation for 3D problems --- p.97 / Chapter 5.1 --- Introduction and Algorithm Overview --- p.98 / Chapter 5.2 --- Hybrid Model Representation and Interface Tracking --- p.100 / Chapter 5.2.1 --- Octree Based Implicit Model --- p.101 / Chapter 5.2.2 --- Triangle Mesh Based Explicit Model --- p.102 / Chapter 5.2.3 --- Interface Tracking --- p.102 / Chapter 5.3 --- Engineering Model Simplification --- p.103 / Chapter 5.3.1 --- Introduction --- p.104 / Chapter 5.3.2 --- Algorithm of Progressive Multi-Pass Simplification --- p.105 / Chapter 5.3.3 --- Numerical Results of Mesh Simplification --- p.109 / Chapter 5.4 --- Structural Analysis --- p.115 / Chapter 5.5 --- Numerical Example of A 3D Optimal Design --- p.116 / Chapter 5.6 --- Summary --- p.116 / Chapter 6 --- Conclusions and Future work --- p.118 / Chapter 6.1 --- Conclusions --- p.118 / Chapter 6.2 --- Future Work --- p.120 / Bibliography --- p.123 / Publications --- p.136

Lee, Hon Leung. / "August 2011." / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 98-101) and index. / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.6 / Chapter 2 --- Preliminaries --- p.11 / Chapter 2.1 --- Functional analysis --- p.11 / Chapter 2.2 --- Convex analysis --- p.14 / Chapter 2.3 --- Relative interiors --- p.19 / Chapter 2.4 --- Multifunctions --- p.21 / Chapter 2.5 --- Variational analysis --- p.22 / Chapter 3 --- A unified notion of optimality --- p.29 / Chapter 3.1 --- Basic notions of minimality --- p.29 / Chapter 3.2 --- A unified notion --- p.32 / Chapter 4 --- Separation theorems --- p.38 / Chapter 4.1 --- Zheng and Ng fuzzy separation theorem --- p.38 / Chapter 4.2 --- Extremal principles and other consequences --- p.43 / Chapter 5 --- Necessary conditions for the unified notion of optimality --- p.49 / Chapter 5.1 --- Local asymptotic closedness --- p.49 / Chapter 5.2 --- First order necessary conditions --- p.56 / Chapter 5.2.1 --- Introductory remark --- p.56 / Chapter 5.2.2 --- Without operator constraints --- p.59 / Chapter 5.2.3 --- With operator constraints --- p.66 / Chapter 5.3 --- Comparisons with known necessary conditions --- p.74 / Chapter 5.3.1 --- Finite-dimensional setting --- p.74 / Chapter 5.3.2 --- Zheng and Ng's work --- p.76 / Chapter 5.3.3 --- Dutta and Tammer's work --- p.80 / Chapter 5.3.4 --- Bao and Mordukhovich's previous work --- p.81 / Chapter 6 --- A weak notion: approximate efficiency --- p.84 / Chapter 6.1 --- Approximate minimality --- p.85 / Chapter 6.2 --- A scalarization result --- p.86 / Chapter 6.3 --- Variational approach --- p.94 / Bibliography --- p.98 / Index --- p.102

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.