DC规划的理论和算法研究及其在机器学习中的应用

DC programming (where both the objective function and constraints are DC functions) problems are in general nonconvex and nonsmooth. DC programming is widely applied in engineering, economics, management and artificial intelligence etc. The existing optimality conditions are mainly described through the Clark subgradient, and most of them are hardly to be verified; the algorithms for solving DC programming problems can be roughly classified as convex analysis type and combinatorial type, and the convex analysis type algorithms normally can only obtain local solutions, the combinatorial type algorithms can obtain global solutions, however, they are hardly useful for large scale practical problems. In this project, based on the preliminary work in DC programming and related areas by the project team, we aim to investigate the methods to convert a nonconvex problem into a DC programming problem, the DC approximating methods, and the more reasonable convex decomposition structure for DC programming; to investigate new subgradient concepts and properties as well as simple approximating functions based on the convex decomposition structure, and furthermore, to investigate new optimality conditions for DC programming, especially verifiable global optimality conditions; to design new optimization algorithms for DC programming, especially global optimization algorithms for solving large scale practical problems; to develop new penalty function methods for constrained DC programming problems based on the special structure of the DC programming; to propose new theories and methods for solving some optimization problems arising in machine leaning via the obtained research results.

DC规划（目标和约束都是DC函数的优化问题）一般是非凸非光滑的，其应用广泛见于工程、经济、管理、人工智能等领域。现有DC规划的最优性条件主要通过Clark次梯度刻画，但绝大多数都很难验证；算法主要有凸分析类和组合类，凸分析类算法往往只能求得局部最优解，组合类算法虽可求得全局最优解，但很难解决大规模实际问题。本项目将基于项目组成员在DC规划及相关领域的前期研究基础，研究非凸规划的DC化方法、DC近似逼近法及更合理的DC凸分解结构；利用DC凸分解结构研究其新的次梯度概念及性质、新的近似简单逼近函数，进而研究DC规划的新的最优性条件，特别是一些可验证的全局最优性条件；利用所得到的最优性条件设计DC规划的新的最优化算法，特别是一些能解大规模实际问题的全局最优化算法；利用DC规划的特殊结构研究新的求解约束DC规划的罚函数方法；利用所得到的研究成果，为求解机器学习中的一些优化问题提供新的理论和方法。

本项目组成员在DC规划及相关领域的前期研究基础上，充分深入研究了非凸规划的DC化方法、DC近似逼近法及更合理的DC凸分解结构；利用DC凸分解结构研究其新的次梯度概念及性质、新的近似简单逼近函数，进而研究DC规划的新的最优性条件， DC规划的新的最优化算法，以及运用DC规划来解决机器学习中的问题。本项目开展至今，对以上内容进行充分深入研究，取得了较好的理论成果，发表论文30篇，并将理论与实际问题相结合，横向课题15项，同时，为促进学术沟通与交流，项目负责人主办全国性会议4次，项目负责人作为主要负责人之一承办全国性会议1次，本项目开展至今，也培养本科生73名，培养硕士研究生28名，培养博士研究生3名，已圆满完成预设的项目结题要求。