网络通讯中的优化模型与近似束方法的计算研究

Many practical problems arising from information and computing science (for example, problems for optimizing telecommunication network performance) are nonsmooth optimization problems. Bundle algorithms are one of promising methods for solving these problems, and are of great importance in both theory and practice. In view of the basic assumptions of bundle algorithms that function value and one arbitrary subgradient are available at any point and the inexactness of data acquisition, the construction of optimization model with the help of approximate computation and the investigation of theory and implementable algorithms of inexact bundle method are of necessity. The main research work includes: (1)Construct theoretical framework for inexact bundle method and define nonnegative effective decrease to establish the test criterion for serious step by employing the so called UV decomposition theory. (2)Construct general optimization model for multicommodity flow by utilizing inexact information, and by combining subgradient deletion rules with subgradient locality measures we not only redefine linearization errors,construct effective algorithms, but also discuss the rate of convergence. (3)Apply the obtained results to several practical problems, which includes: solve variational inequality problems, solve special types of mathematical programs with equilibrium constraints, study the multicommodity flow problem occurred in telecommunication data networks. The results of this project have more practical value than exact bundle methods, and will promote the study of theory and numerical computational methods for information network optimization.

信息计算科学中的许多问题（如优化电信网络服务质量问题）均是非光滑优化问题，束算法是解决这类问题最具前景的方法之一，具有重要的研究价值。考虑到束方法需要获取任意一点的函数值和一个次梯度值的基本要求和实际操作中数据采集的非精确性，通过近似计算获取的优化模型与可执行高效非精确束算法的研究变得十分必要。主要内容包括：(1)利用分解理论构造近似束方法的理论框架，定义有效非负下降，建立下降步检验准则。(2)利用非精确信息构建涵盖电子通讯中多种物资流问题的一般优化模型，结合次梯度删除、度量准则，重新定义线性化误差，构造有效数值算法，讨论收敛速度。(3)将取得的成果用于解决实际问题，如，求解变分不等式问题；求解特殊均衡规划问题；求解源于通讯数据网络的多种物资流问题。本课题取得的成果比精确束方法更具实际应用价值，对信息网络优化理论与数值计算方法的研究会起到促进作用。

在自然科学和现代电子通讯技术中有重要研究价值和应用意义的数学模型中都出现了非光滑函数，这类问题统称为非光滑问题，具有重要的理论意义和实际研究价值。优化电信网络服务质量问题就是一种非光滑优化问题，束算法是解决这类问题最具前景的方法之一，具有重要的研究价值。考虑到束方法需要获取任意一点的函数值和一个次梯度值的基本要求和实际操作中数据采集的非精确性，通过近似计算获取的优化模型与可执行高效非精确束算法的研究变得十分必要。本项目主要内容包括：构造近似束方法的理论框架，定义有效非负下降，建立下降步检验准则；利用非精确信息构建一般近似模型，重新定义线性化误差，构造有效数值算法，讨论收敛速度；将取得的成果用于解决实际问题，如，CVaR投资组合问题、源于通讯数据网络的优化问题。.取得的结果如下：.（1）构建一般的非精确信息采集平台，明确函数非精确信息与优化问题近似最优解之间的牵制关系，将函数的近似信息融入到不同类型的下降定义中，并应用于停止准则。.（2）对基于CVaR投资组合优化问题，着重研究不可行束方法。应用拉格朗日函数和对偶理论，获得试探点的显式表达，构造基于原问题改进函数的一个下近似模型，提出新的下降步检验准则，理论分析表明算法在较弱条件下仍然具有较好的收敛性。.（3）多目标非光滑DC优化问题。根据帕累托最优性条件构建改进函数, 利用DC分量位于稳定中心附近的次梯度信息，分别构建DC分量函数的近似模型，凸化参数自动调整可以保证增广线性化误差非负，提出的的重新分配迫近束算法产生的点列收敛到Clarke稳定点。.（4）关于通信数据网络优化问题的研究。利用函数的非精确信息，构建通信数据网络优化问题的近似模型，利用惩罚束方法和指示函数对通信数据网络优化问题的近似模型展开研究，给出原问题与对偶问题的最优解的显式表达式，得到了非精确近似优化模型的相关结论，对该问题的研究已经延伸到整体算法的构造和算法的收敛性分析。