可行问题的投影算法

VIP免费

3.0 牛悦 2024-11-19 6 4 868.15KB 53 页 15积分

侵权投诉

摘要

在数学、物理科学和工程技术的众多领域中，大量的问题可以归结为在一组

凸集中寻找其交集中的一点。这个问题通常被称为凸可行问题。凸可行问题广泛

应用于最优化理论、逼近论、图象恢复与重建、控制论和信号与图像处理等方面。

解决凸可行问题较常用的方法是投影算法。

研究凸可行问题的算法及其收敛性，是国内外一个主要的研究方向。当前的

工作就是在针对凸可行问题已提出的投影算法基础上，研究其收敛速度以及各种

改进技巧，并将解决凸可行问题的已有算法推广到更一般的拟凸可行问题，从而，

可行问题的解决更切合实际意义。

本文针对凸可行问题中的凸不等式组，结合凸可行问题投影算法的思想与优

化算法中下降迭代算法，利用凸不等式组自身的特点，设计算法并给出算法的收

敛性分析，同时，将解决凸可行问题广泛使用的投影算法推广到拟凸可行问题。

在第三章，第四章和第五章，介绍了论文的主要结果，概括如下：

第三章：将目前解决凸可行问题的投影算法思想与优化算法中的 Armijo 线搜

索下降迭代算法相结合，研究并设计出解决凸可行问题的算法。建立合理的算法

结构，并对该算法的收敛性进行分析和证明。给出的数值实验说明了算法的有效

性和优越性。

第四章：用



次梯度代替在一般投影算法中所使用的次梯度，首次给出了一

个解决凸可行问题的



次梯度投影算法。根据



次梯度的概念和迭代投影技巧，

建立了一系列的投影超平面

(选择不同的

对算法的收敛速度有重要的影

响)．与次梯度投影算法构造的投影超平面相比，这类特殊的投影超平面随着



的

不同而变化。在较温和的假设下给出了该算法的收敛性，并由具体例子说明主要

结果。

第五章：针对文献[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

are established (It is worth mentioning that for some problems the

choice of

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]，

逼近论[2]，图象恢复与重建[3]，控制论，信号与图象处理，生物工程，通信等方面，

有着广泛的应用．在优化理论中尤为常见，例如，约束优化问题中的初始可行点

的确定．

凸可行问题的精确描述如下：

假设

是有限维空间，

1 2

, , , N

C C C

是

中的闭凸集，并且它们的交集非空：

1 2 N

C C C C    

．

凸可行问题：求解

使得

x C

．

这类问题主要有两种类型：

(1) 在某种意义上，

是简单的，即在

的投影能够被简单的计算，例如

是超平面或半空间．

(2) 在

上的投影不可能被计算，然而计算包含

的集合上的投影是可能

的，典型的如

是某些凸函数的水平集．

解决凸可行问题最常用的方法是投影算法．它的主要思想是根据当前迭代点

到每个

(或包含

的集合)的投影从而得到新的迭代点，这样产生一个序列并保

证序列收敛到凸可行问题的解．其利用的主要工具是压缩映射和 Fejer 不等式．详

细的方法综述见文献[4]．

凸可行问题根据它们的应用分为四大类：

(1) 最佳逼近理论：主要包括偏微分方程，复分析，统计(线性预测理论)等，

参见[5]．

(2) 离散模式图像重构：主要包括数字医学图像等，参见[6,7]．

(3) 连续模式图像重构：主要包括信号处理等，参见[3]．

(4) 次梯度方法：主要包括凸不等式组、凸非光滑函数最优化等，参见

[8,9,10]．

通常考虑下属不等式组约束形式的集合

{ : ( ) 0, 1, , }

C x R f x i m    

． (1.1.1)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要在数学、物理科学和工程技术的众多领域中，大量的问题可以归结为在一组凸集中寻找其交集中的一点。这个问题通常被称为凸可行问题。凸可行问题广泛应用于最优化理论、逼近论、图象恢复与重建、控制论和信号与图像处理等方面。解决凸可行问题较常用的方法是投影算法。研究凸可行问题的算法及其收敛性，是国内外一个主要的研究方向。当前的工作就是在针对凸可行问题已提出的投影算法基础上，研究其收敛速度以及各种改进技巧，并将解决凸可行问题的已有算法推广到更一般的拟凸可行问题，从而，可行问题的解决更切合实际意义。本文针对凸可行问题中的凸不等式组，结合凸可行问题投影算法的思想与优化算法中下降迭代算法，利用凸不等式组自身的特点...

展开>> 收起<<

可行问题的投影算法.pdf

共53页,预览6页

还剩页未读，继续阅读

可行问题的投影算法

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: