一类特殊多项式整数规划问题的最优化算法(英文)

考虑一类特殊的多项式整数规划问题.此类问题有很广泛的实际应用,并且是NP难问题.对于这类问题,最优性必要条件和最优性充分条件已经给出,利用这些最优性条件设计最优化算法.首先,利用最优性必要条件,给出一种新的局部优化算法.进而结合最优性充分条件、新的局部优化算法和辅助函数,设计新的全局最优化算法.给出的算例展示算法是有效的和可靠的.

次梯度法在求解非光滑最优化问题时的计算效果研究(英文)

本文研究了次梯度法的一些重要问题。次梯度法是梯度法在非光滑优化中的直接推广。在每一步的迭代中,选取一个负次梯度方向为搜索方向,并以一定的规则设置搜索步长。次梯度法的每一步迭代不一定都下降,但是可以证明,对于非光滑凸优化问题,次梯度法能够保证全局收敛性。次梯度法的搜索步长是预先设置的,步长设置准则包括常值步长准则、有限平方和步长准则和已知全局极小值的步长准则。本文对各种步长准则的收敛性进行了证明。为了验证次梯度法在不同的步长准则下的计算效果,本文应用次梯度法对一系列非光滑最优化问题进行了计算实验,并分析了他们的计算结果。数值实验结果表明,常值步长准则收敛速度慢,精度不高,而且步长的选择困难。而有限平方和步长准则收敛速度更快,也能够达到更高的精度。至于已知全局极小值的步长准则,虽然精度也较高,但是因为需要事先已知凸优化问题的全局极小值,所以这种步长准则的应用范围有限。

基因算法在求解非光滑优化问题中的应用(英文)

本文考虑了基因算法在求解非光滑优化问题中的应用。非光滑优化方法致力于求解目标函数为连续不可微函数的数学规划问题。因为目标函数的不可微性,传统的以梯度为基础的确定性算法在求解非光滑问题时会遇到障碍,所以运用不需要梯度信息而只需要目标函数值信息的遗传算法来求解非光滑问题是一个不错的选择。遗传算法是基于自然界生物遗传变异过程而设计的一种优化算法,它首先对问题的可行解进行编码,编码方法有0-1编码,格雷编码和实数编码,然后运用交叉算子,变异算子和选择算子产生下一代种群。当种群迭代达到一定的次数后,种群中的最优染色体就会收敛到原问题的最优解。本文设计的基因算法基于实数编码,算子分别采用算术交叉算子,非一致变异算子,最佳选择算子。