No description available.

The continuous facility layout problem consists of arranging a set of facilities so that no pair overlaps and the total sum of the pairwise connection costs (proportional to the center-to-center rectilinear distance) is minimized. This thesis presents a completely mixed integer semidefinite programming (MISDP) model for the continuous facility layout problem. To begin we describe the problem in detail; discuss the conditions required for a feasible layout; and define quaternary variables. These variables are the basis of the MISDP model. We prove that the model is an exact formulation and a distinction is made between the constraints that semidefinite programming (SDP) optimization software can solve and those that must be relaxed. The latter are called exactness constraints and three possible exactness constraints are shown to be equivalent. The main contribution of this thesis is the theoretical development of a MISDP model that is based on quaternary, as oppose to binary, variables; nevertheless preliminary computational results will be presented for problems with 5 to 20 facilities. The optimal solution is found for problems with 5 and 6 facilities, confirming the validity of the model; and the potential of the model is revealed as a new upper bound is found for an 11-facility problem.

The Lovasz theta function and the associated convex sets known as theta bodies are fundamental objects in combinatorial and semidefinite optimization. They are accompanied by a rich duality theory and deep connections to the geometric concept of orthonormal representations of graphs. In this thesis, we investigate several ramifications of the theory underlying these objects, including those arising from the illuminating viewpoint of duality. We study some optimization problems over unit-distance representations of graphs, which are intimately related to the Lovasz theta function and orthonormal representations. We also strengthen some known results about dual descriptions of theta bodies and their variants. Our main goal throughout the thesis is to lay some of the foundations for using semidefinite optimization and convex analysis in a way analogous to how polyhedral combinatorics has been using linear optimization to prove min-max theorems. A unit-distance representation of a graph $G$ maps its nodes to some Euclidean space so that adjacent nodes are sent to pairs of points at distance one. The hypersphere number of $G$, denoted by $t(G)$, is the (square of the) minimum radius of a hypersphere that contains a unit-distance representation of $G$. Lovasz proved a min-max relation describing $t(G)$ as a function of $\vartheta(\overline{G})$, the theta number of the complement of $G$. This relation provides a dictionary between unit-distance representations in hyperspheres and orthonormal representations, which we exploit in a number of ways: we develop a weighted generalization of $t(G)$, parallel to the weighted version of $\vartheta$; we prove that $t(G)$ is equal to the (square of the) minimum radius of an Euclidean ball that contains a unit-distance representation of $G$; we abstract some properties of $\vartheta$ that yield the famous Sandwich Theorem and use them to define another weighted generalization of $t(G)$, called ellipsoidal number of $G$, where the unit-distance representation of $G$ is required to be in an ellipsoid of a given shape with minimum volume. We determine an analytic formula for the ellipsoidal number of the complete graph on $n$ nodes whenever there exists a Hadamard matrix of order $n$. We then study several duality aspects of the description of the theta body $\operatorname{TH}(G)$. For a graph $G$, the convex corner $\operatorname{TH}(G)$ is known to be the projection of a certain convex set, denoted by $\widehat{\operatorname{TH}}(G)$, which lies in a much higher-dimensional matrix space. We prove that the vertices of $\widehat{\operatorname{TH}}(G)$ are precisely the symmetric tensors of incidence vectors of stable sets in $G$, thus broadly generalizing previous results about vertices of the elliptope due to Laurent and Poljak from 1995. Along the way, we also identify all the vertices of several variants of $\widehat{\operatorname{TH}}(G)$ and of the elliptope. Next we introduce an axiomatic framework for studying generalized theta bodies, based on the concept of diagonally scaling invariant cones, which allows us to prove in a unified way several characterizations of $\vartheta$ and the variants $\vartheta'$ and $\vartheta^+$, introduced independently by Schrijver, and by McEliece, Rodemich, and Rumsey in the late 1970's, and by Szegedy in 1994. The beautiful duality equation which states that the antiblocker of $\operatorname{TH}(G)$ is $\operatorname{TH}(\overline{G})$ is extended to this setting. The framework allows us to treat the stable set polytope and its classical polyhedral relaxations as generalized theta bodies, using the completely positive cone and its dual, and it allows us to derive a (weighted generalization of a) copositive formulation for the fractional chromatic number due to Dukanovic and Rendl in 2010 from a completely positive formulation for the stability number due to de Klerk and Pasechnik in 2002. Finally, we study a non-convex constraint for semidefinite programs (SDPs) that may be regarded as analogous to the usual integrality constraint for linear programs. When applied to certain classical SDPs, it specializes to the standard rank-one constraint. More importantly, the non-convex constraint also applies to the dual SDP, and for a certain SDP formulation of $\vartheta$, the modified dual yields precisely the clique covering number. This opens the way to study some exactness properties of SDP relaxations for combinatorial optimization problems akin to the corresponding classical notions from polyhedral combinatorics, as well as approximation algorithms based on SDP relaxations.

Digital filter banks have found in a wide variety of applications in data compression, digital communications, and adaptive signal processing. The common objectives of the filter bank design consist of frequency selectivity of the individual filters and perfect reconstruction of the filter banks. The design problems of filter banks are intrinsically challenging because their natural formulations are nonconvex constrained optimization problems. Therefore, there is a strong motivation to cast the design problems into convex optimization problems whose globally optimal solutions can be efficiently obtained. The main contributions of this dissertation are to exploit the convex optimization algorithms to design several classes of the filter banks. First, the two-channel orthogonal symmetric complex-valued filter banks are investigated. A key contribution is to derive the necessary and sufficient condition for the existence of complex-valued symmetric spectral factors. Moreover, this condition can be expressed as linear matrix inequalities (LMIs), and hence semi-definite programming (SDP) is applicable. Secondly, for two-channel symmetric real-valued filter banks, a more general and efficient method for designing the optimal triplet halfband filter banks with regularity is developed. By exploiting the LMI characterization of nonnegative cosine polynomials, the semi-infinite constraints can be efficiently handled. Consequently, the filter bank design is cast as an SDP problem. Furthermore, it is demonstrated that the resulting filter banks are applied to image coding with improved performance. It is not straightforward to extend the proposed design methods for two-channel filter banks to M-channel filter banks. However, it is investigated that the design problem of M-channel cosine-modulated filter banks is a nonconvex optimization problem with the low degree of nonconvexity. Therefore, the efficient semidefinite relaxation technique is proposed to design optimal prototype filters. Additionally, a cheap iterative algorithm is developed to further improve the performance of the filter banks. Finally, the application of filter banks to multicarrier systems is considered. The condition on the transmit filter bank and channel for the existence of zero-forcing filter bank equalizers is obtained. A closed-form expression of the optimal equalizer is then derived. The proposed filter bank transceivers are shown to outperform the orthogonal frequency-division multiplexing (OFDM) systems.

University, Diss., 2004--Mannheim.

In this thesis, several computationally-efficient approximate soft demodulation schemes are developed for multiple-input multiple-output (MIMO) communication systems. These soft demodulators are designed to be deployed in the conventional iterative receiver ('turbo') architecture, and they are designed to provide good performance at substantially lower computational cost than that of the exact soft demodulator. The proposed demodulators are based on the principle of list demodulation and can be classified into two classes, according to the nature of the list-generation algorithm. One class is based on a tree-search algorithm and the other is based on insight generated from the analysis of semidefinite relaxation techniques for hard demodulation. The proposed tree-search demodulators are based on a multi-stack algorithm, developed herein, for efficiently traversing the tree structure that is inherent in the MIMO demodulation problem. The proposed scheme was inspired, in part, by the stack algorithm, which stores all the visited nodes in the tree in a single stack and chooses the next node to expand based on a 'best-first' selection scheme. The proposed algorithm partitions this global stack into a stack for each level of the tree. It examines the tree in the natural ordering of the levels and performs a best-first search in each of the stacks. By assigning appropriate priorities to the level at which the search for the next leaf node re-starts, the proposed demodulators can achieve performance-complexity trade-offs that dominate several existing soft demodulators, including those based on the stack algorithm and those based on 'sphere decoding' principles, especially in the low-complexity region. In the second part of this thesis it is shown that the randomization procedure that is inherent in the semidefinite relaxation (SDR) technique for hard demodulation can be exploited to generate the list members required for list-based soft demodulation. The direct application of this observation yields list-based soft demodulators that only require the solution of one SDP per demodulation-decoding iteration. By approximating the randomization procedure by a set of independent Bernoulli trials, this requirement can be reduced to just one semidefinite program (SDP) per channel use. An advantage of these demodulators over those based on optimal tree-search algorithms is that the computational cost of solving the SDP is a low-order polynomial in the problem size. The analysis and simulation experiments provided in the thesis show that the proposed SDR-based demodulators offer an attractive trade-off between performance and computational cost. The structure of the SDP in the proposed SDR-based demodulators depends on the signaling scheme, and the initial development focuses on the case of QPSK signaling. In the last chapter of this thesis, the extension to MIMO 16-QAM systems is developed, and some interesting observations regarding some existing SDR-based hard demodulation schemes for MIMO 16-QAM systems are derived. The simulation results reveal that the excellent performance-complexity trade-off of the proposed SDR-based schemes is preserved under the extension to 16-QAM signaling. / Thesis / Doctor of Philosophy (PhD)

This thesis presents the mixed integer bilevel programming problems where some optimality conditions and solution algorithms are derived. Bilevel programming problems are optimization problems which are partly constrained by another optimization problem. The theoretical part of this dissertation is mainly based on the investigation of optimality conditions of mixed integer bilevel program. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. After that, we are able to discuss local optimality conditions using tools of variational analysis for each different approach. Moreover, bilevel optimization problems with semidefinite programming in the lower level are considered in order to formulate more optimality conditions for the mixed integer bilevel program. We end the thesis by developing some algorithms based on the theory presented

This thesis presents the research work regarding the solution of a localization problem in indoor WLANs by introducing a distributive time division multiplexed localization technique based on the convex semidefinite programming. Convex optimizations have proven to give promising results but have limitations of computational complexity for a larger problem size. In the case of localization problem the size is determined depending on the number of nodes to be localized. Thus a convex localization technique could not be applied to real time tracking of mobile nodes within the WLANs that are already providing computationally intensive real time multimedia services. Here we have developed a distributive technique to circumvent this problem such that we divide a larger network into computationally manageable smaller subnets. The division of a larger network is based on the mobility levels of the nodes. There are two types of nodes in a network; mobile, and stationery. We have placed the mobile nodes into separate subnets which are tagged as mobile whereas the stationary nodes are placed into subnets tagged as stationary. The purpose of this classification of networks into subnets is to achieve a priority-based localization with a higher priority given to mobile subnets. Then the classified subnets are localized by scheduling them in a time division multiplexed way. For this purpose a time-frame is defined consisting of finite number of fixed duration time-slots such that within the slot duration a subnet could be localized. The subnets are scheduled within the frames with a 1:n ratio pattern that is within n number of frames each mobile subnet is localized n times while each stationary subnet consisting of stationary nodes is localized once. By using this priority-based scheduling we have achieved a real time tracking of mobile node positions by using the computationally intensive convex optimization technique. In addition, we present that the resultant distributive technique can be applied to a network having diverse node density that is a network with its nodes varying from very few to large numbers can be localized by increasing frame duration. This results in a scalable technique. In addition to computational complexity, another problem that arises while formulating the distance based localization as a convex optimization problem is the high-rank solution. We have also developed the solution based on virtual nodes to circumvent this problem. Virtual nodes are not real nodes but these are nodes that are only added within the network to achieve low rank realization. Finally, we developed a distributive 3D real-time localization technique that exploited the mobile user behaviour within the multi-storey indoor environments. The estimates of heights by using this technique were found to be coarse. Therefore, it can only be used to identify floors in which a node is located.

We propose a new method, based on semidefinite optimization, to find tight upper bounds on the expected project completion time and expected project tardiness in a stochastic project scheduling environment, when only limited information in the form of first and second (joint) moments of the durations of individual activities in the project is available. Our computational experiments suggest that the bounds provided by the new method are stronger and often significant compared to the bounds found by alternative methods. / Singapore-MIT Alliance (SMA)

Using recent progress on moment problems, and their connections with semidefinite optimization, we present in this paper a new methodology based on semidefinite optimization, to obtain a hierarchy of upper and lower bounds on both linear and certain nonlinear functionals defined on solutions of linear partial differential equations. We apply the proposed methods to examples of PDEs in one and two dimensions with very encouraging results. We also provide computation evidence that the semidefinite constraints are critically important in improving the quality of the bounds, that is without them the bounds are weak. / Singapore-MIT Alliance (SMA)