基于互补约束的非凸优化方法及其应用

This project mainly discusses a class of non-convex optimization based on complementary constraint. In the fields of machine learning and computer vision, some common non-convex functions/constraints include sparse, low-rank, discrete, and orthogonal function/constraint. However, existing algorithms are mainly based on convex relaxation or non-convex approximation and they often lead to sub-optimal solutions. In order to seek better solutions to the original non-convex problems, this project establishes the following three contributions. (1) We first reformulate the original non-convex problem as equivalent locally Lipschitz continuous optimization problems with bi-linear complementary constraints. (2) In order to solve the resulting constrained problem, we propose two optimization frameworks (exact penalty method and alternating direction method). Generally speaking, our methods have five advantages. (a) They solve a completely equivalent problem. (b) They find a good initialization. (c) They exhibit strong convergence. (d) They have a monotone/greedy property. (e) They are modular and amenable to the use of existing convex methods. (3) Finally, we apply our methods to the optimization problems with sparsity function, low-rank function, discrete constraint, and orthogonal constraint, especially on binary low-rank matrix completion and social graph influence maximization. Extensive experiments have demonstrated that our method achieves state-of-the-art performance.

本课题主要探讨一类基于对偶互补约束的非凸优化方法。在机器学习和图像处理中，常见的非凸函数或约束包括：稀疏、低秩、离散、正交函数或约束。然而目前很多方法都是基于凸松弛或非凸近似的优化方法，这些方法通常只能得到次优的解。为了更好地求解这类问题，本项目有以下三大贡献。(1)通过一种新颖的变分等价变换，我们把原来的非凸函数或约束的优化问题转变成等价的具有双线性结构且局部Lipschitz连续的互补约束优化问题。(2)为了求解该互补约束优化问题，我们提出精确罚函数法和自惩罚的交替方向法两个优化框架。这类方法有着等价优化、初始化好、强收敛性、贪心单调性、以及模块优化等优点。(3)为了验证我们算法的有效性，我们把这类非凸优化方法应用到涉及稀疏、低秩、离散、正交函数或约束的机器学习和机器视觉问题上，尤其是二值低秩矩阵填充问题和社交图影响最大化问题。大量的实验表明我们的方法达到了当前领域的领先水平。

很多机器学习和数据挖掘问题本质上是一个非凸优化问题。然而这些问题通常涉及大规模数据、高维度变量、以及内在的非凸组合结构，因此比较难求解。我们提出两个新的近似优化算法框架：多阶段凸近似和强最优点近似。前者通过一种新颖的变分等价变换，把原来的非凸函数或约束的优化问题(涉及稀疏、低秩、离散、正交约束或目标函数)转变成等价的具有双线性结构且局部Lipschitz连续的互补约束优化问题，然后使用精确罚函数或自惩罚型交替方向法求解。后者利用坐标下降和拐点搜索策略，使得算法满足更多的必要非充分条件和更近似原来的最优解集空间。对于一些特殊结构的非凸优化问题(涉及稀疏、离散、DC、分式约束或目标函数)，我们证明了算法总能收敛到一个更强的稳定点。两个算法框架都有着等价优化、初始点好、严格收敛、贪心单调、模块优化、强最优保证等优点。最后，我们把我们所提出的非凸优化算法应用到很多机器学习和数据挖掘问题中；大量的实验表明，我们的算法取得的精度性能臻于艺境。