Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 18 of 18 for “"Semidefinite relaxation"”.
-
Discrete-continuous optimization for robot perception via semidefinite relaxation
… we propose polynomial-time algorithms based on semidefinite programming (SDP) relaxation to find approximate solutions to nonconvex problems arising in two fields of robot perception, semantic segmentation and robust pose graph optimization. Compared with other inference techniques, SDP …
-
Semidefinite relaxation based branch-and-bound method for nonconvex quadratic programming
In this thesis, we use a semidefinite relaxation based branch-and-bound method to solve nonconvex quadratic programming problems. Firstly, we show an interval branch-and-bound method to calculate the bounds for the minimum of bounded polynomials. Then we demonstrate four SDP relaxation methods to …
-
Perfect Recovery in Heterogeneous Stochastic Bicluster Models
… with high probability by solving a particular semidefinite relaxation, provided the input graph is drawn from a heterogeneous planted–bicluster model. We proceed to derive necessary and sufficient conditions for exact recovery, then via numerical simulations, we explore the impact of sparsity, …
-
Linear and nonlinear semidefinite relaxations of some NP-hard problems
Semidefinite relaxation (SDR) is a powerful tool to estimate bounds and obtain approximate solutions for NP-hard problems. This thesis introduces and studies several novel linear and nonlinear semidefinite relaxation models for some NP-hard problems. We first study the semidefinite relaxation of …
-
Relaxing Topological Barriers in Geometry Processing
… and local minima. This thesis explores convex relaxation as a powerful guide and tool for reframing such problems. We bring the tools of semidefinite relaxation to bear on challenging optimization problems in field-based meshing and unlock polynomial geometry kernels for physical simulation. We …
-
Optimization Techniques for Trustworthy 3D Object Understanding
… it to certifiable optimality using a smallsize semidefinite relaxation. We also present a compatibility-based outlier rejection scheme to handle outliers, and evaluate the proposed approach on synthetic and real data. Next, we focus on estimating the pose of an object given its shape and a …
-
Convex relaxation based locational marginal prices for electricity markets
We propose and analyze semidefinite relaxation-based locational marginal prices (RLMPs) for real and reactive power in electricity markets. Our analysis reveals that when the nonconvex economic dispatch problem has zero duality gap, the RLMPs exhibit properties similar to locational marginal prices …
-
Mixed Integer Nonlinear Programs: Theory, Algorithms and Applications
… Demonstrating the technique, we derive a semidefinite relaxation for fractional programs. In the process, we introduce the concept of convex extensions, study its convexification properties, and apply it to develop tight relaxations for hyperbolic programs and pooling/blending problems. …
-
Accurate range free localization in multi-hop wireless sensor networks
… estimator. By employing Jensen’s inequality and semidefinite relaxation, the originally offered nonlinear and nonconvex estimator is relaxed into a convex optimization difficulty, which is able to be professionally resolved to acquire the totally best solution. Moreover, the resultant Cramer–Rao …
-
Certifiably correct SLAM
… of our approach is the development of a (convex) semidefinite relaxation of the SLAM MLE that is frequently exact in the low to moderate measurement noise regime. We show that when exactness holds, it is straightforward to construct an optimal solution Z* for this relaxation from an optimal …
-
Polynomial Structure in Semidefinite Relaxations and Non-Convex Formulations
Semidefinite relaxation is a powerful tool used to approximate otherwise intractable non-convex problems, but tend to run into scalability issues in large-scale instances. The goal of this thesis is to explore the power of semidefinite relaxations and address the scalability issues, for special …
-
Statistical limits of graphical channel models and a semidefinite programming approach
… call "truncate-and-relax", based on a standard semidefinite relaxation technique. We show that in these two models, the algorithm based on this strategy achieves exact recovery up to a threshold which orderwise matches the statistical threshold. We complement this by showing the limitation of …
-
Joint Task Offloading and Resource Allocation for Mobile Cloud with Computing Access Point
… general. An efficient heuristic algorithm using semidefinite relaxation (SDR) and a new randomization mapping approach is proposed. For the case with strict delay constraints for each task, we propose a three-step algorithm to obtain a feasible solution that is locally optimal. We further …
-
Exploiting Spatial Degrees-of-Freedom for Energy-Efficient Next Generation Cellular Systems
… applies both recurrent neural network (RNN)- and semidefinite relaxation (SDR)-based schemes for different purposes to reduce PAPR. The highly parallel structure of RNN is proposed in this work to address the issues of scalability and stringent requirements on computational times in PAPR-aware …
-
Wireless Network Physical Layer Security with Smart Antenna
… due to its intractable nature, we solve it using semidefinite relaxation (SDR) in conjunction with a heuristic local search algorithm. Simulation results show the effectiveness of our analytical approach and indicate the correlation between the geometry of anchor deployment and the feasibility of …
-
Computationally Efficient Multiuser and MIMO Detection based on Dichotomous Coordinate Descent Iterations
… outperforms such advanced detector as the semidefinite relaxation detector in both the detection performance and complexity. In MIMO systems, the MPD exhibits more favorable performance/complexity characteristics and can be considered as a promising alternative to the sphere decoder. The …
-
Joint relay beamforming and transceiver processing in multiuser relay network
… problem is solved by ordinary semi-definite relaxation (SDR) and separable SDR approaches. Compared to conventional rank-one scheme, proposed rank-two methods provide one more degree of freedom in optimal solution, and have significantly better performance in terms of min-max per-relay power …
-
Resource allocation and secure communication design in simultaneous wireless information and power transfer systems
… The non-convex problem is converted into a semidefinite programming (SDP) problem by using the semidefinite relaxation (SDR) approach. In addition, a rank-one proof presents that the solution generated by the relaxed problem is optimal to the original problem. Second, a security issue about …