求解大规模界约束优化问题的有效集识别策略

求解大规模界约束优化问题的有效集识别策略

1.基于投影搜索的大规模界考虑到以下限制。其中x,l,u∈R所谓有效集识别策略,即用一个工作集来估计最优解处的有效约束,工作集随着迭代的进行不断的被修正.最初的有效集方法采取线搜索策略,每次迭代仅允许一个约束增加到工作集或从工作集去掉,此类方法只适合于求解小规模或中等规模的问题,在处理大规模问题时,若选取了不好的初始点,算法的效率会很低.针对界约束问题,近年来人们提出了许多有效的算法,它们允许多个有效约束指标进出有效集.其中一个策略是通过投影搜索确定有效集,参见文献本文通过一个求解大规模界约束问题的有效集拟牛顿算法,比较了三种有效集识别策略的优缺点.这一有效集拟牛顿算法产生可行迭代点列,其迭代格式为x文中所采用的记号如下:对于n×n矩阵M,其元素记为M2.svm算法和算法界约束最优化问题的应用背景十分广泛,如轴颈轴承问题以及支持向量机等均可转化为界约束问题求解.本部分以支持向量机为例给出说明.支持向量机(SupportVectorMachine,简称SVM)是解决分类问题的一类有效算法.考虑n维空间上的分类问题,它包含n个指标(x∈RT={(x其中xC-支持向量机的问题模型为其中C为间隔最大化和错分最小化的权衡系数,ξ引入问题(2.1)的对偶问题,其中H为核矩阵,α为问题(2.1)的拉格朗日乘子.需要说明的是,经过一定的转换,问题(2.2)可以简化为只含有界约束的模型.对偶问题(2.2)中有一解α=(α3.有效总结牛顿算法设(首先给出基于求解大规模界约束问题的四个有效集识别策略.3.1.有效组合策略3.1.1.slmqn算法的有效集分类策略1997年倪勤在文献这里0<3.1.2.基于梯度的有效排序策略1998年Facchinei在文献这里a3.1.3.外在中或为同一定义2002年Facchinei在文献这里其中α和β为事先定义好的任意向量;λ(x),μ(x)是两个Lagrange乘子函数[4],定义如下,运算3.1.4.策略关键指标的获取1998年Facchinei等人针对不等式约束问题提出了可以精确识别最优解处有效集的识别策略其中定义L(x),U(x),F(x)如下,作者通过数值测试发现(3.10)定义的L(x)∩U(x)≠在确定了三个指标集合L非有效约束变量的搜索方向其中3.2.有效集拟牛顿算法对于问题(1.1),我们给出一个基于上述几种有效集识别策略的拟牛顿算法.算法3.1.有效集拟牛顿算法(ASNA)步1(初始化)选择σ∈(0,步2(确定搜索方向)根据(3.11),(3.12)确定步长d步3(确定步长)求最小的正整数i=0,1,…,使得置α步4(更新Hessian阵)利用BFGS公式更新B注.L4.算法终止准则和有效集识别策略这一部分给出本文所列出的三个有效集识别策略运行ASNA的数值实验结果.首先利用文献其中g(x)为非线性无约束问题,通过以上的策略可以容易的定义上下界,以及有效约束的数目和位置.表1中的十个测试函数选自文献ASNA算法的终止准则是||d由表1可以看出,ALBFGS和QNAS算法的有效集识别策略因为分别建立在目标函数梯度或者乘子函数的基础之上,它们可以比较好的近似总的来说,求解界约束问题时,ALBFGS的识别策略比较好.首先,SLMQN中的ε有效集识别策略是一个很有应用前景的算法,本文提出的ASNA算法使得有效约束变量可以直接走到边界,而自由变量则是通过求解一个降维后的二次规划问题进