《多维尺度分析中的算法研究》由会员分享，可在线阅读，更多相关《多维尺度分析中的算法研究（8页珍藏版）》请在金锄头文库上搜索。
1、第卷第期清 华 大 学学报自然 科 学 版多维尺度分析中的算法研究福州大学甘资先清华大 学 应 用数学 系周方俊北京工 业大学应用数学 系肖奕文摘提出一种新的多维尺度分析算法。该算法是对算法进行了实质性的修改而获得的,从而在理论上首次证明了算法的收敛性。所做的数值实验表明文中所提出的算法仍具有良好的实际计算效果。关键词多维尺度分析,收敛性,梯度,相异性分类号引言多维尺 度分 析是在年提出的川。然而使这种方法得到真正的广泛应用要归功 于“和”,他 们对的工作在概念上和计算上进行了实质性 的改进。目前在多维尺度分析中较为有效 而且使用得最多的算法是算法,这个算法最早在软件中实现。虽然算法在实际计算
2、中较有效,但 由于算法本身的回步过程结构,因而在理论上无法保证其收敛性。本文提出了一种新的算法,这种算法保持了算法 的优良特性,并且从理论上得到 了收敛性的结论。在下节中介绍 了多维尺度分析的背景,算法及对该算法 的改进在中介绍,中证明了收敛性结论,数值实验结果 在中给出。问题及其背景多维尺度分析研究这样的问题已知”个研究对 象,每个研究对象都可 以表示为欧氏空间中的一 个点。设已知研究对象两两 间的相异性度量可 以是相似性度量,求出这。个研究对象在该空 间的散布图,使图 中点间 的欧氏距离与已知的相异性度量吻合得尽可能好。许多上述类型 的问题可以抽象为 下面 的数学模型给定”、,、二,一,。
3、,设应力函数为本文于年月日收到第期甘资先等多维尺度分析中的算法研究了,“了,一。“,求解式中,一,劣,。,为维向量,为实数】二为二的欧氏模下 同。为 了保证解的唯一性,一般要求满足如下条件,“ “,乙乙育。公一瀚旋转到 主坐标轴上。上述数学模型,有许多实际背景,举个简单的例子假定有个总统候选人、,通过某种办法得到了他们两两之间的相异性度量氏,通过 上述模型构造出一个点图,由图给 出个 总统候选人 的散布图。从图可 以看出,、主张对抗的外交政策鹰派,、主张缓和鸽派,、主 张高福利的经济政策,主张低消费,在所 有政策上都采用 中间立场。从 图中很容易知道各个总统候选人政治主张上的差异,以便于 改进
4、竞选工作,也有利于选 民选择合适的总统。类似于上述例子,多维尺度分析在社会科学和自然科学等许多领域都有广泛 的应用,如心理学、教育学、社会学、考古学、地质学、市场分析等。心的问题。低消费图个总统候选人的散布图故多维尺度分析的算法研究一直是人们非常关算法求解间题的算法研究可以追 溯到年代。现在通常使用 的求解该问题算法的思想是在年代初形成的,简单地说,这类算法属于不精确一维搜索的最速下降法,其中步长的选取有 良好的直观性。算法的主要步骤如下算法算法给定。及初始结构。广。,一,老。,计算才,二矛。一夕。,确定。,。,使。,。,。,。,置。清华大学学报第卷确定下述几项确定新的迭代点十。一七日。日,几
5、,备,吞一汽月一月口一一合式中八。,全 尘雪为角因子,爪为 机 遇 因子,几为偏性因子,它们是通过经验方法确定的。确定“,“,使“一“,“哭几“,“,“卫妞二卫氏,一了二 丹,斗,乙才,云,了乙十”占、一一,孟孟十无七寸了才如果。十,一。,停否则置吞,转。注记在第步中使用 的是经验步长,因此在迭代过程中有可能出现应力上升的情形,为 避免应力过多上升,采 用“回步”的手段如果八,。、。,。,。,卜,忆 二卜。十户取有口无,孙一二汁不万 不久一甘勺纵组学耕歹 长刀佩术歹下 日甘念十日日订否日 、,继续迭 代,一般允许回步次。注记步长确定为的形式,是基于这样一种观点对各种适 当有效的梯度法,在迭代过
6、程 中,步长可 以变化,甚至可 以相差很多量级,但在相邻两次迭代中,步长一般不会相 差很悬 殊。因此一 个好 的步长在多数情况下近似等于上 次迭代中好的步长。这样如果前次步长近于合适,则本次迭代步长用与 上次迭代步长相似的值如果前次步长太小,则本次用较大 的步 长值否则用 较小的步长值。因此需要有一种确定前次步长是否太大或太小的方法。而且这 种方法应该以获得 的计算信息为基础。从直观上看,相 继两次迭代梯度间的夹角提供了一 个有用 的信息若。,合适,则,接近该直线上的一 维极小,而在极小点处,二旷,因此若接近。,则前次步长合适,可 取近 于前次 的步长。若前 次步长太小,则。与。接近,从 而接
7、近零,因 此当前 要用较大 的步长。若前次步长太大,则接近“,本次步长应 用较 小的值,这样新步长二老步长“、 ,卜令一一丁瓦“一、盆图两次迭代梯度间的夹角“就是角因子。若考虑迭代 的整个过程,角因子 的形式可 以稍加改变”。迭代过程 中相继两次 迭代应力值的变化,也提供了一个可用的信息。由于机遇,相继二次迭代中,应力可能极陡地下降,可以假设这种现象反映出到达极 小值附近的机遇,如果发生这种情况,则 不 必离一开低 应力区,而应在下次迭代中取不是太大的步长继续做下 去,因 此引入如下 的机遇因子盆 了,。一,第期甘资先等多维尺度分析中的算法研究综合考虑 应力值与梯度夹角的变化,引入 了偏性因子
8、八。几 有同 样的直观背景。基于上述一些考虑,一般取卜云“轰亿,。几“云正一乙七。,刀。一告。,子一一一一忍无、“百田“,。,合。一,号哭“哪。一川川】,否西二近年来,这类算法在使用中都有很好的收敛效果。但是迄今为止,理论上还没有得到任何收敛性结论。事实 上,由于算法中回步原则的形式,在整个迭代过程中,应力值的上升量难以控制,因此在理论上无法保证好收敛。这样,算法不一定能够根据终止原则。一。终止。本文提出的新算法算法,保持了算法中确定初始步长的直观合理性,又对回步原则进行修改。在不增加计算量的前提下,使算法的收敛性在理论上得到保证。算法同算法中的。给定任,。任,整数确定新的迭代点。十一式 中,
9、一砂一了 卜八几全、盆、几 分别 由式人七,。为使下式成立的第一个非负整数几七殆,。,给出,七“。一、。一,“。二一尹 飞、。,了价含优一,同算法中的。如果,十,一。,停否则,转。清华大学学报第卷由式可以看出,新的应力值十可 以比上一次的应力值。有所上升,只要。、相对于。有一定的下降量,则不再 回步。这样,算法中的回步原则定量地控制了应力值的上升。收敛性结论为证明收敛性结论,需要下 面 的引理设口。,镇,。,。,。引理。,儿。口。证明用 归纳法。当时,显 然有,“。,任。设簇二时,有,。仁。,则对存,由二、,二十,十镇二一人。于是。,二十,。十二但镇,于是 由归纳法假设可知二,。十,。任。证毕
10、。引理。,。由算法确定,则。收敛。证明首先证 明,单调下降。,十饥成 仇。十,但 由式,因此十毛。,即。收敛。证毕。下面证 明本文的主 要结论。定理由算法确定的单调下降。另一方面,由定义。,因此。收敛。证明由式有由引理有叮,咔公。毛。一下一,。一。设伪十十,下 面证 明对任意 的整数,以下两式成立。“几。一介。,一,全。,“几,十。用归纳法。当时,式显然成立,因为仁“存。日全。,一宁,一,日“介“卜全。,一因此宁。 一宁。 一川二人卜十冈另一方面、皆为的连续函数,于是 由。为紧集,有个。一全一,卜全,、一全。一,卜。第期甘资先等多维尺度分析中的算法研究幻但宁,宁。,个。,一全,一,全,一,宁。
11、,一川】会一宁, 一,日全。一宁。,一全。,一食一,因而对了,式成立。设对给定的整数,、式成立,则由式,有全。一,毛宁。,一丫入个。卜,宁,一由引理即式对及归纳假设,有介,一,个,一,十成 立,且此时】宁。一,一全、,几。十留,于是,类似二时的推导,可知式对也成立。对任意的正整数 气,产、几一白一。全 。一层人全 一,八一全。 一宁一川而一一寿一镇户八、几一为 一 则 由。十一全、簇口人宁一,八九可知乙。一宁,为今十沈于是,类似时式 的推导,有即,收敛。证毕。注记由上述定理的证 明,还得到了即。一。卜。几一争十民为,十的。二十为仗 注记相 应 于本文中的应力函数的结构方程为,占,从收敛性结论
12、的证 明过程 可以看出,对于更 广泛 的一类结构方程,了,“ “,只要连续,仍然可以得到同样的收敛性结论。目前多维尺 度分析方法所讨论 的大多数的模型都具有这样的性质。数值实验为 了比较算法与算法的实际计算效果,做了一 些数值实验。具体例子取自根据算法所 编制的软件的检测报告。计算中取一一丫一一 一一表中的代表空 间维数,为最后 的应力值。清华大学学报第卷表数值实验结果算法算法 问题代号几几谧司几一甘,曰斤砚,工,上,丹口。孟占,丹,月,曰。曰,自,上述所有的计算都是 在大 型机一上完成的。从 上述计算结果 可以看出,算法与算法在计算时间上几乎没有什么差别,但算法在理论上可 以保证收敛性。当然
13、,调整算法中参数的取值,可能获得更好 的计算结果,但 由于本文 的主 要 目的并不在此,因 此这方面没有做进一步的数值实验。文 中的算法模型,还可用于一般的无约束优化 问题。参考文献,七七,一七七七七,一,一,七,河,一七,七,七七,第期甘资先等多维尺度分析中的算法研究七,七,七七,七尸怜 科技简讯 精仪系研制成功“新型储能式运动假肢”首次使用打破伤残人跳远世界 纪录为研制有储能功能的适合于残疾人运动员使用的下肢运动假肢,精密仪器与机械原理教研组金德闻等教师从年开始研究,经过 两年多的艰苦努力,于年月日研制成功。我 国著名伤残人 运动员天津体育学 院学生孙长亭使用这种假肢于年月日在天津市第三届大学 生运动会跳远比赛中跳出了的好成绩,这 项成绩比他穿德意志联邦共和 国制造 的假肢跳出的最好成绩还超过,一举打破了该项 比赛的世界 纪录世界纪录为。此成绩已为这次运动会的组委会所确认,并正在通过天津市向国家体委 申报。孙 长亭表示再经过一段时间 的适 应性训 练后,有信心进一步提高跳远成绩,并 向伤残六运动员短跑的世界纪录冲刺。
