非凸优化问题的全局优化算法

全局最优化问题广泛见于经济模型,金融,网络交通,数据库,集成电路设计,图象处理,化学工程设计及控制,分子生物学,环境工程学等等.因为存在多个不同于全局最优解的局部最优解,而传统的非线性规划方法都只能求其局部最优解,所以不能顺利地应用于求解全局最优化问题.在过去的几十年里,由于全局最优化在许多领域的重要应用,其理论和方法已经得到了很大的发展.这些方法主要包括确定性方法和随机方法. 本文给出了求解几类非凸优化问题的全局优化算法.第一章,概述了目前国内外几种主要的全局最优化确定性方法.第二章,讨论凸集上的线性乘性规划(LMP)的全局优化解法.在2.2节,首先利用合适的变化,可以将问题(LMP)转化为等价的参数凸规划、参数凹最小化问题或参数D.C.规划,并能利用凸规划与单变量搜索方法求解此线性乘性规划问题,再次,给定的非空紧凸集,能构造一个具有局部极大点不是全局最大点的线性乘性规划测试问题.在2.3节通过引入辅助变量,将问题(LMP)转化为一个等价的非凸优化问题,再利用双线性函数的凸包络构造等价问题的线性松驰规划.在2.4节利用单纯形分支与对偶界算法在细分集上解一系列线性规划来求线性乘性规划问题的全局最优解.分支只发生在p-维实空间,p是线性乘性规划的目标函数的项数,在搜索过程中,下界是通过解普通的线性规划求得,这些线性规划是利用非线性规划的Lagrangian弱对偶定理构造得到的,并且可以利用线性规划的最优对偶解计算得到原问题的一个可行解.第三章讨论一类具有指数的线性乘性规划问题(MPE)的全局优化算法.在3.2节提出加速收敛的全局优化方法——删除技术,即删除不存在全局最优解的可行域.在3.3节,利用对数变换将问题(MPE)转换为一个等价的非线性优化问题,并利用参数线性化方法在细分集上将等价问题转化为一系列线性松驰规划,并利用分支定界法求得问题(MPE)的全局最优解.在3.4节,经过的变换将原问题的非线性函数转化为D.C.函数,再利用新的线性化方法将(MPE)转化为一系列线性规划.第四章讨论凸集上的D.C.乘性规划的全局优化算法,首先通过引入辅助变量将D.C.乘性规划问题转化为一个等价的D.C.规划问题,再综合利用分支定界与外逼近求解等价问题.第五章利用分支定界与线性规划求解可微凹-凸分式规划的全局最优解,5.2节将说明如何将可微凹-凸分式规划问题转化一个等价的非线性规划问题；在5.3节,讨论如何利用双线性函数凸包络与二次函数的特殊性质构造等价问题的松弛线性规划；并利用分支定界法求得原问题的全局最优解.第六章,提出利用两阶段参数线性化技术求解广义线性分式规划的全局优化算法.在6.2节,我们将呈现如何利用两阶段参数线性技术构造松驰线性规划问题.在6.3节,提出求解广义线性分式规划的分支定界算法并证明其收敛性.