• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 156
  • 14
  • 12
  • 12
  • 6
  • 1
  • 1
  • 1
  • Tagged with
  • 238
  • 238
  • 53
  • 45
  • 42
  • 40
  • 37
  • 32
  • 27
  • 26
  • 25
  • 25
  • 24
  • 21
  • 21
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
31

Online convex optimization: algorithms, learning, and duality / Otimização convexa online: algoritmos, aprendizado, e dualidade

Portella, Victor Sanches 03 May 2019 (has links)
Online Convex Optimization (OCO) is a field in the intersection of game theory, optimization, and machine learning which has been receiving increasing attention due to its recent applications to a wide range of topics such as complexity theory and graph sparsification. Besides the usually simple description and implementation of OCO algorithms, a lot of this recent success is due to a deepening of our understanding of the OCO setting and their algorithms by using cornerstone ideas from convex analysis and optimization such as the powerful results from convex duality theory. In this text we present a mostly self-contained introduction to the field of online convex optimization. We first describe the online learning and online convex optimization settings, proposing an alternative way to formalize both of them so we can make formal claims in a clear and unambiguous fashion while not cluttering the readers understanding. We then present an overview of the main concepts of convex analysis we use, with a focus on building intuition. With respect to algorithms for OCO, we first present and analyze the Adaptive Follow the Regularized Leader (AdaFTRL) together with an analysis which relies mainly on the duality between strongly convex and strongly smooth functions. We then describe the Adaptive Online Mirror Descent (AdaOMD) and the Adaptive Dual Averaging (AdaDA) algorithms and analyze both by writing them as special cases of the AdaFTRL algorithm. Additionally, we show simple sufficient conditions for Eager and Lazy Online Mirror Descent (the non-adaptive counter-parts of AdaOMD and AdaDA) to be equivalent. We also present the well-known AdaGrad and Online Newton Step algorithms as special cases of the AdaReg algorithm, proposed by Gupta, Koren, and Singer, which is itself a special case of the AdaOMD algorithm. We conclude by taking a bird\'s-eyes view of the connections shown throughout the text, forming a ``genealogy\'\' of OCO algorithms, and discuss some possible path for future research. / Otimização Convexa Online (OCO) é uma área na intersecção de teoria dos jogos, otimização e aprendizado de máquina que tem recebido maior atenção recentemente devido a suas recentes aplicações em uma grande gama de áreas como complexidade computacional e esparsificação de grafos. Além dos algoritmos de OCO usualmente terem descrições diretas e poderem ser implementados de forma relativamente simples, muito do recente sucesso da área foi possível graças a um melhor entendimento do cenário e dos algoritmos de OCO que se deu com uso de conhecidas ideias de análise e otimização convexa como a poderosa teoria de dualidade convexa. Nesse texto nós apresentamos uma introdução (em sua maioria auto-contida) à área de otimização convexa online. Primeiro, descrevemos os cenários de aprendizado online e de otimização convexa online, propondo uma forma alternativa de formalizar ambos os modelos de forma que conseguimos enunciar afirmações claras e formais de forma que não atrapalha o entendimento do leitor. Nós então apresentamos um resumo dos principais conceitos e resultados de análise convexa que usamos no texto com um foco em criar intuição sobre os mesmos. Com relação a algoritmos para OCO, nós começamos apresentando o algoritmo Adaptive Follow the Regularized Leader (AdaFTRL) e analisamos sua eficácia com um resultado sobre a dualidade de funções strongly convex e strongly smooth. Na sequência, descrevemos os algoritmos Adaptive Online Mirror Descent (AdaOMD) e Adaptive Dual Averaging (AdaDA), analisando a eficácia de cada um escrevendo eles como instâncias do algoritmo AdaFTRL. Além disso, nós mostramos condições simples para que as versões Eager e Lazy do Online Mirror Descent (que são as versões não adaptativas do AdaOMD e do AdaDA, respectivamente) sejam equivalentes. Também apresentamos os algoritmos AdaGrad e Online Newton Step, bem conhecidos na literatura sobre OCO, como casos especiais do algoritmo AdaReg, esse último um algoritmo proposto por Gupta, Koren, and Singer, que, por sua vez, é um caso especial do algoritmo AdaOMD. Nós concluímos o texto com uma visão global das conexões entre os algoritmos que mostramos durante o texto, formando uma \"genealogia\" de algoritmos para OCO, além de discutirmos possíveis direções futuras de pesquisa.
32

New insights into conjugate duality

Grad, Sorin - Mihai 19 July 2006 (has links) (PDF)
With this thesis we bring some new results and improve some existing ones in conjugate duality and some of the areas it is applied in. First we recall the way Lagrange, Fenchel and Fenchel - Lagrange dual problems to a given primal optimization problem can be obtained via perturbations and we present some connections between them. For the Fenchel - Lagrange dual problem we prove strong duality under more general conditions than known so far, while for the Fenchel duality we show that the convexity assumptions on the functions involved can be weakened without altering the conclusion. In order to prove the latter we prove also that some formulae concerning conjugate functions given so far only for convex functions hold also for almost convex, respectively nearly convex functions. After proving that the generalized geometric dual problem can be obtained via perturbations, we show that the geometric duality is a special case of the Fenchel - Lagrange duality and the strong duality can be obtained under weaker conditions than stated in the existing literature. For various problems treated in the literature via geometric duality we show that Fenchel - Lagrange duality is easier to apply, bringing moreover strong duality and optimality conditions under weaker assumptions. The results presented so far are applied also in convex composite optimization and entropy optimization. For the composed convex cone - constrained optimization problem we give strong duality and the related optimality conditions, then we apply these when showing that the formula of the conjugate of the precomposition with a proper convex K - increasing function of a K - convex function on some n - dimensional non - empty convex set X, where K is a k - dimensional non - empty closed convex cone, holds under weaker conditions than known so far. Another field were we apply these results is vector optimization, where we provide a general duality framework based on a more general scalarization that includes as special cases and improves some previous results in the literature. Concerning entropy optimization, we treat first via duality a problem having an entropy - like objective function, from which arise as special cases some problems found in the literature on entropy optimization. Finally, an application of entropy optimization into text classification is presented.
33

A Convex Decomposition Perspective on Dynamic Bandwidth Allocation and Applications

Morell Pérez, Antoni 23 September 2008 (has links)
Tradicionalment, les tècniques d'accés múltiple en sistemes de comunicacions multi-usuari han estat desenvolupades o bé orientades a la connexió o bé orientades al tràfic. En el primer cas, l'objectiu és establir tants canals ortogonals com sigui possible per tal d'assignar-los als usuaris. Aquesta idea va motivar el disseny de les estratègies més conegudes, com són FDMA, TDMA i CDMA. Per altra banda, però, els mètodes d'accés aleatori que s'iniciaren amb el conegut ALOHA pretenen compartir estadísticament un mateix medi de comunicació aprofitant la necessitat de transmetre la informació a ràfegues que s'origina en les xarxes de dades. Així, molts dels actuals sistemes es poden encabir dins d'aquest esquema si a més a més, tenim en compte combinacions d'aquestes. No obstant, sistemes moderns com el DVB-RCS en l'entorn de comunicacions digitals per satèl·lit o el WiMAX en l'accés terrestre de banda ampla implementen mecanismes de petició i assignació de recursos, els quals requereixen una gestió dinàmica d'aquests en el sistema (és el que s'anomena distribució dinàmica de l'amplada de banda en un sentit ampli).L'anterior concepte inclou múltiples variables, configuracions i protocols tant de capa física com de capa d'enllaç. En aquesta tesi s'exploren en primer lloc les bases matemàtiques que permeten coordinar les diferents capes de la divisió OSI dels sistemes i els distints nodes dins la xarxa. Ens referim a les tècniques de descomposició focalitzades en problemes d'optimització convexa, els quals han aportat, durant els últims anys, solucions elegants a molts problemes dins dels camps del processament del senyal i les comunicacions. Revisarem els esquemes coneguts i proposarem una nova metodologia. Acte seguit, es comparen les diferents possibilitats de descomposició, cadascuna de les quals implica diferents maneres d'establir la senyalització. A la pràctica, són aquestes diverses opcions de descomposició les que infereixen les diferents interaccions entre capes o els protocols de control entre elements de la xarxa. Els resultats en quant a nombre d'iteracions requerides per a convergir a la solució òptima són favorables al nou mètode proposat, la qual cosa obra noves línies d'investigació.Finalment, es contribueix també amb dos exemples d'aplicació, en DVB-RCS i en WiMAX. Formulem el problema de gestió de recursos resultant de l'accés múltiple dissenyat per cadascun dels sistemes com un problema de maximització d'utilitat de xarxa (conegut com a NUM en la bibliografia) i el solucionarem aplicant les tècniques anteriors. L'objectiu serà garantir l'equitativitat entre els usuaris i preservar, al mateix temps, la seva qualitat de servei. Per aconseguir-ho, cal seleccionar funcions d'utilitat adequades que permetin balancejar l'assignació de recursos cap als serveis més prioritaris. Mostrarem que en els escenaris considerats, l'ús del mètode proposat comporta guanys significatius ja que requereix menys iteracions en el procés (i per tant, menys senyalització) o bé menys temps de càlcul en un enfoc centralitzat (que es tradueix en la possibilitat d'incloure més usuaris). També es mostren els avantatges de considerar interaccions entre capes, ja que es poden ajustar els paràmetres de capa física per tal d'afavorir els tràfics més prioritaris o bé extreure els requeriments de servei de valors típicament disponibles en capes superiors.En general, la implementació eficient de tècniques de gestió dinàmica de recursos treballant en l'accés múltiple dels sistemes pot aportar guanys significatius però implica establir una bona coordinació entre capes i elements de xarxa. L'eina matemàtica que ho possibilita són les tècniques de descomposició. Cada nou escenari i sistema introdueix un nou repte d'optimització i la capacitat que tinguem de coordinar totes les variables del sistema cap al punt òptim en determinarà el rendiment global. / Traditionally, multiple access schemes in multi-user communications systems have been designed either connection-oriented or traffic-oriented. In the first ones, the goal was to provide as many orthogonal channels as possible, each one serving a different connection. That is the motivation of the so-called FDMA, TDMA and CDMA solutions. On the other hand, random access techniques, which started with the so-called ALOHA protocol, aim to statistically multiplex a shared communication medium by means of exploiting the random and bursty nature of transmission needs in data networks. Most of the multiple access solutions can be interpreted according to that classification or as a combination of those approaches. Notwithstanding, modern systems, such as the digital satellite communications standard DVB-RCS or the broadband wireless access WiMAX, have implemented a multiple access technique where users request for transmission opportunities and receive grants from the network, therefore requiring dynamic bandwidth allocation techniques. The concept of dynamic bandwidth allocation is wide and involves a number of physical and link layer variables, configurations and protocols. In this Ph.D. dissertation we first explore the mathematical foundation that is required to coordinate the distinct layers of the OSI protocol stack and the distinct nodes within the network. We talk about decomposition techniques focused on the resolution of convex programs, which have elegantly solved many problems in the signal processing and communications fields during the last years. Known schemes are reviewed and a novel decomposition methodology is proposed. Thereafter, we compare the four resulting strategies, each one having its own particular signalling needs, which results in distinct cross-layer interactions or signalling protocols at implementation level. The results in terms of iterations required to converge are favourable to the proposed method, thus opening a new line of research.Finally, we contribute with two practical application examples in the DVB-RCS and WiMAX systems. First, we formulate the dynamic bandwidth allocation problem that is derived from the multiple access schemes of both systems. Thereafter, the resulting Network Utility Maximization (NUM) based problem is solved by means of the previous decomposition mechanisms. The goal is to guarantee fairness among the users at the same time that Quality of Service (QoS) is preserved. In order to achieve that, we choose adequate utility functions that allow to balance the allocation towards the most priority traffic flows under a common fairness framework. We show that in the scenarios considered, the novel proposed coupled-decomposition method reports significant gains since it reduces significantly the iterations required (less iterations implies less signalling) or it reduces the time needed to obtain the optimal allocation when it is centrally computed (more users can be managed). We further show the advantages of cross-layer interactions with the physical and upper layers, which allow to benefit from more favourable adjustments of the transmission parameters and to consider the QoS requirements at upper layers. In general, an efficient implementation of dynamic bandwidth allocation techniques in Demand Assignment Multiple Access (DAMA) schemes may report significant performance gains but it requires proper coordination among system layers and network nodes, which is attained thanks to decomposition techniques. Each new scenario and system adds another optimization challenge and, as far as we are able to coordinate all the variables in the system towards that optimal point, the highest will be the revenue.
34

Distance Measurement-Based Cooperative Source Localization: A Convex Range-Free Approach

Kiraz, Fatma January 2013 (has links)
One of the most essential objectives in WSNs is to determine the spatial coordinates of a source or a sensor node having information. In this study, the problem of range measurement-based localization of a signal source or a sensor is revisited. The main challenge of the problem results from the non-convexity associated with range measurements calculated using the distances from the set of nodes with known positions to a xed sen- sor node. Such measurements corresponding to certain distances are non-convex in two and three dimensions. Attempts recently proposed in the literature to eliminate the non- convexity approach the problem as a non-convex geometric minimization problem, using techniques to handle the non-convexity. This study proposes a new fuzzy range-free sensor localization method. The method suggests using some notions of Euclidean geometry to convert the problem into a convex geometric problem. The convex equivalent problem is built using convex fuzzy sets, thus avoiding multiple stable local minima issues, then a gradient based localization algorithm is chosen to solve the problem. Next, the proposed algorithm is simulated considering various scenarios, including the number of available source nodes, fuzzi cation level, and area coverage. The results are compared with an algorithm having similar fuzzy logic settings. Also, the behaviour of both algorithms with noisy measurements are discussed. Finally, future extensions of the algorithm are suggested, along with some guidelines.
35

New Convex Relaxations for the Maximum Cut and VLSI Layout Problems

Ferreira Fialho dos Anjos, Miguel Nuno January 2001 (has links)
It is well known that many of the optimization problems which arise in applications are <I>hard</I>, which usually means that they are NP-hard. Hence much research has been devoted to finding <I>good</I> relaxations for these hard problems. Usually a <I>good</I> relaxation is one which can be solved (either exactly or within a prescribed numerical tolerance) in polynomial-time. Nesterov and Nemirovskii showed that by this criterion, many convex optimization problems are good relaxations. This thesis presents new convex relaxations for two such hard problems, namely the Maximum-Cut (Max-Cut) problem and the VLSI (Very Large Scale Integration of electronic circuits) layout problem. We derive and study the properties of two new strengthened semidefinite programming relaxations for the Max-Cut problem. Our theoretical results hold for every instance of Max-Cut; in particular, we make no assumptions about the edge weights. The first relaxation provides a strengthening of the well-known Goemans-Williamson relaxation, and the second relaxation is a further tightening of the first. We prove that the tighter relaxation automatically enforces the well-known triangle inequalities, and in fact is stronger than the simple addition of these inequalities to the Goemans-Williamson relaxation. We further prove that the tighter relaxation fully characterizes some low dimensional faces of the cut polytope via the rank of its feasible matrices. We also address some practical issues arising in the solution of these relaxations and present numerical results showing the remarkably good bounds computed by the tighter relaxation. For the VLSI layout problem, we derive a new relaxation by extending the <I>target distance</I> concept recently introduced by Etawil and Vannelli. The resulting AR (Attractor-Repeller) model improves on the NLT (Non-linear optimization Layout Technique) method of van Camp et al. by efficiently finding a good initial point for the NLT solver. Because the AR model is not a convex optimization problem, we isolate the source of the non-convexity and thereby derive a convex version of the model. This derivation leads to the definition of certain generalized target distances with an interesting practical interpretation. Finally, we present numerical results that demonstrate the potential of the AR model.
36

A Branch-and-Cut Algorithm based on Semidefinite Programming for the Minimum k-Partition Problem

Ghaddar, Bissan January 2007 (has links)
The minimum k-partition (MkP) problem is a well-known optimization problem encountered in various applications most notably in telecommunication and physics. Formulated in the early 1990s by Chopra and Rao, the MkP problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in different partitions. In this thesis, we design and implement a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. We describe and study the properties of two relaxations of the MkP problem, the linear programming and the semidefinite programming relaxations. We then derive a new strengthened relaxation based on semidefinite programming. This new relaxation provides tighter bounds compared to the other two discussed relaxations but suffers in term of computational time. We further devise an iterative clustering heuristic (ICH), a novel heuristic that finds feasible solution to the MkP problem and we compare it to the hyperplane rounding techniques of Goemans and Williamson and Frieze and Jerrum for k=2 and for k=3 respectively. Our computational results support the conclusion that ICH provides a better feasible solution for the MkP. Furthermore, unlike the hyperplane rounding, ICH remains very effective in the presence of negative edge weights. Next we describe in detail the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) to find optimal solution for the MkP problem. The ICH heuristic is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-cut tree. Finally, we present computational results for the SBC algorithm on several classes of test instances with k=3, 5, and 7. Complete graphs with up to 60 vertices and sparse graphs with up to 100 vertices arising from a physics application were considered.
37

Distance Measurement-Based Cooperative Source Localization: A Convex Range-Free Approach

Kiraz, Fatma January 2013 (has links)
One of the most essential objectives in WSNs is to determine the spatial coordinates of a source or a sensor node having information. In this study, the problem of range measurement-based localization of a signal source or a sensor is revisited. The main challenge of the problem results from the non-convexity associated with range measurements calculated using the distances from the set of nodes with known positions to a xed sen- sor node. Such measurements corresponding to certain distances are non-convex in two and three dimensions. Attempts recently proposed in the literature to eliminate the non- convexity approach the problem as a non-convex geometric minimization problem, using techniques to handle the non-convexity. This study proposes a new fuzzy range-free sensor localization method. The method suggests using some notions of Euclidean geometry to convert the problem into a convex geometric problem. The convex equivalent problem is built using convex fuzzy sets, thus avoiding multiple stable local minima issues, then a gradient based localization algorithm is chosen to solve the problem. Next, the proposed algorithm is simulated considering various scenarios, including the number of available source nodes, fuzzi cation level, and area coverage. The results are compared with an algorithm having similar fuzzy logic settings. Also, the behaviour of both algorithms with noisy measurements are discussed. Finally, future extensions of the algorithm are suggested, along with some guidelines.
38

Structured sparsity-inducing norms : statistical and algorithmic properties with applications to neuroimaging

Jenatton, Rodolphe 24 November 2011 (has links) (PDF)
Numerous fields of applied sciences and industries have been recently witnessing a process of digitisation. This trend has come with an increase in the amount digital data whose processing becomes a challenging task. In this context, parsimony, also known as sparsity, has emerged as a key concept in machine learning and signal processing. It is indeed appealing to exploit data only via a reduced number of parameters. This thesis focuses on a particular and more recent form of sparsity, referred to as structured sparsity. As its name indicates, we shall consider situations where we are not only interested in sparsity, but where some structural prior knowledge is also available. The goal of this thesis is to analyze the concept of structured sparsity, based on statistical, algorithmic and applied considerations. To begin with, we introduce a family of structured sparsity-inducing norms whose statistical aspects are closely studied. In particular, we show what type of prior knowledge they correspond to. We then turn to sparse structured dictionary learning, where we use the previous norms within the framework of matrix factorization. From an optimization viewpoint, we derive several efficient and scalable algorithmic tools, such as working-set strategies and proximal-gradient techniques. With these methods in place, we illustrate on numerous real-world applications from various fields, when and why structured sparsity is useful. This includes, for instance, restoration tasks in image processing, the modelling of text documents as hierarchy of topics, the inter-subject prediction of sizes of objects from fMRI signals, and background-subtraction problems in computer vision.
39

Sparse coding for machine learning, image processing and computer vision

Mairal, Julien 30 November 2010 (has links) (PDF)
We study in this thesis a particular machine learning approach to represent signals that that consists of modelling data as linear combinations of a few elements from a learned dictionary. It can be viewed as an extension of the classical wavelet framework, whose goal is to design such dictionaries (often orthonormal basis) that are adapted to natural signals. An important success of dictionary learning methods has been their ability to model natural image patches and the performance of image denoising algorithms that it has yielded. We address several open questions related to this framework: How to efficiently optimize the dictionary? How can the model be enriched by adding a structure to the dictionary? Can current image processing tools based on this method be further improved? How should one learn the dictionary when it is used for a different task than signal reconstruction? How can it be used for solving computer vision problems? We answer these questions with a multidisciplinarity approach, using tools from statistical machine learning, convex and stochastic optimization, image and signal processing, computer vision, but also optimization on graphs.
40

Modélisation du langage à l'aide de pénalités structurées

Nelakanti, Anil Kumar 11 February 2014 (has links) (PDF)
Modeling natural language is among fundamental challenges of artificial intelligence and the design of interactive machines, with applications spanning across various domains, such as dialogue systems, text generation and machine translation. We propose a discriminatively trained log-linear model to learn the distribution of words following a given context. Due to data sparsity, it is necessary to appropriately regularize the model using a penalty term. We design a penalty term that properly encodes the structure of the feature space to avoid overfitting and improve generalization while appropriately capturing long range dependencies. Some nice properties of specific structured penalties can be used to reduce the number of parameters required to encode the model. The outcome is an efficient model that suitably captures long dependencies in language without a significant increase in time or space requirements. In a log-linear model, both training and testing become increasingly expensive with growing number of classes. The number of classes in a language model is the size of the vocabulary which is typically very large. A common trick is to cluster classes and apply the model in two-steps; the first step picks the most probable cluster and the second picks the most probable word from the chosen cluster. This idea can be generalized to a hierarchy of larger depth with multiple levels of clustering. However, the performance of the resulting hierarchical classifier depends on the suitability of the clustering to the problem. We study different strategies to build the hierarchy of categories from their observations.

Page generated in 0.2128 seconds