fmincon函数浅析(ZT)

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矩阵的近似计算是需要用到有限差分法。

制作一个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盘安装盘的工具，应该不用那么折腾了，不过还没试～～

在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/

Waterloo见闻（一）

Waterloo见闻（一）

到达多伦多机场已是当地时间晚上7点多，不过太阳仍未下山，就像白天一般，有些不习惯。

走出机舱，就算踏入了加国的土地，内心有些许惶恐和无助，还有萦绕在心头的伤感，因为仍无法忘记MM的眼泪，无法忘记在机场父亲孤独的背影。是的，从踏上他乡异国土地上的那一刻起，我就开始想念小白父亲奶奶我的家人，想念中国广州湛江。

好在这次跟着师兄过来，一路上他带着我办理各种手续，出关，办理study permit，到订去Waterloo的Van，一切都还顺利。只是去取行李的时候发生了点小问题，我以为机场的推车也像国内一样随便用，所以看到就拽着一个使劲拉，结果怎么也没弄出来，后来才知道这个推车也是要钱的，要投币才能拉出来。

从机场到Waterloo的小车一共可以坐7个人，和国内的面包车一般大，后面放行李，需要提前预订。开车的是一个女司机，一路上和坐在旁边的男乘客唠叨个不停。到了这边才发觉英语远远不够用，他们之间的对话我就没听懂几句，索性干脆望着窗外发呆。由于车上还有其他乘客，所以小车要一个个送到家，先到的是也是两个来着中国的女生，好像是先过来学习语言，homestay那种。一开始司机送错了地方，一敲门，开门的老外也一头雾水。仔细一对才发觉弄错了门牌号码。

辗转了半天，一直到晚上快11点才到达我的住处。开门的是一位40左右的大叔，张口一句中文“你终于到了”，打消了我之前以为他们不说中文需要用英文交流的疑虑。房东夫妇是已移民加拿大将近10年的华人，房东老颜现在也在UW读博，大概今年毕业。老颜带着我到我的房间，我收拾了房间，给爸和MM都打了个电话。洗完澡，由于时差还没倒过来，躺在床上就睡着了。

还好，在Waterloo的第一个晚上，没有像在长沙、在西安、在广州的第一个夜晚一样失眠。

Blog via itouch

Just a trial to test blog via itouch