Numerical Methods for Integer Parameter Estimation and Applications

整数参数估计的数值方法及应用

• 批准号: RGPIN-2017-05138
• 负责人: Chang, XiaoWen
• 金额: $ 3.06万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=688521
• 关键词: Numerical; Methods; Integer; Parameter; Estimation

In many applications such as communications, control, finance, global navigation satellite systems, operations research, one needs to estimate an unknown integer parameter vector in a linear or linearized model. A typical approach is to solve an integer least squares problem. Sometimes a sparse solution is needed, and then one solves or approximately solves an optimization problem, such as an integer least squares problem with l0 or l1 norm regularization - this is an emerging area which has great potential in such applications. The difficulty is that often the optimization problems in this area are NP-hard. However it is possible to find optimal solutions within reasonable time for some problems of moderate size arising in many practical applications. The main objectives of this proposal are to develop fast algorithms and the relevant software for solving these integer least squares related problems. Specifically we will develop efficient search algorithms. To make the search process faster, we will develop effective and efficient reduction strategies and lower bounds for those optimization problems. The potential of reduction strategies to improve the search speed and success probability of some sub-optimal estimators has not been realized or fully realized. Our proposed research is expected to have significant impacts on the development of algorithms in this area, especially on the development of reduction algorithms. The resulting algorithms and software will greatly benefit people in applied fields and their related industries.

在通信、控制、金融、全球导航卫星系统、运筹学等应用中，需要估计线性或线性化模型中的未知整数参数向量。一个典型的方法是解决整数最小二乘问题。有时需要稀疏解，然后求解或近似求解优化问题，例如l0或l1范数正则化的整数最小二乘问题-这是一个新兴领域，在此类应用中具有巨大潜力。困难的是，在这个领域的优化问题往往是NP难的。然而，在许多实际应用中，对于一些中等规模的问题，在合理的时间内找到最优解是可能的。本建议的主要目标是开发快速算法和相关软件来解决这些整数最小二乘相关问题。具体来说，我们将开发高效的搜索算法。为了使搜索过程更快，我们将为这些优化问题开发有效和高效的约简策略和下界。约简策略提高搜索速度和成功概率的潜力还没有实现或完全实现。我们提出的研究预计将有显着的影响，在这一领域的算法的发展，特别是约简算法的发展。由此产生的算法和软件将极大地造福于应用领域及其相关行业的人们。