Numerical Methods for Integer Parameter Estimation and Applications

在通信、控制、金融、全球卫星导航系统、运筹学等许多应用中，需要在线性或线性化模型中估计未知的整数参数向量。一个典型的方法是解决一个整数最小二乘问题。有时需要一个稀疏解，然后解决或近似解决一个优化问题，例如具有10或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.