一类结构型非凸优化问题的算法研究及应用

Structured optimization problems are widely used in real applications, such as machine learning, compressed sensing, imagine processing, data mining, network optimization, matrix/tensor factorization and completion. How to solve this kind of optimization problems plays a critical role in these applications. Thus, it is important to develop efficient algorithms for solving them.In the literature a lot of first-order algorithms have been proposed to solve structured convex optimization problems. However, there exist few research results for non-convex case. Moreover，recent studies show that the Newton-type algorithms using the “second-order” information can lead to substantial overall improvements. This proposal aims to develop new, novel and fast proximal Newton-type methods for structured nonconvex optimization problems by exploiting the use of “second-order” information. More specifically, we will design the new methods through the following four aspects:1).Using a locally piece-wise quadratic model to approximate the structured nonconvex problem; 2).Utilizing the “second-order”information and designing inexact proximal Newton-type methods;3).Adopting the strategy of randomized block-coordinate descent methods and developing a new technique to decompose the original large-scaled optimization problem into parallel small-scaled optimization problems such that the computational methods can be implemented in parallel;4).Applying the proposed algorithms to the non-negative matrix factorization.

结构型优化问题在实际生活中有着广泛的应用，如机器学习，压缩感知，图像处理，数据挖掘，网络优化，矩阵或张量的分解和完整化等应用领域。如何有效求解这类优化问题是这些应用中的关键步骤。因此，针对这类结构型优化开发专门的高效算法显得十分重要。对于结构型凸优化问题，目前已有许多较为成熟的一阶算法。然而对于结构型非凸优化，目前的相关研究结果还比较少。最近研究表明：开发基于二阶信息的牛顿型算法可以显著提高算法效率。为了有效求解结构型非凸优化，我们设计出新的基于二阶信息的牛顿并行算法，以满足快速计算需要。具体的，我们将从以下几方面展开研究：1)、采用局部分块二次模型来序列逼近结构型非凸优化问题；2)、利用二阶信息，设计出不精确邻近牛顿型算法；3)、采用某种块随机选择策略，开发新的并行算法，从而将原来的大规模问题分解成小规模并行子问题求解；4)、将已建立的算法应用到非负矩阵分解模型。

结构型优化问题在实际生活中有着广泛的应用，如机器学习，压缩感知，图像处理，智能电网，网络优化，矩阵或张量的分解和完整化等应用领域。如何有效求解这类优化问题是这些应用中的关键步骤。因此，针对这类结构型优化开发专门的高效算法显得十分重要。对于结构型凸优化问题，目前已有许多较为成熟的一阶算法。然而对于结构型非凸优化，目前的相关研究结果还比较少。最近研究表明：开发基于二阶信息的牛顿型算法或者加速一阶算法可以显著提高算法效率。为了有效求解结构型非凸优化，我们设计出新的基于二阶信息的牛顿算法和加速一阶算法，以满足快速计算需要。. 本项目主要研究了几类具有特殊结构的凸和非凸优化问题，以及求解它们的一阶和二阶分布式算法，包括分布式拟牛顿算法，分布式序列凸逼近算法，分布式加速对偶梯度算法，分布式mirror下降算法以及它们的应用等等。具体地，. 1） 针对一类特殊的可和非凸优化问题，我们设计了一种基于Nikaido-Isoda 正则化泛函的拟牛顿型方法来求解，并理论分析了该算法具有超线性收敛。将该方法应用到一个插入式充电车的分布式充电控制模型，并根据模型特点设计了相应的分布式拟牛顿型算法。另外，针对一类可和非凸分布式约束优化问题，采用序列凸逼近方法和罚函数方法，我们提出了一种分布式序列凸逼近方法。. 2） 针对一类具有可分结构的约束优化问题，基于Nesterov的光滑化方法和快速梯度算法，我们提出了一种快速对偶型梯度算法。同时我们也将该算法应用到：（i）基于用户满意度的分布式充电控制模型；（ii）一类虚拟电站的分布式优化模型；（iii）智能电网实时收费问题。. 3） 针对一类具有可和结构的分布式凸优化问题，我们设计一种分布式mirror下降算法，并分别考虑有向网络的通讯时延，通讯量化，通讯误差等情形。