To see the other types of publications on this topic, follow the link: Linear Algorithms.
Dissertations / Theses on the topic 'Linear Algorithms'
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 'Linear Algorithms.'
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
Wilbanks, John W. (John Winston). "Linear Unification." Thesis, University of North Texas, 1989. https://digital.library.unt.edu/ark:/67531/metadc500971/.
Full textAbstract:
Efficient unification is considered within the context of logic programming. Unification is explained in terms of equivalence classes made up of terms, where there is a constraint that no equivalence class may contain more than one function term. It is demonstrated that several well-known "efficient" but nonlinear unification algorithms continually maintain the said constraint as a consequence of their choice of data structure for representing equivalence classes. The linearity of the Paterson-Wegman unification algorithm is shown largely to be a consequence of its use of unbounded lists of pointers for representing equivalences between terms, which allows it to avoid the nonlinearity of "union-find".
2
Rettes, Julio Alberto Sibaja. "Robust algorithms for linear regression and locally linear embedding." reponame:Repositório Institucional da UFC, 2017. http://www.repositorio.ufc.br/handle/riufc/22445.
Full textAbstract:
RETTES, Julio Alberto Sibaja. Robust algorithms for linear regression and locally linear embedding. 2017. 105 f. Dissertação (Mestrado em Ciência da Computação)- Universidade Federal do Ceará, Fortaleza, 2017.Submitted by Weslayne Nunes de Sales (weslaynesales@ufc.br) on 2017-03-30T13:15:27Z No. of bitstreams: 1 2017_dis_rettesjas.pdf: 3569500 bytes, checksum: 46cedc2d9f96d0f58bcdfe3e0d975d78 (MD5)
Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-04-04T11:10:44Z (GMT) No. of bitstreams: 1 2017_dis_rettesjas.pdf: 3569500 bytes, checksum: 46cedc2d9f96d0f58bcdfe3e0d975d78 (MD5)
Made available in DSpace on 2017-04-04T11:10:44Z (GMT). No. of bitstreams: 1 2017_dis_rettesjas.pdf: 3569500 bytes, checksum: 46cedc2d9f96d0f58bcdfe3e0d975d78 (MD5) Previous issue date: 2017
Nowadays a very large quantity of data is flowing around our digital society. There is a growing interest in converting this large amount of data into valuable and useful information. Machine learning plays an essential role in the transformation of data into knowledge. However, the probability of outliers inside the data is too high to marginalize the importance of robust algorithms. To understand that, various models of outliers are studied. In this work, several robust estimators within the generalized linear model for regression framework are discussed and analyzed: namely, the M-Estimator, the S-Estimator, the MM-Estimator, the RANSAC and the Theil-Sen estimator. This choice is motivated by the necessity of examining algorithms with different working principles. In particular, the M-, S-, MM-Estimator are based on a modification of the least squares criterion, whereas the RANSAC is based on finding the smallest subset of points that guarantees a predefined model accuracy. The Theil Sen, on the other hand, uses the median of least square models to estimate. The performance of the estimators under a wide range of experimental conditions is compared and analyzed. In addition to the linear regression problem, the dimensionality reduction problem is considered. More specifically, the locally linear embedding, the principal component analysis and some robust approaches of them are treated. Motivated by giving some robustness to the LLE algorithm, the RALLE algorithm is proposed. Its main idea is to use different sizes of neighborhoods to construct the weights of the points; to achieve this, the RAPCA is executed in each set of neighbors and the risky points are discarded from the corresponding neighborhood. The performance of the LLE, the RLLE and the RALLE over some datasets is evaluated.
Na atualidade um grande volume de dados é produzido na nossa sociedade digital. Existe um crescente interesse em converter esses dados em informação útil e o aprendizado de máquinas tem um papel central nessa transformação de dados em conhecimento. Por outro lado, a probabilidade dos dados conterem outliers é muito alta para ignorar a importância dos algoritmos robustos. Para se familiarizar com isso, são estudados vários modelos de outliers. Neste trabalho, discutimos e analisamos vários estimadores robustos dentro do contexto dos modelos de regressão linear generalizados: são eles o M-Estimator, o S-Estimator, o MM-Estimator, o RANSAC e o Theil-Senestimator. A escolha dos estimadores é motivada pelo principio de explorar algoritmos com distintos conceitos de funcionamento. Em particular os estimadores M, S e MM são baseados na modificação do critério de minimização dos mínimos quadrados, enquanto que o RANSAC se fundamenta em achar o menor subconjunto que permita garantir uma acurácia predefinida ao modelo. Por outro lado o Theil-Sen usa a mediana de modelos obtidos usando mínimos quadradosno processo de estimação. O desempenho dos estimadores em uma ampla gama de condições experimentais é comparado e analisado. Além do problema de regressão linear, considera-se o problema de redução da dimensionalidade. Especificamente, são tratados o Locally Linear Embedding, o Principal ComponentAnalysis e outras abordagens robustas destes. É proposto um método denominado RALLE com a motivação de prover de robustez ao algoritmo de LLE. A ideia principal é usar vizinhanças de tamanhos variáveis para construir os pesos dos pontos; para fazer isto possível, o RAPCA é executado em cada grupo de vizinhos e os pontos sob risco são descartados da vizinhança correspondente. É feita uma avaliação do desempenho do LLE, do RLLE e do RALLE sobre algumas bases de dados.
3
Li, Zhentao. "Tree decompositions and linear time algorithms." Thesis, McGill University, 2012. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=107654.
Full textAbstract:
This thesis concerns tree decompositions. Trees are one of the simplest and most well understood class of graphs. A tree decomposition of a graph improves our understanding of the graph in a similar way. For example, as a consequence of Robertson and Seymour's groundbreaking work in the theory of graph minors, there are linear time algorithms for NP-hard problem on graphs that admit a tree decomposition of a certain type. We classify existing tree decompositions and examine what makes a tree decomposition unique.The first result of this thesis is a linear time algorithm for building a tree decomposition for the class of graphs that exclude K5 as a minor. The second result is a significant modification to this algorithm which results in a linear time algorithm to construct the tree decomposition for graphs which exclude a special set of paths. These are vertex disjoint paths between two pairs of input vertices (s_1, t_1), (s_2, t_2), one from s_1 to t_1 and the other from s_2 to t_2.We then use these tree decompositions to improve the running time of existing algorithms and extend the allowed input of other algorithms from planar graphs to graphs that exclude K_5 as a minor.Cette thèse traite de décompositions arborescentes. Les arbres font partie des classes de graphes les mieux comprises. La décomposition arborescente d'un graphe améliore notre compréhension de ce dernier. Par exemple, grâce aux travaux de Robertson et Seymour sur les mineurs d'un graphe, nous savons qu'il existe, pour des problèmes qui sont en général NP-difficiles, un algorithme linéaire pour les graphes admettant une certaine décomposition arborescente. Nous classons les décompositions arborescentes connues et déterminons les propiétés qui rendent cette décomposition unique.Comme premier résultat, nous donnons un algorithme linéaire pour construire une décomposition arborescente d'un graphe sans mineur du graphe complet K_5. Notre deuxième resultat repose sur une modification de cet algorithme afin d'obtenir un autre algorithme linéaire. Ce dernier permet la construction d'une décomposition arborescente d'un graphe qui ne contient pas deux chemins à sommets disjoints entre deux paires de sommets données (s_1, t_1) et (s_2, t_2).Nous utilisons ces deux décompositions pour améliorer le temps de calcul des algorithmes existants et modifions des algorithmes pour graphes planaires pour leur permettre de prendre comme donnée des graphes sans mineur K_5.
4
Lee, Richard. "3D non-linear image restoration algorithms." Thesis, University of East Anglia, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.338227.
Full text
5
TORTORELLI, MARCUS MAGNO FERNANDES. "CENTRAL PATH ALGORITHMS FOR LINEAR PROGRAMMING." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 1991. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=9405@1.
Full textAbstract:
Neste trabalho estudamos os algoritmos de Pontos Interiores para programação Linear. Publicados após o Algoritmo de Karmarkar. Que seguem, de algum modo, a Trajetória Central. São considerados tanto algoritmos Primais quanto Primais-Duais e também verificadas a eficácia da aplicação da metodologia de busca bidirecional. Estes métodos foram implementados e testados resolvendo um conjunto de problemas gerados aleatoriamente. Através da comparação dos resultados analisamos o desempenho das diferentes metodologias.We study here the Interior Points Algorithms for Linear Programming, developed after Karmarkar s Algorithm, which follow the Central Path. Both Primal and Primal-dual Algorithms are considered and also the efficiency of applying a bidirecional Search procedure is verified. These methods were implemented and tested solving a set of randomly generated problems. Comparing these results we analyze the performance of the methodologies.
6
Yodpinyanee, Anak. "Sub-linear algorithms for graph problems." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120411.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 189-199).
In the face of massive data sets, classical algorithmic models, where the algorithm reads the entire input, performs a full computation, then reports the entire output, are rendered infeasible. To handle these data sets, alternative algorithmic models are suggested to solve problems under the restricted, namely sub-linear, resources such as time, memory or randomness. This thesis aims at addressing these limitations on graph problems and combinatorial optimization problems through a number of different models. First, we consider the graph spanner problem in the local computation algorithm (LCA) model. A graph spanner is a subgraph of the input graph that preserves all pairwise distances up to a small multiplicative stretch. Given a query edge from the input graph, the LCA explores a sub-linear portion of the input graph, then decides whether to include this edge in its spanner or not - the answers to all edge queries constitute the output of the LCA. We provide the first LCA constructions for 3 and 5-spanners of general graphs with almost optimal trade-offs between spanner sizes and stretches, and for fixed-stretch spanners of low maximum-degree graphs. Next, we study the set cover problem in the oracle access model. The algorithm accesses a sub-linear portion of the input set system by probing for elements in a set, and for sets containing an element, then computes an approximate minimum set cover: a collection of an approximately-minimum number of sets whose union includes all elements. We provide probe-efficient algorithms for set cover, and complement our results with almost tight lower bound constructions. We further extend our study to the LP-relaxation variants and to the streaming setting, obtaining the first streaming results for the fractional set cover problem. Lastly, we design local-access generators for a collection of fundamental random graph models. We demonstrate how to generate graphs according to the desired probability distribution in an on-the-fly fashion. Our algorithms receive probes about arbitrary parts of the input graph, then construct just enough of the graph to answer these probes, using only polylogarithmic time, additional space and random bits per probe. We also provide the first implementation of random neighbor probes, which is a basic algorithmic building block with applications in various huge graph models.
by Anak Yodpinyanee.
Ph. D.
7
Kong, Seunghyun. "Linear programming algorithms using least-squares method." Diss., Available online, Georgia Institute of Technology, 2007, 2007. http://etd.gatech.edu/theses/available/etd-04012007-010244/.
Full textAbstract:
Thesis (Ph. D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2007.Martin Savelsbergh, Committee Member ; Joel Sokol, Committee Member ; Earl Barnes, Committee Co-Chair ; Ellis L. Johnson, Committee Chair ; Prasad Tetali, Committee Member.
8
Jamieson, Alan C. "Linear-time algorithms for edge-based problems." Connect to this title online, 2007. http://etd.lib.clemson.edu/documents/1193079463/.
Full text
9
Amir-Azizi, Siamak. "Linear filtering algorithms for Monte Carlo simulations." Thesis, University of Southampton, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.280859.
Full text
10
Pullan, Malcolm Craig. "Separated continuous linear programs : theory and algorithms." Thesis, University of Cambridge, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.260693.
Full text
11
Luo, Xiaodong. "Continuous linear programming : theory, algorithms and applications." Thesis, Massachusetts Institute of Technology, 1995. http://hdl.handle.net/1721.1/10591.
Full text
12
Axiotis, Kyriakos. "Algorithms for Subset Sum using linear sketching." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/122750.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019Cataloged from PDF version of thesis.
Includes bibliographical references (pages 41-43).
Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum problem (where m = + [infinity symbol]) with ties to additive combinatorics and cryptography. The non-modular case was long known to be NP-complete but to admit pseudo-polynomial time algorithms and, recently, algorithms running in near-linear pseudo-polynomial time were developed [9, 211. For the modular case, however, the best known algorithm by Koiliaris and Xu [21] runs in time 0̃ (m⁵/⁴). In this thesis we tackle this problem by devising a faster algorithm for the Modular Subset Sum problem, running in 0̃(m) randomized time, which matches a recent conditional lower bound of [1] based on the Strong Exponential Time Hypothesis. Interestingly, in contrast to most previous results on Subset Sum, our algorithm does not use the Fast Fourier Transform. Instead, it is able to simulate the "textbook" Dynamic Programming algorithm much faster, using ideas from linear sketching. This is one of the first applications of sketching-based techniques to obtain fast algorithms for exact combinatorial problems in an offline setting.
by Kyriakos Axiotis.
S.M.
S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
13
Silva, Jair da. "Uma familia de algoritmos para programação linear baseada no algoritmo de Von Neumann." [s.n.], 2009. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306741.
Full textAbstract:
Orientador: Aurelio R. Leite Oliveira, Marta Ines VelazcoTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-13T08:57:24Z (GMT). No. of bitstreams: 1 Silva_Jairda1_D.pdf: 1755258 bytes, checksum: 2ecb493aab3646838f54c2df2012b5d9 (MD5) Previous issue date: 2009
Resumo: Neste trabalho apresentamos uma nova família de algoritmos para resolver problemas de programação linear. A vantagem desta família de algoritmos é a sua simplicidade, a possibilidade de explorar a esparsidade dos dados do problema original e geralmente possuir raio de convergência inicial rápido. Esta família de algoritmos surgiu da generalização da idéia apresentada por João Gonçalves, Robert Storer e Jacek Gondzio, para desenvolver o algoritmo de ajustamento pelo par ótimo. Este algoritmo foi desenvolvido por sua vez tendo como base o algoritmo de Von Neumann. O algoritmo de Von Neumann possui propriedades interessantes, como simplicidade e convergência inicial rápida, porém, ele não é muito prático para resolver problemas lineares, visto que sua convergência é muito lenta. Do ponto de vista computacional, nossa proposta não é utilizar a família de algoritmos para resolver os problemas de programação linear até encontrar uma solução e sim explorar a sua simplicidade e seu raio de convergência inicial geralmente rápido e usá-la em conjunto com um método primal-dual de pontos interiores infactível, para melhorar a eficiência deste. Experimentos numéricos revelam que ao usar esta família de algoritmos em conjunto com um método primal-dual de pontos interiores infactível melhoramos o seu desempenho na solução de algumas classes de problemas de programação linear de grande porte.
Abstract: In this work, we present a new family of algorithms to solve linear programming problems. The advantage of this family of algorithms relies in its simplicity, the possibility of exploiting the sparsity of the original problem data and usually to have fast initial ratio of convergence. This family of algorithms arose from the generalization of the idea presented by João Gonçalves, Robert Storer and Jacek Gondzio to develop the optimal pair adjustment algorithm. This algorithm was developed in its own turn based on the Von Neumann's algorithm. It has interesting properties, such as simplicity and fast initial convergence, but it is not very practical for solving linear problems, since its convergence is very slow. From the computational point of view, our suggestion is not to use the family of algorithms to solve problems of linear programming until optimality, but to exploit its simplicity and its fast initial ratio of convergence and use it together with a infeasible primal-dual interior point method to improve its efficiency. Numerical experiments show that using this family of algorithms with an infeasible primal-dual interior point method improves its performance in the solution of some classes of large-scale linear programming problems.
Doutorado
Doutor em Matemática Aplicada
14
Wang, Yanhui. "Affine scaling algorithms for linear programs and linearly constrained convex and concave programs." Diss., Georgia Institute of Technology, 1996. http://hdl.handle.net/1853/24919.
Full text
15
Beauchamp, Gerson. "Algorithms for singular systems." Diss., Georgia Institute of Technology, 1990. http://hdl.handle.net/1853/15368.
Full text
16
Borie, Richard Bryan. "Recursively constructed graph families : membership and linear algorithms." Diss., Georgia Institute of Technology, 1988. http://hdl.handle.net/1853/8140.
Full text
17
Horton, Steven Bradish. "The optimal linear arrangement problem : algorithms and approximation." Diss., Georgia Institute of Technology, 1997. http://hdl.handle.net/1853/30878.
Full text
18
Mehadhebi, Karim. "Linear expected time algorithms for nearest neighbor problems." Thesis, McGill University, 1994. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=22774.
Full textAbstract:
This thesis presents and analyses a bucketing algorithm that finds a proximity graph in linear expected time when the points are independent identically distributed with a Lipschitz density f, provided f satisfies a weak assumption. From this proximity graph one can either find the minimum spanning tree in $O(n$ log* $n)$ time or solve the all nearest neighbors problem in $O(n)$ time.
19
Peng, Wei. "Non-linear detection algorithms for MIMO multiplexing systems." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/HKUTO/record/B39558563.
Full text
20
Nwana, Vincent Lebga. "Parallel algorithms for solving mixed integer linear programs." Thesis, Brunel University, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.368540.
Full text
21
朱紫君 and Chi-kwan Chu. "Polynomial time algorithms for linear and integer programming." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2000. http://hub.hku.hk/bib/B31224301.
Full text
22
Peng, Wei, and 彭薇. "Non-linear detection algorithms for MIMO multiplexing systems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39558563.
Full text
23
Chu, Chi-kwan. "Polynomial time algorithms for linear and integer programming." Hong Kong : University of Hong Kong, 2000. http://sunzi.lib.hku.hk/hkuto/record.jsp?B22718710.
Full text
24
MANRIQUE, ANDRÉ ROBERT FLORES. "DATA-SELECTIVE ADAPTIVE LINEAR AND KERNEL-BASED ALGORITHMS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2017. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=30566@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
FUNDAÇÃO DE APOIO À PESQUISA DO ESTADO DO RIO DE JANEIRO
BOLSA NOTA 10
Nesta dissertação, diversos algoritmos adaptativos para processamento de sinais com seleção de dados são desenvolvidos e estudados, com o objetivo de resolver dois problemas diferentes. O primeiro problema envolve ambientes com sistemas esparsos, onde uma função penalidade é incorporada na função de custo para aproveitar a esparsidade do modelo. Nesta perspectiva, são propostos três algoritmos com função penalidade ajustável, o primeiro baseado na função penalidade l1 é denominado SM-NLMS com atração para zero e função penalidade ajustável (ZA-SM-NLMS-ADP). O segundo algoritmo está baseado na função penalidade log-sum e o terceiro na função penalidade l0 , denominados SM-NLMS com atração ponderada para zero e função de penalidade ajustável (RZA-SM-NLMS-ADP) e SM-NLMS com atração para zero exponencial e função de penalidade ajustável (EZA-SM-NLMSADP), respectivamente. Além disso, foi desenvolvida uma análise estatística do algoritmo SM-NLMS com uma função penalidade genérica, obtendo expressões matemáticas para o erro médio quadrático em estado estacionário. O segundo problema abordado, considera algoritmos adaptativos não lineares baseados em funções de kernels. Neste contexto, são desenvolvidos dois algoritmos com seleção de dados, o algoritmo SM-NKLMS e o algoritmo SM-KAP, os quais possuem a capacidade de limitar o crescimento da estrutura criada pelas funções de kernels, tratando um dos maiores problemas que surge quando se utilizam algoritmos baseados em kernels. Os algoritmos baseados em kernels foram testados para predição de séries temporais. Também é realizada uma análise estatística do algoritmo SM-NKLMS. As simulações mostram que os algoritmos desenvolvidos superam os algoritmos lineares e não lineares convencionais tanto na velocidade de convergência quanto no erro médio quadrático atingido.
In this dissertation, several data-selective adaptive signal processing algorithms are derived and investigated for solving two different problems. The first one involves scenarios handling sparse systems, where we introduce a framework in which a general penalty function is incorporated into the cost function for exploiting the sparsity of the model. Under this scope, we propose three algorithms with an adjustable penalty function, the first one based on the l1 - norm, which we term zero-attracting SM-NLMS with adjustable penalty function (ZA-SM-NLMS-ADP). The second algorithm is based on the log-sum penalty function and the third one on the l0 - norm, named reweighted ZASM- NLMS (RZA-SM-NLMS-ADP) and the exponential ZA-SM-NLMS (EZASM- NLMS-ADP), respectively. We also carry out a statistical analysis of the sparsity-aware SM-NLMS algorithms with a general penalty function, arriving at mathematical expressions for the mean-square error at steady state. The second problem addressed considers nonlinear adaptive algorithms based on kernel functions. In this context, we develop two data selective algorithms, the Set-Membership Normalized Kernel Least Mean Squares (SM-NKLMS) algorithm and the Set-Membership Kernel Affine Projection (SM-KAP) algorithm, which have the capability of naturally limiting the growing structure created by the kernels, dealing with one of the major problems presented when working with kernel algorithms. The kernel algorithms developed have been tested for a time series prediction task. A statistical analysis of the proposed SM-NKLMS algorithm is also developed. Simulation results show that the proposed algorithms, outperform standard linear and nonlinear adaptive algorithms in both convergence rate and steady state performance.
25
Lammoglia, Bruna. "Sobre minimização de quadraticas em caixas." [s.n.], 2007. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306045.
Full textAbstract:
Orientador: Maria Aparecida Diniz EhrhardtDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-10T01:30:21Z (GMT). No. of bitstreams: 1 Lammoglia_Bruna_M.pdf: 679586 bytes, checksum: 221fa89afc7d9f594781baed1dfe6b0e (MD5) Previous issue date: 2007
Resumo: Neste trabalho o objetivo principal foi a minimização de quadráticas em caixas. Dissertamos sobre os métodos de máxima descida e dos gradientes conjugados, bem como sobre um método mais recente denominado gradiente espectral. O GENCAN, um algoritmo que minimiza funções em caixas, foi estudado em detalhe, particularmente avaliando sua aplicação para quadráticas. O objetivo foi analisar o desempenho do GENCAN, comparado com algoritmos anteriores, como o LANCELOT e o QUACAN. Foram executados experimentos numéricos a fim de avaliar o desempenho das versões de GENCAN sem e com pré-condicionamento. Concluiu-se que pré-condicionar o método dos gradientes conjugados neste caso tornou o GENCAN mais robusto. No entanto, o pré-condicionador usado neste software mostrou-se computacionalmente caro. Em relação à comparação do GENCAN, LANCELOT e QUACÁN, podemos afirmar que o GENCAN. mostrou-se competitivo
Abstract: The focus of this work was the minimization of quadratic functions with box constraints. We were mainly concerned about the steepest descent and conjugated gradient methods, besides a more recent approach called spectral gradient method. The GENCAN, an algorithm that minimizes functions on a box, was studied in details particularly evaluating this algorithm applied to quadratics. The objective was to analyze the efficiency of GENCAN, comparing it to classical algorithms, such as LANCELOT and QUACAN. We executed numerical experiments in order to investigate the efficiency of GENCAN version with and without preconditioning. Evaluating the results we concluded that preconditioning the conjugated gradient method makes the GENCAN work considerably better; despite the fact that the preconditioner used here turned the computational process more expensive. Comparing GENCA'N, LANCELOT, and QUACAN we can state that GENCAN is competitive
Mestrado
Otimização
Mestre em Matemática Aplicada
26
Lopez, Mario A., Shlomo Reisner, and reisner@math haifa ac il. "Linear Time Approximation of 3D Convex Polytopes." ESI preprints, 2001. ftp://ftp.esi.ac.at/pub/Preprints/esi1005.ps.
Full text
27
Tam, Siu-lung. "Linear-size indexes for approximate pattern matching and dictionary matching." Click to view the E-thesis via HKUTO, 2010. http://sunzi.lib.hku.hk/hkuto/record/B44205326.
Full text
28
Tam, Siu-lung, and 譚小龍. "Linear-size indexes for approximate pattern matching and dictionary matching." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2010. http://hub.hku.hk/bib/B44205326.
Full text
29
Ajlouni, Naim. "Genetic algorithms for control system design." Thesis, University of Salford, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.308088.
Full text
30
Ben, Daya Mohamed. "Barrier function algorithms for linear and convex quadratic programming." Diss., Georgia Institute of Technology, 1988. http://hdl.handle.net/1853/25502.
Full text
31
Weihrauch, Christian. "Analysis of Monte Carlo algorithms for linear algebra problems." Thesis, University of Reading, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.515747.
Full text
32
Yagoob, Muhammad Moeen. "Computationally efficient algorithms for non-linear target tracking problems." Thesis, Imperial College London, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.499109.
Full text
33
Chen, Fei, and 陳飛. "Linear programming techniques for algorithms with applications in economics." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/206329.
Full textAbstract:
We study algorithms and models for several economics-related problems from the perspective of linear programming.
In network bargaining games, stable and balanced outcomes have been investigated in previous work. However, existence of such outcomes requires that the linear program relaxation of a certain maximum matching problem has integral optimal solution. We propose an alternative model for network bargaining games in which each edge acts as a player, who proposes how to split the weight of the edge among the two incident nodes. We show that the distributed protocol by Kanoria et. al can be modified to be run by the edge players such that the configuration of proposals will converge to a pure Nash Equilibrium, without the linear program integrality gap assumption. Moreover, ambiguous choices can be resolved in a way such that there exists a Nash Equilibrium that will not hurt the social welfare too much.
In the oblivious matching problem, an algorithm aims to find a maximum matching while it can only makes (random) decisions that are essentially oblivious to the input graph. Any greedy algorithm can achieve performance ratio 0:5, which is the expected number of matched nodes to the number of nodes in a maximum matching. We revisit the Ranking algorithm using the linear programming framework, where the constraints of the linear program are given by the structural properties of Ranking. We use continuous linear program relaxation to analyze the limiting behavior as the finite linear program grows. Of particular interest are new duality and complementary slackness characterizations that can handle monotone constraints and mixed evolving and boundary constraints in continuous linear program, which enable us to achieve a theoretical ratio of 0:523 on arbitrary graphs.
The J-choice K-best secretary problem, also known as the (J;K)-secretary problem, is a generalization of the classical secretary problem. An algorithm for the (J;K)-secretary problem is allowed to make J choices and the payoff to be maximized is the expected number of items chosen among the K best items. We use primal-dual continuous linear program techniques to analyze a class of infinite algorithms, which are general enough to capture the asymptotic behavior of the finite model with large number of items. Our techniques allow us to prove that the optimal solution can be achieved by a (J;K)-threshold algorithm, which has a nice \rational description" for the case K = 1.published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
34
Tsaig, Yaakov. "Sparse solution of underdetermined linear systems : algorithms and applications /." May be available electronically:, 2007. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.
Full text
35
Costa, da Silva Marco Aurelio. "Applications and algorithms for two-stage robust linear optimization." Thesis, Avignon, 2018. http://www.theses.fr/2018AVIG0229/document.
Full textAbstract:
Le domaine de recherche de cette thèse est l'optimisation linéaire robuste en deux étapes. Nous sommes intéressés par des algorithmes d'exploration de sa structure et aussi pour ajouter des alternatives afin d'atténuer le conservatisme inhérent à une solution robuste. Nous développons des algorithmes qui incorporent ces alternatives et sont personnalisés pour fonctionner avec des exemples de problèmes à moyenne ou grande échelle. En faisant cela, nous expérimentons une approche holistique du conservatisme en optimisation linéaire robuste et nous rassemblons les dernières avancées dans des domaines tels que l'optimisation robuste basée sur les données, optimisation robuste par distribution et optimisation robuste adaptative. Nous appliquons ces algorithmes dans des applications définies du problème de conception / chargement du réseau, problème de planification, problème combinatoire min-max-min et problème d'affectation de la flotte aérienne. Nous montrons comment les algorithmes développés améliorent les performances par rapport aux implémentations précédentesThe research scope of this thesis is two-stage robust linear optimization. We are interested in investigating algorithms that can explore its structure and also on adding alternatives to mitigate conservatism inherent to a robust solution. We develop algorithms that incorporate these alternatives and are customized to work with rather medium or large scale instances of problems. By doing this we experiment a holistic approach to conservatism in robust linear optimization and bring together the most recent advances in areas such as data-driven robust optimization, distributionally robust optimization and adaptive robust optimization. We apply these algorithms in defined applications of the network design/loading problem, the scheduling problem, a min-max-min combinatorial problem and the airline fleet assignment problem. We show how the algorithms developed improve performance when compared to previous implementations
36
Nicolae, Maria-Irina. "Learning similarities for linear classification : theoretical foundations and algorithms." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSES062/document.
Full textAbstract:
La notion de métrique joue un rôle clef dans les problèmes d’apprentissage automatique tels que la classification, le clustering et le ranking. L’apprentissage à partir de données de métriques adaptées à une tâche spécifique a suscité un intérêt croissant ces dernières années. Ce domaine vise généralement à trouver les meilleurs paramètres pour une métrique donnée sous certaines contraintes imposées par les données. La métrique apprise est utilisée dans un algorithme d’apprentissage automatique dans le but d’améliorer sa performance. La plupart des méthodes d’apprentissage de métriques optimisent les paramètres d’une distance de Mahalanobis pour des vecteurs de features. Les méthodes actuelles de l’état de l’art arrivent à traiter des jeux de données de tailles significatives. En revanche, le sujet plus complexe des séries temporelles multivariées n’a reçu qu’une attention limitée, malgré l’omniprésence de ce type de données dans les applications réelles. Une importante partie de la recherche sur les séries temporelles est basée sur la dynamic time warping (DTW), qui détermine l’alignement optimal entre deux séries temporelles. L’état actuel de l’apprentissage de métriques souffre de certaines limitations. La plus importante est probablement le manque de garanties théoriques concernant la métrique apprise et sa performance pour la classification. La théorie des fonctions de similarité (ℰ , ϓ, T)-bonnes a été l’un des premiers résultats liant les propriétés d’une similarité à celles du classifieur qui l’utilise. Une deuxième limitation vient du fait que la plupart des méthodes imposent des propriétés de distance, qui sont coûteuses en terme de calcul et souvent non justifiées. Dans cette thèse, nous abordons les limitations précédentes à travers deux contributions principales. La première est un nouveau cadre général pour l’apprentissage conjoint d’une fonction de similarité et d’un classifieur linéaire. Cette formulation est inspirée de la théorie de similarités (ℰ , ϓ, τ) -bonnes, fournissant un lien entre la similarité et le classifieur linéaire. Elle est convexe pour une large gamme de fonctions de similarité et de régulariseurs. Nous dérivons deux bornes de généralisation équivalentes à travers les cadres de robustesse algorithmique et de convergence uniforme basée sur la complexité de Rademacher, prouvant les propriétés théoriques de notre formulation. Notre deuxième contribution est une méthode d’apprentissage de similarités basée sur DTW pour la classification de séries temporelles multivariées. Le problème est convexe et utilise la théorie des fonctions (ℰ , ϓ, T)-bonnes liant la performance de la métrique à celle du classifieur linéaire associé. A l’aide de la stabilité uniforme, nous prouvons la consistance de la similarité apprise conduisant à la dérivation d’une borne de généralisationThe notion of metric plays a key role in machine learning problems, such as classification, clustering and ranking. Learning metrics from training data in order to make them adapted to the task at hand has attracted a growing interest in the past years. This research field, known as metric learning, usually aims at finding the best parameters for a given metric under some constraints from the data. The learned metric is used in a machine learning algorithm in hopes of improving performance. Most of the metric learning algorithms focus on learning the parameters of Mahalanobis distances for feature vectors. Current state of the art methods scale well for datasets of significant size. On the other hand, the more complex topic of multivariate time series has received only limited attention, despite the omnipresence of this type of data in applications. An important part of the research on time series is based on the dynamic time warping (DTW) computing the optimal alignment between two time series. The current state of metric learning suffers from some significant limitations which we aim to address in this thesis. The most important one is probably the lack of theoretical guarantees for the learned metric and its performance for classification.The theory of (ℰ , ϓ, τ)-good similarity functions has been one of the first results relating the properties of a similarity to its classification performance. A second limitation in metric learning comes from the fact that most methods work with metrics that enforce distance properties, which are computationally expensive and often not justified. In this thesis, we address these limitations through two main contributions. The first one is a novel general framework for jointly learning a similarity function and a linear classifier. This formulation is inspired from the (ℰ , ϓ, τ)-good theory, providing a link between the similarity and the linear classifier. It is also convex for a broad range of similarity functions and regularizers. We derive two equivalent generalization bounds through the frameworks of algorithmic robustness and uniform convergence using the Rademacher complexity, proving the good theoretical properties of our framework. Our second contribution is a method for learning similarity functions based on DTW for multivariate time series classification. The formulation is convex and makes use of the(ℰ , ϓ, τ)-good framework for relating the performance of the metric to that of its associated linear classifier. Using uniform stability arguments, we prove the consistency of the learned similarity leading to the derivation of a generalization bound
37
Zheng, Gan. "Optimization in linear multiuser MIMO systems." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/HKUTO/record/B39557923.
Full text
38
Zheng, Gan, and 鄭淦. "Optimization in linear multiuser MIMO systems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39557923.
Full text
39
Zhao, Jianmin. "Optimal Clustering: Genetic Constrained K-Means and Linear Programming Algorithms." VCU Scholars Compass, 2006. http://hdl.handle.net/10156/1583.
Full text
40
Zhao, Zhanlue. "Performance Appraisal of Estimation Algorithms and Application of Estimation Algorithms to Target Tracking." ScholarWorks@UNO, 2006. http://scholarworks.uno.edu/td/394.
Full textAbstract:
This dissertation consists of two parts. The first part deals with the performance appraisal of estimation algorithms. The second part focuses on the application of estimation algorithms to target tracking. Performance appraisal is crucial for understanding, developing and comparing various estimation algorithms. In particular, with the evolvement of estimation theory and the increase of problem complexity, performance appraisal is getting more and more challenging for engineers to make comprehensive conclusions. However, the existing theoretical results are inadequate for practical reference. The first part of this dissertation is dedicated to performance measures which include local performance measures, global performance measures and model distortion measure. The second part focuses on application of the recursive best linear unbiased estimation (BLUE) or lineae minimum mean square error (LMMSE) estimation to nonlinear measurement problem in target tracking. Kalman filter has been the dominant basis for dynamic state filtering for several decades. Beyond Kalman filter, a more fundamental basis for the recursive best linear unbiased filtering has been thoroughly investigated in a series of papers by Dr. X. Rong Li. Based on the so-called quasirecursive best linear unbiased filtering technique, the constraints of the Kalman filter Linear-Gaussian assumptions can be relaxed such that a general linear filtering technique for nonlinear systems can be achieved. An approximate optimal BLUE filter is implemented for nonlinear measurements in target tracking which outperforms the existing method significantly in terms of accuracy, credibility and robustness.
41
Silva, Magno Teófilo Madeira da. "Equalização não-linear de canais de comunicação." Universidade de São Paulo, 2001. http://www.teses.usp.br/teses/disponiveis/3/3142/tde-03072001-162729/.
Full textAbstract:
É investigado o uso de redes neurais aplicadas à equalização de canais de comunicação, sendo consideradas três tipos de redes: MLP (Multilayer Perceptron), RBF (Radial Basis Function) e RNN (Recurrent Neural Network). Os equalizadores não-lineares baseados nestas redes foram comparados com o equalizador linear transversal e com os equalizadores ótimos segundo os critérios de Bayes e da máxima verossimilhança. Nestas comparações foram utilizados um alfabeto binário e um quaternário transmitidos em modelos de canais cuja resposta ao pulso unitário é finita. Além das versões usuais de equalizadores, foram consideradas versões com realimentação de decisões sempre que isso se mostrou adequado. O treinamento desses equalizadores foi feito de forma supervisionada, ou seja, na fase de treinamento a seqüência de símbolos transmitida era conhecida no receptor. Além disso, foi realizado um estudo comparativo dos algoritmos de treinamento das redes. Neste âmbito, foi obtido um algoritmo do tipo acelerador para o treinamento de redes MLP. Com o intuito de se obter uma estrutura não-linear menos complexa e mais flexível, foi proposto ainda um equalizador híbrido constituído de uma combinação do equalizador linear e da rede RNN que faz uso de realimentação de decisões. Resultados de simulações indicam que o seu uso pode ser vantajoso tanto para canais não-lineares como lineares.Equalization of communication channels using neural networks is investigated by considering three kinds of networks: MLP (Multilayer Perceptron), RBF (Radial Basis Function) and RNN (Recurrent Neural Network). The performance of the nonlinear equalizers based on these networks are compared with the linear transversal equalizer and the optimal equalizers given by the bayesian and maximum likelihood criteria. Binary and quaternary alphabets are used and transmitted over finite pulse response channel models. Decision feedback is considered whenever it is worthwhile. The training of these equalizers is considered in the supervised form and a comparison of some training algorithms has been performed. In this scope, a new algorithm based on parameter acceleration is introduced for the training of MLP networks. Moreover, a hybrid equalizer composed of a linear transversal equalizer and a RNN network is proposed. It is a simple and flexible nonlinear structure making use of decision feedback. imulation results show that it may be advantageously used to equalize linear and nonlinear channels.
42
Sanders, Daniel Preston. "Linear algorithms for graphs of tree-width at most four." Diss., Georgia Institute of Technology, 1993. http://hdl.handle.net/1853/30061.
Full text
43
Dawkins, Ian. "Development of practical evolution Galerkin algorithms on unstructured meshes." Thesis, University of Oxford, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.390460.
Full text
44
Poire, Xavier Corvera. "Model generation and sampling algorithms for dynamic stochastic programming." Thesis, University of Essex, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.294674.
Full text
45
Castillo, Ileana. "Some properties of the affine scaling algorithm." Diss., Georgia Institute of Technology, 1996. http://hdl.handle.net/1853/25459.
Full text
46
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
47
Levin, Matthew D. "Parallel algorithms for SIMD and MIMD computers." Thesis, Loughborough University, 1990. https://dspace.lboro.ac.uk/2134/32962.
Full textAbstract:
The thesis is concerned with the inversion of matrices and the solution of linear systems and eigensystems in a parallel environment. Following an introductory chapter of concepts and definitions in the field of linear algebra, a general survey of parallel machines and algorithms is presented in Chapters 2 and 3, including a detailed description of the Distributed Array Processor (DAP) and the Neptune multiprocessing system. In Chapter 4, a new technique, the double-bordering algorithm, for the solution of linear systems is derived, and its application to the parallel solution of difference systems described. A modified form of the method for the inversion of matrices is derived, implemented on the Neptune multiprocessing system, and its performance compared with that of the Gauss-Jordan and (single) bordering algorithms. The results of the implementation of several other parallel algorithms are also presented. Chapter 5 deals with the class of matrices known as Toeplitz matrices, which arise in the field of signal processing. Trench's algorithm for the inversion of such matrices is implemented on the Neptune multiprocessing system, and, for the solution of banded symmetric Toeplitz systems, the relative efficiencies of three sequential strategies are compared: Levinson's algorithm, the double-bordering algorithm, and a method based on a novel factorisation scheme. Chapter 6 is concerned with the implementation of various iterative methods on the DAP. The solution of several difference systems by the Jacobi, Gauss-Seidel and successive over-relaxation (SOR) algorithms is compared with their solution by a variation (c. 1943) of the algorithms proposed by Hotelling, in which matrix-vector products are replaced by successive matrix squarings. The technique is also applied to the power method for the solution of the eigenvalue problem. The thesis concludes with a summary and recommendations for future work.
48
Rahmouni, M. K. "The conversion of linear programmes to network flow problems." Thesis, University of Southampton, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.380042.
Full text
49
Lopez, Erazo Tulio Emiro. "Metodos derivative-free para resolver um problema de programação não linear com restrições lineares." [s.n.], 2007. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306666.
Full textAbstract:
Orientador: Vera Lucia da Rocha LopesDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-10T21:50:16Z (GMT). No. of bitstreams: 1 LopezErazo_TulioEmiro_M.pdf: 12666478 bytes, checksum: df86afcc58096ac12697d7d0fefe8ee5 (MD5) Previous issue date: 2007
Resumo: No presente trabalho estudamos métodos numéricos que resolvem um problema de programação não linear com restrições lineares de desigualdade e de igualdade, os quais não fazem uso explícito do gradiente da função objetivo nem tampouco de aproximações ao mesmo. Um método de decréscimo su_ciente e um método de decréscimo simples são estudados. O primeiro, procura melhores valores para a função objetivo ao longo de um conjunto de direções, as quais geram positivamente o cone poliedral convexo no ponto atual. O segundo método procura melhorar o valor da função objetivo ao longo de um conjunto de direções, as quais, dependendo do ponto atual, ou geram positivamente todo o espaço Rn, ou geram positivamente o cone poliedral convexo em tal ponto. Algoritmos dos métodos, comentários das implementa ções feitas e testes numéricos de tais implementações com problemas da coleção Hock-Schittkowski são feitos ao final do trabalho
Abstract: In the present work we study numerical methods that solve a problem of nonlinear programming with linear inequality and equality constraints, which do not make explicit use either neither of the gradient of the objective function nor approaches to the same one. A method of su_cient decrease and a method of simple decrease are studied. The _rst one, looks for better values for the objective function throughout a set of directions, which positively generate the convex polyhedral cone in the current point. The second method looks for to improve the value of the objective function throughout a set of directions, which, depending on the current point, either generates positively the whole spaces, or positively generates the convex polyhedral cone in this point. Algorithms of the methods, commentaries of the implementations done and numerical tests of such implementations with problems of the Hock-Schittkowski collection are made at the end of the work
Mestrado
Mestre em Matemática Aplicada
50
Iakymchuk, Roman [Verfasser]. "Performance modeling and prediction for linear algebra algorithms / Roman Iakymchuk." Aachen : Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2012. http://d-nb.info/1026308690/34.
Full text