原子范数最小化问题的理论与算法研究

In this program we endeavor to study atomic norm minimization arising from wide application fields. Atomic norm is a natural generalization of L1 norm and nuclear norm. Our work is as follows:.(1).We study descent type methods for solving L1 minimization which means that the sequence of objective funcion value is decreasing, it is a brand new approach to solve L1 minimization..(2).We study algorithms such as semismooth Newton method, smoothing Newton method and spectral gradient projection method for solving equation reformulation to L1 minimization..(3).We study gradient-based methods for solving L1 minimization. We first construct a function with similar roles as gradient of objective function in smooth optimization. Then we extend the idea of the gradient-based algorithms for smooth optimization to L1 minimization, and deveop our methods which can be applied to solve large scale problems. .(4).We study proximal point algorithm for solving atomic norm minimization. Proximal point algorithm for solving convex optimization with linear constraints is more efficient than the augmented Lagrangian method, another classical method in the area of convex optimization. It becomes easy if it is easy to solve the proximal point of the objective function. In view of these advantages, we have two ways to solve atomic norm minimization. On the one hand, we first derive variational inequality problem reformulation to the atomic norm minimization, then exploit the idea of proximal point algorithm for solving variational inequality problem, taking advantage of the available structures of the models under consideration, we construct appropriate metric proximal parameter and develop efficient proximal point algorithm. On the other hand, we revisit the alternate direction methods from the prospective of the proximal point algorithm, and develop accelebrated alternative direction methods.

本项目研究具有广泛应用背景的原子范数最小化问题。原子范数是L1 、核范数概念的自然推广。主要工作如下：（1）研究求解L1最小化问题的下降型算法，开辟求解L1最小化问题的新途径；(2)研究牛顿法或谱梯度投影算法求解与L1 最小化问题等价的方程组。（3）研究求解 L1最小化问题的梯度法。构造一个与光滑优化问题的梯度具有同等作用的函数，借鉴求解光滑优化问题的各种梯度法的思想，设计求解 L1最小化问题的梯度法。(4)研究求解原子范数最小化问题的邻近点算法。鉴于邻近点算法在求解线性约束的凸优化问题的优势：邻近点算法比交替方向法具有更好的数值表现及算法适合目标函数的邻近函数易求，一方面我们将问题转化为等价的变分不等式，借鉴求解变分不等式的邻近点算法的思想、成果，充分利用问题的具体结构特征构造合适的度量邻近参数设计出更有效的邻近点算法。另一方面从邻近点算法的角度审视现有的交替方向法并提出新的交替方向法。

本项目研究原子范数最小化问题的理论与算法。该问题在信号处理，统计，控制，计算机图形学，机器学习，系统识别等领域具有广泛的应用背景。原子范数是L1、核范数概念的自然推广。梯度法、增广的拉格朗日法，交替方向法、邻近点算法是求解L1、核范数最小化的算法。本项目进一步研究这些求解L1、核范数最小化的算法; 我们将梯度法、邻近点算法结合提出一种算法求解非光滑凸优化问题，该文章已正式发表。我们将原子范数最小化转化为变分不等式或半定规划，采用增广的拉格朗日法，交替方向法、邻近点算法求解变分不等式或半定规划。提出求解原子范数最小化问题的梯度法框架、增广的拉格朗日法框架，交替方向法框架、邻近点算法框架，这些算法框架给出现有某些求解L1最小化问题的统一形式，给出收敛性分析，并进行数值实验，并从概率的角度分析算法的可行性和有效性。