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 8 of 8 for “"Semidefinite Relaxations"”.
-
Semidefinite Relaxations for Geometric Problems in Robotics
… We begin with a summary and extension of the semidefinite relaxation machinery that we apply to both problems. This machinery is used to develop fast and accurate extrinsic calibration algorithms with novel performance guarantees provided by certificates of global optimality. We proceed to …
-
On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic Programming
… the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form trace(X^TQX + 2C^T X) + β, and trace(X^TQX + XPX^T + 2C^T X)+ β respectively, where X is an n by r real matrix. For each …
-
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 …
-
A Blueprint for Semidefinite Relaxations of Binary-Constrained Quadratic Programs Computing tight bounds on NP-hard problems using ADMM
… and lower bounds for the BCQP by formulating the semidefinite programming (SDP) relaxation and applying the Alternating Direction Method of Multipliers (ADMM) algorithm to solve it. By unifying the two problems under the umbrella of the BCQP, we better understand why the method is so successful …
-
Matchings and Representation Theory
… light on the algebraic structure of symmetric semidefinite relaxations of the perfect matching problem
-
Design and analysis of competitive electricity markets
… To get around this difficulty, we exploit semidefinite relaxations of the optimal power flow problem and leverage duality theory to define prices for electricity as the optimal Lagrange multipliers of nodal real and reactive power balance constraints. We demonstrate that such prices stand …
-
Semidefinite Facial Reduction for Low-Rank Euclidean Distance Matrix Completion
… of this thesis is the development of a theory of semidefinite facial reduction for the Euclidean distance matrix completion problem. Our key result shows a close connection between cliques in the graph of the partial Euclidean distance matrix and faces of the semidefinite cone containing the …
-
CONVEX OPTIMIZATION METHODS FOR ROBUST AND DETERMINISTIC OPTIMAL POWER FLOW PROBLEMS
… tractable convex inner and outer approximations (relaxations) for the AC-OPF problem and the RAC-OPF problem. In the first part of the thesis, we focus on the AC-OPF problem, its equivalent reformulation as a rank one constrained semidefinite program, and its semidefinite programming relaxation. …