非线性机会约束半定规划的数值算法理论与实现

Many practical problems such as signal engineering, wireless network and military random target striking can be reduced to chance constrained semi-definite programming (SDP). Current researches mainly focus on linear or linearly perturbed chance-constrained SDP and theoretical convergence results are found in literatures. Therefore, the research of numerical methods for nonlinear chance-constrained SDP is significant valuable..This project aims to study the numerical algorithm for chance-constrained SDP based on sequentially convex and smooth (or semi-smooth) approximation. The main contents include: According to the subdifferential characterization of the probability function, studing the first order necessary conditions and the constraint qualification; utilizing the D.C. decomposition to construct sequentially convex approximation of the original problem; based on spectral functions and their smoothing approximation, constructing the smooth approximation of the original problem; according to the theory of variational analysis and perturbation analysis, proving the convergence of the KKT-point sets of the constructed approximate problem; by combining the SAA algorithm and sequentially convex-smooth (or semi-smooth) approximation, studying effective numerical algorithms for solving chance-constrained SDP and implementing numerical experiments.. The main innovation of the project is that the optimality theory is studied based on the subdifferential characterization of the probability function， and D.C. decomposition and smoothing spectral function are applied into solving chance-constrained SDP problem. The convergence of the constructed algorithm, which aims at nonlinear chance constrained SDP problems, can be guaranteed.

诸如信号工程，无线网络布局，军事随机目标打击等许多实际问题都可归结为机会约束半定规划（SDP）。而目前的研究多集中于线性或线性扰动的该类问题，且算法缺乏理论上的收敛性结果。因此研究非线性机会约束SDP问题的数值算法有重要意义。.本项目拟研究基于半光滑与光滑序列凸近似求解非线性机会约束SDP问题的算法理论与实现。主要包括：依据概率函数的次微分刻画，研究问题一阶必要性条件与约束规范；利用D.C.分解构造问题的序列凸近似；依据谱函数光滑化构造问题的光滑近似；证明构造的序列近似问题的KKT点集收敛性；结合SAA算法与光滑序列凸近似，构造求解非线性机会约束SDP问题的有效数值算法，并进行数值实验。本项目的创新之处在于：首次基于变分分析理论，研究机会约束SDP问题的最优性理论，利用D.C.分解与谱函数的光滑化，处理问题的非凸非光滑性。针对非线性该类问题构建的序列近似算法有理论的收敛性保证。

诸如信号工程，无线网络布局，军事随机目标打击等许多实际问题都可归结为机会约束半定规划（SDP）。而目前的研究多集中于线性或线性扰动的该类问题，且算法缺乏理论上的收敛性结果。因此研究非线性机会约束SDP问题的数值算法有重要意义。.本项目研究了半定机会约束规划问题的光滑化近似与序列凸化近似的数值求解方法。主要利用约束的DC分解与基于谱函数的光滑化，构造了研究问题的光滑化DC近似。进一步利用序列凸近似方法与SAA算法来有效求解光滑化的DC近似问题。在矩阵值随机函数几乎处处凸且连续可微、复合最大特征值随机函数对应的累积分布函数Lipschitz连续等合理的假设条件下，我们证明了近似约束函数，近似问题的可行域，最优值与最优解集到原问题约束函数，可行域，最优值与最优解集的收敛性质。再结合SAA算法的渐进收敛性结论，得到了本项目构造的数值算法的整体收敛性理论。数值实验验证了构造算法对算例的有效性。这一研究成果为半定规划问题在更广泛的非确定数据条件下的应用，提供了可行的算法理论与有力的计算工具。.与该项目研究问题相关的，我们也在变分不等式误差界及随机变分不等式的SAA算法求解、包括束方法在内的求解非光滑问题的方法及其在模糊关系约束规划的应用等方面，取得了一系列的相关成果。这些成果极有可能在网络数据传输等方面有一定的应用前景。