【作者】 唐春明；

【导师】 简金宝；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2008， 博士

【摘要】 最优化在工程设计、生产管理、交通运输、政府决策等重要领域日益得到广泛的应用,因此更加快速有效的最优化算法成为迫切需求。序列二次规划(SQP)算法是求解非线性约束优化最有效的算法之一,而可行SQP算法又是其中一类重要的算法,因为它能产生可行迭代点序列,故在工程设计和实时控制等方面有着十分重要的实际应用。然而可行SQP算法的较大缺陷就是需要一个可行初始迭代点,而通常计算一个可行点不是一个容易的工作。为此,简金宝教授近年提出了一个强次可行方向法,并成功应用于可行SQP算法。该方法能从任意初始点开始,能保证迭代的可行性单调增加,且一旦迭代点落入可行域即变成可行方向法。然而,强次可行方向法中仍然有一些问题亟待解决,如:能否在理论上保证在经过有限次迭代之后迭代点落入可行域;在理论分析当中一些较强的假设条件能否去掉或者减弱;数值计算量能否进一步减少等。在过去三四十年里SQP方法的研究得到了极大的完善,然而当要求解的问题非线性程度比较高时,如人造卫星轨道问题,SQP方法可能进程较为缓慢,甚至会失败。于是近年来一些学者专门针对该类问题提出了一种有效的方法,称为序列二次约束二次规划(SQCQP)方法。与SQP方法相比,SQCQP方法每步迭代只需求解一个二次约束二次规划(QCQP)子问题,并且在不需要任何方向修正的情况下可以克服Maratos效应,达到超线性收敛性。由于QCQP子问题是原问题的二次近似,因此相对于SQP方法中的二次规划(QP)子问题而言,QCQP子问题对原问题的近似程度要好,从而SQCQP方法预期的数值效果要比SQP方法好。本学位论文首先结合强次可行方向法,SQP方法和SQCQP方法的思想,分别给了一个强次可行SQP算法和一个强次可行SQCQP算法。然后专门针对目前SQCQP方法中存在的缺陷,提出了两个新的SQCQP算法。本论文共分为六章,各章内容简要介绍如下。第一章主要介绍了强次可行方向法的思想,可行SQP方法和SQCQP方法的研究进展,以及QCQP子问题的求解方法。第二章结合强次可行方向法和可行SQP方法的思想,提出了一个新的强次可行SQP算法。通过构造新的修正方向和设计新的Armijio型曲线搜索,提出的算法弥补了传统强次可行SQP算法的多个缺陷。首先能在理论上保证算法经过有限次迭代之后,迭代点落入可行域,之后自动变为可行SQP算法,并由此克服了一个较强的假设条件(即最大约束违背函数是QP子问题解的高阶)。其次,去掉了严格互补条件。最后,由于两个修正方向均由简单的显式产生,而且包含的逆矩阵是一样的,从而极大减少了计算量。算法具备全局和超线性收敛性。初步的数值试验说明该算法是稳定有效的。第三章结合强次可行方向法和可行模松弛SQCQP方法的思想,提出了一个强次可行模松弛SQCQP算法。通过对线搜索和QCQP子问题精心的构造,算法能从任意初始点开始,并保证有限步之后迭代点落入可行域。算法每次迭代只需求解一个凸QCQP子问题,且无需任何修正方向就能得到算法的全局、超线性及拟二次收敛性。数值试验说明算法的数值效果与测试的SQP算法相比有一定的优越性。第四章提出了一个新的罚函数型SQCQP算法。算法引入了一个简单的非单调罚参数调整技术,该技术仅利用QCQP子问题中有界约束的KKT乘子来更新罚参数,因为当把QCQP转化为二阶锥规划求解时,对应于二次约束的乘子往往比较难获取。该技术还允许罚参数在早期迭代减小,从而缓解了因罚参数增大过快而导致罚函数及子问题性态变差的问题。此外,我们利用了工作集技术剔除了QCQP子问题中局部不相关的约束,从而极大地减少了计算量。在不需要假设目标和约束函数为凸的情况下,算法是全局、超线性及二次收敛性的。初步的数值试验表明算法对测试的算例要比SQP方法优越。第五章结合增广Lagrange函数线搜索技术和SQCQP方法的思想,提出了一个增广Lagrange函数型SQCQP算法。算法中构造了一个新型的凸QCQP子问题,该子问题不仅始终有可行解,而且通过应用积极约束集技术避免了那些局部不相关的梯度和(近似)Hesse阵的计算,从而减少了计算量。步长由Armijio型线搜索产生,罚参数允许减小。在适当的假设下,算法不需要任何修正方向就具有全局、超线性及二次收敛性。此外,与以往SQCQP算法不同的是,该算法还能简单地推广到求解混合等式与不等式的一般约束优化,以及推广到非单调线搜索。第六章总结了本文的主要工作,并引出了一些需要进一步研究的问题。最后,值得指出的是,我们对本文中提出的两个SQCQP算法做了比较充分和完整的数值试验,而以往给出的SQCQP算法中,除了一个局部收敛的算法给出了一些初步的数值试验结果(而且当中还是把QCQP子问题当成一个一般的非线性规划问题来求解)外,其余算法都没有做数值试验,其主要原因可能在于QCQP子问题求解上的困难。更多还原

【Abstract】 Optimization plays more and more important roles in many areas,such as engineering design,production management,transportation,government decisionmaking. So more faster and efficient optimization algorithms are urgently demanded. Sequential quadratic programming(SQP) algorithms are among the most efficient algorithms for solving nonlinear constrained optimization.As an important kind of SQP algorithms,feasible SQP algorithms have many important applications in practice,such as engineering design and real-time control,since they can generate feasible iterations.However,a major disadvantage of feasible SQP is that a feasible starting point is required in advance,while computing such a point is generally a nontrivial work.Recently,in order to overcome this shortcoming,Prof.Jian has proposed a strongly sub-feasible direction method,and then successfully applied it to feasible SQP algorithms.This method allows arbitrary starting points,and guarantees that the feasibility of constraints is monotonously increasing.Furthermore, once a certain iterate gets into the feasible set,the corresponding algorithm will become feasible direction algorithm.However,there are still some problems in strongly sub-feasible direction method that needed to be resolved:ensuring theoretically the iterates getting into the feasible set after a finite number of iterations, removing some strong assumptions,reducing the computational cost and so on.During the past several decades,the researches of SQP methods have been greatly improved,but when the problems we solved are highly nonlinear,SQP methods usually show slow convergence,even fail.For this,in recent years,a so-called sequential quadratically constrained quadratic programming(SQCQP) method has been proposed. Compared with SQP methods,at each iteration SQCQP methods only need to solve a quadratically constrained quadratic programming(QCQP) subproblem, and without any correctional directions the Maratos effect will not occur and there- fore the superlinear convergence can obtained.QCQP subproblem is a quadratic approximation of the original problem,so it is a better approximation than the quadratic programming(QP) subproblem solved in SQP methods,and therefore the expected numerical performance of SQCQP will be better than SQP.Combining the ideas of strongly sub-feasible direction methods,SQP methods and SQCQP methods,this dissertation firstly proposed a strongly sub-feasible SQP algorithm and a strongly sub-feasible SQCQP algorithm.Secondly,with the motivation of overcoming the shortcomings of the existing SQCQP algorithms,two new SQCQP algorithms are proposed.The dissertation is divided into six chapters as follows.Chapter 1 mainly introduces the ideas of strongly sub-feasible direction methods and feasible SQP methods,recent developments of SQCQP methods,and the solution method of QCQP subproblem.Combining the ideas of strongly sub-feasible direction methods and feasible SQP methods,chapter 2 presents a new strongly sub-feasible SQP algorithm.By constructing new correctional directions and new Armijio-type curve search,the new algorithm overcomes several shortcomings of the traditional strongly sub-feasible SQP algorithm.At first,the algorithm theoretically ensures that the iterates get into the feasible set after a finite number of iterations,and then automatically becomes feasible SQP algorithm,as a result,a strong assumption(the order of the maximal constraint violation function is higher than the solution of the QP subproblem) is removed.Secondly,the strict complementarity condition is removed. At last,two correctional directions are generated by explicit formulas that contain the same inverse matrix,so the computational cost is reduced.The algorithm is proved to be globally and superlinearly convergent.Some preliminary numerical results show that the proposed algorithm is stable and efficient.Combining the ideas of strongly sub-feasible direction methods and feasible normrelaxed SQCQP methods,chapter 3 presents a strongly sub-feasible norm-relaxed SQCQP algorithm.By constructing new QCQP subproblem and new line search, the algorithm can start from arbitrary initial point,and ensure that the iterates get into the feasible set after a finite number of iterations.Only one convex QCQP subproblem needs to be solved at each iteration,and without any other correctional directions,the global,superlinear and quasi-quadratic convergence properties are obtained.Preliminary numerical results show that the proposed SQCQP algorithm is superior to a related SQP algorithm for the test problems.Chapter 4 presents a new penalty function type SQCQP algorithm,in which a simple nonmonotone penalty parameter updating technique is introduced.This technique only uses the KKT multiplier corresponding to the bounded constraint of the QCQP subproblem,since the multipliers corresponding to the quadratic con-straints are usually hard to be obtained when QCQP is cast and then solved as an second-order cone programming.This technique allows penalty parameters to be decreasing, which prevents the penalty parameters from increasing too fast and therefore prevents the penalty function and QCQP subproblem from being ill-conditioned. In addition,by using the working set technique,we remove the constraints of the QCQP subproblem that are locally irrelevant,so the computational cost is greatly reduced.Without assuming the convexity of the objective or constraints,the algorithm is globally,superlinearly and quadratically convergent.Preliminary numerical results show that the algorithm is superior to the tested SQP algorithms for the test problems.Combining the augmented Lagrange function line search technique and the idea of SQCQP methods,chapter 5 presents an augmented Lagrange function SQCQP algorithm, in which a new consistent convex QCQP subproblem is proposed.The active set strategy used in this subproblem can avoid calculating the unnecessary gradients and(approximate) Hessian matrices.The step size is generated by Armijio-type line search,and the penalty parameters can be reduced.Under suitable assumptions, the algorithm is proved to be globally,superlinearly,and quadratically convergent. Compared with previous SQCQP algorithms,the proposed algorithm can be easily extended to general problems with inequality and equality constraints,and to nonmonotone line search.Chapter 6 summarizes the main contributions of this dissertation,and raises some problems needed to be further studied.Finally,we should point out that sufficient and full numerical experiments were done for two SQCQP algorithms proposed in this dissertation,whereas except for a local convergent one(in which the QCQP subproblem is treated and solved as a general nonlinear programming),the previous SQCQP algorithms have not reported numerical experiments,mainly due to the difficulty of solving the QCQP subproblem.更多还原