多目标规划问题（Multi-object Programming Problem）,简称MPP,是类有着重要应用的优化问题。它在许多经济和工程领域都有十分重要的应用,因而其研究越来越受到人们的广泛关注。然而,这类问题的研究却非常复杂。它不同于单目标规划问题,针对单目标规划问题的成套理论对多目标规划问题并不适用。因此,近几年人们从理论到算法对MPP展开了全面的研究。理论上,人们主要集中于建立一套平行于单目标规划问题的理论,而且取得了不少成果。算法上,虽然人们进行了大量的研究,但很有效的算法并不多。本文的贡献是在适当的条件下,提出了求解多目标规划问题（MPP）的路径与隧道跟踪算法并研究其收敛性,扩大了利用组合同伦方法求解非凸域上多目标规划问题的范围。全文共分四章：第一章：概述了多目标规划问题在理论和算法方面的研究现状和遇到的困难。同时,对同伦方法的发展过程和取得的进展进行了简要描述。第二章：概述了本文涉及到的多目标规划问题的主要理论。第三章：研究了非凸域上多目标规划问题的路径跟踪算法。本章考虑的多目标规划问题如下：首先,对于多目标规划问题的求解,考虑到路径跟踪算法在求解优化问题方面的优势,在法锥条件下提出了求解这类问题的路径跟踪算法,建立相应的同伦方程并证明了其同伦路径的存在性和大范围收敛性。其次,针对法锥条件下求解这类问题的路径跟踪算法的缺点,结合（弱）拟法锥的特点又分别提出了在拟法锥条件、修正拟法锥条件和修正弱拟法锥条件下求解多目标规划问题的路径跟踪算法,并在较弱的条件下证明了同伦路径的存在性和大范围收敛性。与法锥条件下的路径跟踪算法相比,拟法锥条件、修正拟法锥条件和修正弱拟法锥条件下的路径跟踪算法扩大了组合同伦内点算法求解非凸域上多目标规划问题的范围,且所给条件更弱。如果存在（x,λ,,u,z）∈Ω×R+p+m×Rs,满足宋文等人[83]提出了法锥条件下求解多目标规划问题的组合同伦内点法,建立了和KKT系统直接相联系的同伦方程。假设条件：组合同伦方程构造如下文献[59]中给出了“正线性独立”的定义。为了把它拓广到非凸多目标规划问题上,同时削弱文献[83]中的假设条件,首先对不等式约束部分做了一定的工作,引入拟法锥意义下的“正线性独立映射”,随后又兼顾考虑等式约束部分,提出了修正拟法锥条件,然后,分别在不同的假设条件下构造了新的同伦方程。假设条件Ⅰ：（B1）Ω0非空有界；（B2）对任意的x∈Ω和t∈[0,1],存在关于（?）g（x）和（?）h（x）的正线性独立映射（?）η（x）,使得{ηi（x）：i∈B（x）}关于（?）g（x）和（?）h（x）是正线性独立的；（B3）对任意的x∈（?）Ω,存在关于（?）g（x）和（?）h（x）的正线性独立映射η（x）,使得（拟法锥条件）注如果Ω满足假设条件（A1）-（A3）,则一定满足假设条件（B1）-（B3）。事实上,若令η（x）=（?）g（x）,则很容易得到结论。为了求解拟法锥条件下的KKT系统（1a）-（1c）,构造组合同伦方程如下：定理1设f,g和h是三次连续可微的函数,假设条件（B1）-（B2）成立,并且ηi,βj是二次连续可微的函数,则对于几乎所有的初始点ω（0）∈Ω0×∧++×R++m×{0},0是Hω（0）的正则值,且Hω（0）-1包含一条起始于（ω（0）,1）的光滑曲线Γω定理2假设条件（B1）-（B2）成立,对于给定的ω（0）=（x（0）,λ（0）,u（0）,z（0））∈Ω0×∧++×R++m×{0},如果0是Hω（0）的正则值,那么λ有界。定理3设f,g和h是三次连续可微的函数,假设条件（B1）-（B3）成立,并且ηi,βj是二次连续可微函数。则对于几乎所有的初始点ω（0）∈Ω0×Λ++×R++m×{0},Hω（0）-1（0）包含一条起始于（ω（0）,1）的光滑曲线Tω（0）（？）Ω×R+p×R+m Rs×(0,1]。当t→0时,Γω（o）的极限集合T×{0}（?）Ω×Λ+×R|m×Rs×{0}是非空的。特别的,如果rω（o）是有限的,并且（ω*,0）是rω（o）的终点,那么ω*是KKT系统（1a）-（1c）的解。定理4同伦路径Γω（0）由下面的常微分方程初值问题确定：ω（0）=ω（0）,t（0）=1,对于t（s*）=0,ω*是KKT系统（1a）-（1c）的解。假设条件Ⅱ：（C1）Ω0非空有界；（C2）对任意的x∈Ω和t∈[0,1],存在映射η（x）和β（x）,使得{（?）gi（x）,ηi（x）：i∈B（x）}关于（?）h（x）+t（β（x）-（?）h（x））是正线性独立的；{x}；（修正的拟法锥条件）（C4）对任意的x∈Ω,（?）h（x）Tβ（x）非奇异。注若Ω满足假设条件（A1）-（A3）,则它必满足假设条件（C1）-（C4）。事实上,如果选择η（x）=（?）g（x）和β（x）=（?）h（x）,则很容易得出以上结论。修正拟法锥条件下,构造的组合同伦方程如下：H（ω,ω（0）,t）=当t=1时,同伦方程化为由假设条件（C3）,可以得到z=0,x=x（0）。由于g（x（0））<0和x=x（0）,（c）意味着u=u（0）。再根据（d）,可以得到λ=λ（0）。即,方程H（ω,ω（0）,1）=0关于ω有唯一的解ω=ω（0）=（x（0）,λ（0）,u（0）,0）。当t=0时,H（ω,ω（0）,t）=0就转变为KKT系统（1a）-（1c）。对于给定的ω（0）,将H（ω,ω（0）,t）重新记为Hω（0）（ω,t）.将Hω（0）的零点集合记为Hω（0）-1={（ω,t）∈Ω×R+-p+m×Rs×(0,1]:H（ω,ω（0）,t）=0}。定理5设f,g和h是三次连续可微的函数,假设条件（C1）-（C2）成立,并且ηi,βj是二次连续可微函数,则对于几乎所有的初始点ω（0）∈Ω0×Λ++×R++m×{0},0是Hω（0）的正则值,并且Hω（0）-1构成一些光滑曲线。其中,存在一条起始于（ω（0）,1）的光滑曲线,记为Γω定理6假设条件（C1）-（C2）成立。对于给定的ω（0）=（x（0）,λ（0）,u（0）,z（0））∈Ω0×Λ++×R++m+×{0},如果0是Hω（0）的正则值,那么λ是有界。定理7设f,g和h是三次连续可微的函数,假设条件（C1）-（C4）成立,并且ηi,βj是二次连续可微函数,则对于几乎所有的初始点ω（0）∈Ω0×Λ++×R++m×{0},Hηω（0）-1（0）包含一条起始于（ω（0）,1）的光滑曲线Tω（0）（?）Ω×R|p×R+m×Rs×(0,1]。当t→0时,Γω（0）的极限集合T×{0|（?）Ω×Λ+×Τ+M×rS×{0}是非空的,并且T内的任何一点都是KKT系统（1a）-（1c）的解。定理8同伦路径Γω（0）由下面的常微分方程初值问题确定：ω（0）=ω(0,T（0）=1,对于t（s*）=0,ω*是KKT系统（1a）-（1c）的解。为了拓广已有的结果到更一般的非凸域上的多目标规划问题,削弱非凸约束区域的限制,我们定义了修正的弱拟法锥条件。只需要构造的锥与可行域内的某个子集Ω10的交集为空即可,由此拓广了组合同伦内点法求解多目标规划问题的范围。从而进一步拓广了路径跟踪算法求解多目标规划问题的范围。假设条件如下（G1）Ω10非空有界,Ω10cΩ0；（C2）对任意的x∈Ω和t∈[0,1],存在映射η（x）和β（x）,使得{（?）gi姨（x）,ηi（x）：i∈B（x）}关于（?）h（x）+t（β（x）-（?）h（x））是正线性独立的；{x}；（修正的弱拟法锥条件）（C4）对任意的x∈Ω,（?）h（x）Tβ（x）非奇异。为了求解修正弱拟法锥条件下的KKT系统（1a）-（1c）,构造组合同伦方程如下：H（ω,ω（0）,t）=其中ω（0）=（x（0）,λ（0）,u（0）,z（0））∈Ω10×Λ++R++m×{0},ω=（x,u,z）∈Ω×Rp+m+s,u2=（u12,u22…,um2）T∈Rm,λ5/2=（λ15/2,λ25/2,…,λp5/2）T∈Rp, U=diag（u）,e=（1,1,…,1）T∈Rp和t∈[0,1].定理9设f,g和h三次连续可微函数,假设条件（C1）-（C2）成立,并且ηi,βj岛是二次连续可微函数,则对于几乎所有的初始点ω（0）∈Ω12×Λ++×R++m×{0},0是Hω（0）的正则值,并且Hω（0）-1包含一些光滑曲线。其中,一条起始于（ω（0）,1）的光滑曲线记为Γω（0）。定理10假设条件（C1）-（C2）成立,对于给定的ω（0）=（x（0）,λ（0）,u（0）,z（0））∈Ω0\10×Λ++×R||m×{0},如果0是Hω（0）的正则值,那么λ有界。定理11设f,g和h是三次连续可微函数,假设条件（C1）-（C4）成立,并且ηi,βj是二次连续可微函数。则对于几乎所有的初始点ω（0）∈Ω10×Λ-+×R-+m×{0},Hω（0）-1（0）包含一条起始于（ω（0）,1）的光滑曲线Tω（0）（?）Ω×R|p×R+m×Rs×(0,1]。当t→0时,Γω（0）的极限集合T×{0}（?）Ω×Λ+×R|m×Rs×{0}是非空的,并且T内每一个点是KKT系统（1a）-（1c）的解。定理12同伦路径Γω（0）由下面的常微分方程初值问题确定：对于t（s*）=0,ω*是KKT系统（1a）-（1c）的解。第四章：研究多目标规划问题的隧道跟踪算法。我们真心希望的是利用同伦方法这一工具,寻求一个能求得多目标规划问题有效解（弱有效解）集的隧道跟踪算法。试图求得多目标规划问题的部分或全部有效解（弱有效解）。本章共分为两部分：第一部分主要研究凸多目标规划问题的隧道跟踪算法。凸多目标规划问题的模型如下：其中f=（f1,f2,…,fp）T:Rn→Rp,g=（g1,g2,…,gm）T:Rn→Rm是凸函数。假设条件如下：（H1）Ω0非空且有界；（H2）（?）x∈（?）Ω,{▽gi（x）|i∈B（x）}是线性独立的。如果存在（x,λ,u）∈Ω×R+p+m,满足其中▽f（x）=（▽f1（x）,…,▽fp（x））∈Rn×p,▽g（x）=（▽g1（x）,…,▽gm（x））∈Rn×m。则称x是（2）的KKT点,（a）-（c）就是（2）的KKT系统。为了求解KKT系统（a）-（c）,构造组合同伦方程如下其中ω（0）=（x（0）,u（0））∈Ω0×R++m,λ（0）∈Λ++,ω=（x,u）∈Ω×R+m,λ∈R+m,t∈[0,1]。记H（ω,ω（0）,λ,t）为Hω（0）（ω,λ,t）,对于一个给定的ω（0）,Hω（0）的零点集合是H-1（0）={（ω,ω（0）,λ,t）|H（ω,ω（0）,λ,t）=0}。并记Hω（0）-1（0）={（ω,λ,t）|Hω（0）（ω,λ,t）=0}。定理1设f,g∈Cr（r≥3）是凸函数,且Ω0≠（?）,则对于几乎所有的初始点ω（0）∈Ω0×R++m,0是Hω（0）的正则值,并且Hω（0）-1（0）包含一个起始于（ω（0）,λ,1）的光滑流形（简称同伦隧道）,记作Vω（0）。定理2设f,g∈Cr（r≥3）是凸函数,并且假设条件（H1,H2）成立。对于给定的ω（0）∈Ω0×R++m,如果0是Hω（0）的正则值,则Vω（0）是一个有界光滑遂道。定理3设f,g∈Cr（r≥3）是凸函数,并且假设条件（H1,H2）成立,则（2）有解。对于几乎所有的初始点ω（0）∈Ω0×R++m,Vω（0）是包含一个起始于（ω（0）,λ,1）的同伦遂道。当t→0时,Vω（0）的极限集合S×{0}（?）Ω×R+m×Λ+×{0}非空,并且S内的每一点都是（2）的一个解。特别的,如果Vω,（0）有限,并且（ω,λ,0）是Vω（0）的极限点,则（ω,λ）是（2）的解。定理4同伦隧道Vω（0）的每一条起始于（ω（0）,λ,1）的曲线Tω（0）,由以下微分方程的初值问题决定：t（0）=1,λ=λ,ω（0）=ω（0）如果t（s*）=0,则（ω*（s）,λ（s））是（2）的解。第二部分主要研究非凸域上多目标规划问题的隧道跟踪算法。首先,考虑仅含有不等式约束的多目标规划问题模型：其中f=（f1,f2,…,fp）T:Rn→Rp,g=（g1,g2,…,gm）T:Rn→Rm假设条件如下：（A1）Ω0非空有界；（A2）（?）x∈Ω,{▽gi（x）,i∈B（x）}线性独立;如果存在（x,λ,u）∈Ω×R+p+m,满足其中▽f（x）=（▽f1（x）,…,▽fp（x））∈Rn×p,▽g（x）=（▽g1（x）,…,▽gm（x））∈Rn×m。则称x是（4）的KKT点,（a）-（c）就是（4）的KKT系统。为了求解KKT系统（a）-（c）,构造组合同伦方程如下：其中ω（0）=（x（0）,u（0））∈Ω0×R++m,λ（0）∈Λ++,ω=（x,u）∈Rn×Rm,λ∈Λ+,e=（1,1,…,1）,U=diag（u）和|λ5/2-λ（0）5/2|=（|λ15/2-（λ1（0））5/2|,|λ25/2（λ2（0））5/2|,…,|λp5/2-（λp（0））5/2|）T∈Rp定理1设f,g是三次连续可微函数,且Ω0≠（?）,则对于几乎所有的初始点（ω（0）,λ（0）=（x（0）,u（0）,λ（0））∈Ω0×R||m×{0）×Λ++和t∈(0,1],0是Hω（0）的正则值,并且Hω-1（0）包含一个起始于（ω（0）,λ（0）,1）的光滑流形（简称同伦隧道）,记作Vω定理2假设条件（A1）-（A2）成立,对于给定的(ω（0）,λ（0）=（x（0）,u（0）,z（0）,λ（0））∈Ω0×R++m×Λ++如果0是Hω（0）的正则值,那么Vω（0）中的分量λ有界。定理3设f,g是三次连续可微函数,并且假设条件（A1）-（A3）成立。则对于几乎所有的初始点(ω（0）,λ（0）=（x（0）,u（0）,λ（0））∈Ω0×R++m×Λ++如果0是Hω（0）的正则值,则Vω（0）是一个有界光滑隧道。定理4设f,g是三次连续可微函数,并且假设条件（A1）-（A3）成立。如果对于任意的初始点(ω（0）,λ（0）=（x（0）,u（0）,λ（0））∈Ω0×R++m×Λ++,Vω（0）是一个起始于（ω（0）,A（0）,1）的同伦遂道。则当t→0时,Vω（0）的极限集S非空,并且S内的每个点都是KKT系统（a）-（c）的解。定理5同伦隧道Vω（0）的每一条起始于（ω（0）,A（0）,1）的曲线,由以下微分方程的初值问题决定：t（0）=1,λ=λ（0）,ω（0）=ω（0）如果t（s*）=0,则（ω*（s）,λ（s））是KKT系统（a）-（c）的解。其次,考虑含有混合约束的多目标规划问题模型：其中f=（f1,f2,…,fp）T:Rn→Rp,g=（g1,g2,…,gm）T:Rn→Rm h=（h1,h2,…,hs）T:Rn→Rs假设条件如下：（A1）Ω0非空有界；（A2）（?）x∈Ω,{▽gi（x）,i∈B（x）,▽hj（x）,j∈J}线性独立；如果存在（x,λ,u,z）∈Ω×R+p+m×Rs,满足其中▽f（x）=（▽f1（x）,…,▽fp（x））∈Rn×p,▽g（x）=（▽g1（x）,…,▽gm（x））∈Rn×m,▽h（x）=（▽h1（x）,…,▽hs（x））∈Rn×s。则称x是MPP的KKT点,（la）-（lc）就是MPP的KKT系统。为了求解KKT系统（1a）-（1c）,构造组合同伦方程如下：其中ω（0）=（x（0）,u（0）,z（0））∈Ω0×R++m×{0},λ（0）∈Λ++,ω=（x,u,z）∈Rn×Rm×Rs,λ∈Λ+,e=（1,1,…,1）,U=diag（u）和|λ5/2-λ（0）5/2|=（|λ15/2（λ1（0））5/2|,|λ25/2-（λ2（0））5/2|,…,|λp5/2-（λp（0））5/2|）T∈Pp当t=1时,同伦方程为由条件（A2）和（A3）知,（ω,λ）=（ω（0）,λ（0））。当t=0时,同伦方程就转变为KKT系统（1a）-（1c）。记H（ω,ω（0）,λ,t）为Hω（0）（ω,λ,t）。对于一个给定的（ω（0）,λ（0））,Hω（0）的零点集合是Hω（0）-1（0）={（ω,λ,t）|H（ω,ω（0）,λ,t）=0}。定理6设f,g,h是三次连续可微函数,且Ω0≠（?）,则对于几乎所有的初始点（ω（0）,λ（0）=（x（0）,u（0）,z（0）,λ（0））∈Ω0×R++m×{0）×Λ++和t∈(0,1],0是Hω（0）的正则值,并且Hω（0）-1包含一个起始于（ω（0）,λ（0）,1）的光滑流形（简称同伦隧道）,记作Vω（0）定理7假设条件（A1）-（A2）成立,对于给定的（ω（0）,λ（0））=（x（（0）,u（0）,z（（0）,λ（0））∈Ω0×R++m×{0}×∧++,如果0是Hω（0）的正则值,那么Vω（0）中的分量λ有界。定理8设f,g,h是三次连续可微函数,并且假设条件（A1）-（A3）成立。对于给定的（ω（0）,λ（0）=（x（0）,u（0）,z（0）,λ（0））∈Ω0×R||m×{0）×Λ++如果0是Hω（0）的正则值,则Vω（0）是一个有界光滑隧道。定理9设f,g,h是三次连续可微函数,并且假设条件（A1）-（A3）成立。如果对于任意的初始点（ω（0）,λ（0））=（x（0）,u（0）,z（0）,λ（0））∈Ω0×R++m×{0）×Λ++,Vω（0）是一个起始于（ω（0）,λ（0）,1））的同伦隧道。则当t→0时,Vω（0）的极限集S非空,并且S内的每个点都是KKT系统（1a）-（1c）的解。定理10同伦隧道Vω（0）的每一条起始于（ω（0）,λ（0）,1）的曲线,由以下微分方程的初值问题决定：t（0）=1,λ=λ（0）,ω（0）=ω（0）,如果t（s*）=0,则（ω*（s）,λ（s））是KKT系统（1a）-（1c）的解。