Dissertations / Theses on the topic 'Semidefinite programming'
To see the other types of publications on this topic, follow the link: Semidefinite programming.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Semidefinite programming.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Zhu, Yuntao. "Semidefinite programming under uncertainty." Online access for everyone, 2006. http://www.dissertations.wsu.edu/Dissertations/summer2006/y%5Fzhu%5F073106.pdf.
Full text
2
Jibrin, Shafiu. "Redundancy in semidefinite programming." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/tape15/PQDD_0010/NQ32337.pdf.
Full text
3
Jibrin, Shafiu Carleton University Dissertation Mathematics and Statistics. "Redundancy in semidefinite programming." Ottawa, 1997.
Find full text
4
Wei, Hua. "Numerical Stability in Linear Programming and Semidefinite Programming." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/2922.
Full textAbstract:
We study numerical stability for interior-point methods applied to Linear Programming, LP, and Semidefinite Programming, SDP. We analyze the difficulties inherent in current methods and present robust algorithms. We start with the error bound analysis of the search directions for the normal equation approach for LP. Our error analysis explains the surprising fact that the ill-conditioning is not a significant problem for the normal equation system. We also explain why most of the popular LP solvers have a default stop tolerance of only 10-8 when the machine precision on a 32-bit computer is approximately 10-16.
We then propose a simple alternative approach for the normal equation based interior-point method. This approach has better numerical stability than the normal equation based method. Although, our approach is not competitive in terms of CPU time for the NETLIB problem set, we do obtain higher accuracy. In addition, we obtain significantly smaller CPU times compared to the normal equation based direct solver, when we solve well-conditioned, huge, and sparse problems by using our iterative based linear solver. Additional techniques discussed are: crossover; purification step; and no backtracking.
Finally, we present an algorithm to construct SDP problem instances with prescribed strict complementarity gaps. We then introduce two measures of strict complementarity gaps. We empirically show that: (i) these measures can be evaluated accurately; (ii) the size of the strict complementarity gaps correlate well with the number of iteration for the SDPT3 solver, as well as with the local asymptotic convergence rate; and (iii) large strict complementarity gaps, coupled with the failure of Slater's condition, correlate well with loss of accuracy in the solutions. In addition, the numerical tests show that there is no correlation between the strict complementarity gaps and the geometrical measure used in [31], or with Renegar's condition number.
5
Zanjácomo, Paulo Régis. "On weighted paths for nonlinear semidefinite complementarity problems and newton methods for semidefinite programming." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/21680.
Full text
6
Ye, Kai. "Applications of semidefinite programming in finance." Thesis, Imperial College London, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.508489.
Full text
7
Keuchel, Jens. "Image partitioning based on semidefinite programming." [S.l. : s.n.], 2004. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB11513861.
Full text
8
Qian, Xun. "Continuous methods for convex programming and convex semidefinite programming." HKBU Institutional Repository, 2017. https://repository.hkbu.edu.hk/etd_oa/422.
Full textAbstract:
In this thesis, we study several interior point continuous trajectories for linearly constrained convex programming (CP) and convex semidefinite programming (SDP). The continuous trajectories are characterized as the solution trajectories of corresponding ordinary differential equation (ODE) systems. All our ODE systems are closely related to interior point methods.. First, we propose and analyze three continuous trajectories, which are the solutions of three ODE systems for linearly constrained convex programming. The three ODE systems are formulated based on an variant of the affine scaling direction, the central path, and the affine scaling direction in interior point methods. The resulting solutions of the first two ODE systems are called generalized affine scaling trajectory and generalized central path, respectively. Under some mild conditions, the properties of the continuous trajectories, the optimality and convergence of the continuous trajectories are all obtained. Furthermore, we show that for the example of Gilbert et al. [Math. Program., { 103}, 63-94 (2005)], where the central path does not converge, our generalized central path converges to an optimal solution of the same example in the limit.. Then we analyze two primal dual continuous trajectories for convex programming. The two continuous trajectories are derived from the primal-dual path-following method and the primal-dual affine scaling method, respectively. Theoretical properties of the two interior point continuous trajectories are fully studied. The optimality and convergence of both interior point continuous trajectories are obtained for any interior feasible point under some mild conditions. In particular, with proper choice of some parameters, the convergence for both continuous trajectories does not require the strict complementarity or the analyticity of the objective function.. For convex semidefinite programming, four interior continuous trajectories defined by matrix differential equations are proposed and analyzed. Optimality and convergence of the continuous trajectories are also obtained under some mild conditions. We also propose a strategy to guarantee the optimality of the affine scaling algorithm for convex SDP.
9
Shen, Yijiang. "Binary image restoration by positive semidefinite programming and signomial programming." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/HKUTO/record/B39557431.
Full text
10
沈逸江 and Yijiang Shen. "Binary image restoration by positive semidefinite programming and signomial programming." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39557431.
Full text
11
Zhao, Qing. "Semidefinite programming for assignment and partitioning problems." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/nq21405.pdf.
Full text
12
Stovall, Kazumi Niki. "Semidefinite Programming and Stability of Dynamical System." Digital Archive @ GSU, 2006. http://digitalarchive.gsu.edu/math_theses/4.
Full textAbstract:
In the first part of the thesis we present several interior point algorithms for solving certain positive definite programming problems. One of the algorithms is adapted for finding out whether there exists or not a positive definite matrix which is a real linear combination of some given symmetric matrices A1,A2, . . . ,Am. In the second part of the thesis we discuss stability of nonlinear dynamical systems. We search using algorithms described in the first part, for Lyapunov functions of a few forms. A suitable Lyapunov function implies the existence of a hyperellipsoidal attraction region for the dynamical system, thus guaranteeing stability.
13
Biswas, Pratik. "Semidefinite programming approaches to distance geometry problems /." May be available electronically:, 2007. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.
Full text
14
Lopez, Rafaël. "Stochastic quadratic knapsack problems and semidefinite programming." Paris 11, 2009. http://www.theses.fr/2009PA112283.
Full textAbstract:
Dans cette thèse, nous présentons une étude détaillée de problèmes de sac-à-dos stochastiques quadratiques, ainsi que des applications de la Programmation Semidéfinie (SDP) pour un problème de télécommunications et pour une étude expérimentale pour des problèmes de Coupe Max et de CDMA. La première partie de cette thèse consiste en un rappel des notions et résultats utilisés par la suite. La seconde partie est consacrée à l’étude du problème du sac- à- dos stochastique, dont nous développons un nouveau modèle, à deux phases (recours) et à contraintes probabilistes. Nous en proposons plusieurs variantes. Nous présentons de multiples relaxations, basées sur la relaxation linéaire et la SDP. Nous montrons que la SDP donne des bornes significativement meilleures que la relaxation linéaire. Enfin, nous proposons une heuristique d’approximation basée sur le résultat de la relaxation linéaire et la SDP. Nous montrons que la SDP donne des bornes significativement meilleures que la relaxation linéaire. Enfin nous proposons une heuristique d’approximation, basée sur le résultat de la relaxation linéaire et sur le résultat de la seconde relaxation SDP , dont nous détaillons les performances. La troisième partie de la thèse est centrée sur l’usage de la SDP sur des problèmes pratiques. La première application étudiée est sur un problème de détection multiutilisateur dans le CDMA. Nous développons un nouvel algorithme combinant SDP et une méta-heuristique VNS pour obtenir un signal de meilleure qualité. Nous détaillons les résultats expérimentaux de notre méthode et d’autres, basées sur SDP. La seconde application est une comparaison expérimentale de diverses relaxations pour le problème de la Coupe Max et dans le CDMA. Nous présentons les performances des relaxations Lagrangienne et SDP comparées à la relaxation linéaire, ainsi que celles de la décomposition spectrale dans le cas du CDMAIn this thesis, we study stochastic quadratic knapsack problems and applications of Semidefinite Programming for a telecommunication problem and for an experimental study of the MaxCut and CDMA problems. The first part of this thesis gives the prelimary notions and results necessary to develop and understand the contents of this thesis. The second part is the study of the stochastic quadratic knapsack problem, for which we develop a new formulation, using recourse (two-stage) and probabilistic contraints. We give multiple variants of this formulation. We propose various relaxations of this problems, based on the linear relaxation and on SDP. We show that SDP gives significantly better bounds than linear relaxation. Finally, we develop an approximation heuristic based on the result of the linear relaxation and of the second SDP relaxation, and give details of their respective performances. The third part of this thesis is dedicated to applications of SDP on pratical problems. The first application we study is a telecommunication problem : the multiuser detection problem in CDMA. We develop a new algorithm combining SDP and a VNS meta-heuristic to obtain a better signal quality. We detail the experimental results of our method and of other SDP based methods. The second application is an experimental comparison of various relaxations for the MaxCut problem and the CDMA problem. We detail the performances of Lagrangian and SDP relaxations compared to linear relaxation, and to the spectral decomposition in the CDMA case
15
Fantuzzi, Giovanni. "Construction of optimal background fields using semidefinite programming." Thesis, Imperial College London, 2018. http://hdl.handle.net/10044/1/60642.
Full textAbstract:
Quantitative analysis of systems exhibiting turbulence is challenging due to the lack of exact solutions and the cost of accurate simulations, but asymptotic or time-averaged properties can often be bounded rigorously using the background method. This rests on the construction of a background field for the system subject to a spectral constraint, which requires that a background-field-dependent linear operator has non-negative eigenvalues. This thesis develops techniques for the numerical optimisation of background fields and their corresponding bounds. First, bounds on the asymptotic energy of solutions of the Kuramoto–Sivashinsky equation are optimised by solving the Euler–Lagrange (EL) equations for the optimal background field using a time-marching algorithm. It is demonstrated that convergence to incorrect solutions occurs unless the derivation of the EL equations accounts for the multiplicity of eigenvalues in the spectral constraints. Second, semidefinite programmes (SDPs) are formulated to approximately solve optimisation problems subject to a class of integral inequalities on function spaces, to which spectral constraints can often be reduced. More precisely, inner and outer approximations of the feasible set of an integral inequality with one-dimensional compact integration domain, whose integrand is quadratic in the test functions and affine in the optimisation variables, are constructed using linear matrix inequalities. These SDP-based techniques, implemented in the MATLAB toolbox QUINOPT, are then utilised to bound the dissipation coefficient C_ε in stress-driven shear flows, and further improved to bound the Nusselt number Nu in Bénard-Marangoni convection at infinite Prandtl number. The results suggest that the existing analytical bounds on C_ε attain the optimal asymptotic scaling, while those on Nu may be lowered by a logarithmic factor upon constructing a non-monotonic background field. It is also concluded that semidefinite programming will offer an efficient, robust, and flexible framework to optimise background fields if the computational challenges presented by large-scale SDPs can be addressed.
16
Yan, Zhifei. "Semidefinite Programming Approaches to Network Clustering and Smoothing." The Ohio State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=osu1503180139155502.
Full text
17
Naldi, Simone. "Exact algorithms for determinantal varieties and semidefinite programming." Thesis, Toulouse, INSA, 2015. http://www.theses.fr/2015ISAT0021/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à l'étude des structures déterminantielles apparaissent dans l'optimisation semi-définie (SDP), le prolongement naturel de la programmation linéaire au cône des matrices symétrique semi-définie positives. Si l'approximation d'une solution d'un programme semi-défini peut être calculé efficacement à l'aide des algorithmes de points intérieurs, ni des algorithmes exacts efficaces pour la SDP sont disponibles, ni une compréhension complète de sa complexité théorique a été atteinte. Afin de contribuer à cette question centrale en optimisation convexe, nous concevons un algorithme exact pour décider la faisabilité d'une inégalité matricielle linéaire (LMI) $A(x)\succeq 0$. Quand le spectraèdre associé (le lieu $\spec$ des $x \in \RR^n$ ou $A(x)\succeq 0$) n'est pas vide, la sortie de cet algorithme est une représentation algébrique d'un ensemble fini qui contient au moins un point $x \in \spec$: dans ce cas, le point $x$ minimise le rang de $A(x)$ sur $\spec$. La complexité est essentiellement quadratique en le degré de la représentation en sortie, qui coïncide, expérimentalement, avec le degré algébrique de l'optimisation semi-définie. C'est un garantie d'optimalité de cette approche dans le contexte des algorithmes exacts pour les LMI et la SDP. Remarquablement, l'algorithme ne suppose pas la présence d'un point intérieur dans $\spec$, et il profite de l'existence de solutions de rang faible de l'LMI $A(x)\succeq 0$. Afin d'atteindre cet objectif principal, nous développons une approche systématique pour les variétés déterminantielles associées aux matrices linéaires. Nous prouvons que décider la faisabilité d'une LMI $A(x)\succeq 0$ se réduit à calculer des points témoins dans les variétés déterminantielles définies sur $A(x)$. Nous résolvons ce problème en concevant un algorithme exact pour calculer au moins un point dans chaque composante connexe réelle du lieu des chutes de rang de $A(x)$. Cet algorithme prend aussi avantage des structures supplémentaires, et sa complexité améliore l'état de l'art en géométrie algébrique réelle. Enfin, les algorithmes développés dans cette thèse sont implantés dans une nouvelle bibliothèque Maple appelé Spectra, et les résultats des expériences mettant en évidence la meilleure complexité sont fournisIn this thesis we focus on the study of determinantal structures arising in semidefinite programming (SDP), the natural extension of linear programming to the cone of symetric positive semidefinite matrices. While the approximation of a solution of a semidefinite program can be computed efficiently by interior-point algorithms, neither efficient exact algorithms for SDP are available, nor a complete understanding of its theoretical complexity has been achieved. In order to contribute to this central question in convex optimization, we design an exact algorithm for deciding the feasibility of a linear matrix inequality (LMI) $A(x) \succeq 0$. When the spectrahedron $\spec = \{x \in \RR^n \mymid A(x) \succeq 0\}$ is not empty, the output of this algorithm is an algebraic representation of a finite set meeting $\spec$ in at least one point $x^*$: in this case, the point $x^*$ minimizes the rank of the pencil on the spectrahedron. The complexity is essentially quadratic in the degree of the output representation, which meets, experimentally, the algebraic degree of semidefinite programs associated to $A(x)$. This is a guarantee of optimality of this approach in the context of exact algorithms for LMI and SDP. Remarkably, the algorithm does not assume the presence of an interior point in the spectrahedron, and it takes advantage of the existence of low rank solutions of the LMI. In order to reach this main goal, we develop a systematic approach to determinantal varieties associated to linear matrices. Indeed, we prove that deciding the feasibility of a LMI can be performed by computing a sample set of real solutions of determinantal polynomial systems. We solve this problem by designing an exact algorithm for computing at least one point in each real connected component of the locus of rank defects of a pencil $A(x)$. This algorithm admits as input generic linear matrices but takes also advantage of additional structures, and its complexity improves the state of the art in computational real algebraic geometry. Finally, the algorithms developed in this thesis are implemented in a new Maple library called {Spectra}, and results of experiments highlighting the complexity gain are provided
18
Han, Weiqiao. "Semidefinite programming approaches to multi-contact feedback control." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/122698.
Full textAbstract:
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 71-77).
We consider the feedback design for stabilizing a rigid body system by making and breaking multiple contacts with the environment without prespecifying the timing or the number of occurrence of the contacts. We examine several different models of such systems and the roles of semidefinite programming and sums-of-squares programming in designing and verifying stabilizing controllers. First the system is modelled as a discrete-time piecewise affine system and we use semidefinite programming to design stabilizing controllers according to Lyapunov theory. Second the system is modelled as a discrete-time piecewise polynomial system and we use sums-of-squares programming to design feedback controllers. Third the system is modelled as a discrete-time polynomial system with linear complimentarity constraints for contacts and we use sums-of-squares to verify the controllers according to Lyapunov theory.
"Supported by MIT Cronin Fellowship, NASA Award NNX16AC49A, Air Force/Lincoln Laboratory Award No. 7000374874, Army Research Office Award No. W911NF-15-1-0166, and Department of the Navy, Office of Naval Research, Award No. N00014-18-1-2210"
by Weiqiao Han.
S.M.
S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
19
Lu, Zhaosong. "Algorithm Design and Analysis for Large-Scale Semidefinite Programming and Nonlinear Programming." Diss., Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/7151.
Full textAbstract:
The limiting behavior of weighted paths associated with the semidefinite program (SDP) map $X^{1/2}SX^{1/2}$ was studied and some applications to error bound analysis and superlinear convergence of a class of
primal-dual interior-point methods were provided. A new approach for solving large-scale well-structured sparse SDPs via a saddle point mirror-prox algorithm with ${cal O}(epsilon^{-1})$ efficiency was developed based on exploiting sparsity structure and reformulating SDPs into smooth convex-concave saddle point problems. An iterative solver-based
long-step primal-dual infeasible path-following algorithm for convex quadratic programming (CQP) was developed. The search directions of
this algorithm were computed by means of a preconditioned iterative linear solver. A uniform bound, depending only on the CQP data, on
the number of iterations performed by a preconditioned iterative linear solver was established. A polynomial bound on the number of
iterations of this algorithm was also obtained. One efficient ``nearly exact' type of method for solving large-scale ``low-rank' trust region
subproblems was proposed by completely avoiding the computations of Cholesky or partial Cholesky factorizations. A computational study of this method was also provided by applying it to solve some large-scale nonlinear programming problems.
20
Macedo, Eloísa Catarina Monteiro de Figueiredo Amaral e. "Numerical study of regularity in semidefinite programming and applications." Doctoral thesis, Universidade de Aveiro, 2016. http://hdl.handle.net/10773/16278.
Full textAbstract:
Doutoramento em MatemáticaThis thesis is devoted to the study of regularity in semidefinite programming (SDP), an important area of convex optimization with a wide range of applications. The duality theory, optimality conditions and methods for SDP rely on certain assumptions of regularity that are not always satisfied. Absence of regularity, i.e., nonregularity, may affect the characterization of optimality of solutions and SDP solvers may run into numerical difficulties, leading to unreliable results. There exist different notions associated to regularity. In this thesis, we study in particular, well-posedness, good behaviour and constraint qualifications (CQs), as well as relations among them. A widely used CQ in SDP is the Slater condition. This condition guarantees that the first order necessary optimality conditions in the Karush-Kuhn-Tucker formulation are satisfied. Current SDP solvers do not check if a problem satisfies the Slater condition, but work assuming its fulfilment. We develop and implement in MATLAB numerical procedures to verify if a given SDP problem is regular in terms of the Slater condition and to determine the irregularity degree in the case of nonregularity. Numerical experiments presented in this work show that the proposed procedures are quite effcient and confirm the obtained conclusions about the relationship between the Slater condition and other regularity notions. Other contribution of the thesis consists in the development and MATLAB implementation of an algorithm for generating nonregular SDP problems with a desired irregularity degree. The database of nonregular problems constructed using this generator is publicly available and can be used for testing new SDP methods and solvers. Another contribution of this thesis is concerned with an SDP application to data analysis. We consider a nonlinear SDP model and linear SDP relaxations for clustering problems and study their regularity. We show that the nonlinear SDP model is nonregular, while its relaxations are regular. We suggest a SDP-based algorithm for solving clustering and dimensionality reduction problems and implement it in R. Numerical tests on various real-life data sets confirm the fastness and efficiency of this numerical procedure.
Esta tese _e dedicada ao estudo de regularidade em programação semidefinida (SDP - semidefinite programming), uma importante área da optimização convexa com uma vasta gama de aplicações. A teoria de dualidade, condições de optimalidade e métodos para SDP assentam em certos pressupostos de regularidade que nem sempre são satisfeitos. A ausência de regularidade, isto é, não regularidade, pode afetar a caracterização da optimalidade de soluções e os solvers podem apresentar dificuldades numéricas, conduzindo a resultados pouco fiáveis. Existem diferentes noções associadas a regularidade. Nesta tese, estudamos em particular, os conceitos de problemas bem-postos, bem comportados e condições de qualificação de restrições (CQ - constraint qualifications), bem como as relações entre eles. Uma das CQs mais utilizadas em SDP é a condição de Slater. Esta condição garante que as condições de optimalidade de primeira ordem, conhecidas como condições de Karush-Kuhn-Tucker, estão satisfeitas. Os solvers atuais não verificam se um problema a resolver satisfaz a condição de Slater, mas trabalham nesse pressuposto. Desenvolvemos e implementamos em MATLAB procedimentos numéricos para verificar se um dado problema de SDP é regular em termos da condição de Slater e determinar o grau de irregularidade no caso de problemas não regulares. Os resultados das experiências numéricas apresentados neste trabalho mostram que os procedimentos propostos são eficientes e confirmam as conclusões obtidas sobre a relação entre a condição de Slater e outras noções de regularidade. Outra contribuição da tese consiste no desenvolvimento e na implementação em MATLAB de um procedimento numérico para gerar problemas de SDP não regulares com um determinado grau de irregularidade. A colecção de problemas não regulares construídos usando este gerador é de acesso livre e permite testar novos métodos e solvers para SDP. Uma outra contribuição desta tese está relacionada com uma aplicação de SDP em análise de dados. Consideramos um modelo de SDP não linear, bem como as suas relaxações lineares para problemas de clusterização, e estudamos a sua regularidade. Mostramos que o modelo não linear é não regular, enquanto que as suas relaxações são regulares. Sugerimos um algoritmo baseado em modelos de SDP para resolver problemas de clusterização e redução de dimensionalidade, e implementámo-lo em R. Os testes numéricos usando vários conjuntos de dados confirmam a rapidez e eficiência deste procedimento numérico.
21
Yamakawa, Yuya. "Studies on Optimization Methods for Nonlinear Semidefinite Programming Problems." 京都大学 (Kyoto University), 2015. http://hdl.handle.net/2433/199446.
Full text
22
Li, Chao. "Semidefinite programming, binary codes and a graph coloring problem." Digital WPI, 2015. https://digitalcommons.wpi.edu/etd-theses/863.
Full textAbstract:
"Experts in information theory have long been interested in the maximal size, A(n, d), of a binary error-correcting code of length n and minimum distance d, The problem of determining A(n, d) involves both the construction of good codes and the search for good upper bounds. For quite some time now, Delsarte's linear programming approach has been the dominant approach to obtaining the strongest general purpose upper bounds on the efficiency of error-correcting codes. From 1973 forward, the linear programming bound found many applications, but there were few significant theoretical advances until Schrijver proposed a new code upper bound via semidefinite programming in 2003. Using the Terwilliger algebra, a recently introduced extension of the Bose-Mesner algebra, Schrijver formulated a new SDP strengthening of the LP approach. In this project we look at the dual solutions of the semidefinite programming bound for binary error-correcting codes. We explore the combinatorial meaning of these variables for small n and d, such as n = 4 and d = 2. To obtain information like this, we wrote a computer program with both Matlab and CVX modules to get solution of our primal SDP formulation. Our program efficiently generates the primal solutions with corresponding constraints for any n and d. We also wrote a program in C++ to parse the output of the primal SDP problem, and another Matlab script to generate the dual SDP problem, which could be used in assigning combinatorial meaning to the values given in the dual optimal solution. Our code not only computes both the primal and dual optimal variable values, but allows the researcher to display them in meaningful ways and to explore their relationship and dependence on arameters. These values are expected to be useful for later study of the combinatorial meaning of such solutions."
23
Monir, Vaghefi Sayed Reza. "Cooperative Positioning in Wireless Sensor Networks Using Semidefinite Programming." Diss., Virginia Tech, 2015. http://hdl.handle.net/10919/71884.
Full textAbstract:
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.
24
Mefo, Kue Floriane. "Mixed integer bilevel programming problems." Doctoral thesis, Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola", 2017. http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-230335.
Full textAbstract:
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
25
Salinas, Varela Adrián Alberto. "Semidefinite programming-based analysis of continuous-time piecewise affine systems." Thesis, University of Cambridge, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.608522.
Full text
26
Dowdy, Garrett Ryan. "Using semidefinite programming to bound distributions in chemical engineering systems." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/121820.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Chemical Engineering, 2019Cataloged from PDF version of thesis.
Includes bibliographical references (pages 329-334).
Distributions appear in many forms in models of chemical engineering systems. Such distributions account for microscopic variability in the system while simultaneously explaining its macroscopic properties. These macroscopic properties are often of practical engineering interest. Thus, it is valuable to be able to characterize the underlying distributions that affect them. Recently, in the mathematical programming literature, it was shown that it is possible to optimize a linear objective over a set of distributions by solving a specific type of convex optimization problem called a semidefinite program (SDP). From a theoretical perspective, SDPs can be solved efficiently. Furthermore, there exist several off-the-shelf codes designed specifically to solve SDPs. This thesis demonstrates how these theoretical and practical advancements can be applied to chemical engineering problems featuring distributions. Broadly speaking, it shows how, given limited information about a distribution, one can use SDPs to calculate mathematically rigorous bounds on various descriptions of that distribution. Two specific types of distributions are examined: particle size distributions and probability distributions arising in stochastic chemical kinetics, with the majority of the thesis covering the latter topic. The SDP-based bounding method described herein provides a rigorous solution to the long-standing "moment closure problem" arising in stochastic chemical kinetics. Moreover, it provides a means of analyzing of stochastic chemical kinetic systems which cannot be effectively analyzed using existing methods. The bounding method does have some limitations, and we present several refinements of the method aimed at overcoming these limitations. Finally, we discuss several ideas through which the bounding method may be further improved, which have not yet been explored.
by Garrett Ryan Dowdy.
Ph. D.
Ph.D. Massachusetts Institute of Technology, Department of Chemical Engineering
27
Skomra, Mateusz. "Tropical spectrahedra : Application to semidefinite programming and mean payoff games." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLX058/document.
Full textAbstract:
La programmation semi-définie est un outil fondamental d'optimisation convexe et polynomiale. Elle revient à optimiser une fonction linéaire sur un spectraèdre (un ensemble défini par des inégalités matricielles linéaires). En particulier, la programmation semi-définie est une généralisation de la programmation linéaire.Nous étudions l'analogue non-archimédien de la programmation semi-définie, en remplaçant le corps des nombres réels par le corps des séries de Puiseux. Notre approche est fondée sur des méthodes issues de la géométrie tropicale et, en particulier, sur l'étude de la tropicalisation des spectraèdres.En première partie de la thèse, nous analysons les images par la valuation des ensembles semi-algébriques généraux définis dans le corps des séries de Puiseux. Nous montrons que ces images ont une structure polyédrale, ce qui fournit un analogue réel du théorème de Bieri et Groves. Ensuite, nous introduisons la notion de spectraèdres tropicaux et nous montrons que, sous une hypothèse de généricité, ces objets sont décrits par des systèmes d'inégalités polynomiales de degré 2 sur le semi-corps tropical. Cela généralise un résultat de Yu sur la tropicalisation du cône des matrices positives.Une question importante relative à la programmation semi-définie sur les réels consiste à caractériser des projections de spectraèdres. Dans ce cadre, Helton et Nie ont conjecturé que tout ensemble semi-algébrique convexe est la projection d'un spectraèdre. La conjecture a été réfutée par Scheiderer. Néanmoins, nous montrons qu'elle est vraie ''à valuation près'' : dans le corps réel clos des séries de Puiseux, les ensembles semi-algébriques convexes et les spectraèdres projetés ont exactement les mêmes images par la valuation non-archimédienne.En seconde partie de la thèse, nous étudions des questions algorithmiques liées à la programmation semi-définie. Le problème algorithmique de base consiste à décider si un spectraèdre est vide. On ne sait pas si ce problème appartient à NP dans le modèle de la machine de Turing, et les algorithmes fondés sur la décomposition cylindrique algébrique ou la méthode de points critiques constituent l'état de l'art dans ce domaine. Nous montrons que, dans le cadre non-archimédien, les spectraèdres tropicaux génériques sont décrits par des opérateurs de Shapley associés aux jeux à paiement moyen stochastiques. Cela donne une méthode pour résoudre des problèmes de réalisabilité en programmation semi-définie non-archimédienne en utilisant les algorithmes combinatoires conçus pour les jeux stochastiques.Dans les chapitres finals de la thèse, nous établissons des bornes de complexité pour l'algorithme d'itération sur les valeurs qui exploitent la correspondance entre les jeux stochastiques et la convexité tropicale. Nous montrons que le nombre d'itérations est contrôlé par un nombre de conditionnement relié au diamètre intérieur du spectraèdre tropical associé.Nous fournissons des bornes supérieures générales sur le nombre de conditionnement. Pour cela, nous établissons des bornes optimales sur la taille en bits des mesures invariantes de chaînes de Markov. Comme corollaire, notre estimation montre que l'itération sur la valeur résout les jeux ergodiques à paiement moyen en temps pseudo-polynomial si le nombre de positions aléatoires est fixé. Enfin, nous expérimentons notre approche à la résolution de programmes semi-définis non-archimédiens aléatoires de grande tailleSemidefinite programming (SDP) is a fundamental tool in convex and polynomial optimization. It consists in minimizing the linear functions over the spectrahedra (sets defined by linear matrix inequalities). In particular, SDP is a generalization of linear programming.The purpose of this thesis is to study the nonarchimedean analogue of SDP, replacing the field of real numbers by the field of Puiseux series. Our methods rely on tropical geometry and, in particular, on the study of tropicalization of spectrahedra.In the first part of the thesis, we analyze the images by valuation of general semialgebraic sets defined over the Puiseux series. We show that these images have a polyhedral structure, giving the real analogue of the Bieri--Groves theorem. Subsequently, we introduce the notion of tropical spectrahedra and show that, under genericity conditions, these objects can be described explicitly by systems of polynomial inequalities of degree 2 in the tropical semifield. This generalizes the result of Yu on the tropicalization of the SDP cone.One of the most important questions about real SDPs is to characterize the sets that arise as projections of spectrahedra. In this context, Helton and Nie conjectured that every semialgebraic convex set is a projected spectrahedron. This conjecture was disproved by Scheiderer. However, we show that the conjecture is true ''up to taking the valuation'': over a real closed nonarchimedean field of Puiseux series, the convex semialgebraic sets and the projections of spectrahedra have precisely the same images by the nonarchimedean valuation.In the second part of the thesis, we study the algorithmic questions related to SDP. The basic computational problem associated with SDP over real numbers is to decide whether a spectrahedron is nonempty. It is unknown whether this problem belongs to NP in the Turing machine model, and the state-of-the-art algorithms that certify the (in)feasibility of spectrahedra are based on cylindrical decomposition or the critical points method. We show that, in the nonarchimedean setting, generic tropical spectrahedra can be described by Shapley operators associated with stochastic mean payoff games. This provides a tool to solve nonarchimedean semidefinite feasibility problems using combinatorial algorithms designed for stochastic games.In the final chapters of the thesis, we provide new complexity bounds for the value iteration algorithm, exploiting the correspondence between stochastic games and tropical convexity. We show that the number of iterations needed to solve a game is controlled by a condition number, which is related to the inner radius of the associated tropical spectrahedron. We provide general upper bounds on the condition number. To this end, we establish optimal bounds on the bit-length of stationary distributions of Markov chains. As a corollary, our estimates show that value iteration can solve ergodic mean payoff games in pseudopolynomial time, provided that the number of random positions of the game is fixed. Finally, we apply our approach to large scale random nonarchimedean SDPs
28
Oskoorouchi, Mohammad R. "The analytic center cutting plane method with semidefinite cuts /." Thesis, McGill University, 2002. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=38507.
Full textAbstract:
We propose an analytic center cutting plane algorithm for semidefinite programming (SDP). Reformulation of the dual problem of SDP into an eigenvalue optimization, when the trace of any feasible primal matrix is a positive constant, is well known. We transform the eigenvalue optimization problem into a convex feasibility problem. The problem of interest seeks a feasible point in a bounded convex set, which contains a full dimensional ball with &egr;(<1) radius and is contained in a compact convex set described by matrix inequalities, known as the set of localization. At each iteration, an approximate analytic center of the set of localization is computed. If this point is not in the solution set, an oracle is called to return a p-dimensional semidefinite cut. The set of localization then, is updated by adding the semidefinite cut through the center. We prove that the analytic center is recovered after adding a p-dimensional semidefinite cut in O(plog(p + 1)) damped Newton's iteration and that the ACCPM with semidefinite cuts is a fully polynomial approximation scheme. We report the numerical result of our algorithm when applied to the semidefinite relaxation of the Max-Cut problem.
29
Jiao, Chunxi. "Semidefinite relaxations for a linear programming approach to exit-time stochastic control." Thesis, The University of Sydney, 2021. https://hdl.handle.net/2123/24569.
Full textAbstract:
In this thesis, we investigate the linear programming framework for exit-time stochastic control problems and apply the moment-sum-of-squares (moment-SOS) hierarchy to obtain convergent pointwise bounds and global bounding functions for the value functions. The primal linear program over suitable measures and the dual linear program over continuous test functions are implemented numerically by semidefinite programs which target moments and SOS polynomial representations respectively. Numerically optimised bounds converge to the value function from below as polynomial degree increases under suitable technical conditions. For exit-time stochastic control with diffusions and similarly for optimal stopping problems on bounded domains (or equivalently, classic obstacle problems), we approach the equivalence between the value of the primal linear program and that of the original stochastic problem using a mollification approach in Fleming and Vermes (1989) with connections to the dual side. For exit-time stochastic control with switching diffusions, we construct a primal linear program with multiple equality constraints to disentangle the interdependency between test functions arising from the switching component, and approach a similar equivalence result using a well-studied probabilistic argument in Kurtz and Stockbridge (1998). We provide numerical examples in each of the main chapters to support our theoretical findings and to illustrate the applicability of the proposed framework.
30
Burer, Samuel A. "New algorithmic approaches for semidefinite programming with applications to combinatorial optimization." Diss., Georgia Institute of Technology, 2001. http://hdl.handle.net/1853/30268.
Full text
31
Gong, Yun. "On semidefinite programming and vector quantization with application to image coding." Diss., Georgia Institute of Technology, 2000. http://hdl.handle.net/1853/14876.
Full text
32
Kim, Chiheon. "Statistical limits of graphical channel models and a semidefinite programming approach." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120659.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 205-213).
Community recovery is a major challenge in data science and computer science. The goal in community recovery is to find the hidden clusters from given relational data, which is often represented as a labeled hyper graph where nodes correspond to items needing to be labeled and edges correspond to observed relations between the items. We investigate the problem of exact recovery in the class of statistical models which can be expressed in terms of graphical channels. In a graphical channel model, we observe noisy measurements of the relations between k nodes while the true labeling is unknown to us, and the goal is to recover the labels correctly. This generalizes both the stochastic block models and spiked tensor models for principal component analysis, which has gained much interest over the last decade. We focus on two aspects of exact recovery: statistical limits and efficient algorithms achieving the statistic limit. For the statistical limits, we show that the achievability of exact recovery is essentially determined by whether we can recover the label of one node given other nodes labels with fairly high probability. This phenomenon was observed by Abbe et al. for generic stochastic block models, and called "local-to-global amplification". We confirm that local-to-global amplification indeed holds for generic graphical channel models, under some regularity assumptions. As a corollary, the threshold for exact recovery is explicitly determined. For algorithmic concerns, we consider two examples of graphical channel models, (i) the spiked tensor model with additive Gaussian noise, and (ii) the generalization of the stochastic block model for k-uniform hypergraphs. We propose a strategy which we 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 the algorithm.
by Chiheon Kim.
Ph. D.
33
Hu, Sha S. M. Massachusetts Institute of Technology. "Semidefinite relaxation based branch-and-bound method for nonconvex quadratic programming." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/39217.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006.Includes bibliographical references (leaves 73-75).
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 solve nonconvex Box constrained Quadratic Programming (BoxQP) problems and the comparison of the four methods. For some lower dimensional problems, SDP relaxation methods can achieve tight bounds for the BoxQP problem; whereas for higher dimensional cases (more than 20 dimensions), the bounds achieved by the four Semidefinite programming (SDP) relaxation methods are always loose. To achieve tight bounds for higher dimensional BoxQP problems, we combine the branch-and-bound method and SDP relaxation method to develop an SDP relaxation based branch-and-bound (SDPBB) method. We introduce a sensitivity analysis method for the branching process of SDPBB. This sensitivity analysis method can improve the convergence speed significantly.
(cont.) Compared to the interval branch-and-bound method and the global optimization software BARON, SDPBB can achieve better bounds and is also much more efficient. Additionally, we have developed a multisection algorithm for SDPBB and the multisection algorithm has been parallelized using Message Passing Interface (MPI). By parallelizing the program, we can significantly improve the speed of solving higher dimensional BoxQP problems.
by Sha Hu.
S.M.
34
Ha, Hoang Kha Electrical Engineering & Telecommunications Faculty of Engineering UNSW. "Linear phase filter bank design by convex programming." Publisher:University of New South Wales. Electrical Engineering & Telecommunications, 2008. http://handle.unsw.edu.au/1959.4/43268.
Full textAbstract:
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.
35
Habermehl, Kai [Verfasser]. "Robust optimization of active trusses via mixed-integer semidefinite programming / Kai Habermehl." München : Verlag Dr. Hut, 2014. http://d-nb.info/1058285092/34.
Full text
36
Passuello, Alberto. "Semidefinite programming in combinatorial optimization with applications to coding theory and geometry." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2013. http://tel.archives-ouvertes.fr/tel-00948055.
Full textAbstract:
We apply the semidefinite programming method to obtain a new upper bound on the cardinality of codes made of subspaces of a linear vector space over a finite field. Such codes are of interest in network coding.Next, with the same method, we prove an upper bound on the cardinality of sets avoiding one distance in the Johnson space, which is essentially Schrijver semidefinite program. This bound is used to improve existing results on the measurable chromatic number of the Euclidean space.We build a new hierarchy of semidefinite programs whose optimal values give upper bounds on the independence number of a graph. This hierarchy is based on matrices arising from simplicial complexes. We show some properties that our hierarchy shares with other classical ones. As an example, we show its application to the problem of determining the independence number of Paley graphs.
37
Yeung, Sai Hei. "Analysis of the Projective Re-Normalization method on semidefinite programming feasibility problems." Thesis, Massachusetts Institute of Technology, 2008. http://hdl.handle.net/1721.1/43800.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008.Includes bibliographical references (p. 75-76).
In this thesis, we study the Projective Re-Normalization method (PRM) for semidefinite programming feasibility problems. To compute a good normalizer for PRM, we propose and study the advantages and disadvantages of a Hit & Run random walk with Dikin ball dilation. We perform this procedure on an ill-conditioned two dimensional simplex to show the Dikin ball Hit & Run random walk mixes much faster than standard Hit & Run random walk. In the last part of this thesis, we conduct computational testing of the PRM on a set of problems from the SDPLIB [3] library derived from control theory and several univariate polynomial problems sum of squares (SOS) problems. Our results reveal that our PRM implementation is effective for problems of smaller dimensions but tends to be ineffective (or even detrimental) for problems of larger dimensions.
by Sai Hei Yeung.
S.M.
38
Fawzi, Hamza. "Power and limitations of convex formulations via linear and semidefinite programming lifts." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/107331.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 155-162).
Convex relaxation methods play an important role in mathematical optimization to tackle hard nonconvex problems, and have been applied successfully in many areas of science and engineering. At the heart of such methods lies the question of obtaining a tractable description of the convex hull of a set. In this thesis we focus on the question of finding tractable representations of convex sets via the method of lifting, whereby the "hard" convex set is expressed as the projection of a simpler one living in higher-dimensional space. We derive new results and insights on the power and limitations of such liftings. In the first part of the thesis we study limitations of the lifting method and develop lower bounds on the sizes of linear programming (LP) and semidefinite programming (SDP) lifts of polytopes. For LP lifts the bound we develop applies generally for the nonnegative rank of matrices and we compare our method with existing combinatorial and non-combinatorial techniques. For SDP lifts we focus on so-called equivariant lifts that respect symmetry, and obtain lower bounds on the size of such lifts for certain combinatorial polytopes by exploiting the connection with the sum-of-squares method. In the second part of the thesis, we study the power of the lifting procedure and show how to obtain small semidefinite lifts for certain classes of polytopes via the idea of sparse sums of squares. We develop a graph-theoretic method to construct such lifts and use it to resolve a conjecture of Laurent from 2003 on the cut polytope, and to give an explicit sequence of polytopes with a gap between LP and SDP lifts. Finally we depart from the specific question of constructing lifts and consider the general problem of certifying nonnegativity of functions. We study a class of certificates rooted in convex duality and show that they encompass many existing methods for proving nonnegativity based on convex optimization. In particular we propose a new proof system to certify nonnegativity of entropy-like functions, which we illustrate on the problem of computing the logarithmic Sobolev constant of finite Markov chains.
by Hamza Fawzi.
Ph. D.
39
Mars, Sonja [Verfasser]. "Mixed-Integer Semidefinite Programming with an Application to Truss Topology Design / Sonja Mars." München : Verlag Dr. Hut, 2013. http://d-nb.info/1037286774/34.
Full text
40
Kleniati, Polyxeni M. "Decomposition schemes for polynomial optimisation, semidefinite programming and applications to nonconvex portfolio decisions." Thesis, Imperial College London, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.509792.
Full text
41
Adasme, Soto Pablo Alberto. "Deterministic uncertain nonlinear formulations for wireless OFDMA networks with applications on semidefinite programming." Paris 11, 2010. http://www.theses.fr/2010PA112323.
Full textAbstract:
Dans cette thèse, on étudie l'utilisation de la programmation semi-définie (SDP), l'optimisation robuste, la programmation stochastique, les relaxations lagrangiennes et des approches polyédriques de traitement de l'incertitude pour résoudre le problème d'allocation de ressources dans les réseaux sans fil OFDMA. Le premier chapitre introduit ce problème d'allocation de ressources. Puis, on fournit dans le chapitre 2 un bref aperçu théorique des concepts et méthodes dont on aura besoin dans la suite de la thèse. Dans le chapitre 3, les principales formulations mathématiques de la littérature liées aux canaux OFDMA à liaison montante sont présentées. Un schéma de M-allocation sur liaison montante est proposé sous l'hypothèse de faisabilité d'une méthode de détection de M signaux entrants sur chaque sous-porteuse. Un algorithme glouton de complexité polynomiale est dérivé de la relaxation lagrangienne de la formulation mathématique. Dans le chapitre 4, on propose deux programmes quadratiques sous contraintes quadratiques (BQCQP) en variables binaires pour la minimisation de l'énergie (contraintes de débit binaire et d'allocation sur les sous-porteuses) et on en déduit ensuite deux relaxations SDP. Dans le chapitre 5, trois approches d'optimisation robuste sont étudiées ; deux relaxations SDP et un programme de second ordre conique sont proposés. Dans le chapitre 6, on formule d'autres modèles quadratiques en utilisant la programmation stochastique et une approche polyédrale. Enfin dans le chapitre 7, on décrit les contributions principales et les conclusions générales de la thèse. En outre, de futures directions de recherche sont décritesLn this thesis, modern optimization techniques such as semidefinite programming (SDP), robust optimization, stochastic programming, lagrangian relaxations and polyhedral based uncertainty approaches are used to deal with the problem of resource allocation in wireless OFDMA networks. The thesis starts in chapter 1 by introducing the resource allocation problem. Ln chapter 2 a brief theoretical background describing the concepts and methods necessary for the development of the thesis are provided. Ln chapter 3, the main mathematical formulations from the literature related to uplink OFDMA channels are presented while an uplink M-Allocation scheme is proposed under the feasibility assumption of a new detection scheme of M incoming signals on each sub-carrier. A polynomial complexity greedy algorithm is derived from the lagrangian relaxation. Ln chapter 4, two binary quadratically constrained quadratic programs (BQCQP) for minimizing power subject to bit rate and sub-carrier allocation constraints for OFDMA are proposed and two SDP relaxations are derived. Ln chapter 5, three robust optimization approaches are studied; two SDP relaxations and a second order conic program are proposed. Ln chapter 6, further BQCQP models are formulated using stochastic programming and a robustness polyhedral approach. Finally in chapter 7, the main contributions as well as general conclusions of the thesis are outlined. Besides, further research directions are pointed
42
So, Anthony Man-Cho. "A semidefinite programming approach to the graph realization problem : theory, applications and extensions /." May be available electronically:, 2007. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.
Full text
43
Fortin, Charles. "A survey of the trust region subproblem within a semidefinite framework." Thesis, University of Waterloo, 2000. http://hdl.handle.net/10012/1038.
Full textAbstract:
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.
44
Yang, Shaoshi. "Detection for multiple-input multiple-output systems : probabilistic data association and semidefinite programming relaxation." Thesis, University of Southampton, 2013. https://eprints.soton.ac.uk/360710/.
Full textAbstract:
As a highly effective physical-layer interference management technique, the joint detection of a vector of non-orthogonal information-bearing symbols simultaneously transmitted over multiple-input multiple-output (MIMO) channels is of fundamental importance for high throughput digital communications. This is because the generic mathematical model of MIMO detection underpins a wide range of relevant applications including (but not limited to) the equalization of dispersive band-limited channels imposing intersymbol interference (ISI), the multiuser detection (MUD) in code-division multiple-access (CDMA) systems and the multi-stream detection for multiple-antenna based spatial-division multiplexing (SDM) systems. With the evolution of wireless networks, the “virtual MIMO” concept was conceived,which is also described by the generic mathematical MIMO model. MIMO detection becomes even more important, because the achievable performance of spectrum-efficient wireless networks is typically interference-limited, rather than noise-limited. In this thesis, a pair of detection methods that are well-suited for large-scale MIMO systems are investigated. The first one is the probabilistic data association (PDA) algorithm, which is essentially an interference-modelling approach based on iterative Gaussian approximation. The second one is the semidefinite programming (SDP) relaxation based approach, which approximates the optimal maximum likelihood (ML) detection problem to a convex optimization problem. The main advantage of both methods is that they impose a moderate computational complexity that increases as a polynomial function of the problem size, while providing competitive performance. The contributions of this thesis can be broadly categorized into two groups. The first group is related to the design of virtually antipodal (VA) detection of rectangular M-ary quadrature amplitude modulation (M-QAM) symbols transmitted in SDM-MIMO systems. As a foundation, in the first parts of Chapter 2 and Chapter 3 the rigorous mathematical relationship between the vector space of transmitted bits and that of transmitted rectangular M-QAM symbols is investigated. Both linear and nonlinear bit-to-symbol mappings are considered. It is revealed that the two vector spaces are linked by linear/quasi-linear transformations, which are explicitly characterized by certain transformation matrices. This formulation may potentially be applicable to many signal processing problems of wireless communications. For example, when used for detection of rectangular M-QAM symbol vector, it enables us to transform the conventional three-step “signal-to-symbol-to-bits” decision process to a direct “signal-to-bits” decision process. More specifically, based on the linear VA transformation, in Chapter 2 we propose a unified bit-based PDA (B-PDA) detection method for linear natural mapping aided rectangular M-QAM symbols transmitted in SDM-MIMO systems. We show that the proposed linear natural mapping based B-PDA approach attains an improved detection performance, despite dramatically reducing the omputational complexity in contrast to the conventional symbol-based PDA detector. Furthermore, in Chapter 3 a quasi-linear VA transformation based generalized low-complexity semidefinite programming relaxation (SDPR) detection approach is proposed for Gray-coded rectangular M-QAM signalling over MIMO channels. Compared to the linear natural mapping based B-PDA of Chapter 2, the quasi-linear VA transformation based SDPR method is capable of directly deciding on the information bits of the ubiquitous Gray-mapping aided rectangular M-QAM by decoupling the M-QAM constellation into several 4-QAM constellations. Moreover, it may be readily combined with the low-complexity bit-flipping based “hill climbing” technique for exploiting the unequal error protection (UEP) property of rectangular M-QAM, and the resultant VA-SDPR detector achieves the best bit-error rate (BER) performance among the known SDPR-based MIMO detectors conceived for high-order QAM constellations, while still maintaining the same order of polynomial-time worst-case computational complexity. Additionally, we reveal that the linear natural mapping based VA detectors attain the same performance provided by the binary reflected Gray mapping based VA detectors, but the former are simpler for implementation. Therefore, only if there are other constraints requiring using the nonlinear Gray mapping, it is preferable to use the linear natural mapping rather than the Gray mapping, when the VA detectors are used in uncoded MIMO systems. The second group explores the application of the PDA-aided detectors in some more sophisticated systems that are of great interest to the wireless research community. In particular, the design of iterative detection and decoding (IDD) schemes relying on the proposed low complexity PDA methods is investigated for the turbo-coded MIMO systems in Chapter 4 and 5. It has conventionally been regarded that the existing PDA algorithms output the estimated symbol-wise a posteriori probabilities (APPs) as soft information. In Chapter 4 and 5, however, we demonstrate that these probabilities are not the true APPs in the rigorous mathematical sense, but a type of nominal APPs, which are unsuitable for the classic architecture of IDD receivers. Moreover, our study shows that the known methods of calculating the bit-wise extrinsic logarithmic likelihood ratios (LLRs) are no longer applicable to the conventional PDA based methods when detecting M-ary modulation symbols. Additionally, the existing PDA based MIMO detectors typically operate purely in the probabilistic domain. Therefore, the existing PDA methods are not readily applicable to IDD receivers. To overcome this predicament, in Chapter 4 and Chapter 5 we propose the approximate Bayes’ theorem based logarithmic domain PDA (AB-Log-PDA) and the exact Bayes’ theorem based logarithmic domain PDA (EB-Log-PDA) detectors, respectively. We present the approaches of calculating the bit-wise extrinsic LLRs for both the AB-Log-PDA and the EB-Log-PDA, which makes them well-suited for IDD receivers. Furthermore, we demonstrate that invoking inner iterations within the PDA algorithms – which is common practice in PDA-aided uncoded MIMO systems – would actually degrade the IDD receiver’s performance, despite significantly increasing its overall computational complexity. Additionally, we investigate the relationship between the extrinsic LLRs of the proposed EB-Log-PDA and of the AB-Log-PDA. It is also shown that both the proposed AB-Log-PDA- and the EB-Log-PDA-based IDD schemes dispensing with any inner PDA iterations are capable of achieving a performance comparable to that of the optimal maximum a posteriori (MAP) detector based IDD receiver in the scenarios considered, despite their significantly lower computational complexity. Finally, in Chapter 6, a base station (BS) cooperation aided distributed soft reception scheme using the symbol-based PDA algorithm and soft combining (SC) is proposed for the uplink of multiuser multicell MIMO systems. The realistic 19-cell hexagonal cellular model relying on radical unity frequency reuse (FR) is considered, and local cooperation based message passing is used instead of a global message passing chain for the sake of reducing the backhaul traffic. We show that despite its moderate complexity and backhaul traffic, the proposed distributed PDA (DPDA) aided SC (DPDA-SC) reception scheme significantly outperforms the conventional non-cooperative benchmarkers. Furthermore, since only the index of the quantized converged soft information has to be exchanged between collaborative BSs for SC, the proposed DPDA-SC scheme is relatively robust to the quantization errors of the soft information exchanged. As an appealling benefit, the backhaul traffic is dramatically reduced at a negligible performance degradation.
45
ONO, Takao, and Tomio HIRATA. "Approximation Algorithms for MAX SAT." Institute of Electronics, Information and Communication Engineers, 2000. http://hdl.handle.net/2237/15068.
Full text
46
Fraticelli, Barbara M. P. "Semidefinite Cuts and Partial Convexification Techniques with Applications to Continuous Nonconvex Optimization, Stochastic Integer Programming, and Facility Layout Problems." Diss., Virginia Tech, 2001. http://hdl.handle.net/10919/27293.
Full textAbstract:
This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone.
We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Bendersâ decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Bendersâ methodology for problems having 0-1 mixed-integer subproblems.
We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach.Ph. D.
47
Yang, Boshi. "A conic optimization approach to variants of the trust region subproblem." Diss., University of Iowa, 2015. https://ir.uiowa.edu/etd/1938.
Full textAbstract:
The Trust Region Subproblem (TRS), which minimizes a nonconvex quadratic function over the unit ball, is an important subproblem in trust region methods for nonlinear optimization. Even though TRS is a nonconvex problem, it can be solved in polynomial time using, for example, a semidefinite programming (SDP) relaxation. Different variants of TRS have been considered from both theoretical and practical perspectives. In this thesis, we study three variants of TRS and their SDP/conic relaxations.
We first study an extended trust region subproblem (eTRS) in which the trust region equals the intersection of the unit ball with M linear cuts. When m = 0, when m = 1, or when m = 2 and the linear cuts are parallel, it is known that the eTRS optimal value equals the optimal value of a particular conic relaxation, which is solvable in polynomial time. However, it is also known that, when m ≥2 and at least two of the linear cuts intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same conic relaxation may admit a gap with eTRS. We show that the conic relaxation admits no gap for arbitrary M as long as the linear cuts are non-intersecting.
We then extend our result to a more general setting. We study an eTRS in which a quadratic function is minimized over a structured nonconvex feasible region: the unit ball with M linear cuts and R hollows. In the special case when m = 0 and r = 1, it is known that the eTRS has a tight polynomial-time solvable conic relaxation. We show that a certain conic relaxation is also tight for general R and M as long as the cuts and hollows satisfy some non-intersecting assumptions that generalize the previous paragraph.
Finally, intersecting the feasible region of TRS with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing approaches do not provide a concise conic relaxation. We investigate the use of conic relaxation for TTRS. Starting from the basic SDP relaxation of TTRS, which admits a gap, recent research has tightened the basic relaxation using valid second-order-cone (SOC) inequalities. For the special case of TTRS in dimension n=2, we fully characterize the remaining valid inequalities, which can be viewed as strengthened versions of the SOC inequalities just mentioned. We also demonstrate that these valid inequalities can be used computationally even when n > 2 to solve TTRS instances that were previously unsolved using techniques of conic relaxation.
48
ROJAS, JHONATAN EDWAR GARCIA. "NUMERICAL LIMIT ANALYSIS USING SEMIDEFINITE AND SECOND ORDER CONIC PROGRAMMING WITH APPLICATION IN STABILITY OF SHALLOW TUNNELS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2018. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=36904@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE EXCELENCIA ACADEMICA
Nesse trabalho é avaliada a solução numérica do colapso na frente de escavação em túneis rasos, através da teoria de análise limite numérico, usando o teorema do limite inferior, a partir da condição de equilíbrio para as condições plásticas, além de considerar o comportamento do material rígido perfeitamente plástico. O teorema de limite inferior implica em maximizar o fator multiplicador na carga atuante, por isso a análise limite se torna um problema de otimização, nele tem que se usar a programação matemática para ser resolvido. É avaliada a solução numérica tridimensional da análise limite através do método dos elementos finitos, usando malha de elementos hexaédricos de oito nós, a análise dos elementos finitos é feita com o próprio código gerado na linguagem de programação do MATLAB 2017.As metodologias de programação matemática empregadas são: programação cônica de segunda ordem e programação semidefinida. Antes deve-se adaptar os critérios de ruptura de Drucker Prager à programação cônica de segunda ordem e Mohr-Coulomb tridimensional à programação semidefinida. Para a otimização se usa o algoritmo comercial MOSEK Aps 7.1 baseado no método do ponto interior em grande escala, na linguagem do MATLAB 2017. Além disso, obteve-se o mecanismo de colapso através da propriedade da dualidade do problema de otimização, dualidade que é cumprida pelos teoremas de limite superior e inferior.
In this work the numerical solution of the collapse in the front of excavation in shallow tunnels is evaluated through the theory of numerical limit analysis, using the lower limit theorem, from the equilibrium condition for the plastic conditions, considering the behavior of the perfectly plastic rigid material. The lower limit theorem implies maximizing the multiplier factor in the acting load, so that the limit analysis becomes an optimization problem. The three-dimensional numerical solution of the limit analysis using the finite element method is evaluated using a mesh of eight-node hexahedral elements. The finite element analysis is done using the code generated in the MATLAB 2017 programming language. The mathematical programming methodologies used are: second order conic programming and semidefinite programming. The Drucker-Prager three-dimensional criteria should be adapted to the conic programming of the second order and Mohr-Coulomb three-dimensional to the semidefinite programming. For the optimization, the MOSEK Aps 7.1 commercial algorithm based on the large-scale interior point method is used in the MATLAB 2017 language. In addition, the collapse mechanism was obtained through the duality property of the optimization problem, duality that is fulfilled by the upper and lower limit theorems.
49
Khan, Adnan Umar. "Distributive time division multiplexed localization technique for WLANs." Thesis, De Montfort University, 2012. http://hdl.handle.net/2086/7102.
Full textAbstract:
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.
50
Evangelista, Tatiane da Silva. "Discriminação de estados quanticos via programação semidefinida." [s.n.], 2009. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306810.
Full textAbstract:
Orientadores: Carlile Campos Lavor, Wilson Ricardo Matos RabeloTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-13T05:05:06Z (GMT). No. of bitstreams: 1 Evangelista_TatianedaSilva_D.pdf: 1204224 bytes, checksum: 78ba86ca8ac235e2775ed6a048ccf353 (MD5) Previous issue date: 2009
Resumo: Neste trabalho, apresentamos um novo algoritmo para realizar a discriminação ótima de N estados quânticos puros não-ortogonais, que fornece o melhor conjunto de medidas POVM para o problema, através da extensão do espaço de Hilbert de N para 2N - 1 dimensões. O algoritmo é baseado na programação semidefinida e na solução de sistemas lineares. O algoritmo foi implementado em Matlab e apresentou bons resultados computacionais.
Abstract: In this work, we propose a new algorithm to perform the optimal discrimination of N non-orthogonal pure quantum states. This algorithm obtains the best set of POVM measurements for the problem, through the extension of the Hilbert space of N to 2N-1 dimensions. The algorithm is based on semidefinite programming and on the solution of linear systems. The algorithm was implemented in Matlab and presented good computational results.
Doutorado
Otimização
Doutor em Matemática Aplicada