线性约束优化的仿射尺度内点算法

摘要

内点法是起源于线性规划的一类重要的优化方法，该算法通过一种变换使迭代点从可行域的内部向最优解逼近，内点法对约束优化问题的求解有比较显著的效果，现在已经被广泛应用于非线性规划，组合优化，互补问题等优化问题. 本文是用仿射尺度内点算法来解决带线性约束的优化问题，在算法中，定义信赖域子问题时，在每一个迭代点，不要求xk+sk严格在边界里边，只要求l≤xk+sk≤u，当xk+sk在边界上时，通过因子σk来缩小sk使得迭代点都在边界里边，而且σk给出了具体的计算方法，通过求解信赖域子问题得到尝试步sk，如果目标函数f(x)从xk到xk+sk，f(x)有一个充分下降量，那么迭代步sk可接受，即xk+1=xk+sk.否则的话，我们不用信赖域方法而是执行Armijo直线搜索使得，f(xk+ωisk)＜f(xk)，其中ω∈(0，1)是一常数，i是正整数，其目的是减少信赖域子问题的求解次数，提高计算效率. 本文在通常假设条件下证明了全局收敛性，在合理的条件下给出了超线性收敛性结果，最后用Matlab语言对所提方法进行了数值实验，结果表明了算法的有效性.

目录

文摘

英文文摘

声明

第一章引言

第二章算法

第三章全局收敛性

第四章局部收敛性

第五章数值试验

第六章结论

参考文献

附录 测试问题

致谢