求可测函数的总体极小值方法的收敛性分析

[1]中提出了求解连续函数f(x)总体极小值的均值算法，并证明了算法的全局收敛性．若假设f(t)是定义在某可测集G上的可测函数，本证明了均值算法产生的迭代序列全局收敛到f(t)的本质极小值，若进一步假设函数f(t)满足测度Lipschitz条件，还证明了求可测函数的均值算法是线性收敛的．     

一类带非精确线性搜索的 DFP 算法

众所周知,以DFP和BFGS为代表的拟牛顿法是解无约束非线性规划问题:min{f(x);x∈R~n}的最常用和最有效的方法之一。但是在实际计算中,若选择步长因子时作的线性搜索“低精度”时,DFP算法的计算效果有时并不理想。而且,尽管1976年Powell证明了带非精确线性搜索的BFGS算法有一步超线性收敛率,1988年吴士泉采用重复使用原始正定矩阵的方法使得算法中用到的变尺度矩阵及其逆阵的迹有界,并且证明这类修改后的DFP算法,对一致凸目标函数,当线性搜索是非精确时,也具有一步超线性收敛率。但是对一般的DFP算法相应的结论是否成立,至今还是一个没有解决的问题。     

结合广义Armijo步长搜索的超记忆梯度算法及其收敛特征

对无约束规划 ( P) :minx∈ Rnf ( x) ,其中 f ( x)是 Rn→ R1上的一阶连续可微函数 ,设计了一个超记忆梯度求解算法 ,并在去掉迭代点列 { xk}有界和广义 Armijo步长搜索下 ,讨论了算法的全局的收敛性 ,证明了算法具有较强的收敛性质     

非光滑优化的二阶必要条件

1 引言 对无约束最优化问题,其必要条件要求在局部极小点x处沿任何方向的梯度为零,曲率为正。而对约束最优化问题,首先它的局部极小点必须是可行点,其次不仅要求验证局部 极小点的某个邻域内的二阶项(曲率),而且也要认识到约束曲率也起相当重要的作用。现实中存在这样的问题,在x点处G正定,而它不是局部极小点。因此必须考虑约束最优化问题的二阶必要性条件。 本文研究了非线性规划的二阶必要性条件,其约束函数的一阶导数为方向Lipschitz连续。 2 方向Lipschitz连续函数的性质 定义2.1 设f是R~n上的一个广义实值函数,f在x∈R~n处有限,称f在x处是方向Lipschitz连续的,如果至少存在一点y∈R~n使得 其中( 定义2.2 设f如定义2.1,定义f在R~n处的次导数集如下 其中 本文多次引用f↑(x;y),因此我们首先介绍f↑(x;y)的3个基本性质:     

无约束非光滑优化问题信赖域算法的收敛条件

1 引言 考虑下列无约束非光滑优化问题 minf(x),(1) x∈R~n,其中f为R~n上的局部Lipschitz函数,本文将‖·‖_2简记为‖·‖.记下列信赖域子问题为S∪B(x,△). min m(x,s)=φ(x,s)+1/2s~TBs, 其中φ:R~(2m)→R为f的迭代函数。 对于无约束非光滑优化问题(1),[11],[13],[3]、[4]和[5]分别在特殊的条件下给出了信赖域算法用以求解(1)的收敛性结果。最近,[10]、[2]和[6]在不同的假设条件下分别给出了信赖域算法求解无约束非光滑优化问题的一般模型,并在子问题的目标函数满足局部一致有界性条件时证明了算法模型的整体收敛性。在目标函数满足某种正则性条件时,[11]和[9]给出了当信赖域子问题的目标函数中二次项不满足一致有界性条件时的收敛性结果.本文则在目标函数仅为局部Lipschitz函数时得到了和[8]、[11]、[9]相同的收敛性结果。     

Broyden算法类中两个新的开关算法

<正> 本文从变分的角度,对求解无约束最优化问题 minf(x)x∈R~n给出了Broyden算法中两个新的开关算法。在Wolfe不精确线性搜索的准则下,证明了它们具有全局收敛性,并对超线性收敛进行探讨。计算实例表明,新算法是有效的。     

求解广义互补问题

1 引言 设为一闭凸锥,f是R~n到自身的一映射.广义互补问题,记作GCP(K,f),即找一向量x满足 GCP(K,f) x∈K,f(x)∈且x~Tf(x)=0,(1) 其中,是K的对偶锥(即对任一K中向量x,满足x~Ty≤0的所有y的集合).该问题首先 由Habetler和Price提出.当K=R_+~n(R~n空间的正卦限),此问题就是一般的互补问题.许多作者已经提出了很多求解线性或非线性互补问题的方法.例如:Dafermos,Fukushima,Harker和Price以及其它如参考文献所列.近年来,何针对单调线性变分不等式提出了一些投影收缩算法. Fang在函数是Lipschitz连续及强单调的条件下,在[3]给出一简单的迭代投影法,在[4]中给出一线性化方法去求解广义互补问题(1).在[3]中,他的迭代模式是     

关于乘子法的一种新算法

本文提出了关于增广乘子法的一种新算法.证明了该算法的合理性及其收敛速率为超线性的.对于非线性规划问题:(P)minf(x) x∈R~ns.t.h(x)=0,g(x)≤0.其中f:R~n→R~1;h:R~n→R~m;g:R~m→R~p均为二次连续可微.等式与不等式的有效约束的     

修改的DFP算法

众所周知,以DFP和BFGS为代表的变尺度算法是数学规划中最常用和最有效的方法之一.但是在不假定目标函数f(x)是凸的情况下,这类算法的整体收敛性还是一个没有完全解决的问题.本文提出一类修改的DFP算法,简称为MDFP算法.具体步骤如下:     

求解非单调变分不等式的一种半空间投影算法

本文提出了一种求解非单调变分不等式的半空间投影算法,在映射是连续和对偶变分不等式解集非空的假设条件下证明了该算法生成的无穷序列是全局收敛的,并在局部误差界和Lipschitz连续条件下给出了收敛率分析.通过数值实验验证了所提出算法的有效性和可行性.     

Lipschitz函数近似次微分的凸性

A.D.IOFFE 在研究不可微优化中针对一类 Lipschitz 函数提出了近似次微分的概念.有许多问题有待解决.本文主要讨论了 Lipschitz 函数近似次微分的凸性,并在一维的情况下给出了一个充分条件.为方便起见,我们用“f∈L.(R~m→R~1)”来表示“f 是 R~m 上的 Lipschitz 函数”.定义1 设 R~n 为 n 维欧氏空间.f:R~n→R~1,|f(x)|<+∞,定义 f(x)的 Dini 导数为     

基于简单二次函数模型的带线搜索的新信赖域算法

基于简单二次函数模型,结合非精确大步长Armijo线搜索技术,建立了一个新的求解无约束最优化问题的组合信赖域与线搜索算法,在目标函数梯度▽f(x)在R~n上一致连续条件下证明了算法的全局收敛性.数值例子表明算法是有效的,适合求解大规模问题.     

退化线性约束凸规划问题的变尺度法

考虑问题: (?)f(x) (NP)其中R={x∈R~n|a_i~Tx≤b_i,i=1,…,m},f(x)一阶连续可微且凸。本文在R退化条件下,给出了一个整体超线性收敛的变尺度法。记N={1,…,m),J(?)N,记A_J={a_i|i∈J}。当γ(A_J)=|J|时,R~n到 R_J={x∈R~n|a_i~Tx=0,i∈J}的正投影矩阵P_J=E_n-A_J(A_J~TA_J)~(-1)A_J~T。若{a_i|i∈I}和{a_i|i∈J}都是{a_i|i∈N′(?)N}的最大线性无关组,则P_J=P_I。x~k∈R,记N_k={i∈N|a_i~Tx~k=b_i},gk=▽f(x~k)。     

非线性最优化的抽象算法模型及非闭性收敛条件的研究(下)

本文叙述了具有单调性的最优化算法的若干重要的收敛性条件,包括这方面最近的新成果,并且证明了新的收敛性条件比文献中已有的条件要严格地弱;其次讨论了常见的可行点算法类的一致可行性收敛条件,证明了本文介绍的新的收敛性条件比一致可行性收敛条件要弱。 1.单调最优化算法的全局收敛性大多数具体的最优化算法是单调算法,即对应于迭代点列{x_i}的某一函数f(目标函数或特定的另一函数)的值{f(x_i)}是单调数列,所以文献中对于单调的抽象算法模型的全局收敛性研究很多。Zangwill提出的第一个抽象算法和相应的收敛性条件就是关于单调算法的。对于这类算法,函数值{f(x_i)}的单调性与算法的全局收敛性有密切关系。一般而言,单调算法的收敛性条件比较简单些,见文献以[1～6],[8～15]。在文献[12]中,     

全局优化问题随机型方法综述

本文综述了七十年代以来全局优化问题随机型方法的若干研究成果,重点是最近几年的某些新结果.§1 引言全局优化问题足寻求实值日标函数 f:R~n→R 的全局极值点(例如极小点)x,即求一点 x∈R~n 使得     

可行方向法的一个统一探讨

本文给出了一种一般理论,讨论非线性规划min{f(x)|Ax=b,x≥0}的某类可行方向方法的全局收敛性。在 f∈C~1和约束条件为非退化的假定下,提出了下降可行方向的一般模型以及一类可行方向算法,并且证明了这类算法在某些条件下是全局收敛的。这里验证了文献中常见的一些可行方向法都是这类算法的特例,并且也满足本文中提出的收敛性条件。最后构造出几种新的可行方向方法,它们都具有全局收敛性。     

不用导数求函数无约束极小值的一种方法

本文在Powell法和华罗庚的抛物体法的基础上提出了不用导数求函数无约束极小值的一种新方法。方法的基本思想是,将所给的非线性函数φ(x)在初始点x_1附近用一个近似二次函数f(x)来代替,对这个二次函数求出R~n上或一个子空间上的极小点x_2,并以此作为新的初始点,重复迭代过程,直至求出一个极小点的满意的近似点。本文给出了计算实例,显示了本方法具有比目前公认的有效算法——变尺度法收敛速度快的优点。     

非线性规划的拟下降方法：概念,模型及应用

§1.引言 考虑一般非线性规划问题: (P)min{f(x)|x∈S},其中S?R~n为一非空闭集,f:R~n→R~1。 求解(P)的下降算法的基本思想是:在当前点x_k∈S处,(若x_k不是某种期望的     

可行方向法的一个统一探讨

本文给出了一种一般理论,讨论非线性规划 min{f(x)|Ax=b,x≥0}的某类可行方向方法的全局收敛性.在 f∈C~1和约束条件为非退化的假定下,提出了下降可行方向的一般模型以及一类可行方向算法,并且证明了这类算法在某些条件下是全局收敛的.这里验证了文献中常见的一些可行方向法都是这类算法的特例,并且也满足本文中提出的收敛性条件.最后构造出几种新的可行方向方法,它们都具有全局收敛性.     

解变分不等式的一种二次投影算法

该文研究一种新的解变分不等式的二次投影算法.通过构造一类新的严格分离当前迭代和变分不等式解集的超平面,进而建立了解决伪单调变分不等式投影算法的一种新的框架.通过改进已有结果的证明方法,证明了该算法生成的无穷序列是全局收敛的,并且在局部误差和Lipschitz条件下给出了收敛率分析.