均衡约束数学规划问题的几个算法及其在机器学习中的应用

Mathematical program with equilibrium constraints (MPEC) is a class of special mathematical program which has wide applications in many fields,we shall study the algorithms for solving MPEC and their applications in machine learning. The main contents are listed as follows:.(1) Based on pseudo Huber function, we propose a locally smoothing method for the large scale MPEC, which only locally smooths the complementarity constraints. Without the second order necessary condition, we analyze the strong convergence behavior of the smoothing method under the weaker condition than MPEC-LICQ；.(2) We shall propose a potential reduction Newton method for solving MPEC. By this method, the penalty subproblem can be solved efficiently. And under the weaker condition than MPEC-LICQ, we shall discuss its strong convergence property;.(3) Based on the lower order penalty function, we shall introduce an interior point l_1/2 penalty method for MPEC. Its computational accuracy will be improved, and the times of inner loop will be little. Its convergence property will be investigated under the weaker condition than MPEC-LICQ;.(4) For the feature selection in machine learning, we shall propose the MPEC model which is suitable for the large scale problems,and the objective function is separable. Lastly we apply the above methods to solve the MPEC model..For the above algorithms, we will report the numerical results to show their efficiency.

均衡约束数学规划问题(MPEC)是一类具有广泛应用背景的特殊数学规划，本项目研究求解MPEC的算法及其在机器学习中的应用，具体研究内容如下:.(1)提出基于pseudo Huber函数适合于大规模问题的部分光滑化算法，对均衡约束进行部分光滑化近似，在不用二阶必要条件且比MPEC-LICQ弱的假设条件下讨论算法的强收敛性；.(2)提出求解MPEC问题的势缩减牛顿算法，该算法能有效求解罚子问题，并在比MPEC-LICQ弱的条件下考虑强收敛性质；.(3)提出基于低阶罚函数的内点l_1/2罚算法，使其具有较好的计算精度和较少内循环次数，并在比MPEC-LICQ弱的条件下讨论该算法全局收敛性;.(4)针对机器学习中的特征选择问题，给出一个适合大规模问题且目标函数具有可分结构的MPEC模型，并用上述方法求解。.对以上算法均给出数值结果验证算法有效性。

均衡约束数学规划问题(MPEC)是一类特殊数学规划问题，它在电力交通网络管理、经济博弈和最优设计等领域都有广泛应用.本项目研究求解MPEC问题的算法及其相关理论结果,具体研究内容如下:.(1)研究MPEC问题的求解方法和精确罚结果..(a)提出了求解MPEC问题的基于凝聚函数的部分光滑化方法，该算法只部分光滑化均衡约束,在较弱的MPEC-CCP条件下证明了光滑近似问题解序列的聚点是原问题MPCC的M稳定点. .(b)在伪正则和非严格极小点条件下得出了一般约束问题和MPEC问题的精确罚结果.改进了D.P.Bertsekas,A.E.Ozdaglar(2002)和C.Kanzow,A.Vath(2010)的工作..(c)基于原始对偶增广拉格朗日函数,提出了求解MPEC问题的广义部分增广拉格朗日算法,利用改善的对偶变量估计值,减少子问题求解次数..(d)基于低阶罚函数的思想, 提出了均衡约束优化问题的非光滑内点l_1/2罚方法,证明了算法迭代序列的极限点是S-稳定点..(2)研究多目标锥规划的高阶对偶理论和互补问题解的性质..(a)对多目标锥规划的高阶Wolfe对偶问题建立了一个新的高阶逆对偶定理,该结果改进Kim等(2010)的工作..(b)提出了非线性互补问题的一个新的广义例外族,给出了互补问题有解的充分条件..(c)利用例外族的概念研究了半定互补问题解集的有界性与非空性..(3)研究消失约束数学规划问题(MPVC)的对偶理论与精确罚结果..(a)给出了MPVC问题的Wolfe对偶和Mond-Weir对偶的改进模型，该模型不涉及未知指标集的计算,克服了Mishra等(2016)提出的对偶模型的缺陷..(b)通过引入MPVC问题的F-J条件,提出了几个新的MPVC型约束规格,在新的约束规格下讨论了MPVC型罚函数的精确性. .(4)研究无约束优化问题的求解方法.提出了求解无约束优化问题的改进的PRP共轭梯度法、改进记忆梯度算法和改进的无线搜索共轭梯度算法.