Numerical Methods for Integer Parameter Estimation and Applications

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

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.