一类不可微的NP-hard优化问题研究

Absolute value equations (AVE) Ax-|x| = b is a class of non-differentiable NP-hard optimization problem, proposed by Mangasarian in 2006. The researches on AVE at present are focuse mainly on two respects: the theory and the algorithm. The former mainly study the uniqueness and existence of solutions to the AVE; while the latter basically is to establish an effective algorithm and give the corresponding convergence analysis. First, by using some characteristics of the matrix, we establish the conditions of existence of the solution to the AVE. Then we construct an optimal objective function and directly solve large-scale AVE by non gradient-based algorithm. Second we establish some smoothing function to approximate absolute value equation, then translate the AVE into a smooth optimization problem, and solve by gradient-based algorithm. Finally we propose a hybrid algorithm for the AVE. The hybrid algorithm sufficiently possesses the characteristics of intelligent optimization algorithm’s group searching and gradient-based algorithm’s local strong searching. At the same time, the hybrid algorithm can overcome the problem of high sensitivity to initial point of gradient-based algorithm and improve the exploration and exploitation ability of intelligent optimization algorithm which reduces the searching efficiency in later period．The studies of the project can further extend the applications of new hybrid optimization algorithm, and has great significance in theory and practical application value in knapsack feasibility problem and boundary value problem of linear differential equation.

绝对值方程Ax-|x|=b是Mangasarian在2006年提出的一类不可微NP-hard优化问题。目前对于绝对值方程的研究主要集中在理论与算法两个方面, 一个是研究解的存在性和唯一性；另一个是建立有效的算法并进行相应的收敛性分析。本项目首先利用矩阵的一些特性来建立绝对值方程解的存在性条件；然后构造适当的优化目标函数，采用非梯度型算法直接求解大规模绝对值方程；其次构造一些光滑函数来逼近绝对值方程，进而转化为一个光滑优化问题，采用梯度型算法进行求解；最后结合智能优化算法的群体搜索性和梯度型算法的局部细致搜索性的优点，给出求解绝对值方程的混合算法，该混合算法能克服智能优化算法后期搜索效率降低和梯度型算法对初始点敏感的缺陷。该项目的研究能进一步扩展新型混合优化算法的应用范围，并在背包可行性问题与微分方程边值问题中具有重要的理论意义和实际应用价值。

线性规划和二次规划均可以转化为线性互补，而线性互补问题又可以转化为绝对值方程，因此目前对绝对值方程的研究便引起了众多学者的关注。绝对值方程是国际著名优化专家Mangasarian O. L.教授在2006年提出的一类NP-hard问题，绝对值方程等价于一个不可微优化问题。本项目主要研究内容：(1)研究了绝对值方程解的存在性条件，并分别构造了唯一解、多个解、无穷解及无解的算例；此外还研究了绝对值方程的稀疏解。(2)构造了绝对值函数的上方一致光滑逼近函数和下方一致光滑逼近函数，研究了这些光滑逼近函数的性质，并应用于具有唯一解的绝对值方程，建立了绝对值方程的光滑牛顿法。(3)针对存在多个解的绝对值方程，研究了解的结构，采于“聚类+智能优化算法”进行求解。(4)研究了几类智能优化算法，并应用于投资组合优化模型、纳什均衡、工程优化等问题。这些成果完善了绝对值函数的一致光滑逼近函数体系，丰富了绝对值方程的求解算法，提出了利用绝对值函数处理非线性规划中的不等式约束，为研究约束优化开辟了新的方向。这些研究是前沿性的，具有重要学术价值。