【作者】 卞凯；

【导师】 陈中文；

【作者基本信息】 苏州大学 ， 运筹学与控制论， 2012， 硕士

【摘要】 半定规划是线性与非线性规划的一种推广,在组合优化、控制论、系统论、滤波器的设计、临床医学等方面都有很广泛的应用.研究非线性半定规划问题的算法及其理论具有重要的理论意义和应用价值.许多线性与非线性规划的算法被成功地推广应用于求解非线性半定规划问题,例如光滑与非光滑牛顿法、势下降方法、原始对偶内点法、序列半定规划方法和增广拉格朗日方法等,这些方法有一个共同点：借助于某个罚函数作为效益函数来判断当前尝试步是否可以接受,即要求效益函数值有充分下降,但罚因子的选取是一个复杂而困难的问题Fletcher等人提出的过滤方法是不使用罚函数的一种新方法,其基本原理类似于多目标规划的处理方法,这种思想在处理非线性半定规划问题时,滤子集的存储是一个值得考虑的问题.本文对非线性不等式约束半定规划问题提出一种新的逐次线性化方法,新算法既不要求罚函数单调下降,也不使用过滤技巧,从而避免了迭代过程中滤子集的存储.另外,尝试步的接受准则仅仅依赖于目标函数和约束违反度,因此,罚函数中对应于成功迭代点的罚因子不需要单调增加.为了判断尝试步是否可以接受,新算法或者要求违反约束的度量有足够改善,或者在约束违反度的一个合理范围内要求目标函数值充分下降,在通常的假设条件下,分析了新算法的适定性及全局收敛性.最后,给出了非线性半定规划问题的数值试验结果,结果表明了新算法的有效性.更多还原

【Abstract】 Semidefnite programming is an extension of linear and nonlinear programming.There are very extensive applications in many felds, such as combinatorial optimiza-tion, control theory, system theory, design of flter, clinical medicine, etc. Therefore,the research of the algorithms and their theory for nonlinear semidefnite programmingis of great theoretical signifcance and application value.Many algorithms for linear and nonlinear programming are successfully appliedto solve nonlinear semidefnite programming problems, for example, smooth and nons-mooth Newton methods, potential reduction methods, primal-dual interior point meth-ods, sequential semidefnite programming methods and augmented Lagrangian meth-ods, etc. There is a common feature of the above methods: using some penalty functionas merit function to decide whether the current trial step is accepted or not. But theselection of the penalty factor is a complex and difcult problem. Filter techniquepresented by Fletcher et al is a new method without using penalty function. Its basicprinciple is similar to the processing of multiobjective programming. The storage offlter set is a problem when it is applied to solve nonlinear semidefnite programming.A new successive linearization method is presented to solve nonlinear semidefniteprogramming with nonlinear inequality constraints. The new method does not requirethe penalty function to be reduced and does not use flter technique. The storage offlter set is avoided. The penalty parameter sequence corresponding to the successfuliterate point does not increase monotonically. To decide whether the trial step can beaccepted or not, the new method requires the measure of constraint violation to be im-proved or the objective function value to be improved within the measure of feasibilitycontrol. Under the usual assumptions, we prove that the algorithm is welldefned andconvergent. Finally, the preliminary numerical results are reported.更多还原