Academic literature on the topic 'SDP optimization'

We propose two multigrid approaches for the global optimization of polynomial op- timization problems. In our first contribution we consider problems that arise from the discretization of infinite dimensional optimization problems, such as PDE optimiza- tion problems, boundary value problems and some global optimization applications. In many of these applications, the level of discretization can be used to obtain a hierarchy of optimization models that captures the underlying infinite dimensional problem at different degrees of fidelity. This approach, inspired by multigrid methods, has been successfully used for decades to solve large systems of linear equations. However, it has not been adapted to SDP relaxations of polynomial optimization problems. The main difficulty is that the geometric information between grids is lost when the original problem is approximated via an SDP relaxation. Despite the loss of geometric infor- mation, we show how a multigrid approach can be applied by developing prolongation operators to relate the primal and dual variables of the SDP relaxation between lower and higher levels in the hierarchy of discretizations. We develop sufficient conditions for the operators to be useful in applications. Our conditions are easy to verify in prac- tice, and we discuss how they can be used to reduce the complexity of infeasible interior iv point methods. Following the same reasoning, the second approach does not assume any particular structure of the underlying polynomial problem, but instead considers the hierarchy of sparse SDP relaxations that can be obtained for any unconstrained polynomial optimizations problem with structured sparsity. Prolongation operators are defined for this type of hierarchy, and theoretical results that show their usefulness are proved. Our preliminary results highlight two promising advantages of following a multigrid approach in contrast with a pure interior point method: the percentage of problems that can be solved to a high accuracy is much higher, and the time necessary to find a solution can be reduced significantly, especially for large scale problems.

Dans la première partie de cette thèse, nous utilisons l'algorithme d'Expectation-Maximization (EM) pour estimer en aveugle les amplitudes des coefficients du canal, et nous comparons les résultats avec la borne de Cramer-Rao. De plus, nous développons une version relaxe de la détection MV, à faible complexité et montrons que ses performances surpassent celles du détecteur d'erreur quadratique moyenne minimale (EQMM). La deuxième partie de cette thèse concerne le problème de la détection dans les systèmes MEMS. Nous proposerons un algorithme de détection MV utilisant une approche géométrique discrète. L'avantage de cet algorithme est sa complexité polynomiale, quel que soit le rapport signal-bruit, et le fait qu'aucune méthode heuristique n'est employé. Nous obtenons une méthode MV approches a faible complexité par l'approche de la programmation en cone du deuxième ordre. Nous établissons également des bornes sur la performance de la méthode de programmation semi-definie. Jusqu'ici, la connaissance de l'état du canal était considéré comme parfaite. Nous avons également explore le problème de la détection sans connaissance du canal au récepteur. Le résultat est un algorithme d'estimation conjointe du canal et des symboles, base sur l'algorithme EM, et la théorie du champ dynamique moyen (CDM, ou mean field theory, méthode largement utilise en physique statistique) pour en réduire la complexité L'approche du CDM est utilise pour approximer les probabilité {\em a posteriori} d'interférence d'access multiple. Les performances de la méthode propose sont compares a celles du détecteur MV exact pour un canal connu<br>We focus on low complexity maximum likelihood detection. The em algorithm is a broadly applicable approach to the iterative computation of ml estimates, useful in variety of incomplete-data problems, where algorithms such as the newton-raphson method may turn out to be more complicated. In the first part of the thesis, we use em algorithm to estimate the channel amplitudes blindly and compare the results with the cramer-rao bound (crb). The second part of the thesis concerns the detection problem in mimo systems. We are able to device an algorithm for approximate ml detection using a discrete geometric approach. The advantage of this algorithm is that its performance is polynomial irrespective of the snr and no heuristic is employed in our algorithm. An alternative way to ml problem is to devise low complexity algorithms whose performance is close to the exact ml. This can be done using semidefinite programming (sdp) approach. The computational complexity of the sdp approach is comparable to the average complexity of the sphere decoder but still it is quite complicated for large systems. We obtained low complexity (by reducing the number of the variables) approximate ml by second order cone programming (socp) approach. In the above discussion the channel state information is assumed to be known at the receiver. We further looked into the problem of detection with no channel knowledge at the receiver. The result was the joint channel-symbol estimation. We obtained the results of joint channel-symbol estimation using em algorithm and in order to reduce the complexity of the resulting em algorithm, we used mean field theory (mft) approach