多目标规划问题的路径与隧道跟踪算法
|
摘要
多目标规划问题(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)的解。
The Multi-object Programming Problem(MPP) is a special optimizationproblem. It is regarded by more and more people since the multi-object pro-gramming problem is important in economics and engineering. However, thisclass of optimization problems are very complicate. It is diferent from thesingle-object programming problem, so those theories of single-object program-ming problem are not applicable to the MPP. Therefore, serious attention hasrecently been paid to theory and numerical method.Theoretically, people havemade some achievements since they committed to establish a set of theorysystem which parallel to the single-object programming problem.On the otherhand, the efective algorithms are not enough.Although there has been a lotof research. The main work of this dissertation is that the path and tunnelfollowing algorithm for solving multi-objective programming problem is pre-sented under appropriate conditions and study the convergence, which expandthe range of combined homotopy interior point for solving multi-objective pro-gramming problem.This dissertation is organized as follows:
Chapter1: We summarize the past and the present in the theory andalgorithm about multi-object programming problem and the difcult in theresearch. On the other hand, we describe the developmental process of thehomotopy interior-point method.
Chapter2:We summarize the main theory of multi-object programming problem involved in this dissertation.
Chapter3:We study the path following algorithm for solving multi-object programming problem on the non-convex regional.
In this chapter, we consider the MPP as follows: wheref=(f1,f2,…, fp)T:Rn→Rp, g=(g1,g2,…,9m)T:Rn→Rm h=(h1,h2…,hs)T:Rn→Rs
Firstly, we consider the advantage in solving optimization problem about path following algorithm and put forward the path following algorithm for solving this kind of problem on the normal cone condition. Meanwhile, we construct a new combined homotopy equation and prove the existence and convergence of the homotopy path.
Secondly, in accordance with the defects of path following algorithm on normal cone condition, we put forward the path following algorithm on the quasi-normal cone condition, the modified quasi-normal cone condition and the modified weake quasi-normal cone condition combined with the characteistics of normal cone and (weak)quasi-norm cone. Meanwhile, we prove the existence and convergence of the homotopy path under weaker conditions.
Let x∈Ω, we call that x is a KKT point of MPP, if there exists (λ, u, z)∈R_P+m×Rs.such that
Meanwhile, the KKT system of MPP is (1a)-(1c).
In [83], assumptions as follows:(A1)Ω0is nonempty and bounded;(A2)(?)x∈Ω,{▽gi(x),i∈B(x),▽hj(x),j∈J} is linear independent;
In addition, the definition of "positive linea independent" is given in [59]. In order to extend it to non-convex multi-object programming problem and weaken the assumptions in literature [83], we do some works for inequality con-strained part firstly, introduce "positive linea independent mapping". Then take into consideration the equality constraint part, we construct a new ho-motopy equation under different assumptions.
Assumptions Ⅰ:
(B1)Ω0is nonempty and bounded;(B2) For any x∈Ω, there exists a positive linear independent map η(x) with respect to▽g(x) and▽h(x) such that,{ηi(x): i∈B(x)} is positive linear independent with respect to▽g(x) and▽h(x);(B3) For any x∈(?)Ω, there exists a positive linear independent map η(x) with respect to▽g(x) and▽h(x), such that (quasi-normal cone condition)
Remark If Ω satisfies the Assumptions (A1)-(A3), then it necessarily satisfies the Assumptions (B1)-(B3).
In fact, if we choose η(x)=▽g(x), then it is easy to get the result. Clearly, if Ω satisfies the Assumptions (B1)-(B3), then it does not necessarily satisfies the Assumptions (A1)-(A3).
To solve the KKT system (1a)-(1c), we construct a homotopy equation as follows where ω(0)=(x(0),λ(0),u(0),z(0))∈Ω0×Λ++×R+-m×{0}, ω=(x,λ,u,z)∈Rn×RP×Rm×Rs,u2=[u12,u22…,um2)T∈Rm,λ5/2=(λ15/2J,λ25/2,…,λp5/2)T∈Rp U=diag(u), e=(1,1,…,1)T∈Rp and t∈[0,1].
Theoreml Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (B1)-(B2) hold and ηi be twice times continuously differentiable function. Then for almost all initial points ω(0)∈Ω0×Λ||×R||m×{0},0is a regular value of Hω(0) and Hω(0)1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).
Theorem2Let Assumptions(B1)-(B2)hold.For a given ω(0)(x(0),λ(0),u(0),z(0))∈Ω0×Λ-+×R++m×{0}, if0is a regular value of Hω(then the projection of the smooth curve Γω(0) on the component A is bounded.
Theorem3Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (B1)-(B3) hold and ηi be twice times continuously differentiable function. Then, for almost all of
ω(0)∈Ω0×Λ++×R++m×{0}, Hω(0)-1contains a smooth curve Γw(0)(？) Ω×R|p×R-m×Rs×(0,1], which starts from (ω(0),1). As l→0, the limit set T×{0}(?)Ω×Λ-×R+m×Rs×{0} of Γω(0) is nonempty and every point in T is a solution of the KKT system (1a)-(1c).
Theorem4Homoty path Γω(0) is denned by: for t(s*)=0, ω*is one solution of (1a)-(1c). Assumptions Ⅱ:(C1)Ω0is nonempty and bounded;(C2) For any x∈Ω and t∈[0,1], there exists map η(x) and β(x), such that {▽gi(x),ηi(x): i∈B(x)} is positive linear independent with respect to▽h(x)+t(β(x)-▽h(x));(C3) For any x∈(?)Ω,(modified quasi-normal cone condition)(C4) For any x∈Ω,▽h(x)Tβ(x) is nonsingular.
Remark If Ω satisfies the Assumptions (A1)-(A3), then it necessarily sat-isfies the Assumptions {C1)-{C4).
In fact, if we choose η(x)=▽g{x) andβ(x)=▽h(x), then it is easy to get the result.Clearly, if Ω satisfies the Assumptions (C1)-(C4), then it does not necessarily satisfies the Assumptions (A1)-(A3).
Under modified quasi-norm cone condition, we construct a homotopy equation as follows: H(ω,ω(01),t)= where ω(0)=(x(0),λ(0),u(0),z(0))∈Ω0×Λ++×R++m×x{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 andt∈[0,1].
As t=1, the homotopy equation becomes
By the Assumption (C3), we get z=0,x=x(0) Since g(x(0))<0and x=x(0)(c) implies that u=u(0).(d) shows that λ=λ(0). That is, the equation H(ω,ω(0),1)=0with respect to uj has only one solution ω=ω(0)(x(0),λ(0),u(0),0).
As t=0, H(ω,ω(0))=0turns to the KKT system (1a)-(1c).
For a given ω(0) rewrite H(ω,ω(0),t) as Hω(0)(ω, t). The zero-point set of Hω(0) is
Theorem5Suppose that/, g and h are three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C2) hold and ηi,βj be twice times continuously differentiable functions. Then for almost all initial points ω(0)∈Ω0×A++×R+-m×{0},0is a regular value of Hω(0) and Hω(0)-1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).
Theorem6Let Assumptions (C1)-(C2) hold. For a given ω(0)=(x(0),λ(0) u(0),z(0))∈Ω0×Λ++×R++m×{0}, if0is a regular value of Hω(0), then the projection of the smooth curveΓω(0) on the component λ is bounded.
Theorem7Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C4) hold and ηi,βj be twice times continuously differentiable functions. Then, for almost all of ω(0)∈Ω0×Λ++×B++m×{0}, Hω(0)-1contains a smooth curve Γω Ω×R+p×R+m×Rs×(0,1], which starts from (ω(0),1). As t→0, the limit set T×{0}(?)Ω×Λ+×R+m×Rs×{0} of Γω(0)is nonempty and every point in T is a solution of the KKT system (1a)-(1c).
Theorem8Homoty path Γω(0)is denned by: for t(s*)=0, ω*is one solution of (1a)-(1c).
In order to extend the existing results to the general non-convex multi-objet programming problem,weaken the restrictions of the non-convex con-strains reginal.We define the modified weak quasi-norm cone condition and construct a new combined homotopy equation,which extends the scope for solving multi-object programming problem by the path following algorithm. The Assumptions as follows:(C1)Ω0is nonempty and bounded;(C2) For any x∈Ω and t∈[0,1], there exists map η(x) and β(x), such that {▽gi(x),ηi(x): i∪B(x)} is positive linear independent with respect to▽h(x)+t(β(x)-▽h(x)y,(C3) For any x∈(?)Ω,(modified quasi-normal cone condition)(C4) For any x∈Ω,▽h{x)Tβ{x) is nonsingular.
To solve the KKT system (1a)-(1c), we construct a homotopy equation as follows: H(ω,ω(0),t)=where ω(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 and t∈[0,1].
Theorem9Suppose that f, g and h are three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C2) hold and ηi,βj be twice times continuously differentiate functions. Then for almost all initial points ω(0)∈Ω10×Λ++×R++m×{0},0is a regular value of Hω(0) and Hω(0)-1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).
TheoremlO Let Assumptions (C1)-(C2) hold.For a given ω(0)(x(0),λ(0),u(0),z(0))∈Ω10×Λ++×R++m×{0}, if0is a regular value of Hω(then the projection of the smooth curve Γω(0) on the component A is bounded.
Theoremll Suppose that f,g and h be three times continuous differ-entiable functions.In addition, let the Assumptions (C1)-(C4) hold and ηi,βj be twice times continuously differentiable functions. Then, for almost all of ω(0)∈Ω10×Λ++×R++m×{0},Hω(0)-1(0) contains a smooth curve Γω Ω×R+p×R+m×Rs×(0,1], which starts from (ω(0),1). As t→0, the limit set T×{0}(?)Ω×Λ+×R+m×Rs×{0} of Γω(0) is nonempty and every point in T is a solution of the KKT system (1a)-(1c).
Theoreml2Homoty path Γω(0) is denned by: ω(0)=ω(0)=1, for t(s*)=0, ω*is one solution of (1a)-(1c).
Chapter4: We study the tunnel following algorithm for solving multi-object programming problem.
We really hope to find a kind of tunnel following algorithm for solving MPP by homoyopy, and try to obtain some or all of the efficient solutions (weak efficient solutions). This chapter has two sections:
In the first section, we consider the convex Multi-objective programming with inequality constraints as follows: wheref=(f1,f2,…,fP)T: Rn→Rp, g=(g1,g2,…,gm)T: Rn→Rm are convex functions. Assumptions as follows:(H1) Ω0is nonempty and bounded;(H2)(?)x∈(?)Ω,{▽gi(x)|i∈B(x)} is linear independent.
If there exists (x,λ,u)∈Ω×R+p+m, such that where▽f{x)=(▽f1(x),???,▽fP(x))∈Rn×p,▽g(x)=(▽g1(x),…,▽gm(x))∈Rn×m. Then x isa KTT point of (2),(a)-(c) are KKT system of (2).
In order to solve (a)-(c), the homoty equation as follows: where ω(0)=(x(0),u(0))∈Ω0×R++m,λ(0)∈Λ++,ω=(x,u)∈Ω×R+m,λ∈R+m,t∈[0,1].
Theoreml Let f,g∈Cr(r≥3) are convex functions, and Ω0≠(?), then for almost ω(0)∈Ω0×R++m,0is Hω(0) a, and Hω(0)-1consists of a smooth manifold(ω(0),λ,1)(a homotopy tunnel), say Vω(
Theorem2Let f,g∈Cr(r≥3) are convex functions, and (H1,H2) be hold. For ω(0)∈Ω0×R++m, if0is a regular value of Hω(0), then Vω(0) is a bounded and smooth tunnel.
Theorem3Let f,g∈Cr(r≥3) are convex functions, and (H1,H2) be hold, then (2) has solution. For almost all of ω(0)∈Ω0×R++m, Vω(0) is a homotopy tunnel, which starts from (ω(0),λ,1). When t→0, the limit set S×{0}∈Ω×R+m×Λ+×{0} of Vω(0) is nonempty, and every point of S is a solution of (2). Especially, if Vω(0) is finite, and (ω,λ,0) is the limite point of Vω(0), then(ω,λ) is a solution of (2).
Theorem4The curve Tω(0) of the Homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: If t(s*)=0, then (ω*(s), λ(s)) is one solution of (3).
In the second section, we consider the Multi-objective programming prob-lem on the non-convex region.
Firstly, we consider the convex Multi-objective programming with inequal-ity constraints. where f=(f1,f2,…, fp)T: Rn→R0, g=(g1,g2,…, gm)T: Rn→Rn Assumptions as follows:(A1)Ω0is nonempty and bounded;(A2)(?)x∈Ω,{▽gi(x),i∈B(x)} is linear independent; where Ω={x∈Rn|g(x)≦0,h(x)=0},Ω0={x∈Rn|g(x)<0},B(x)={i∈{1,2,…m}|gi(x)=0}.
If there exists (x,λ,u)∈Ω×R+p+m, such that where▽f(x)=(▽f1(x),…,▽fp(x))∈Rn×p,▽g(x)=(▽91(x),…,▽gm(x))∈Rn×m. Then x sa KKT point of (4),(a)-(c) is the KKT system of (4).
To solve the KKT system (a)—(c), we construct a homotopy equation as follows: where ω(0)=(x(0),u(0))∈Ω0×R++,λ(0)∈Λ++, ω=(x,u)∈R+m+p,λ∈Λ+,e=(1,1,---,1),U=diag(u) and|λ5/2-λ(0)5/2)=(|λ15/2|-(λ1(05/2|,|λ25/2-(λ2(0))5/2|,…,|λP5/2-(λP(0)5/2|T∈Rp
When t=1, the homotopy equation becomes x-x(0)=0, Ug(x)-U(0)g(x(0))=0, e|λ5/2-λ(0)5/2|=0
We can get (ω,λ)=(ω(0),λ(0).
When t=0, the homotopy equation becomes (a)—(c).
For a given ω(0), rewrite H(ω,ω(0), t) asHω(0)(ω, t). The zero-point set of Hω(0) is Hω(0)-1={(ω,t)∈Ω×R++p+m×Rs×(0,1]: H(ω,ω(0),t)=0}.
Theoreml Suppose that f, g be three times continuous differentiable functions, and Ω0≠0. then, for almost all of (ω(0), λ(0))=(x(0),n(0),λ(0)∈Ω0×R++m×Λ++,and t∈[0,1],0is a regular value of Hω(0),and Hω(0)-1(0) consists of a homotopy tunnel, say Vω(0), is starting from (ω(0),λ(0),1).
Theorem2Let (A1)-(A2) be hold, for (ω(0),λ(0))=(ω(0),λ(0))∈Ω0×R++m×Λ++. If0is a regular value of Hω(0), then the component A of Vω(0) is bounded.
Theorem3Suppose that f, g be three times continuous differentiable functions, and let (A1)-(A3) be hold, then, for almost all of (ω(0),λ(0))(x(0),u(0),λ(0))∈Ω0×R++m×Λ++, if0is a regular value of Hω(0), then Vω(0) is a bounded and smooth tunnel.
Theorem4Suppose that/, g be three times continuous differentiable functions, and let (A1)-(A3) hold,then, for almost all of (ω(0),λ(0))(0(0),u(0),λ(0))∈Ω0×R++m×Λ++, Hω(0) contains a homotopy tunnel Vω(which starts from (ω(0),λ(0),1), the limit set S of Vω(0) is nonempty and every point in S is a solution of (4).
Theorem5The curve Tω(0) of the Homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: t(0)=1,λ=λ,ω(0)=ω(0) If t(s*)=0, then (ω*(s), λ(s)) is a solution of (4).
Secondly, we consider the MPP as follows: min f(x) s.t. g(x)≦0, h(x)=0, wheref=(f1, f2,…, fp)T: Rn→Rp, g=(g1,g2,…,gm)T: Rn→Rm h=(h1,h2…,hs)T: Rn→Rs. Assumptions as follows:(A1) Ω0is nonempty and bounded;(A2)(?)x∈Ω,{▽gi(x),i∈B(x),▽hj(x),j∈J} is linear independent;{x}; where Ω={x∈Rn|g(x)≦0,h(x)=0},Ω0={x∈Rn|g(x)<0,h(x)0},B(x)={i∈{1,2,…m}|gi(x)=0
If there exists (x,λ,u,z)∈Ω×R+p+m×Rs, such that where▽f(x)=(▽f1(x),…,▽fp(x))∈Rn×p,▽g(x)=(▽g1(x),…,▽gm{x))∈Rn×m,▽h(x)=(▽h1(x),…,▽hs(x))∈Rn×s. then x is a KKT point of MPP,(1a)-(1c) is the KKT system.
To solve the KKT system (la)—(lc), we construct a homotopy equation as follows: where ω(0)=(x(0),u(0),z(0))∈Ω0×R++m×{0},λ(0)∈Λ++, ω=(x,u,z)∈R+m+p×Rs,λ∈Λ+, e=(1,1,…,1), U=diag(u) and|λ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
When t=1, the homotopy equation becomes▽h(x)z+x-x(0)=0, h(x)=0, Ug(x)-U(0)g(x(0))=0,
We can get (ω,λ)=(ω(0),λ(0)).
When t=0, the homotopy equation becomes (1a)-(1c).
For a given ω(0), rewrite H(ω,ω(0),t) as Hω(0)(ω,t). The zero-point set of Hω(0) is Hω(0)-1={(ω,t)∈Ω×R++p+m×Rs×(0,1]: H(ω,ω(0),t)=0}.
Theorem6Suppose that f, g and h be three times continuous differen-tiate functions, and Ω0≠0. then, for almost all of (ω(0),λ(0))=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0}×Λ++,and t∈[0,1],0is a regular value of Hω(0), and Hω(0)-1(0) consists of a homotopy tunnel, say Vω(0), is starting from (ω(0),λ(0),1).
Theorem7Let (A1)-(A2) be hold, for (ω(0),λ(0))=(x(0),u(0),λ(0))∈Ω0×R+=m×Λ++. If0is a regular value of Hω(0), then the component A of Vω(is bounded.
Theorem8Suppose that f, g and h be three times continuous differen-tiable functions, and let (A1)-(A3) hold, then, for almost all of (ω(0),λ(0)=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0} x Λ++,if0is a regular value of Hω(0) then Vω(0) is a bounded and smooth tunnel.
Theorem9Suppose that f,g and h be three times continuous differen-tiate functions, and let (A1)-(A3) hold, then, for almost all of (ω(0),λ(0))=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0}×Λ++, Hω(0)-1(0) contains a homotopy tunnel Vω(0), which starts from (ω(0),λ(0),1), the limit set S of Vω(0) is nonempty and every point in S is a solution of the KKT system (1a)-(1c).
TheoremlO The curve Tω(0) of the homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: t(0)=1,λ=λ,ω(0)=ω(0) If t(s*)=0, then (ω*(s),λ(s)) is a solution of (1a)-(1c).
第一章：概述了多目标规划问题在理论和算法方面的研究现状和遇到的困难。同时,对同伦方法的发展过程和取得的进展进行了简要描述。
第二章：概述了本文涉及到的多目标规划问题的主要理论。
第三章：研究了非凸域上多目标规划问题的路径跟踪算法。
本章考虑的多目标规划问题如下：
首先,对于多目标规划问题的求解,考虑到路径跟踪算法在求解优化问题方面的优势,在法锥条件下提出了求解这类问题的路径跟踪算法,建立相应的同伦方程并证明了其同伦路径的存在性和大范围收敛性。
其次,针对法锥条件下求解这类问题的路径跟踪算法的缺点,结合(弱)拟法锥的特点又分别提出了在拟法锥条件、修正拟法锥条件和修正弱拟法锥条件下求解多目标规划问题的路径跟踪算法,并在较弱的条件下证明了同伦路径的存在性和大范围收敛性。与法锥条件下的路径跟踪算法相比,拟法锥条件、修正拟法锥条件和修正弱拟法锥条件下的路径跟踪算法扩大了组合同伦内点算法求解非凸域上多目标规划问题的范围,且所给条件更弱。
如果存在(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)的解。
The Multi-object Programming Problem(MPP) is a special optimizationproblem. It is regarded by more and more people since the multi-object pro-gramming problem is important in economics and engineering. However, thisclass of optimization problems are very complicate. It is diferent from thesingle-object programming problem, so those theories of single-object program-ming problem are not applicable to the MPP. Therefore, serious attention hasrecently been paid to theory and numerical method.Theoretically, people havemade some achievements since they committed to establish a set of theorysystem which parallel to the single-object programming problem.On the otherhand, the efective algorithms are not enough.Although there has been a lotof research. The main work of this dissertation is that the path and tunnelfollowing algorithm for solving multi-objective programming problem is pre-sented under appropriate conditions and study the convergence, which expandthe range of combined homotopy interior point for solving multi-objective pro-gramming problem.This dissertation is organized as follows:
Chapter1: We summarize the past and the present in the theory andalgorithm about multi-object programming problem and the difcult in theresearch. On the other hand, we describe the developmental process of thehomotopy interior-point method.
Chapter2:We summarize the main theory of multi-object programming problem involved in this dissertation.
Chapter3:We study the path following algorithm for solving multi-object programming problem on the non-convex regional.
In this chapter, we consider the MPP as follows: wheref=(f1,f2,…, fp)T:Rn→Rp, g=(g1,g2,…,9m)T:Rn→Rm h=(h1,h2…,hs)T:Rn→Rs
Firstly, we consider the advantage in solving optimization problem about path following algorithm and put forward the path following algorithm for solving this kind of problem on the normal cone condition. Meanwhile, we construct a new combined homotopy equation and prove the existence and convergence of the homotopy path.
Secondly, in accordance with the defects of path following algorithm on normal cone condition, we put forward the path following algorithm on the quasi-normal cone condition, the modified quasi-normal cone condition and the modified weake quasi-normal cone condition combined with the characteistics of normal cone and (weak)quasi-norm cone. Meanwhile, we prove the existence and convergence of the homotopy path under weaker conditions.
Let x∈Ω, we call that x is a KKT point of MPP, if there exists (λ, u, z)∈R_P+m×Rs.such that
Meanwhile, the KKT system of MPP is (1a)-(1c).
In [83], assumptions as follows:(A1)Ω0is nonempty and bounded;(A2)(?)x∈Ω,{▽gi(x),i∈B(x),▽hj(x),j∈J} is linear independent;
In addition, the definition of "positive linea independent" is given in [59]. In order to extend it to non-convex multi-object programming problem and weaken the assumptions in literature [83], we do some works for inequality con-strained part firstly, introduce "positive linea independent mapping". Then take into consideration the equality constraint part, we construct a new ho-motopy equation under different assumptions.
Assumptions Ⅰ:
(B1)Ω0is nonempty and bounded;(B2) For any x∈Ω, there exists a positive linear independent map η(x) with respect to▽g(x) and▽h(x) such that,{ηi(x): i∈B(x)} is positive linear independent with respect to▽g(x) and▽h(x);(B3) For any x∈(?)Ω, there exists a positive linear independent map η(x) with respect to▽g(x) and▽h(x), such that (quasi-normal cone condition)
Remark If Ω satisfies the Assumptions (A1)-(A3), then it necessarily satisfies the Assumptions (B1)-(B3).
In fact, if we choose η(x)=▽g(x), then it is easy to get the result. Clearly, if Ω satisfies the Assumptions (B1)-(B3), then it does not necessarily satisfies the Assumptions (A1)-(A3).
To solve the KKT system (1a)-(1c), we construct a homotopy equation as follows where ω(0)=(x(0),λ(0),u(0),z(0))∈Ω0×Λ++×R+-m×{0}, ω=(x,λ,u,z)∈Rn×RP×Rm×Rs,u2=[u12,u22…,um2)T∈Rm,λ5/2=(λ15/2J,λ25/2,…,λp5/2)T∈Rp U=diag(u), e=(1,1,…,1)T∈Rp and t∈[0,1].
Theoreml Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (B1)-(B2) hold and ηi be twice times continuously differentiable function. Then for almost all initial points ω(0)∈Ω0×Λ||×R||m×{0},0is a regular value of Hω(0) and Hω(0)1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).
Theorem2Let Assumptions(B1)-(B2)hold.For a given ω(0)(x(0),λ(0),u(0),z(0))∈Ω0×Λ-+×R++m×{0}, if0is a regular value of Hω(then the projection of the smooth curve Γω(0) on the component A is bounded.
Theorem3Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (B1)-(B3) hold and ηi be twice times continuously differentiable function. Then, for almost all of
ω(0)∈Ω0×Λ++×R++m×{0}, Hω(0)-1contains a smooth curve Γw(0)(？) Ω×R|p×R-m×Rs×(0,1], which starts from (ω(0),1). As l→0, the limit set T×{0}(?)Ω×Λ-×R+m×Rs×{0} of Γω(0) is nonempty and every point in T is a solution of the KKT system (1a)-(1c).
Theorem4Homoty path Γω(0) is denned by: for t(s*)=0, ω*is one solution of (1a)-(1c). Assumptions Ⅱ:(C1)Ω0is nonempty and bounded;(C2) For any x∈Ω and t∈[0,1], there exists map η(x) and β(x), such that {▽gi(x),ηi(x): i∈B(x)} is positive linear independent with respect to▽h(x)+t(β(x)-▽h(x));(C3) For any x∈(?)Ω,(modified quasi-normal cone condition)(C4) For any x∈Ω,▽h(x)Tβ(x) is nonsingular.
Remark If Ω satisfies the Assumptions (A1)-(A3), then it necessarily sat-isfies the Assumptions {C1)-{C4).
In fact, if we choose η(x)=▽g{x) andβ(x)=▽h(x), then it is easy to get the result.Clearly, if Ω satisfies the Assumptions (C1)-(C4), then it does not necessarily satisfies the Assumptions (A1)-(A3).
Under modified quasi-norm cone condition, we construct a homotopy equation as follows: H(ω,ω(01),t)= where ω(0)=(x(0),λ(0),u(0),z(0))∈Ω0×Λ++×R++m×x{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 andt∈[0,1].
As t=1, the homotopy equation becomes
By the Assumption (C3), we get z=0,x=x(0) Since g(x(0))<0and x=x(0)(c) implies that u=u(0).(d) shows that λ=λ(0). That is, the equation H(ω,ω(0),1)=0with respect to uj has only one solution ω=ω(0)(x(0),λ(0),u(0),0).
As t=0, H(ω,ω(0))=0turns to the KKT system (1a)-(1c).
For a given ω(0) rewrite H(ω,ω(0),t) as Hω(0)(ω, t). The zero-point set of Hω(0) is
Theorem5Suppose that/, g and h are three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C2) hold and ηi,βj be twice times continuously differentiable functions. Then for almost all initial points ω(0)∈Ω0×A++×R+-m×{0},0is a regular value of Hω(0) and Hω(0)-1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).
Theorem6Let Assumptions (C1)-(C2) hold. For a given ω(0)=(x(0),λ(0) u(0),z(0))∈Ω0×Λ++×R++m×{0}, if0is a regular value of Hω(0), then the projection of the smooth curveΓω(0) on the component λ is bounded.
Theorem7Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C4) hold and ηi,βj be twice times continuously differentiable functions. Then, for almost all of ω(0)∈Ω0×Λ++×B++m×{0}, Hω(0)-1contains a smooth curve Γω Ω×R+p×R+m×Rs×(0,1], which starts from (ω(0),1). As t→0, the limit set T×{0}(?)Ω×Λ+×R+m×Rs×{0} of Γω(0)is nonempty and every point in T is a solution of the KKT system (1a)-(1c).
Theorem8Homoty path Γω(0)is denned by: for t(s*)=0, ω*is one solution of (1a)-(1c).
In order to extend the existing results to the general non-convex multi-objet programming problem,weaken the restrictions of the non-convex con-strains reginal.We define the modified weak quasi-norm cone condition and construct a new combined homotopy equation,which extends the scope for solving multi-object programming problem by the path following algorithm. The Assumptions as follows:(C1)Ω0is nonempty and bounded;(C2) For any x∈Ω and t∈[0,1], there exists map η(x) and β(x), such that {▽gi(x),ηi(x): i∪B(x)} is positive linear independent with respect to▽h(x)+t(β(x)-▽h(x)y,(C3) For any x∈(?)Ω,(modified quasi-normal cone condition)(C4) For any x∈Ω,▽h{x)Tβ{x) is nonsingular.
To solve the KKT system (1a)-(1c), we construct a homotopy equation as follows: H(ω,ω(0),t)=where ω(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 and t∈[0,1].
Theorem9Suppose that f, g and h are three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C2) hold and ηi,βj be twice times continuously differentiate functions. Then for almost all initial points ω(0)∈Ω10×Λ++×R++m×{0},0is a regular value of Hω(0) and Hω(0)-1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).
TheoremlO Let Assumptions (C1)-(C2) hold.For a given ω(0)(x(0),λ(0),u(0),z(0))∈Ω10×Λ++×R++m×{0}, if0is a regular value of Hω(then the projection of the smooth curve Γω(0) on the component A is bounded.
Theoremll Suppose that f,g and h be three times continuous differ-entiable functions.In addition, let the Assumptions (C1)-(C4) hold and ηi,βj be twice times continuously differentiable functions. Then, for almost all of ω(0)∈Ω10×Λ++×R++m×{0},Hω(0)-1(0) contains a smooth curve Γω Ω×R+p×R+m×Rs×(0,1], which starts from (ω(0),1). As t→0, the limit set T×{0}(?)Ω×Λ+×R+m×Rs×{0} of Γω(0) is nonempty and every point in T is a solution of the KKT system (1a)-(1c).
Theoreml2Homoty path Γω(0) is denned by: ω(0)=ω(0)=1, for t(s*)=0, ω*is one solution of (1a)-(1c).
Chapter4: We study the tunnel following algorithm for solving multi-object programming problem.
We really hope to find a kind of tunnel following algorithm for solving MPP by homoyopy, and try to obtain some or all of the efficient solutions (weak efficient solutions). This chapter has two sections:
In the first section, we consider the convex Multi-objective programming with inequality constraints as follows: wheref=(f1,f2,…,fP)T: Rn→Rp, g=(g1,g2,…,gm)T: Rn→Rm are convex functions. Assumptions as follows:(H1) Ω0is nonempty and bounded;(H2)(?)x∈(?)Ω,{▽gi(x)|i∈B(x)} is linear independent.
If there exists (x,λ,u)∈Ω×R+p+m, such that where▽f{x)=(▽f1(x),???,▽fP(x))∈Rn×p,▽g(x)=(▽g1(x),…,▽gm(x))∈Rn×m. Then x isa KTT point of (2),(a)-(c) are KKT system of (2).
In order to solve (a)-(c), the homoty equation as follows: where ω(0)=(x(0),u(0))∈Ω0×R++m,λ(0)∈Λ++,ω=(x,u)∈Ω×R+m,λ∈R+m,t∈[0,1].
Theoreml Let f,g∈Cr(r≥3) are convex functions, and Ω0≠(?), then for almost ω(0)∈Ω0×R++m,0is Hω(0) a, and Hω(0)-1consists of a smooth manifold(ω(0),λ,1)(a homotopy tunnel), say Vω(
Theorem2Let f,g∈Cr(r≥3) are convex functions, and (H1,H2) be hold. For ω(0)∈Ω0×R++m, if0is a regular value of Hω(0), then Vω(0) is a bounded and smooth tunnel.
Theorem3Let f,g∈Cr(r≥3) are convex functions, and (H1,H2) be hold, then (2) has solution. For almost all of ω(0)∈Ω0×R++m, Vω(0) is a homotopy tunnel, which starts from (ω(0),λ,1). When t→0, the limit set S×{0}∈Ω×R+m×Λ+×{0} of Vω(0) is nonempty, and every point of S is a solution of (2). Especially, if Vω(0) is finite, and (ω,λ,0) is the limite point of Vω(0), then(ω,λ) is a solution of (2).
Theorem4The curve Tω(0) of the Homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: If t(s*)=0, then (ω*(s), λ(s)) is one solution of (3).
In the second section, we consider the Multi-objective programming prob-lem on the non-convex region.
Firstly, we consider the convex Multi-objective programming with inequal-ity constraints. where f=(f1,f2,…, fp)T: Rn→R0, g=(g1,g2,…, gm)T: Rn→Rn Assumptions as follows:(A1)Ω0is nonempty and bounded;(A2)(?)x∈Ω,{▽gi(x),i∈B(x)} is linear independent; where Ω={x∈Rn|g(x)≦0,h(x)=0},Ω0={x∈Rn|g(x)<0},B(x)={i∈{1,2,…m}|gi(x)=0}.
If there exists (x,λ,u)∈Ω×R+p+m, such that where▽f(x)=(▽f1(x),…,▽fp(x))∈Rn×p,▽g(x)=(▽91(x),…,▽gm(x))∈Rn×m. Then x sa KKT point of (4),(a)-(c) is the KKT system of (4).
To solve the KKT system (a)—(c), we construct a homotopy equation as follows: where ω(0)=(x(0),u(0))∈Ω0×R++,λ(0)∈Λ++, ω=(x,u)∈R+m+p,λ∈Λ+,e=(1,1,---,1),U=diag(u) and|λ5/2-λ(0)5/2)=(|λ15/2|-(λ1(05/2|,|λ25/2-(λ2(0))5/2|,…,|λP5/2-(λP(0)5/2|T∈Rp
When t=1, the homotopy equation becomes x-x(0)=0, Ug(x)-U(0)g(x(0))=0, e|λ5/2-λ(0)5/2|=0
We can get (ω,λ)=(ω(0),λ(0).
When t=0, the homotopy equation becomes (a)—(c).
For a given ω(0), rewrite H(ω,ω(0), t) asHω(0)(ω, t). The zero-point set of Hω(0) is Hω(0)-1={(ω,t)∈Ω×R++p+m×Rs×(0,1]: H(ω,ω(0),t)=0}.
Theoreml Suppose that f, g be three times continuous differentiable functions, and Ω0≠0. then, for almost all of (ω(0), λ(0))=(x(0),n(0),λ(0)∈Ω0×R++m×Λ++,and t∈[0,1],0is a regular value of Hω(0),and Hω(0)-1(0) consists of a homotopy tunnel, say Vω(0), is starting from (ω(0),λ(0),1).
Theorem2Let (A1)-(A2) be hold, for (ω(0),λ(0))=(ω(0),λ(0))∈Ω0×R++m×Λ++. If0is a regular value of Hω(0), then the component A of Vω(0) is bounded.
Theorem3Suppose that f, g be three times continuous differentiable functions, and let (A1)-(A3) be hold, then, for almost all of (ω(0),λ(0))(x(0),u(0),λ(0))∈Ω0×R++m×Λ++, if0is a regular value of Hω(0), then Vω(0) is a bounded and smooth tunnel.
Theorem4Suppose that/, g be three times continuous differentiable functions, and let (A1)-(A3) hold,then, for almost all of (ω(0),λ(0))(0(0),u(0),λ(0))∈Ω0×R++m×Λ++, Hω(0) contains a homotopy tunnel Vω(which starts from (ω(0),λ(0),1), the limit set S of Vω(0) is nonempty and every point in S is a solution of (4).
Theorem5The curve Tω(0) of the Homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: t(0)=1,λ=λ,ω(0)=ω(0) If t(s*)=0, then (ω*(s), λ(s)) is a solution of (4).
Secondly, we consider the MPP as follows: min f(x) s.t. g(x)≦0, h(x)=0, wheref=(f1, f2,…, fp)T: Rn→Rp, g=(g1,g2,…,gm)T: Rn→Rm h=(h1,h2…,hs)T: Rn→Rs. Assumptions as follows:(A1) Ω0is nonempty and bounded;(A2)(?)x∈Ω,{▽gi(x),i∈B(x),▽hj(x),j∈J} is linear independent;{x}; where Ω={x∈Rn|g(x)≦0,h(x)=0},Ω0={x∈Rn|g(x)<0,h(x)0},B(x)={i∈{1,2,…m}|gi(x)=0
If there exists (x,λ,u,z)∈Ω×R+p+m×Rs, such that where▽f(x)=(▽f1(x),…,▽fp(x))∈Rn×p,▽g(x)=(▽g1(x),…,▽gm{x))∈Rn×m,▽h(x)=(▽h1(x),…,▽hs(x))∈Rn×s. then x is a KKT point of MPP,(1a)-(1c) is the KKT system.
To solve the KKT system (la)—(lc), we construct a homotopy equation as follows: where ω(0)=(x(0),u(0),z(0))∈Ω0×R++m×{0},λ(0)∈Λ++, ω=(x,u,z)∈R+m+p×Rs,λ∈Λ+, e=(1,1,…,1), U=diag(u) and|λ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
When t=1, the homotopy equation becomes▽h(x)z+x-x(0)=0, h(x)=0, Ug(x)-U(0)g(x(0))=0,
We can get (ω,λ)=(ω(0),λ(0)).
When t=0, the homotopy equation becomes (1a)-(1c).
For a given ω(0), rewrite H(ω,ω(0),t) as Hω(0)(ω,t). The zero-point set of Hω(0) is Hω(0)-1={(ω,t)∈Ω×R++p+m×Rs×(0,1]: H(ω,ω(0),t)=0}.
Theorem6Suppose that f, g and h be three times continuous differen-tiate functions, and Ω0≠0. then, for almost all of (ω(0),λ(0))=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0}×Λ++,and t∈[0,1],0is a regular value of Hω(0), and Hω(0)-1(0) consists of a homotopy tunnel, say Vω(0), is starting from (ω(0),λ(0),1).
Theorem7Let (A1)-(A2) be hold, for (ω(0),λ(0))=(x(0),u(0),λ(0))∈Ω0×R+=m×Λ++. If0is a regular value of Hω(0), then the component A of Vω(is bounded.
Theorem8Suppose that f, g and h be three times continuous differen-tiable functions, and let (A1)-(A3) hold, then, for almost all of (ω(0),λ(0)=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0} x Λ++,if0is a regular value of Hω(0) then Vω(0) is a bounded and smooth tunnel.
Theorem9Suppose that f,g and h be three times continuous differen-tiate functions, and let (A1)-(A3) hold, then, for almost all of (ω(0),λ(0))=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0}×Λ++, Hω(0)-1(0) contains a homotopy tunnel Vω(0), which starts from (ω(0),λ(0),1), the limit set S of Vω(0) is nonempty and every point in S is a solution of the KKT system (1a)-(1c).
TheoremlO The curve Tω(0) of the homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: t(0)=1,λ=λ,ω(0)=ω(0) If t(s*)=0, then (ω*(s),λ(s)) is a solution of (1a)-(1c).
引文
[1]Aghezzaf B, Ouaderhman T, An interactive interior point algorithm for multiobjective linear programming problems,Operations Research Letters29(2001),163-170.
[2]Allgower, E. L., and Georg K., Numerical Continuation Methods:An Intro-duction, Springer Verlag, Berlin, Germany,1990.
[3]Allgower, E. L., and Georg K., Simplicial and continuation methods for ap-proximating fixed points and solutions to systems of equations, SIAM Review,22(1980),28-85.
[4]A. Klarbring, J. Petersson, M. Ronnqvist, Truss topology optimization in-volving unilateral contact, Journal of Optimization Theorey and Applications,87(1995),1-31.
[5]Amouzegar M A, A global optimization method for nonlinear bilevel program-ming problems [J], IEEE Transactions on Systems, Man and Cybernetics, Part B:Cybernetics,1999,29(6):771-777.
[6]B. F. Hobbs, K. A. Kely, Using game theorey to analyze electric transmission pricing policies in the United states, European Journal of operations research,56(1992),154-171.
[7]Bard J F, Moore J T. A branch and bound algorithm for the bilevel program-ming problem [J], SIAM Journal on Science and Statistical Computing,1990,11(2):281-292.
[8]Billups, S. C. and L. T. Watson, A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems, SIAM J. Optim.,12(2002),606-626.
[9]Billups, S. C., A homotopy-based algorithm for mixed complementarity prob-lems, SIAM J. Optim.,12(2002),583-605.
[10]Billups, S. C., A. L. Speight and L. T. Watson, Nonmonotone path follow-ing methods for nonsmooth equations and complementarity problems, in Com-plementarity:applications, algorithms and extensions (Madison, WI,1999),19-41, Appl. Optim.,50, Kluwer Acad. Publ., Dordrecht,2001.
[11]Chankong V, Haimes Y Y, Multiobjective Decision Making Theory and Methodology, New York,Amsterdam,Oxford:North Holland.1983.
[12]Chow, S. N., J. Mallet-Paret and J. A. Yorke, Finding zeros of maps:Ho-motopy methods that are constructive with probanility one, Math. Comput.32(1978),887-899.
[13]Clarke, F. H., Optimization and Nonsmooth Analysis, John Wiley&Sons, Inc., New York,1983.
[14]杜文晖,一种新的多目标优化遗传算法,西安科技大学硕士学位论文,2010.
[15]Das I,Dennis J E, Normal Bounday intersection:a new method fo generating the pareto surface in nonlinear multicriteria optimization problems, SIAM J Optim,8(1998),631-657.
[16]E. Aiyoshi, K. Shimizu, Hierarchical decentralized systems and its new solution by a barrier method, IEEE Trans. Syst. Man Cybern.,11(1981),444-449.
[17]E. Aiyoshi, K. Shimizu, A solution method for the static constrained Stack-elberg problem wia penalty method, IEEE Trans. Automat. Contr.34(1992),1111-1114.
[18]F.A. Al-Khayal, R. Horst, P. M. pardalos, Global optimization of convex func-tions subject to quadratic constrains:an application in nonlinear bilevel pro-gramming, Ann. Oper. Res.34(1992),125-147.
[19]Facchinei F., Jiang H. Y.,and Qi L. Q., A smoothing method for mathematical programs with equilibrium constraints, Math. Program.,85(1999),107-134.
[20]Fang, S. C. and Puthenpura, Linear Optimization and Extensions, Prentice Hall,1994(中译本：线性优化及扩展,汪定伟、王梦光译,科学出版社,1994年)
[21]Feng, G. C. and B. Yu, Combined homotopy interior point method for nonlin-ear programming problems, Lecture Notes in Num. Anal.,14(1995),9-16.
[22]Feng, G. C., Z. Lin and B. Yu, Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, Nonlinear Analysis,32(1998),761-768.
[23]冯果忱,非线性方程组迭代解法,上海科技出版社,上海,1989.
[24]Fiacco, A. V. and G. P. McCormick, Nonlinear Programming:Sequential Un-constrained Minimization Techniques, John Wiley&Sons, New York,1968, reprinted by SIAM Publications,1990.
[25]Friesz, T. L., Tobin, R. L., Cho, H.-J., Mehta, N.J.(1990):Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequal-ity constraints, Math. Program.48,265-284.
[26]Frisch, K. R., The logarithmic potential method of convex programming, Mem-orandum, Institute of Economics, Oslo, Norway,1955.
[27]Fukushima M., Pang J. S., Some feasibility issues in mathematical programs with Equilibrium Constrains, SIAM Journal of Optimization,8(1998),673-681.
[28]Gomez, W., Properties of an interior embedding for solving nonlinear opti-mization problems, Math. Program.,86(1999),649-659.
[29]G. H. Lin and M. Fukushima, New relaxation method for mathematical pro-grams with complementarity constraints, J. Optim. Theory Appl.,118(2003),81-116.
[30]G. Savard, J. Gauvin, The steepest descent direction for the nonlinear bilevel programming problem, Oper. Res. Lett.,15(1994),265-272.
[31]Garcia, C. B. and W. I. Zangwill, Pathways to Solutions, Fixed Points and Equilibria, Prentice-Hall, New Jersey,1981.
[32]Gavurin, M., Nonlinear functions equations and continuous analogues of iter-ative method (Russian), Izv. Vyss. Ucebn. Zaved. Matematica,6(1958),18-31.
[33]贺莉,金鉴禄,谭佳伟,刘庆怀,同伦内点法求一类多目标优化问题的最小弱有效解,哈尔滨理工大学学报,6(2010),62-65.
[34]H. Y. Benson, D. F. Shanno, and R. J. Vanderbei, Interior-point meth-ods for nonconvex nonlinear programming:complementarity constraints, Preprint,Operations Research and Financial Engineering, Princeton Univer-sity, ORFE-02-02, July,2002.
[35]Henderson, J. M., Quandt, R.E.(1980):Microeconomic Theory,3rd edn. McGraw-Hill, New York.
[36]H. Von Stackelberg, The Theory of the Market Economy, Oxford University Press, Oxford, England,1952.
[37]Harker, P. T.(1991):Generalized Nash games and quasi-variational inequali-ties. Eur. J. Oper. Res.54,81-94.
[38]H. Y. Benson, D. F. Shanno, and R. J. Vanderbei, Interior-point meth-ods for nonconvex nonlinear programming:complementarity constraints, Preprint,Operations Research and Financial Engineering, Princeton Univer-sity, ORFE-02-02, July,2002.
[39]Interior Point Methods Onlinear, http://www-unix.mcs.anl.gov/otc/Interior-Point/
[40]J. F. Bard, Optimality conditions for the bilevel programming problems, Naval Research Logistics Quarterly,31(1984),13-26.
[41]J. V. Outrata, Optimality conditions for a class of mathematical programs with equilibrium constraints, Mathematics of Operation Research,24(1999),627-644.
[42]J. Outrata, J. Chemzowe, A numerical approach to optimization problems with variational inequality constraints, Math. Prog.,1995,68:105-130.
[43]J. V. Outrata, M. Koncvar and J. Zowe, Nonsmooth approach to optimization problems with equilibrium constraints, Kluwer Academic Publishers,1998.
[44]J. Bracken, J. T. McGill, Mathematical programs with optimization problems in the constraints, Operations research,22(1973),37-44.
[45]K.Shimizu, E.Aiyoshi, A new computational method for Stackelberg and min-max problems by use of a penalty method, IEEE Trans. Automat. Contr.,26(1981)460-466.
[46]Kanzow C., and Jiang H., A continuation method for (strongly) monotone variational inequalities, Math. Prog.,81(1998),103-125.
[47]Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica,14(1984),373-395.
[48]Kellogg, R. B., T. Y. Li and J. A. Yorke, A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Numer. Anal.,13(1976),473-483.
[49]L. M. Case, An l1penalty function approach to the nonlinear bilevel program-ming problem, Ph. D. Thesis, University of Waterloo, Ontario, Canada,1999.
[50]Lin, Z. H.,and Y. Li, Homotopy method for solving variational inequalities, J. Optim. Theory Appl.,100(1999),207-218.
[51]Lin, Z. H., B. Yu and D. L. Zhu, A continuation mathod for solving fixed points of self-mappings in general nonconvex sete, Nonlinear Analysis,52(2003),905-915.
[52]Lin, Z. H.,, B. Yu and G. C. Feng, Combined homotopy interior point method for convex nonlinear programming, Appl. Math. Comput.,84(1997),193-211.
[53]Lin, Z. H.,, Y. Li and B. Yu, A combined homotopy interior point method for general nonlinear programming problems, Appl. Math. Comput.,80(1996),209-224.
[54]林正华,解数学规划问题的内点法,吉林大学博士学位论文,1993.
[55]林正华、宋岱才、赵立芹,连续化方法求解一般非凸规划的K-K-T点,高校应用数学学报A辑,17(2002),217-224.
[56]Liu, G. X. and B. Yu, Homotopy continuation mathod for linear complemen-tarity problems, Northeast. Math. J.,3(2004),309-316.
[57]刘庆怀,林正华,多目标规划最小弱有效解得同伦内点方法,应用数学学报,23(2000),188-195.
[58]刘国新,求解序列极大极小问题、互补问题和变分不等式的凝聚同伦方法,吉林大学博士学位论文,2003.
[59]Liu, Q. H., B. Yu and G. C. Feng, An interior point path-following method for nonconvex programming with quasi normal cone condition,数学进展,29(2000),281-282.
[60]刘庆怀,解非凸规划问题的组合同伦内点法,吉林大学博士学位论文,1999.
[61]Luo Z Q, Pang J S and Ralph D. Mathematical Programs with Equilibrium Constraints[M], New York:Cambrige University Press,1996.
[62]Makela, M. M. and P. Neittaanmaki, Nonsmooth Optimization:Analysis And Algorithms with Applications to Optimal Control, World Scientific Publishing Co. Pte. Ltd.,1992.
[63]M. Fukushima, Z. Luo, and J. S. Pang, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear com-plementarity constraints, Comput. Optim. Appl.,10(1998),5-34.
[64]Messal A,Ismail Yahaya A, Mattson CA, The nomalized nomal constraint method for geneating the pareto fontier, Stuctural and Multidisciplinay Opti-mization,25(2003),86-98.
[65]Messal A, Physical Progamming:effective optimization fo computational design AIAA J,34(1996),149-158.
[66]Nesterov, Y. E. and A. S. Nemirovsky, Interior Point Polynomial Methods in Convex Programming, SIAM Publications,1994.
[67]Nocedal, J. and S. J. Wright, Numerical Optimization, Springer, New York,2000.
[68]O. Ben-Ayed, C. E. Blair, Computational difficulties of bilevel linear program-ming, Operations Research,38(1990),556-559.
[69]裴胜玉,多目标粒子群优化算法及其应用,广西民族大学硕士学位论文,2010.
[70]Pang, J. S., Complementarity Problem, Handbook of Global Optimization, Edited by R. Horst and P. Pardalos, Kluwer Academic Publishers, Dordrecht, Netherlands,1994.
[71]Peng, J. M. and Z. Lin, A non-interior continuation method for generalized linear complementarity problems, Math. Program.,86(1999),533-563.
[72]R. G. Cassidy, M. J. L. Kriby, W. M. Raike, Efficient distribution of resources through three level of government, Manage. Sci.17(8)(1971)462.
[73]R. W. Cottle, J. S. Pang, R. E. Stone, The linear complementarity prob-lem, Academic Press, Boston,1992.
[74]S. C. Choi, W. S. Desarbo, P. T. Harker, Product positioning under price competition, Management Scince,36(1990),175-199.
[75]Scholtes, S., Convergence properties of a regularization scheme for mathemat-ical programs with complementarity constraints, SIAM J.Optim.,10(2000),315-330.
[76]Scholtes, S., Convergence properties of a regularization scheme for mathemat-ical programs with complementarity constraints, Working paper, Judge Insti-tute of Management Studies, University of Cambridge, Cambridge, UK,1999.
[77]Scholtes, S., and M. Stohr, Exact penalization of mathematical programs with equilibrium constraints, SIAM J.Control Optim.,37(1999),617-652.
[78]商玉凤,解非线性规划、均衡规划和变分不等式问题的动约束组合同伦方法,吉林大学博士学位论文,2006.
[79]Steue R, Multiple Citeia Optimization:Theoy, Computation, Applications, New Yok:John Wiley Sons,1986.
[80]Smale, S., A convergent process of price adjustment and global Newton method, J. Math. Econ.,3(1976),1-14.
[81]S. Scholtes, M. Stohr, Mathematical programs with complementarity con-straints:Stationarity, optimality, and sensitivity, Working paper, The Judge Institute of Management Studies, University of Cambridge, Cambridge, UK,1999.
[82]Tafalis T, Moin TL, Abhyanka ss, Efficient Faces of Polytopes:Interior Point Algorithms, Paametrization of Algebaic Varieties, and Multiple Objective Op-timization,Contemp Math,,114(1991),319-341.
[83]W. Song, C.M. Yao, Homotopy Method for a General Multiobjective Pro-gramming Problem, Journal of Optimization Theorey and Applications,138(2008),139-153.
[84]万中,李董辉,带互补约化优化问题的非精确磨光连读方法,湘潭大学学报(自然科学版),22(2000)pp.87-89.
[85]Wang, Y., G. C. Feng and T. Z. Liu, A interior point algorithm for convex nonlinear programming broblem, Numerical Mathematics,1(1992),1-8.
[86]Wang, Y., The Homotopy Algorithm for Solving Optiminal Problem, The Dalian maritime University press,1996.
[87]王宇,计算机优化同伦算法,大连海事大学出版社,大连,1996.
[88]王宇,直接三角分解Newton型方法和内点法,吉林大学博士学位论文,1991.
[89]Wan Z., Further investigation on feasibility of mathematical programs with equilibrium constrains, Computers and Mathematics with Applications,2002,44:7-11.
[90]王则柯、高堂安,同伦方法引论,重庆出版社,重庆,1990.
[91]Watson, L. T., Theory of globally convergent probability-one homotopies for nonlinear programming, SIAM J. Optim.,11(2000),761-780.
[92]Watson, L. T., Solving the nonlinear complementarity problem by a homotopy method, SIAM J. Control Optim.,17(1979),36-46.
[93]Wolkowicz, H., R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming, Kluwer, Academic Publishers,2000.
[94]Wright, S. J., Primal-Dual Interior-Point Methods, SIAM Publications, Philadelphia, Pa,1997.
[95]王维国,宋阳,郭多祚,一种求解混合多目标规划问题的功效函数法,运筹与管理,4(2007),23-27.
[96]X. Hu and D. Ralph, Convergence of a penalty method for mathematical pro-gramming with equilibrium constraints, Manuscript, Department of Mathe-matics and Statistics, University of Melbourne, Australia,2001.
[97]X. Liu and J. Sun, Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints, Math. Program.,101(2004),231-261.
[98]Xu, Q. and B. Yu, Homotopy method for non-convex programming in un-bounded set. Northeast. Math. J.21(2005),25-31.
Xu, Q., B. Yu and G. C. Feng, Homotopy method for solving variational inequalities in unbounded sets, Journal of Global Optimization,31(2005),121-131.
[100]Xu, Q., B. Yu and G. C. Feng, Homotopy method for variational inequalities, Advances in Mathematics,30(2001),477-479.
[101]Xu, Q., Homotopy method for solving Nash equilibria, to appear.
[102]徐庆,解非线性规划和变分不等式的内点同伦方法,吉林大学博士学位论文,2002.
[103]徐庆、林正华,组合同伦方法在无界域上的收敛性,应用数学学报,27(2004),624-631.
[104]徐庆、朱道立、鲁其辉Nash均衡、变分不等式和广义均衡问题的关系,管理科学学报,8(2005).
[105]Y.F.Sang,B. Yu, A constraint shifting homotopy method for convex multi-objective programming, Journal of Computational and Applied Mathematics,236(2011),640-646.
[106]Yu, B. and Z. Lin, Homotopy method for a class of nonconvex Brouwer fixed point problems, Appl. Math. Comput.,74(1996),65-77.
[107]Yu, B., G. C. Feng and S. L. Zhang, The aggregate constraint homotopy method for nonconvex nonlinear programming, Nonlinear Analysis, TMA,45(2001),839-847.
[108]Yu, B., G. X. Liu and G. C. Feng, The aggregate homotopy method for constrained sequential max-min problems, Northeast. Math. J.,19(2003),287-290.
[109]Yu, B., L. Qi and G. X. Liu, A modified aggregate homotopy method for convex minimax problems, Proceedings of the5th international conference on Opti-mization, ed. Li, D., Hong Kong,(2001),32-38.
[110]Yu, B., Q. H. Liu and G. C. Feng, A combined homotopy interior point method for nonconvex programming with pseudo cone condition, Northeast. Math. J.,16(2000),383-386.
[111]Yu, B., Q. Xu and G. C. Feng, On the complexity of a combined homotopy interior point method for convex programming, J. Comput. Appl. Math已复印,亦见中国科技论文在线,2004,102-169.
[112]Youness EA, Emam T, Chaacteization of efficient solutions of multiobjective Optimization Programming Problems invoving semi-strongly and generalized semi-strongly E-convexity, Acta Mathematica Scientia,28(2008):7-16.
[113]袁亚湘,孙文瑜,最优化理论与方法,科学出版社,北京,1997.
[114]Z. Q. Luo, J. S. Pang, Exact penalization and stationarity conditions of math-ematical programs with equilibrium constraints, Math.Program,75(1996):19-76.
[115]Zhao, Y. B. and J. Han, Exceptional family of elements for a variational inequality problem and its applications, J. Global Optimization,14(1999),313-330.
[116]Zhu, D. L., Q. Xu and Z. H. Lin, A homotopy method for solving bilevel programming problem, Nonlinear Analysis,57(2004),917-928.
[117]Z.H.Lin, D.L.Zhu, Z.P.Sheng, Finding a Minimal Efficient Solution of a Con-vex Multiobjective Program, Journal of Optimization Theory and Applications,118(2003),587-600.
[2]Allgower, E. L., and Georg K., Numerical Continuation Methods:An Intro-duction, Springer Verlag, Berlin, Germany,1990.
[3]Allgower, E. L., and Georg K., Simplicial and continuation methods for ap-proximating fixed points and solutions to systems of equations, SIAM Review,22(1980),28-85.
[4]A. Klarbring, J. Petersson, M. Ronnqvist, Truss topology optimization in-volving unilateral contact, Journal of Optimization Theorey and Applications,87(1995),1-31.
[5]Amouzegar M A, A global optimization method for nonlinear bilevel program-ming problems [J], IEEE Transactions on Systems, Man and Cybernetics, Part B:Cybernetics,1999,29(6):771-777.
[6]B. F. Hobbs, K. A. Kely, Using game theorey to analyze electric transmission pricing policies in the United states, European Journal of operations research,56(1992),154-171.
[7]Bard J F, Moore J T. A branch and bound algorithm for the bilevel program-ming problem [J], SIAM Journal on Science and Statistical Computing,1990,11(2):281-292.
[8]Billups, S. C. and L. T. Watson, A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems, SIAM J. Optim.,12(2002),606-626.
[9]Billups, S. C., A homotopy-based algorithm for mixed complementarity prob-lems, SIAM J. Optim.,12(2002),583-605.
[10]Billups, S. C., A. L. Speight and L. T. Watson, Nonmonotone path follow-ing methods for nonsmooth equations and complementarity problems, in Com-plementarity:applications, algorithms and extensions (Madison, WI,1999),19-41, Appl. Optim.,50, Kluwer Acad. Publ., Dordrecht,2001.
[11]Chankong V, Haimes Y Y, Multiobjective Decision Making Theory and Methodology, New York,Amsterdam,Oxford:North Holland.1983.
[12]Chow, S. N., J. Mallet-Paret and J. A. Yorke, Finding zeros of maps:Ho-motopy methods that are constructive with probanility one, Math. Comput.32(1978),887-899.
[13]Clarke, F. H., Optimization and Nonsmooth Analysis, John Wiley&Sons, Inc., New York,1983.
[14]杜文晖,一种新的多目标优化遗传算法,西安科技大学硕士学位论文,2010.
[15]Das I,Dennis J E, Normal Bounday intersection:a new method fo generating the pareto surface in nonlinear multicriteria optimization problems, SIAM J Optim,8(1998),631-657.
[16]E. Aiyoshi, K. Shimizu, Hierarchical decentralized systems and its new solution by a barrier method, IEEE Trans. Syst. Man Cybern.,11(1981),444-449.
[17]E. Aiyoshi, K. Shimizu, A solution method for the static constrained Stack-elberg problem wia penalty method, IEEE Trans. Automat. Contr.34(1992),1111-1114.
[18]F.A. Al-Khayal, R. Horst, P. M. pardalos, Global optimization of convex func-tions subject to quadratic constrains:an application in nonlinear bilevel pro-gramming, Ann. Oper. Res.34(1992),125-147.
[19]Facchinei F., Jiang H. Y.,and Qi L. Q., A smoothing method for mathematical programs with equilibrium constraints, Math. Program.,85(1999),107-134.
[20]Fang, S. C. and Puthenpura, Linear Optimization and Extensions, Prentice Hall,1994(中译本：线性优化及扩展,汪定伟、王梦光译,科学出版社,1994年)
[21]Feng, G. C. and B. Yu, Combined homotopy interior point method for nonlin-ear programming problems, Lecture Notes in Num. Anal.,14(1995),9-16.
[22]Feng, G. C., Z. Lin and B. Yu, Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, Nonlinear Analysis,32(1998),761-768.
[23]冯果忱,非线性方程组迭代解法,上海科技出版社,上海,1989.
[24]Fiacco, A. V. and G. P. McCormick, Nonlinear Programming:Sequential Un-constrained Minimization Techniques, John Wiley&Sons, New York,1968, reprinted by SIAM Publications,1990.
[25]Friesz, T. L., Tobin, R. L., Cho, H.-J., Mehta, N.J.(1990):Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequal-ity constraints, Math. Program.48,265-284.
[26]Frisch, K. R., The logarithmic potential method of convex programming, Mem-orandum, Institute of Economics, Oslo, Norway,1955.
[27]Fukushima M., Pang J. S., Some feasibility issues in mathematical programs with Equilibrium Constrains, SIAM Journal of Optimization,8(1998),673-681.
[28]Gomez, W., Properties of an interior embedding for solving nonlinear opti-mization problems, Math. Program.,86(1999),649-659.
[29]G. H. Lin and M. Fukushima, New relaxation method for mathematical pro-grams with complementarity constraints, J. Optim. Theory Appl.,118(2003),81-116.
[30]G. Savard, J. Gauvin, The steepest descent direction for the nonlinear bilevel programming problem, Oper. Res. Lett.,15(1994),265-272.
[31]Garcia, C. B. and W. I. Zangwill, Pathways to Solutions, Fixed Points and Equilibria, Prentice-Hall, New Jersey,1981.
[32]Gavurin, M., Nonlinear functions equations and continuous analogues of iter-ative method (Russian), Izv. Vyss. Ucebn. Zaved. Matematica,6(1958),18-31.
[33]贺莉,金鉴禄,谭佳伟,刘庆怀,同伦内点法求一类多目标优化问题的最小弱有效解,哈尔滨理工大学学报,6(2010),62-65.
[34]H. Y. Benson, D. F. Shanno, and R. J. Vanderbei, Interior-point meth-ods for nonconvex nonlinear programming:complementarity constraints, Preprint,Operations Research and Financial Engineering, Princeton Univer-sity, ORFE-02-02, July,2002.
[35]Henderson, J. M., Quandt, R.E.(1980):Microeconomic Theory,3rd edn. McGraw-Hill, New York.
[36]H. Von Stackelberg, The Theory of the Market Economy, Oxford University Press, Oxford, England,1952.
[37]Harker, P. T.(1991):Generalized Nash games and quasi-variational inequali-ties. Eur. J. Oper. Res.54,81-94.
[38]H. Y. Benson, D. F. Shanno, and R. J. Vanderbei, Interior-point meth-ods for nonconvex nonlinear programming:complementarity constraints, Preprint,Operations Research and Financial Engineering, Princeton Univer-sity, ORFE-02-02, July,2002.
[39]Interior Point Methods Onlinear, http://www-unix.mcs.anl.gov/otc/Interior-Point/
[40]J. F. Bard, Optimality conditions for the bilevel programming problems, Naval Research Logistics Quarterly,31(1984),13-26.
[41]J. V. Outrata, Optimality conditions for a class of mathematical programs with equilibrium constraints, Mathematics of Operation Research,24(1999),627-644.
[42]J. Outrata, J. Chemzowe, A numerical approach to optimization problems with variational inequality constraints, Math. Prog.,1995,68:105-130.
[43]J. V. Outrata, M. Koncvar and J. Zowe, Nonsmooth approach to optimization problems with equilibrium constraints, Kluwer Academic Publishers,1998.
[44]J. Bracken, J. T. McGill, Mathematical programs with optimization problems in the constraints, Operations research,22(1973),37-44.
[45]K.Shimizu, E.Aiyoshi, A new computational method for Stackelberg and min-max problems by use of a penalty method, IEEE Trans. Automat. Contr.,26(1981)460-466.
[46]Kanzow C., and Jiang H., A continuation method for (strongly) monotone variational inequalities, Math. Prog.,81(1998),103-125.
[47]Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica,14(1984),373-395.
[48]Kellogg, R. B., T. Y. Li and J. A. Yorke, A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Numer. Anal.,13(1976),473-483.
[49]L. M. Case, An l1penalty function approach to the nonlinear bilevel program-ming problem, Ph. D. Thesis, University of Waterloo, Ontario, Canada,1999.
[50]Lin, Z. H.,and Y. Li, Homotopy method for solving variational inequalities, J. Optim. Theory Appl.,100(1999),207-218.
[51]Lin, Z. H., B. Yu and D. L. Zhu, A continuation mathod for solving fixed points of self-mappings in general nonconvex sete, Nonlinear Analysis,52(2003),905-915.
[52]Lin, Z. H.,, B. Yu and G. C. Feng, Combined homotopy interior point method for convex nonlinear programming, Appl. Math. Comput.,84(1997),193-211.
[53]Lin, Z. H.,, Y. Li and B. Yu, A combined homotopy interior point method for general nonlinear programming problems, Appl. Math. Comput.,80(1996),209-224.
[54]林正华,解数学规划问题的内点法,吉林大学博士学位论文,1993.
[55]林正华、宋岱才、赵立芹,连续化方法求解一般非凸规划的K-K-T点,高校应用数学学报A辑,17(2002),217-224.
[56]Liu, G. X. and B. Yu, Homotopy continuation mathod for linear complemen-tarity problems, Northeast. Math. J.,3(2004),309-316.
[57]刘庆怀,林正华,多目标规划最小弱有效解得同伦内点方法,应用数学学报,23(2000),188-195.
[58]刘国新,求解序列极大极小问题、互补问题和变分不等式的凝聚同伦方法,吉林大学博士学位论文,2003.
[59]Liu, Q. H., B. Yu and G. C. Feng, An interior point path-following method for nonconvex programming with quasi normal cone condition,数学进展,29(2000),281-282.
[60]刘庆怀,解非凸规划问题的组合同伦内点法,吉林大学博士学位论文,1999.
[61]Luo Z Q, Pang J S and Ralph D. Mathematical Programs with Equilibrium Constraints[M], New York:Cambrige University Press,1996.
[62]Makela, M. M. and P. Neittaanmaki, Nonsmooth Optimization:Analysis And Algorithms with Applications to Optimal Control, World Scientific Publishing Co. Pte. Ltd.,1992.
[63]M. Fukushima, Z. Luo, and J. S. Pang, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear com-plementarity constraints, Comput. Optim. Appl.,10(1998),5-34.
[64]Messal A,Ismail Yahaya A, Mattson CA, The nomalized nomal constraint method for geneating the pareto fontier, Stuctural and Multidisciplinay Opti-mization,25(2003),86-98.
[65]Messal A, Physical Progamming:effective optimization fo computational design AIAA J,34(1996),149-158.
[66]Nesterov, Y. E. and A. S. Nemirovsky, Interior Point Polynomial Methods in Convex Programming, SIAM Publications,1994.
[67]Nocedal, J. and S. J. Wright, Numerical Optimization, Springer, New York,2000.
[68]O. Ben-Ayed, C. E. Blair, Computational difficulties of bilevel linear program-ming, Operations Research,38(1990),556-559.
[69]裴胜玉,多目标粒子群优化算法及其应用,广西民族大学硕士学位论文,2010.
[70]Pang, J. S., Complementarity Problem, Handbook of Global Optimization, Edited by R. Horst and P. Pardalos, Kluwer Academic Publishers, Dordrecht, Netherlands,1994.
[71]Peng, J. M. and Z. Lin, A non-interior continuation method for generalized linear complementarity problems, Math. Program.,86(1999),533-563.
[72]R. G. Cassidy, M. J. L. Kriby, W. M. Raike, Efficient distribution of resources through three level of government, Manage. Sci.17(8)(1971)462.
[73]R. W. Cottle, J. S. Pang, R. E. Stone, The linear complementarity prob-lem, Academic Press, Boston,1992.
[74]S. C. Choi, W. S. Desarbo, P. T. Harker, Product positioning under price competition, Management Scince,36(1990),175-199.
[75]Scholtes, S., Convergence properties of a regularization scheme for mathemat-ical programs with complementarity constraints, SIAM J.Optim.,10(2000),315-330.
[76]Scholtes, S., Convergence properties of a regularization scheme for mathemat-ical programs with complementarity constraints, Working paper, Judge Insti-tute of Management Studies, University of Cambridge, Cambridge, UK,1999.
[77]Scholtes, S., and M. Stohr, Exact penalization of mathematical programs with equilibrium constraints, SIAM J.Control Optim.,37(1999),617-652.
[78]商玉凤,解非线性规划、均衡规划和变分不等式问题的动约束组合同伦方法,吉林大学博士学位论文,2006.
[79]Steue R, Multiple Citeia Optimization:Theoy, Computation, Applications, New Yok:John Wiley Sons,1986.
[80]Smale, S., A convergent process of price adjustment and global Newton method, J. Math. Econ.,3(1976),1-14.
[81]S. Scholtes, M. Stohr, Mathematical programs with complementarity con-straints:Stationarity, optimality, and sensitivity, Working paper, The Judge Institute of Management Studies, University of Cambridge, Cambridge, UK,1999.
[82]Tafalis T, Moin TL, Abhyanka ss, Efficient Faces of Polytopes:Interior Point Algorithms, Paametrization of Algebaic Varieties, and Multiple Objective Op-timization,Contemp Math,,114(1991),319-341.
[83]W. Song, C.M. Yao, Homotopy Method for a General Multiobjective Pro-gramming Problem, Journal of Optimization Theorey and Applications,138(2008),139-153.
[84]万中,李董辉,带互补约化优化问题的非精确磨光连读方法,湘潭大学学报(自然科学版),22(2000)pp.87-89.
[85]Wang, Y., G. C. Feng and T. Z. Liu, A interior point algorithm for convex nonlinear programming broblem, Numerical Mathematics,1(1992),1-8.
[86]Wang, Y., The Homotopy Algorithm for Solving Optiminal Problem, The Dalian maritime University press,1996.
[87]王宇,计算机优化同伦算法,大连海事大学出版社,大连,1996.
[88]王宇,直接三角分解Newton型方法和内点法,吉林大学博士学位论文,1991.
[89]Wan Z., Further investigation on feasibility of mathematical programs with equilibrium constrains, Computers and Mathematics with Applications,2002,44:7-11.
[90]王则柯、高堂安,同伦方法引论,重庆出版社,重庆,1990.
[91]Watson, L. T., Theory of globally convergent probability-one homotopies for nonlinear programming, SIAM J. Optim.,11(2000),761-780.
[92]Watson, L. T., Solving the nonlinear complementarity problem by a homotopy method, SIAM J. Control Optim.,17(1979),36-46.
[93]Wolkowicz, H., R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming, Kluwer, Academic Publishers,2000.
[94]Wright, S. J., Primal-Dual Interior-Point Methods, SIAM Publications, Philadelphia, Pa,1997.
[95]王维国,宋阳,郭多祚,一种求解混合多目标规划问题的功效函数法,运筹与管理,4(2007),23-27.
[96]X. Hu and D. Ralph, Convergence of a penalty method for mathematical pro-gramming with equilibrium constraints, Manuscript, Department of Mathe-matics and Statistics, University of Melbourne, Australia,2001.
[97]X. Liu and J. Sun, Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints, Math. Program.,101(2004),231-261.
[98]Xu, Q. and B. Yu, Homotopy method for non-convex programming in un-bounded set. Northeast. Math. J.21(2005),25-31.
Xu, Q., B. Yu and G. C. Feng, Homotopy method for solving variational inequalities in unbounded sets, Journal of Global Optimization,31(2005),121-131.
[100]Xu, Q., B. Yu and G. C. Feng, Homotopy method for variational inequalities, Advances in Mathematics,30(2001),477-479.
[101]Xu, Q., Homotopy method for solving Nash equilibria, to appear.
[102]徐庆,解非线性规划和变分不等式的内点同伦方法,吉林大学博士学位论文,2002.
[103]徐庆、林正华,组合同伦方法在无界域上的收敛性,应用数学学报,27(2004),624-631.
[104]徐庆、朱道立、鲁其辉Nash均衡、变分不等式和广义均衡问题的关系,管理科学学报,8(2005).
[105]Y.F.Sang,B. Yu, A constraint shifting homotopy method for convex multi-objective programming, Journal of Computational and Applied Mathematics,236(2011),640-646.
[106]Yu, B. and Z. Lin, Homotopy method for a class of nonconvex Brouwer fixed point problems, Appl. Math. Comput.,74(1996),65-77.
[107]Yu, B., G. C. Feng and S. L. Zhang, The aggregate constraint homotopy method for nonconvex nonlinear programming, Nonlinear Analysis, TMA,45(2001),839-847.
[108]Yu, B., G. X. Liu and G. C. Feng, The aggregate homotopy method for constrained sequential max-min problems, Northeast. Math. J.,19(2003),287-290.
[109]Yu, B., L. Qi and G. X. Liu, A modified aggregate homotopy method for convex minimax problems, Proceedings of the5th international conference on Opti-mization, ed. Li, D., Hong Kong,(2001),32-38.
[110]Yu, B., Q. H. Liu and G. C. Feng, A combined homotopy interior point method for nonconvex programming with pseudo cone condition, Northeast. Math. J.,16(2000),383-386.
[111]Yu, B., Q. Xu and G. C. Feng, On the complexity of a combined homotopy interior point method for convex programming, J. Comput. Appl. Math已复印,亦见中国科技论文在线,2004,102-169.
[112]Youness EA, Emam T, Chaacteization of efficient solutions of multiobjective Optimization Programming Problems invoving semi-strongly and generalized semi-strongly E-convexity, Acta Mathematica Scientia,28(2008):7-16.
[113]袁亚湘,孙文瑜,最优化理论与方法,科学出版社,北京,1997.
[114]Z. Q. Luo, J. S. Pang, Exact penalization and stationarity conditions of math-ematical programs with equilibrium constraints, Math.Program,75(1996):19-76.
[115]Zhao, Y. B. and J. Han, Exceptional family of elements for a variational inequality problem and its applications, J. Global Optimization,14(1999),313-330.
[116]Zhu, D. L., Q. Xu and Z. H. Lin, A homotopy method for solving bilevel programming problem, Nonlinear Analysis,57(2004),917-928.
[117]Z.H.Lin, D.L.Zhu, Z.P.Sheng, Finding a Minimal Efficient Solution of a Con-vex Multiobjective Program, Journal of Optimization Theory and Applications,118(2003),587-600.