凸可行问题的算法研究

VIP免费
3.0 赵德峰 2024-11-19 4 4 514.29KB 47 页 15积分
侵权投诉
摘 要
在数学、物理科学和工程技术的很多领域中，广泛存在着这样一个问题：在
一些凸集合的交集中寻找满足条件的某些点——这就是所谓的凸可行问题(CFP).
它在很多邻域都有广泛的应用，尤其是在最优化理论、图像处理、控制论和逼近
论等邻域中.在当前针对凸可行问题算法和收敛性的研究，依然是国内外一个主要
和活跃的方向. 本文是在投影算法基础上，研究其收敛性以及各种改进技巧，并
将已解决凸可行问题的算法推广到更一般形式.
本文在第四章，第五章和第六章介绍了主要的研究结果，概括如下：
在第四章中，提出了一种次梯度投影算法求解凸可行问题. 该算法在迭代过
程中采用 Armijo 线搜索规则计算预测步长，且进一步给出一种校正步长规则，从
而使算法的收敛性和收敛效果得到了提高. 最后通过一个数值实例，表明算法的
有效性.
在第五章中，提出了一种凸可行问题的周期
次梯度投影算法. 该算法引入
次梯度代替通常使用的次梯度，推广了周期次梯度投影算法. 基于
次微分
概念，证明了算法的收敛性. 最后通过一个数值实例，表明算法的有效性.
在第 6 章中，提出了一种分裂可行问题的改进算法.该算法通过引入次梯度来
构建半空间取代闭凸集，这样就使投影更加方便计算.另外，算法中采用 Armijo
线搜索线搜索规则计算预测步长，避免了求逆矩阵的过程.
关键词：凸可行问题 投影算法
次梯度 Armijo 线搜索
ABSTRACT
There is a very common problem of trying to find points in the intersection of
some convex sets in diverse areas of mathematics，physical sciences and engineering
technology, which is referred to as the convex feasibility problem (CFP). There are
many applications, especially in the field of optimization theory, image reconstruction,
control theory and approximation theory, etc. Now the algorithm and convergence for
solving the CFP still is still an active research at home and abroad. Based on the
projection algorithm, this article is to study its convergence speed and surrogate
technique，and extends the projection algorithms of the CFP to the more general form.
The main research results of this paper are introduced in chapter 4, chapter 5 and
chapter 6, which can be summarized as follows:
In chapter 4, a sugradient projection algorithm for solving the CFP is proposed.
This algorithm uses the Armijo-like line search rule to calculate predictor step size and
gives a correction step rule in the iterative process, which makes an accelerated
convergence to the solution of the CFP. In the end, a numerical test is listed and the
results generated are really impressive.
In chapter 5, a cyclic
sugradient projection algorithm for the CFP is proposed.
In this algorithm,
subgradient is used to replace the subgradient, which could
extend the cyclic subgradient projection algorithm. Based on the notion of
subgradient, the convergence of the proposed algorithm is given under some mild
conditions. In the end, a numerical test is listed and the results generated are really
impressive.
In chapter 6, a modified algorithm for solving the split feasibility problem (SFP) is
proposed. In this algorithm, subgradient is adopted to establish half space. In this way
the orthogonal projection onto the half space can be computed efficiently. Meanwhile,
this algorithm uses the generalized Armijo line search to compute predictor step size
and needs not to compute the matrix inverses and the large eigenvalue of the matrix.
Key Word ：convex feasibility problem, projection algorithm,
subgradient, Armijo-like line search
I
目 录
中文摘要
ABSTRACT
第一章 绪 论 ....................................................... 1
§1.1 研究背景和意义 ............................................. 1
§1.2 研究现状 ................................................... 2
§1.3 本文结构和主要工作 ......................................... 2
§1.3.1 本文结构 ............................................... 2
§1.3.2 主要工作 ............................................... 3
第二章 凸集和凸函数理论 ............................................ 5
§2.1 凸集 ....................................................... 5
§2.2 凸集上的投影 ............................................... 6
§2.3 凸函数及其相关性质 ......................................... 7
§2.3.1 凸函数的性质 ........................................... 8
§2.3.2 凸函数的 Lipschit 连续性 ................................ 8
§2.4 凸函数的微分及有关性质 ..................................... 9
§2.5 次微分和
次微分 .......................................... 10
第三章 算法和收敛性 ............................................... 13
§3.1 下降迭代算法基本原理 ...................................... 13
§3.2 次梯度法基本原理 .......................................... 14
§3.3 投影算法基本原理 .......................................... 15
§3.4 收敛性与收敛速度 .......................................... 16
第四章 次梯度投影算法 ............................................. 19
§4.1 引言 ...................................................... 19
§4.2 预备知识 .................................................. 19
§4.3 算法和收敛性 .............................................. 21
§4.4 数值实例 .................................................. 25
§4.5 本章小结 .................................................. 26
第五章 周期
次梯度投影算法 ..................................... 27
§5.1 引言 ...................................................... 27
§5.2 预备知识 .................................................. 27
§5.3 算法及其收敛性 ............................................ 28
II
§5.4 数值实例 .................................................. 30
§5.5 本章小结 .................................................. 33
第六章 分裂可行问题的算法研究 ..................................... 35
§6.1 引言 ...................................................... 35
§6.2 预备基础 .................................................. 36
§6.3 算法及其收敛性 ............................................ 36
§6.4 本章小结 .................................................. 40
第七章 结论与展望 ................................................. 41
§7.1 结束语 ................................................... 41
§7.2 未来工作展望 ............................................. 41
参考文献 ............................................................ 43
在读期间公开发表的论文和承担科研项目及取得成果 ...................... 47
致 谢 ............................................................... 49
第一章 绪 论
1
第一章 绪 论
§1.1 研究背景和意义
凸可行问题(Convex Feasibility Problem，简记为CFP)广泛存在于数学研究、物
理科学和工程技术等领域.它是在具体的科学工程应用中形成并不断发展起来的,
在如今的物理科学、生物工程、交通运输、经济管理以及图像处理等很多领域都
有着相当广泛的应用，尤其是在控制论、逼近论[1]、最优化方法[2]、图像恢复和重
建[3]、以及生物工程等方面，就会经常碰到凸可行问题.譬如在最优化方法中，如
何在约束优化问题中确定初始可行点是一类我们经常会遇到的问题.这类问题，常
常并没有好的方法，而通过研究发现该问题可以划归为凸可行问题的一个研究方
面[4,5,6].
在通常情况下，凸可行问题的精确描述如下：
假设
是非空闭凸集，其中
n
R
是希尔伯特空间，且这些非空闭
凸集的交集
C
非空，即
1 2 ... m
C C C C
 
，
本文所研究的凸可行问题就是寻找满足
x C
的点
x
.
一般情况下，上述考虑的非空闭凸集
1 2
, ,..., n
m
C C C R
可以表示为如下不等式
组约束的形式：
{ | ( ) 0, 1, , }
n
i
C x R f x i m
，(1.1.1)
其中
C
为凸集，也就是每个
( )
i
f x
是凸函数，这也称为凸可行问题(CFP).
在介绍了凸可行问题的具体形式之后，我们发现有很多的问题可以转化为求
解凸可行问题，例如在求解线性规划模型、二次规划模型、线性互补模型和约束
线性互补问题的过程中，可以通过运用库恩-塔克条件(K-T 条件)，将这些问题转化
为求解凸可行问题.由于这几种模型在数学、物理科学、图像处理等领域中都会涉
及到，而且通过运用凸可行算法是可以求解的，因此可以说研究凸可行问题是有
非常好的应用价值的.
在介绍了一些凸可行问题的形式之后，下面简单介绍一下在求解凸可行问题
过程中会遇到的一种特殊问题：分裂可行问题(Split Feasibility Problem，简记为
SFP)，它可以看做是凸可行问题的一个特例，通常可以描述如下：
假设
C
、
Q
分别是
n
R
和
m
R
上的非空闭凸集，
A
是
m n
矩阵，分裂可行问题
(SFP)就是要找
x C
，并能满足下式：
Ax Q
，(1.1.2)
如果这样的
x
存在，这就是分裂可行问题.
摘要：

摘要在数学、物理科学和工程技术的很多领域中，广泛存在着这样一个问题：在一些凸集合的交集中寻找满足条件的某些点——这就是所谓的凸可行问题(CFP).它在很多邻域都有广泛的应用，尤其是在最优化理论、图像处理、控制论和逼近论等邻域中.在当前针对凸可行问题算法和收敛性的研究，依然是国内外一个主要和活跃的方向.本文是在投影算法基础上，研究其收敛性以及各种改进技巧，并将已解决凸可行问题的算法推广到更一般形式.本文在第四章，第五章和第六章介绍了主要的研究结果，概括如下：在第四章中，提出了一种次梯度投影算法求解凸可行问题.该算法在迭代过程中采用Armijo线搜索规则计算预测步长，且进一步给出一种校正步长规则，...

展开>> 收起<<
凸可行问题的算法研究.pdf

共47页,预览5页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：赵德峰 分类：高等教育资料 价格：15积分 属性：47 页 大小：514.29KB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 47
评分 收藏
分享
立即下载 VIP免费下载
客服
关注