Orientadores: Carlile Campos Lavor, Wilson Ricardo Matos Rabelo / Tese (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

[pt] A Programação Quadrática Binária Irrestrita (UBQP) é amplamente estudada. Trata-se de uma ferramenta de modelagem poderosa, mas otimizar de um problema NP-difícil. Neste trabalho uma nova abordagem é apresentada, que pode ser usada para construir um algoritmo exato. Além disso, a ideia básica que fundamenta o trabalho pode ser usado em um espectro ainda mais amplo de problemas. O algoritmo exato derivado do novo método é altamente paralelizável, o que é uma característica desejável nos dias de hoje em que cloud computing já é uma realidade. Para instâncias razoavelmente grandes do UBQP, o novo método pode paralelizar a centenas, ou até milhares, de núcleos com facilidade, com um aumento de desempenho quase linear. / [en] Unconstrained Binary Quadratic Programming (UBQP) is widely studied. It is a powerful modeling tool and its associate problem is NP-hard. In this work a new approach is introduced, which can be used to build an exact algorithm. Also, the fundamental idea behind it can be used in an even wider family of problems. This exact algorithm derived from the new method is highly parallelizable, which is a desired feature nowadays, when the cloud computing is a reality. For reasonably large instances of UBQP, the new method can parallelize to hundreds, or even thousands, of cores easily, with a near-linear speedup.

O número de contato do Rn (em inglês, kissing number) é o maior número de esferas de raio unitário e interiores dois-a-dois disjuntos que podem tocar simultaneamente uma esfera de raio unitário central. Nesta dissertação estudamos métodos que limitam o tamanho de tais configurações através de técnicas de otimização, como dualidade e programação semidefinida. O principal resultado obtido foi o cálculo de melhores limitantes para o número de contato nas dimensões 9 a 23; o que foi possível graças à exploração de simetrias dos polinômios presentes no limitante proposto por Bachoc e Vallentin (2008), levando à consideração de programas semidefinidos menores. Por fim, o limitante estudado é estendido para uma classe mais geral de problemas. / The kissing number of Rn is the maximum number of pairwise-nonoverlapping unit spheres that can simultaneously touch a central unit sphere. In this thesis we study methods to bound from above the size of such configurations using optimization techniques, like duality and semidefinite programming. The main result achieved is the computation of better bounds for the kissing number in dimensions 9 to 23; a result possible due to the exploitation of symmetries in the polynomials present in the bound proposed by Bachoc and Vallentin (2008), leading to the consideration of smaller semidefinite programs. Finally, the studied bound is extended to a bigger class of problems.

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.

Tsirelson's bound is the upper bound for a Bell inequality which is valid for all quantum mechanical systems. We discuss why Tsirelson's bound was developed by looking at some historical arguments in quantum physics, such as the Einstein-Podolsky-Rosen (EPR) paradox, an argument for the quantum mechanical description of physical reality being incomplete, and local hidden variables. We present the counterargument to those theories, Bell's inequality, which later expanded to include any inequality that a local system fulfills, but that an entangled quantum system can violate. We present the proof of two specific Bell inequalities: the Clauser-Horne-Shimony-Holt (CHSH) inequality and the I3322 inequality. Then the Tsirelson's bound for the CHSH inequality is proven with a simple system of two entangled spin-1/2 particles and with a general argument that is valid for all entangled systems. We give the upper quantum bound for the generalized CHSH inequality, which describes the situation that we have more than two measurement options, by using semidefinite programming. We prove the Tsirelson's bound for the I3322 inequality by using maximally entangled systems and semidefinite programming. Finally, we discuss the upper bounds that are obtained from these different methods. / Tsirelson's gräns är den övre gränsen till en Bell olikhet som är giltig för alla kvantmekaniska system. Vi diskuterar varför Tsirelson's gräns togs fram genom att titta på histroiska argument i kvantfysik, så som Einstein-Podolsky-Rosen (EPR) paradoxen, ett argument som säger att den kvantmekaniska beskrivningen av den fysikaliska verkligheten är offulständig, och lokala gömda variabler. Vi presenterar motargumentet till dessa teorier, Bell's olikheter, som senare generaliserades för att betyda alla olikheter som lokala system uppfyller, men som ett system i kvantsammanflättning kan bryta. Vi presenterar beviset för två specifika Bell olikheter: CHSH olikheten och I3322 olikheten. Sedan bevisas Tsirelson's gräns för CHSH olikheten med ett enkelt system av två sammanflättade spin-1/2 partiklar och ett generellt argument som stämmer för alla sammanflättade system. Vi ger den övre kvant gränsen för den generaliserade Clauser-Horne-Shimony-Holt (CHSH) olikheten, som beskriver situationen då vi har flera valmöjligheter för mätningar, genom att använda semidefinit programmering. Vi bevisar Tsirelson's gräns för I3322 olikheten genom att använda maximalt sammanflättade system och semidefinit programmering. Till slut diskuterar vi de övre gränserna som har erhållits ifrån de olika metoderna.

Decreasing gas prices and the pressing need for fast-responding electric power generators are currently transforming natural gas networks. The intermittent operation of gas-fired plants to balance wind generation introduces spatiotemporal fluctuations of increasing gas demand. At the heart of modeling, monitoring, and control of gas networks is a set of nonlinear equations relating nodal gas injections and pressures to flows over pipelines. Given gas demands at all points of the network, the gas flow task aims at finding the rest of the physical quantities. For a tree network, the problem enjoys a closed-form solution; yet solving the equations for practical meshed networks is non-trivial. This problem is posed here as a feasibility problem involving quadratic equalities and inequalities, and is further relaxed to a convex semidefinite program (SDP) minimization. Drawing parallels to the power flow problem, the relaxation is shown to be exact if the cost function is judiciously designed using a representative set of network states. Numerical tests on a Belgian gas network corroborate the superiority of the novel method in recovering the actual gas network state over a Newton-Raphson solver. This thesis also considers the coupled infrastructures of natural gas and electric power systems. The gas and electric networks are coupled through gas-fired generators, which serve as shoulder and peaking plants for the electric power system. The optimal dispatch of coupled natural gas and electric power systems is posed as a relaxed convex minimization problem, which is solved using the feasible point pursuit (FPP) algorithm. For a decentralized solution, the alternating direction method of multipliers (ADMM) is used in collaboration with the FPP. Numerical experiments conducted on a Belgian gas network connected to the IEEE 14 bus benchmark system corroborate significant enhancements on computational efficiency compared with the centralized FPP-based approach. / Master of Science

<p>We start by slightly modifying the generic framework for solving online covering and packing linear programs (LP) proposed in the seminal work of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) to obtain efficient implementations in settings in which one has access to a separation oracle.</p> <p><br></p> <p>We then apply the generic framework to several online network connectivity problems with LP formulations, namely pairwise spanners and directed Steiner forests. Our results are comparable to the previous state-of-the-art results for these problems in the offline setting.</p> <p><br></p> <p>Further, we extend the generic frameworks to online optimization problems enhanced with <strong>machine-learning predictions</strong>. In particular, we present <strong>learning-augmented</strong> algorithms for online covering LPs and semidefinite programs (SDP), which outperform any optimal online algorithms when the prediction is accurate while maintaining reasonable guarantees when the prediction is misleading. Specifically, we obtain general online learning-augmented algorithms for covering LPs with fractional advice and general constraints and initiate the study of learning-augmented algorithms for covering SDPs.</p>

MAX−CUT is one of the well-studied NP-hard combinatorial optimization problems. It can be formulated as an Integer Quadratic Programming problem and admits a simple relaxation obtained by replacing the integer “spin” variables xi by unitary vectors v⃗ i. The Goemans–Williamson rounding algorithm assigns the solution vectors of the relaxed quadratic program to a corresponding integer spin depending on the sign of the scalar product v⃗ i⋅r⃗ with a random vector r⃗ . Here, we investigate whether better graph cuts can be obtained by instead using a more sophisticated clustering algorithm. We answer this question affirmatively. Different initializations of k-means and k-medoids clustering produce better cuts for the graph instances of the most well known benchmark for MAX−CUT. In particular, we found a strong correlation of cluster quality and cut weights during the evolution of the clustering algorithms. Finally, since in general the maximal cut weight of a graph is not known beforehand, we derived instance-specific lower bounds for the approximation ratio, which give information of how close a solution is to the global optima for a particular instance. For the graphs in our benchmark, the instance specific lower bounds significantly exceed the Goemans–Williamson guarantee.

[pt] Diversos problemas em engenharia, aprendizado de máquina e economia podem ser resolvidos através de Programação Semidefinida (SDP). Potenciais aplicações podem ser encontradas em telecomunicações, fluxo de potência e teoria dos jogos. Além disso, como SDP é uma subclasse de otimização convexa, temos uma série de propriedades e garantias que fazem da SDP uma tecnologia muito poderosa. Entretanto, dentre as diferentes subclasses de otimização convexa, SDP ainda permanece como uma das mais desafiadoras. Instancias de larga escala ainda não podem ser resolvidas pelos atuais softwares disponíveis. Nesse sentido, esta tese porpõe um novo algoritmo para resolver problemas de SDP. A principal contribuição deste novo algoritmo é explorar a propriedade de posto baixo presente em diversas instancias. A convergência desta nova metodologia é provada ao mostrar que o algoritmo proposto é um caso particular do Approximate Proximal Point Algorithm. Adicionalmente, as variáveis ótimas duais são disponibilizadas como uma consequência do algoritmo proposto. Além disso, disponibilizamos um software para resolver problemas de SDP, chamado ProxSDP. Três estudos de caso são utilizados para avaliar a performance do algoritmo proposto. / [en] Many problems of interest can be solved by means of Semidefinite Programming (SDP). The potential applications range from telecommunications, electrical power systems, game theory and many more fields. Additionally, the fact that SDP is a subclass of convex optimization brings a set of theoretical guarantees that makes SDP very appealing. However, among all sub-classes of convex optimization, SDP remains one of the most challenging in practice. State-of-the-art semidefinite programming solvers still do not efficiently solve large scale instances. In this regard, this thesis proposes a novel algorithm for solving SDP problems. The main contribution of this novel algorithm is to achieve a substantial speedup by exploiting the low-rank property inherent to several SDP problems. The convergence of the new methodology is proved by showing that the novel algorithm reduces to a particular case of the Approximated Proximal Point Algorithm. Along with the theoretical contributions, an open source numerical solver, called ProxSDP, is made available with this work. The performance of ProxSDP in comparison to state-of-the-art SDP solvers is evaluated on three case studies.

Este trabalho é focado num problema clássico das Ciências e Engenharia, que consiste em cobrir um objeto por esferas de mesmo raio, a ser minimizado. A abordagem prática usual conta com sérias desvantagens. Logo, faz-se necessário trabalhar com isto de forma diferenciada. A técnica proposta aqui envolve a utilização de resultados célebres da geometria algébrica real, que tem como peça central o positivstellensatz de Stengle e, fazendo a devida relação entre esses resultados e otimização com restrições envolvendo representações naturais por somas de quadrados, é possível reduzir o problema original a um de programação semidefinida não linear. Mas, por contar com particularidades que favorecem a aplicação do paradigma de restauração inexata, esta foi a técnica utilizada para resolvê-lo. A versatilidade da técnica e a possibilidade de generalização direta dos objetos envolvidos destacam-se como grandes vantagens desta abordagem, além da visão algébrica inovadora do problema. / This work is focused on a classic problem from Engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to nd a dierent way. Here, we explore some renowned results from real algebraic geometry, which has Stengle\'s positivstellensatz as one of its central pieces, and SOS optimization. Once the proper link is made, the original problem can be reduced to a nonlinear semidenite programming one, which has peculiarities that favours the application of an inexact restoration paradigm. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects.