带锥约束的优化问题的弱尖锐性研究

【作者】 罗洪林；

【导师】 黄学祥；

【作者基本信息】 复旦大学 ， 运筹学与控制论， 2010， 博士

【摘要】 二十世纪七十年代晚期,B.T. Polyak在文献[88]中提出了尖锐性(即：强唯一局部极小解)的概念。尖锐性是用来研究某些优化问题的扰动问题的稳定性以及用来分析求解这些问题的算法的收敛性的重要工具。L. Cromme和B.T. Polyak对单目标优化问题的尖锐性的相关研究大大促进了这一类问题研究的发展。二十世纪八十年代晚期,M. C. Ferris在文献[37]中提出了弱尖锐性的概念。弱尖锐性考虑了问题的解的非唯一性,因此,弱尖锐性的概念推广了尖锐性。由于弱尖锐性主要存在于凸规划和凸组合规划问题中,比如：线性规划,线性互补问题和投影问题等,因此,人们主要着重于对这些凸问题的弱尖锐性的研究。本文主要研究了带锥约束的单目标凸优化问题的广义弱尖锐性、带抽象约束集的多目标优化问题的适定性以及带锥约束的多目标优化问题的弱Φ尖锐性。主要工作如下：在第二章中,对带锥约束的单目标凸优化问题,我们引入了广义弱尖锐性的概念。在巴拿赫空间和希尔伯特空间中,我们分别给出了该问题具有广义弱尖锐性的一些充分条件、必要条件和充分必要条件。特别地,当问题的解集满足Robinson约束规格时,我们还给出了该问题具有广义弱尖锐性的几个充分必要条件。在希尔伯特空间中,我们设计了求解这类带约束的单目标凸优化问题的一种算法。当该问题具有广义弱尖锐性时,我们证明了该算法具有有限时间收敛性。在第三章中,我们首先引入了由Zheng和Ng在文献[105]中对凸组合优化问题给出的局部弱尖锐解的概念,我们发现这种局部弱尖锐性的定义非常具有局限性,因为,即便是对于一般的线性规划问题也可能不具有这类局部弱尖锐性。为了打破这个局限性,我们对带锥约束的凸单目标优化问题引入了第一型广义弱尖锐性的概念,并给出了该问题具有第一型广义弱尖锐性的一些充分条件、必要条件和充分必要条件。然后,对于这类带锥约束的单目标凸优化问题,我们引入了几类强KKT条件,并利用这些强KKT条件刻画了问题的第一型广义弱尖锐性。最后,应用所得到的第一型广义弱尖锐性的某些结果,我们讨论了一类非退化的可微凸锥包含问题的误差界。在第四章中,我们研究了带抽象约束集的多目标优化问题的适定性,其中该问题的决策空间X为有限维赋泛线性空间,目标空间Y是一般的赋泛线性空间。对于这类多目标优化问题,我们给出了使得该问题具有广义适定的几个充分条件和必要条件。我们所得到的结果推广了文献[26]中的大部分结果。在较弱的条件下,我们证明了一般的线性多目标优化问题、一类分段线性多目标优化问题和一类多目标二次凸规划问题都具有广义适定性。在第五章中,对于带锥约束的多目标优化问题,我们引入了弱Φ尖锐性的概念和该问题具有弱Φ尖锐性的几个充分条件、必要条件和充分必要条件。建立了一类广义适定性与弱Φ尖锐性之间的相互关系。当该问题的解集具有弱Φ尖锐性时,我们讨论了该问题的扰动问题的稳定性：我们证明了含参数的带锥约束的多目标优化问题的解集映射具有上Holder连续性。更多还原

【Abstract】 The notion of sharp minima, or strongly unique local minima due to B. T. Polyak [88], emerged in the late 1970s as an important tool in the analysis of the perturbation behavior of certain glasses of optimization problems as well as in the convergence analysis of algorithms designed to solve these problems. The related study of sharp minima for single objective optimization problems of L. Cromme and B. T. Polyak is of particular importance in this development. In the late 1980’s M. C. Ferris coined the term weak sharp minima to describe the extension of the notion of sharp minima to include the possibility of a non-unique solution set. The study of weak sharp minima is motivated primarily by applications in convex, and convex composite programming, where such minima commonly occur. For example, such minima frequently occur in linear programming, linear complementarity, and least distance or projection problems. In this paper, we study generalized weak sharp minima for convex optimization problems with cone constraints and weak (?)-sharp minima for multi-objective optimization problems with cone constraints. The main research works are as follows.In chapter two, we introduce a notion of generalized weak sharp minima for convex optimization problems with cone constraints. We study it in the Banach space and Hilbert space settings, respectively. Several characterizations for the solution set to be a set of generalized weak sharp minima for convex optimization problems with cone-constraints are provided. In particular, under the assumption that Robinson’s constraint qualification holds over the solution set, we give several necessary and sufficient conditions for the generalized weak sharp minima property of convex optimization problems with cone constraints. As applications, we propose an algorithm for convex optimization problems with cone constraints in the Hilbert space setting. Convergence analysis of this algorithm is given.In chapter three, We first introduce a notion of local weak sharp solutions for convex-composite optimization problems given by Zheng and Ng [105]. We find that this definition is very limited in applying to the usual mathematical program-ming. Even for linear programming, it is shown that the solution set is not that type of local weak sharp solutions. In this section, we consider a class of convex optimization problem with cone constraints in Banach spaces. We introduce a new notion:type I generalized (local) weak sharp minima for the convex conic optimiza-tion problem. Several types of strong Karush-Kuhn-Tucker characterizations and criteria for a feasible point to be a type I generalized local weak sharp minimum are given. As applications, local error bounds for a class of non-degenerate conic differential convex inclusion problem are studied.In chapter four, we study generalized well-posedness for multi-objective opti-mization problems with cone constraints in the case when the decision space X is a finite dimensional normed space and the object space Y is a normed vector space ordered by a closed convex cone with nonempty interior or a polyhedral cone with nonempty interior. Our results generalize most of the corresponding ones established by Deng [26]. Finally, under mild conditions, we also show that general linear vector optimization problems, a class of piecewise linear vector optimization problems and a class of convex vector quadratic programs are generalized well-posed.In chapter five, we study weak (?)-sharp minima for multi-objective optimiza-tion problems with cone constraints in the Banach space. Several sufficient or necessary conditions for existence of such class of weak sharp minima are obtained. The relationships between weak (?)-sharp minima and a type of well posedness for multi-objective optimization problems with cone constraints are established. As applications, we prove upper Holder continuities of the solution set-valued mapping to the corresponding parametric multi-objective optimization problems with cone constraints.更多还原