可行问题的投影算法
VIP免费
摘 要
在数学、物理科学和工程技术的众多领域中，大量的问题可以归结为在一组
凸集中寻找其交集中的一点。这个问题通常被称为凸可行问题。凸可行问题广泛
应用于最优化理论、逼近论、图象恢复与重建、控制论和信号与图像处理等方面。
解决凸可行问题较常用的方法是投影算法。
研究凸可行问题的算法及其收敛性，是国内外一个主要的研究方向。当前的
工作就是在针对凸可行问题已提出的投影算法基础上，研究其收敛速度以及各种
改进技巧，并将解决凸可行问题的已有算法推广到更一般的拟凸可行问题，从而，
可行问题的解决更切合实际意义。
本文针对凸可行问题中的凸不等式组，结合凸可行问题投影算法的思想与优
化算法中下降迭代算法，利用凸不等式组自身的特点，设计算法并给出算法的收
敛性分析，同时，将解决凸可行问题广泛使用的投影算法推广到拟凸可行问题。
在第三章，第四章和第五章，介绍了论文的主要结果，概括如下：
第三章：将目前解决凸可行问题的投影算法思想与优化算法中的 Armijo 线搜
索下降迭代算法相结合，研究并设计出解决凸可行问题的算法。建立合理的算法
结构，并对该算法的收敛性进行分析和证明。给出的数值实验说明了算法的有效
性和优越性。
第四章：用
次梯度代替在一般投影算法中所使用的次梯度，首次给出了一
个解决凸可行问题的
次梯度投影算法。根据
次梯度的概念和迭代投影技巧，
建立了一系列的投影超平面
k
S
(选择不同的
k
S
对算法的收敛速度有重要的影
响)．与次梯度投影算法构造的投影超平面相比，这类特殊的投影超平面随着
的
不同而变化。在较温和的假设下给出了该算法的收敛性，并由具体例子说明主要
结果。
第五章：针对文献[24]中解决拟凸可行问题的一系列算法，提出另外一种算
法形式，将其与 Eremin 算法相结合，给出了解决拟凸可行问题的投影算法，并给
出了收敛性的证明，其中拟凸函数并不要求是可微函数，只需满足 Lipschitz 连续。
并在解决凸可行问题的投影算法基础上，利用 Plastria 提出的拟凸函数 lower-次
微分，提出了解决拟凸可行问题的一个不完全投影算法，并证明了该算法的收敛
性。
关键词：凸可行问题 投影算法 Armijo-线搜索
次梯度 拟凸函数
lower-次微分
ABSTRACT
A very common problem in diverse areas of mathematics, physical sciences and
engineering technology consists of trying to find a point in the intersection of convex
sets. This problem is referred to as the convex feasibility problem (CFP). This
fundamental problem has many applications in and outside mathematics fields such as
optimization theory, approximation theory, image reconstruction from projections and
computerized tomography, control theory, signal and image processing, etc. Iterative
projection algorithms have been recommended highly for solving this problem.
The algorithm and convergence for solving the CFP was an active research in and
outside the country. Recently, a number of projection algorithms for solving the CFP
have been proposed. Based on these projection algorithms, the investigation of the
convergence speed and surrogate technique, and the projection algorithms for the CFP
are extended to the QFP, have a realistic sense.
In this paper, we present algorithms and the convergence analysis of those
algorithms which solve the convex inequalities belonging to the CFP in the light of the
ideas of projection algorithms, the frame of the decent iterative algorithm and the
distinguishing feature of the convex inequalities. At the same time, the projection
algorithms for solving the CFP are extended to the QFP.
In chapter 3, chapter 4 and chapter 5, the main results which this paper has
introduced can be summarized as follows:
In chapter 3: A modified iterative projection algorithm by adopting Armijo-like line
search is presented to solve the convex feasibility problem. The convergence of the
proposed algorithm is shown under mild conditions. Numerical test is listed and the
results generated are really impressive, which indicate the line search is promising.
In chapter 4: A
subgradient projection algorithm for solving the convex
feasibility problem is presented for the first time. Based on the iterative projection
methods and the notion of
subgradient, a series of special projection
hyperplanes
k
S
are established (It is worth mentioning that for some problems the
choice of
k
S
may influence significantly the rate of convergence of the algorithm).
Moreover, compared with the existing projection hyperplanes methods with
subgradient, hyperplanes proposed in the paper are interactive with
and its range
are much larger. The convergence of the proposed algorithm is given under some mild
conditions and numerical test is listed and the results generated are really impressive.
In chapter 5: Based on a series of algorithms proposed in [24]for solving the
quasiconvex feasibility problem, Eremin’s projection algorithms for solving the QFP,
where related quasiconvex functions are locally Lipschitzian, but not necessarily
differentiable, are extend. The convergence of the proposed algorithm is shown under
some mild conditions. Also, in the light of projection algorithms for the CFP, a
incomplete projection algorithm is proposed for the quasiconvex feasibility problem
based on Plastria’s lower subdifferential. The convergence of the algorithm is proved.
Key Words: Convex Feasibility Problem, Projection Algorithm,
Armijo-line Search,
subgradient, Quasiconvex
Function, Lower-subgradient
目 录
中文摘要
ABSTRACT
第一章 绪 论 ........................................................ 1
§1.1 凸可行问题的研究背景 ...................................... 1
§1.1.1 凸可行问题的概念 ..................................... 1
§1.1.2 凸可行问题的来源 ..................................... 3
§1.2 凸可行问题的研究方法及现状 ................................ 3
§1.3 研究内容、关键技术和意义 .................................. 4
§1.3.1 研究内容 ............................................. 4
§1.3.2 关键技术 ............................................. 5
§1.3.3 意义 ................................................. 5
第二章 预备知识 ..................................................... 6
§2.1 凸分析基础 ................................................ 6
§2.1.1 凸集和凸集上的投影 ................................... 6
§2.1.2 凸函数及其相关性质 ................................... 8
§2.1.3 凸函数的几种推广 ..................................... 9
§2.1.4 凸函数的次微分和
次微分 ............................ 12
§2.2 算法的概念 ............................................... 13
§2.2.1 下降迭代算法的基本格式 .............................. 13
§2.2.2 收敛性与收敛速度 .................................... 14
§2.2.3 次梯度方法 .......................................... 15
§2.2.4 投影算法概述 ........................................ 17
第三章 Armijo 线搜索投影算法 ........................................19
§3.1 引言 ..................................................... 19
§3.2 预备知识 ................................................. 20
§3.3 算法及其收敛性 ........................................... 22
§3.4 数值实验 ................................................. 25
§3.5 本章小结 ................................................. 27
第四章 近似次梯度投影算法 .......................................... 28
§4.1 引言 ..................................................... 28
§4.2 投影超平面 ............................................... 28
§4.3 算法及其收敛性 ........................................... 29
§4.4 数值实验 ................................................. 31
§4.5 本章小结 ................................................. 34
第五章 拟凸可行问题的投影算法 ...................................... 35
§5.1 引言 ..................................................... 35
§5.2 预备知识 ................................................. 35
§5.3 完全投影法 ............................................... 36
§5.3.1 算法及其收敛性 ...................................... 36
§5.3.2 数值实验 ............................................ 38
§5.4 不完全投影法 ............................................. 39
§5.5 本章小结 ................................................. 42
第六章 结论与展望 .................................................. 44
§6.1 结束语 ................................................... 44
§6.2 未来工作展望 ............................................. 44
参考文献 ............................................................ 46
在读期间公开发表的论文和承担科研项目及取得成果 ...................... 49
致 谢 .............................................................. 50
第一章 绪 论
1
第一章 绪 论
§1.1 研究背景
§1.1.1 凸可行问题的概念
在数学、物理科学和工程技术的众多领域中，大量的问题可以归结为在一组
凸集中寻找其交集中的一点．这个问题通常被称为凸可行问题．凸可行问题在科
学研究、工程技术、经济管理、交通运输和国防等众多领域中，如最优化理论[1]，
逼近论[2]，图象恢复与重建[3]，控制论，信号与图象处理，生物工程，通信等方面，
有着广泛的应用．在优化理论中尤为常见，例如，约束优化问题中的初始可行点
的确定．
凸可行问题的精确描述如下：
假设
X
是有限维空间，
1 2
, , , N
C C C
是
X
中的闭凸集，并且它们的交集非空：
1 2 N
C C C C
．
凸可行问题：求解
x
使得
x C
．
这类问题主要有两种类型：
(1) 在某种意义上，
i
C
是简单的，即在
i
C
的投影能够被简单的计算，例如
i
C
是超平面或半空间．
(2) 在
i
C
上的投影不可能被计算，然而计算包含
i
C
的集合上的投影是可能
的，典型的如
i
C
是某些凸函数的水平集．
解决凸可行问题最常用的方法是投影算法．它的主要思想是根据当前迭代点
到每个
i
C
(或包含
i
C
的集合)的投影从而得到新的迭代点，这样产生一个序列并保
证序列收敛到凸可行问题的解．其利用的主要工具是压缩映射和 Fejer 不等式．详
细的方法综述见文献[4]．
凸可行问题根据它们的应用分为四大类：
(1) 最佳逼近理论：主要包括偏微分方程，复分析，统计(线性预测理论)等，
参见[5]．
(2) 离散模式图像重构：主要包括数字医学图像等，参见[6,7]．
(3) 连续模式图像重构：主要包括信号处理等，参见[3]．
(4) 次梯度方法：主要包括凸不等式组、凸非光滑函数最优化等，参见
[8,9,10]．
通常考虑下属不等式组约束形式的集合
{ : ( ) 0, 1, , }
n
i
C x R f x i m
． (1.1.1)
摘要：
展开>>
收起<<
摘要在数学、物理科学和工程技术的众多领域中，大量的问题可以归结为在一组凸集中寻找其交集中的一点。这个问题通常被称为凸可行问题。凸可行问题广泛应用于最优化理论、逼近论、图象恢复与重建、控制论和信号与图像处理等方面。解决凸可行问题较常用的方法是投影算法。研究凸可行问题的算法及其收敛性，是国内外一个主要的研究方向。当前的工作就是在针对凸可行问题已提出的投影算法基础上，研究其收敛速度以及各种改进技巧，并将解决凸可行问题的已有算法推广到更一般的拟凸可行问题，从而，可行问题的解决更切合实际意义。本文针对凸可行问题中的凸不等式组，结合凸可行问题投影算法的思想与优化算法中下降迭代算法，利用凸不等式组自身的特点...
相关推荐
-
跨境电商商业计划书模版VIP免费
2025-01-09 4 -
跨境电商方案范文VIP免费
2025-01-09 4 -
创业计划书VIP免费
2025-01-09 4 -
xx生鲜APP计划书VIP免费
2025-01-09 4 -
跨境电商创业园商业计划书(盈利模式)VIP免费
2025-01-09 4 -
跨境电商计划书VIP免费
2025-01-09 5 -
绿色食品电商平台项目计划书VIP免费
2025-01-09 4 -
农产品电子商务商业计划书VIP免费
2025-01-09 4 -
农村电商平台商业计划书VIP免费
2025-01-09 4 -
生鲜商城平台商业计划书VIP免费
2025-01-09 4
作者：牛悦
分类：高等教育资料
价格：15积分
属性：53 页
大小：868.15KB
格式：PDF
时间：2024-11-19
