大规模互补约束数学规划的信赖域算法研究及应用

Mathematical programs with complementarity constraints (MPCC) is an optimization problem whose constraints include the complementarity problems. It is a difficult problem because of its special feasible region structure. On the other hand, the problem can be found in some engineering fields. Hence, the MPCC becomes a research focus. All above make the problem be worthy for us to research, especially for the large scale case. The main points of our research are as following, (1) We will construct an algorithm based on the trust-region SQP.method and the subspace method and we analyze its convergence. In addition, and numerical results will be presented. (2) We will give an algorithm combining trust region method with qusi-Newton method based on the large scale constrained equations. It will help us to the find the stationary point of the original problem conveniently. Global and local convergence will be considered. (3) We will research a new way to solve absolute value equations(AVE) by transforming the original problem into MPCC form. We also analyze the connection between the two problems and applied the algorithm gotten above to solve it. (4) By applying the theories and methods of the MPCC, we will obtain the values of some parameters arising from the support vector machine problems. The work includes constructing the MPCC type model for the corresponding problems and getting the numerical results by a suitable algorithm.

互补约束数学规划(MPCC)是一类约束中包含互补问题的特殊数学规划，传统的优化理论和算法不能直接应用到研究该问题。同时，互补约束数学规划有着良好的工程应用背景，因而该问题成为优化领域的研究热点之一。另一方面，随着实际问题规模的增大，对大规模互补约束数学规划的算法研究也越显必要。本项目主要研究内容包括： (1) 结合信赖域二次规划和子空间技巧，构造求解大规模互补约束数学规划的子空间算法，并完成收敛性分析及数值试验。(2) 基于大规模约束方程组模型，给出结合拟牛顿法的信赖域算法，进而获得原问题的各稳定点，讨论算法的全局和局部收敛性。(3)在互补约束数学规划框架下研究绝对值方程问题的求解新算法。分析相关问题解之间的关联性，并拟应用前述研究构造相应算法。(4) 建立求解支撑向量机问题中各类参数及相关问题的互补约束数学规划模型，分析模型性质，并基于新模型构造数值算法。

互补约束数学规划(MPCC)是一类约束中包含互补问题的特殊数学规划，传统的优化理论和算法不能直接应用到研究该问题。本申请项目旨在研究信赖域框架下的大规模互补约束数学规划的算法及在其他问题上的应用。 主要完成研究内容有：(1) 对于互补约束规划问题，基于光滑隐函数逼近模型的及其罚函数构造了求解原问题的信赖域算法，证明了算法的全局收敛性； (2) 给出了绝对值方程问题的一类新的基于互补约束数学规划形式的等价刻画模型，并以新模型构造了有效投影Barzilai-Borwein梯度求解算法；(3)对于矩阵非负分解问题，构造了基于罚信赖域方法和交替最小二乘框架下的算法， 同时采用随机奇异值分解获的相应左右投影矩阵来减小原始运算矩阵维数； (4) 对于聚类分析中特征子空间距离度量选取问题，提出了基于信息熵的加权马氏距离及采用随机梯度法获得参数和聚类中心的策略构造了一改进的DEC算法；(5)对于聚类分析算法，提出了基于自然最近邻密度峰值聚类算法；（6）提出了鲁棒主成分分析问题基于l_p（0<p<1)范数的非凸改进模型，当p=1/2，证明了收敛点为原问题的KKT点。并采用交替方向乘子法求解相关非凸模型。以上研究内容对互补约束规划问题算法补充及对信赖域方法的应用有一定理论意义，同时为相关应用背景问题提供一些新的求解途径。