With the rapid development of wireless technologies, the demand for positioning services has grown dramatically over the past three decades. The Global Positioning System (GPS) is widely used in wireless devices for positioning purposes. However, in addition to having bulky and expensive equipment, GPS receivers do not operate properly in dense and indoor environments. Difficulties in using GPS lead us to use sensor localization in which the position information is obtained from the measurements collected within the network without the aid of external resources. Sensor localization has been a great topic of interest during past decades. Although many positioning algorithms have been developed previously in the literature, positioning is still a challenging task. There are many factors that can affect the positioning performance if they are neglected or not treated properly. These factors introduce many nuisance parameters which need to be either estimated or considered when the location is estimated. In this work, we exploit cooperative localization as a recent and trending technology and semidefinite programming (SDP) as a powerful tool in our research. Cooperative localization has several advantages over the traditional noncooperative localization in terms of positioning accuracy and localizability. Cooperation is also highly beneficial for networks with few anchor nodes and low communication range. On the other hand, SDP provides an alternative solution to the optimal maximum-likelihood (ML) estimation. Unlike in the ML estimator, convergence to the global minimum is guaranteed in SDP. It also has significantly lower complexity especially for cooperative networks in exchange for small performance degradation. Using these two concepts, four open problems within the area of cooperative localization and tracking in the presence of nuisance parameters are addressed. In particular, we focus on cooperative received signal strength-based localization when the propagation parameters including path-loss exponent and transmit powers are unknown. Cooperative time-of-arrival-based localization in harsh environments in the presence of severe non-line-of-sight (NLOS) propagation is also investigated. Cooperative localization in asynchronous networks is studied where the clock parameters are considered as nuisance parameters and the focus is on a joint synchronization and localization approach. Lastly, source tracking in NLOS environments is studied where source nodes are mobile and their status changes rapidly from LOS to NLOS and vice versa. / Ph. D.

Sze, Kam Fung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 49-53). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese.

The facility location problem is the task of optimally placing a given number of facilities in a certain subset of the plane. In this thesis, we present various mathematical programming formulations of the planar facility location problem, where potential facility locations are not specified. We first consider mixed-integer programming formulations of the planar facility locations problems with squared Euclidean and rectangular distance metrics to solve this problem to provable optimality. We also investigate a heuristic approach to solving the problem by extending the $K$-means clustering algorithm and formulating the facility location problem as a variant of a semidefinite programming problem, leading to a relaxation algorithm. We present computational results for the mixed-integer formulations, as well as compare the objective values resulting from the relaxation algorithm and the modified $K$-means heuristic. In addition, we briefly discuss some of the practical issues related to the facility location model under the continuous customer distribution.

The facility location problem is the task of optimally placing a given number of facilities in a certain subset of the plane. In this thesis, we present various mathematical programming formulations of the planar facility location problem, where potential facility locations are not specified. We first consider mixed-integer programming formulations of the planar facility locations problems with squared Euclidean and rectangular distance metrics to solve this problem to provable optimality. We also investigate a heuristic approach to solving the problem by extending the $K$-means clustering algorithm and formulating the facility location problem as a variant of a semidefinite programming problem, leading to a relaxation algorithm. We present computational results for the mixed-integer formulations, as well as compare the objective values resulting from the relaxation algorithm and the modified $K$-means heuristic. In addition, we briefly discuss some of the practical issues related to the facility location model under the continuous customer distribution.

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 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.

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)

This thesis concerns the identification of dynamic models in systems biology. and is structured into two parts. Both parts concern building dynamic models from observed data, but are quite different in perspective, rationale and mathematics. The first part considers the development of novel identification techniques that are particularly tailored to (molecular) biology and considers two approaches. The first approach reformulates the parameter estimation problem as a feasibility problem. This reformulation allows the invalidation of models by analysing entire parameter regions. The second approach utilises nonlinear observers and a transformation of the model equations into parameter free coordinates. The parameter free coordinates allow the design of a globally convergent observer, which in turn estimates the parameter values, and further, allows to identify modelling errors or unknown inputs/influences. Both approaches are bottom up approaches that require a mechanistic understanding of the underlying processes (in terms of a biochemical reaction network) leading to complex nonlinear models. The second part is an example of what can be done with classical, well developed tools from systems identification when applied to hitherto unattended problems.In particular, part two of my thesis develops a modelling framework for rat movements in an experimental setup that it widely used to study learning and memory.The approach is a top down approach that is data driven resulting in simple linear models.

Trust region subproblems arise within a class of unconstrained methods called trust region methods. The subproblems consist of minimizing a quadratic function subject to a norm constraint. This thesis is a survey of different methods developed to find an approximate solution to the subproblem. We study the well-known method of More and Sorensen and two recent methods for large sparse subproblems: the so-called Lanczos method of Gould et al. and the Rendland Wolkowicz algorithm. The common ground to explore these methods will be semidefinite programming. This approach has been used by Rendl and Wolkowicz to explain their method and the More and Sorensen algorithm; we extend this work to the Lanczos method. The last chapter of this thesis is dedicated to some improvements done to the Rendl and Wolkowicz algorithm and to comparisons between the Lanczos method and the Rendl and Wolkowicz algorithm. In particular, we show some weakness of the Lanczos method and show that the Rendl and Wolkowicz algorithm is more robust.