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 困难的。然而，对于许多实际应用中出现的一些中等规模的问题，可以在合理的时间内找到最佳解决方案。该提案的主要目标是开发快速算法和相关软件来解决这些整数最小二乘相关问题。具体来说，我们将开发高效的搜索算法。为了使搜索过程更快，我们将为这些优化问题制定有效且高效的缩减策略和下界。缩减策略提高某些次优估计器的搜索速度和成功概率的潜力尚未实现或完全实现。我们提出的研究预计将对这一领域算法的发展产生重大影响，尤其是约简算法的发展。由此产生的算法和软件将极大地造福于应用领域及其相关行业的人们。