结合有效集和多维滤子技术的拟Newton信赖域算法(英文)

针对界约束优化问题,提出一个修正的多维滤子信赖域算法.将滤子技术引入到拟Newton信赖域方法,在每步迭代,Cauchy点用于预测有效集,此时试探步借助于求解一个较小规模的信赖域子问题获得.在一定条件下,本文所提出的修正算法对于凸约束优化问题全局收敛.数值试验验证了新算法的实际运行结果.     

等式约束优化非单调信赖域算法

设计了一个新的求解等式约束优化问题的非单调信赖域算法.该算法不需要罚函数也无需滤子.在每次迭代过程中只需求解满足下降条件的拟法向步及切向步.新算法产生的迭代步比滤子方法更易接受,计算量比单调算法小.在一般条件下,算法具有全局收敛性.     

带NCP函数的信赖域滤子方法

滤子方法最初是由Fletcher和Leyffer在2002年提出的.这种方法的原理是:在一个试探步,如果相应的目标函数值或约束违反度函数值下降,那么该试探步就会被接受.利用Fischer-Burmeister NCP函数来修正滤子中的约束违反度函数,同时证明了这个新的滤子方法具有全局收敛性.     

带等式约束二次规划子问题的滤子SQP算法

一类求解非线性规划问题的滤子序列二次规划(SQP)方法被提出.为了提高收敛速度,给目标函数和约束违反度函数都设置了斜边界.二次规划子问题(QP)设置为两项:不等式约束QP和等式约束QP.两个子问题产生的搜索方向进行线性迭加后为算法的搜索方向.这样的设置可以改善收敛性,并调节算法运行中的一些不良效果.在较温和的条件下,可得到全局收敛性.     

一类修改的带NCP函数信赖域滤子算法

本文针对非线性规划给出了一种修改的带NCP函数的信赖域滤子SQP算法,主要的修改之处是用NCP函数替代了滤子中约束违反度函数,而且进一步证明了这种修改的算法同样具有全局收敛性.     

解决大规模信赖域子问题的一种新算法

信赖域方法是解决无约束优化问题的一类有效的方法,而求解信赖域子问题又是信赖域方法的一个重要的组成部分。在本文中,我们首先介绍Hager[4]的序列子空间方法,并分析了对于不同的子空间序列,该算法所具有的性质。随后我们在以上分析的启发下,给出SSM算法的一种改进算法,改进后的算法不仅是全局收敛的,而且进一步减少了矩阵运算量。最后我们给出一些初步的数值试验报告。     

求解非线性半定规划的一个无罚无滤信赖域型算法

为了避免使用罚函数和滤子,提高非线性半定规划求解效率,通过采用一种新型的非单调接受准则,使用信赖域技术构建搜索方向,提出了一个无罚函数无滤子的信赖域型序列半定规划算法.在一定的假设条件下,证明了该算法的适定性以及全局收敛性.最后初步的数值试验结果表明该算法的有效性与可行性.     

求解线性不等式约束优化问题的一类信赖域算法

本文对线性不等式约束的非线性规划问题提出了一类信赖域算法,证明了算法所产生的序列的任一聚点为Ｋｕｈｎ－Ｔｕｃｋｅｒ点,并讨论了子问题求解的有效集方法．     

一种求解混合约束优化问题的半可行序列线性方程组滤子算法的局部收敛性

作者在[10]中提出了一种半可行序列线性规划滤子方法.它将QP-free方法推广至混合约束优化问题上,并且保持对不等式约束的可行性,对等式约束部分用滤子方法处理,从而避免了罚参数的选取.该算法只需求解四个具有相同系数矩阵的线性方程组以得到搜索方向.在一定程度上克服了序列二次规划方法的缺点.[10]中仅给出了全局收敛性.本文主要给出了该算法的局部超线性收敛性证明以及数值结果.     

求解正定二次规划的一个全局收敛的滤子内点算法

现有的大多数分类问题都能转化成一个正定二次规划问题的求解.通过引入滤子方法,并结合求解非线性规划的原始对偶内点法,给出求解正定二次规划的滤子内点算法.该算法避免了使用效益函数时选取罚因子的困难,在较弱的假设条件下,算法具有全局收敛性.     

Nonlinear Model Predictive Control via Feasibility-Perturbed Sequential Quadratic Programming

Model predictive control requires the solution of a sequence of continuous optimization problems that are nonlinear if a nonlinear model is used for the plant. We describe briefly a trust-region feasibility-perturbed sequential quadratic programming algorithm (developed in a companion report), then discuss its adaptation to the problems arising in nonlinear model predictive control. Computational experience with several representative sample problems is described, demonstrating the effectiveness of the proposed approach.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.     

A Structured Reduced Sequential Quadratic Programming and Its Application to a Shape Design Problem

The objective of this work is to solve a model one dimensional duct design problem using a particular optimization method. The design problem is formulated as an equality constrained optimization, called all at once method, so that the analysis problem is not solved until the optimal design is reached. Furthermore, the sparsity structure in the Jacobian of the linearized constraints is exploited by decomposing the variables into the design and flow parts. To achieve this, sequential quadratic programming with BFGS update for the reduced Hessian of the Lagrangian function is used with the variable reduction method which preserves the structure of the Jacobian in representing the null space basis matrix. By updating the reduced Hessians of which the dimension is the number of design variables, the storage requirement for the Hessians is reduced by a large amount. In addition, the flow part of the Jacobian can be computed analytically.The algorithm with a line search globalization is described. A global and local analysis is provided with a modification of the paper by Byrd and Nocedal [Mathematical Programming 49(1991) pp 285-323] in which they analyzed a similar algorithm with the orthogonal factorization method which assumes the orthogonality of the null space basis matrix. Numerical results are obtained and compared favorably with results from the black box method, unconstrained optimization formulation.     

Stabilized Sequential Quadratic Programming

Recently, Wright proposed a stabilized sequential quadratic programming algorithm for inequality constrained optimization. Assuming the Mangasarian-Fromovitz constraint qualification and the existence of a strictly positive multiplier (but possibly dependent constraint gradients), he proved a local quadratic convergence result. In this paper, we establish quadratic convergence in cases where both strict complementarity and the Mangasarian-Fromovitz constraint qualification do not hold. The constraints on the stabilization parameter are relaxed, and linear convergence is demonstrated when the parameter is kept fixed. We show that the analysis of this method can be carried out using recent results for the stability of variational problems.     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

无约束多目标规划的非单调信赖域算法

本提出了无约束多目标规划的一类非单调信赖域算法，并证明了算法的全局收敛性。     

基于简单二次函数模型的非单调信赖域算法

基于简单二次函数模型,结合非单调技术,建立了一个新的求解无约束最优化问题的非单调信赖域算法,并证明了算法的全局收敛性及超线性收敛性.数值例子表明算法是有效性的,适合求解大规模问题.     

A Trust Region SQP Algorithm for Equality Constrained Parameter Estimation with Simple Parameter Bounds

We describe a new algorithm for a class of parameter estimation problems, which are either unconstrained or have only equality constraints and bounds on parameters. Due to the presence of unobservable variables, parameter estimation problems may have non-unique solutions for these variables. These can also lead to singular or ill-conditioned Hessians and this may be responsible for slow or non-convergence of nonlinear programming (NLP) algorithms used to solve these problems. For this reason, we need an algorithm that leads to strong descent and converges to a stationary point. Our algorithm is based on Successive Quadratic Programming (SQP) and constrains the SQP steps in a trust region for global convergence. We consider the second-order information in three ways: quasi-Newton updates, Gauss-Newton approximation, and exact second derivatives, and we compare their performance. Finally, we provide results of tests of our algorithm on various problems from the CUTE and COPS sets.     

广义几何规划的压缩共轭梯度路径非单调信赖域算法(英文)

In this paper,on the basis of making full use of the characteristics of unconstrained generalized geometric programming（GGP）,we establish a nonmonotonic trust region algorithm via the conjugate path for solving unconstrained GGP problem.A new type of condensation problem is presented,then a particular conjugate path is constructed for the problem,along which we get the approximate solution of the problem by nonmonotonic trust region algorithm,and further prove that the algorithm has global convergence and quadratic convergence properties.