凸二次约束二次规划问题的鲁棒灵敏度分析研究

In this proposal, a new method of combined sensitive analysis and robust optimization is considered for the quadratically constrained quadratic programming problem with perturbation coefficients. This method aims at analyzing the maximum radius of perturbation coefficients to guarentee a pre-decision or some features of the pre-decision robustly optimal. The method provides a promising technique to evaluate the robustness and stability of an optimal control system, extends research areas of the robust optimization and the conic programming problems. We formulate binconvex semi-definite positive programs to get the maximum radium of the perturbation coefficients. Then this methodology is extended to the linear programming, nonconvex quadratically constrained quadratic programming and linear conic programming problems.

本项目以具有扰动系数的凸二次约束二次规划问题为背景，创新性地将鲁棒优化概念和灵敏度分析结合，对给定的一个决策或具有某些特殊结构的决策，在保持该决策鲁棒最优的前提下，分析和求解扰动参数的最大变化范围。这是分析优化控制系统稳定性的一个新方法。我们将通过双凸半定规划（biconvex semi-definite positive programming）模型来描述鲁棒灵敏度分析概念和计算最大变化范围。这将给双凸规划问题研究提供一个新的范例，为锥优化研究提供一个新的研究课题。相同的研究思路将推广到线性规划和非凸二次约束二次规划问题和线性锥规划问题中。

本项目的主要研究结果可归结为三部分。一、借鉴灵敏度分析的思想，创新性地提出以扰动数据变化范围的半径作为决策变量，就给定的决策方案，评价该方案能够满足扰动数据的最大变化半径的鲁棒灵敏度分析模型。从理论上，对于鲁棒线性规划问题，建立其鲁棒灵敏度分析模型，通过对问题中目标系数、约束方程的左右端系数单一或耦合扰动分类，分别给出等价的二阶锥或半定规划模型。基于鲁棒凸二次约束二次规划问题，将其等价地表示半定规划优化模型，通过投资效益组合问题，数值比对我们的模型的计算效率。在应用方面，就单个线性约束的混合整数二次规划机组组合问题，考虑电力需求的扰动，应用鲁棒灵敏度分析，采用共轭对偶原理设计凸松弛方法求解问题的下界，进一步实现分支定界算法，实验结果证实我们算法的计算效率远远高于一些经典优化商业软件。再考虑不确定环境下机组组合问题的启发式控制策略，采用最坏情形分析的方法，给出了一个O(nlog(n)) 复杂性启发式算法，并给出绝对差的紧界分析。二、针对非凸二次约束二次规划问题，提出了“关键特征根”的求解思想，设计了有效的全局优化算法。针对广义信赖域问题，在原问题与二阶锥和SDP松弛问题有相同最优目标值的前提下，给出了求解原广义信赖域问题全局最优解的方法。三、针对线性约束的lp(0<p<1)范数优化问题，从理论上给出一个新的scaled KKT定义，依此设计算法并通过数值实验验证了算法的有效性。针对多输入多输出（MIMO）信道检测问题，利用复变量的结构特点，设计有效的割平面策略，显著改进了半正定松弛方法的松弛下界。从理论上证明了：当问题信噪比高于某个给定的阈值时，改进的半正定松弛方法的松弛间隙一定等于零。针对含有辐角约束的复变量二次规划问题，设计基于变量极坐标表示的分支定界算法。