I am studying MATLAB recently, for the requirement of the Structural Optimization course. MATLAB is such a robust math tool that I have lots of commands and algorithms to learn. What I post below is some great material about fmincon function from SimWe Forum. The original author of this post is clarkyeah in SimWe Forum.fmincon命令浅析
命令格式:
[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
如matlab帮助文档中所述,fmincon命令使用的算法对于大规模优化问题和中等问题是有所区分的:
Large-Scale Optimization
The large-scale algorithm is a subspace trust region method and is based on the interior-reflective Newton method described in [1] and [2]. Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG)..
Medium-Scale Optimization
fmincon uses a sequential quadratic programming (SQP) method. In this method, the function solves a quadratic programming (QP) subproblem at each iteration. An estimate of the Hessian of the Lagrangian is updated at each iteration using the BFGS formula. A line search is performed The QP subproblem is solved using an active set strategy.
这里试图回答三个问题:
1.
什么Large-Scale Optimization,什么是Medium-Scale Optimization?
2.
fimcon提供的subspace trust region和sequential quadratic programming方法原理?
3.
BFGS公式和线性搜索是什么?
问题1
所谓大规模问题指的是出现在工程,化学等领域中有大量优化变量的问题。由于自变量的维数很高,这样的问题是被分解成多个低维子问题来求解的。Medium-Scale优化问题实际上是matlab自己提出和大规模问题对应的一个概念,就是通常一般的优化算法,如牛顿法,最速下降法之类的处理优化变量不是很多的问题。
问题2
对于大规模问题,fmincon采用了subspace trust region优化算法。这种算法是把目标函数在点x的邻域泰勒展开(x可以认为是人为提供的初始猜测),这个展开的邻域就是所谓的trust region,泰勒展开进行到二阶项为止:
Q(x) = 1/2*
(1)
这时目标函数在某一个局部的特性就可以“看出来了”。在这样的一个邻域里,我们求一个新的点x1,使得目标函数值减小,这个问题相比于原来的问题要简单。然而实际上对于存在非常大规模优化变量的问题,直接对这个子问题的求解仍然是不可忍受的。
同时我们注意到,由于泰勒展开要进行的第二项,这就要求我们能够提供一阶导计算的函数。如果我们不能提供一阶导表达式,二阶导(Hessian矩阵)matlab是无法计算的。所以我们使用fmincon命令而不给一阶导表达式,fmincon会放弃使用大规模算法。
如前所述,原问题转化后的直接求解仍然是无法忍受的,通过进一步近似subspace trust region将这个问题局限在trust region的二维子空间内求解。
序列二次规划方法是将一个带有等式和不等式约束(可以是非线性)的非线性优化问题转化为二次规划问题求解,二次规划问题类似公式(1)形式。具体转化过程可以参考:
http://www.caam.rice.edu/~adpadu/talks/sqp1.pdf
问题3
对于medium-scale问题,求解二次规划问题涉及到Hessian矩阵。Hessian矩阵的近似计算是通过拟牛顿法得到的,拟牛顿法提供了两个公式可用于Hessian矩阵(或其逆)的迭代:BFGS公式和DFP公式),而初始的Hessian矩阵是任意给的,如给一个单位阵I。
BFGS公式如下:
H(k+1) = H(k) + /
-
/
(3)
总结:
fmincon运行首先检查有无梯度表达提供,如有则选则大规模算法(subspace trust region),由此涉及到Hessian阵的近似计算,由于已提供了梯度的公式,则Hessian阵可以直接通过有限差分计算。但是如果用户直接提供了Hessian计算公式,则直接计算。
如果没有梯度表达式提供,fmincon选则SQP算法,算法中Hessian阵可以通过BFGS迭代,初始Hessian阵任给。注意BFGS公式中q项是需要计算目标函数梯度得到的。所以Hessian矩阵的近似计算是需要用到有限差分法。
Sunday, November 22, 2009
[+/-] |
fmincon函数浅析(ZT) |
Friday, October 23, 2009
[+/-] |
制作一个U盘当光驱,Windows 7安装新方法【ZT】 |
重装了系统,X200没有光驱,上网搜了下U盘安装的方法,下面这个有效,转载一下,免得下次麻烦。
PS:微软提供给UW学生的Win7是免费的,这个福利不错之前的博文提到过无光驱的电脑,系统安装是一个问题,另外,在32位(包括WinRE\WinPE)系统上执行64bit系统的的安装程序就会报错,在没有光驱的情况下,如果从硬盘上安装64bit Win7需要一点点技巧,这个方法可以帮助你完成系统的安装。不过,对于有U盘、SD卡、移动硬盘的朋友,可以借助这些个工具来帮你安装系统。
适用范围:所有情况的Windows Vista/7/2008系统的全新安装(包括32bit和64bit系统)。不过有两个前提,一是主板支持从U盘启动,二是U盘容量必须在3GB以上(放得下解压后的Vista光盘文件即可)。
★制作可启动的U盘方法一:
1.用diskpart命令来准备U盘。将U盘插到电脑上,打开cmd命令提示窗口(如果是Vista、Win7需要以管理员权限来运行),然后逐个输入以下命令:
diskpart
list disk(显示当前系统下的所有磁盘)
select disk 1(1为U盘在系统中的磁盘编号)
clean(清空U盘的文件格式和内容)
create partition primary(在U盘上建立主分区)
select partition 1(选择刚建立的分区)
active(激活主分区,否则无法启动)
format fs=NTFS quick(快速将当前分区格式化为NTFS格式)
assign letter=U(分配U作为盘符)
exit
2.复制安装文件。使用虚拟光驱等工具把ISO里面的全部文件解压到U盘上。
3.完成上述的步骤之后,一个相当于光盘的U盘就制作好了。在任意一台需要安装Win7的电脑上,进入BIOS设置从U盘启动即可进入跟光盘相同的安装界面了。
补充说明:
1.如果你没有这么大的U盘,那么你还可以稍微延伸一下,只要将部分文件放到U盘,也就是bootmgr、boot目录以及source中的boot.win文件,一共在200多MB(256MB的U盘就够了),其他文件放在硬盘就可以。
2.如果你没有U盘,也没关系,你还可以在系统上找一个主分区,将光盘中所有的文件拷贝到分区的根目录,然后通过diskpart或磁盘管理器将该分区设置为活动分区,重启后就直接从这一分区启动了。切记安装系统之前记得在diskpart将目标分区设置为活动,通常就是C盘,然后再安装Win7或vista,否则启动系统的分区依然是你之前的所选择的那一个,而不是Win7所在的分区了。
★制作可启动的U盘方法二:
将安装程序写入到u盘,并且u盘启动安装直接用ultraiso这个软件就是了。
用管理员身份启动ultraiso,然后打开对应的iso文件,之后选择 启动 -- 写入硬盘映像 ,在里面选择对应的u盘,然后选择写入,就能够安装程序写入到u盘里面,用u盘启动安装系统了。
用ultraiso不光win7的iso可以,其他的哪怕是winxp,linux等各种操作系统的光盘都可以这样做,至少我现在在所有机器上装各种系统,都用这种方式。
至于跨硬件结构安装win7,也就是32位下安装64位的系统,如果有x86和x64两个版本,也能够硬盘安装上去的。将两个安装程序解压出来,比如分别解压到 d:\win7\x86和d:\win7\x64目录中。
只需要运行“d:\win7\x86\setup.exe /installfrom:d:\win7\x64\source\install.wim”即可实现32位装64位了。
========================================
Update:微软出了制作U盘安装盘的工具,应该不用那么折腾了,不过还没试~~
Friday, October 02, 2009
[+/-] |
在Win7上安装DAEMON Tools Lite |
今天在笔记本的Win7上装了个DAEMON Tools Lite,一开始安装会不断的要求重启,然后继续安装重启。上官方的论坛看了下,找到了解决办法,在这里记录一下。除了要安装最新DAEMON Tools Lite,还要安装最新的1.60版的SPTD,相应的帖子可以参考下面的链接
http://forum.daemon-tools.cc/f14/windows-7-7600-rtm-install-not-working-25005/
http://forum.daemon-tools.cc/f26/you-must-reboot-after-previous-operation-16177/
Saturday, September 26, 2009
[+/-] |
Waterloo见闻(一) |
Waterloo见闻(一)
到达多伦多机场已是当地时间晚上7点多,不过太阳仍未下山,就像白天一般,有些不习惯。
走出机舱,就算踏入了加国的土地,内心有些许惶恐和无助,还有萦绕在心头的伤感,因为仍无法忘记MM的眼泪,无法忘记在机场父亲孤独的背影。是的,从踏上他乡异国土地上的那一刻起,我就开始想念小白父亲奶奶我的家人,想念中国广州湛江。
好在这次跟着师兄过来,一路上他带着我办理各种手续,出关,办理study permit,到订去Waterloo的Van,一切都还顺利。只是去取行李的时候发生了点小问题,我以为机场的推车也像国内一样随便用,所以看到就拽着一个使劲拉,结果怎么也没弄出来,后来才知道这个推车也是要钱的,要投币才能拉出来。
从机场到Waterloo的小车一共可以坐7个人,和国内的面包车一般大,后面放行李,需要提前预订。开车的是一个女司机,一路上和坐在旁边的男乘客唠叨个不停。到了这边才发觉英语远远不够用,他们之间的对话我就没听懂几句,索性干脆望着窗外发呆。由于车上还有其他乘客,所以小车要一个个送到家,先到的是也是两个来着中国的女生,好像是先过来学习语言,homestay那种。一开始司机送错了地方,一敲门,开门的老外也一头雾水。仔细一对才发觉弄错了门牌号码。
辗转了半天,一直到晚上快11点才到达我的住处。开门的是一位40左右的大叔,张口一句中文“你终于到了”,打消了我之前以为他们不说中文需要用英文交流的疑虑。房东夫妇是已移民加拿大将近10年的华人,房东老颜现在也在UW读博,大概今年毕业。老颜带着我到我的房间,我收拾了房间,给爸和MM都打了个电话。洗完澡,由于时差还没倒过来,躺在床上就睡着了。
还好,在Waterloo的第一个晚上,没有像在长沙、在西安、在广州的第一个夜晚一样失眠。
Friday, September 25, 2009
[+/-] |
Blog via itouch |
Just a trial to test blog via itouch