AbstractsBiology & Animal Science

Numerical methods for underdetermined box-constrained integer least squares problems

by Jing Zhu




Institution: McGill University
Department:
Year: 2016
Keywords: Computer Science
Posted: 02/05/2017
Record ID: 2070493
Full text PDF: http://digitool.library.mcgill.ca/thesisfile141570.pdf


Abstract

Integer least squares (ILS) is an important class of optimization problems, which can arise in many applications, such as communications, cryptography and cryptanalysis and global navigation satellite systems. This thesis is concerned with solving the underdetermined box constrained ILS (UBILS) problems. For the two existing algorithms, the direct tree search (DTS) algorithm and the partial regularization (PR) algorithm, we propose to incorporate some lower bounds to speed up the search process. Simulation results show that the proposed lower bounds can make the search process of the DTS algorithm perform more efficiently than the original one. Then we propose a modified DTS algorithm by partially using a best-first search strategy in the search process. Numerical tests results indicate that the new search algorithm is very effective in improving the efficiency of the DTS algorithm with or without incorporating the proposed lower bounds. Les moindres carrés en nombres entiers (ILS) est une méthode d'optimisation des problèmes, qui peut être appliqué dans beaucoup de domaines, comme la communication, la cryptographie et la cryptanalyse les systèmes de navigation mondiaux par satellite. Dans cette thèse, on étudiera trois types de problèmes concernant les moindres carrés en nombres entiers: les problèmes de moindres carrés en nombre entiers classiques (OILS), les problèmes hyperdéterminés (OBILS) et hypodéterminés (UBILS) avec les contraintes de boites. Dans un premier temps, on va faire un rappel de dedirents algorithmes pour résoudre ces trois types de problèmes, suivi par une présentation dedirents minorations afin d'augmenter l'efficacité du processus de recherche. Pour les deux algorithmes existants l'algorithme de recherche en arbre directe (DTS) et l'algorithme de régularisation partielle (RP), on va proposer les minorations correspondantes afin d'accélérer le processus de recherche. On montrera les résultats de simulation qui justifient que les minorations qu'on propose peut faire le processus de recherche par l'algorithme de recherche en arbre directe plus performante que la méthode classique. Puis, on va proposer un nouveau algorithme de recherche pour résoudre les problèmes UBILS, qui est en fait une modification directe sur l'algorithme de recherche en arbre directe en utilsant la stratégie de recherche le meilleur en premier (best-first) dans le processus de recherche. Les résultats de test numérique montrera que le nouvel algorithme de recherche est plus efficace que la méthode de recherche en arbre directe existante Advisors/Committee Members: Xiao-Wen Chang (Internal/Supervisor).