《序列二次规划》由会员分享，可在线阅读，更多相关《序列二次规划（151页珍藏版）》请在金锄头文库上搜索。
1、二次规划二次规划 Quadratic Programming二次规划二次规划 Questions什么是二次规划？什么是二次规划？如何求解？如何求解？二次规划二次规划 Definition 二次规划二次规划 （*）二次规划二次规划 二次规划二次规划 Remark二次规划二次规划 等式约束二次规划问题的解法：等式约束二次规划问题的解法： 直接消去法直接消去法(Direct Elimination Method) Lagrange乘子法乘子法直接消去法直接消去法(Direct Elimination Method)直接消去法直接消去法 直接消去法直接消去法 直接消去法直接消去法 (*)直接消去法直接
2、消去法 直接消去法直接消去法 直接消去法直接消去法 Remark直接消去法直接消去法 Example直接消去法直接消去法 Solution直接消去法直接消去法 直接消去法直接消去法 直接消去法直接消去法 RemarkLagrange乘子法乘子法Lagrange乘子法乘子法Lagrange乘子法乘子法Lagrange乘子法乘子法Lagrange乘子法乘子法把c和b代入前面的最优解然后利用H R即可得。Lagrange乘子法乘子法ExampleLagrange乘子法乘子法SolutionLagrange乘子法乘子法Lagrange乘子法乘子法起作用集方法（起作用集方法（Active Set Met
3、hod)起作用集方法起作用集方法正定二次规划正定二次规划（*）定定理理起作用集方法起作用集方法Theorem起作用集方法起作用集方法Theorem(*) 起作用集方法起作用集方法Proof起作用集方法起作用集方法（a）起作用集方法起作用集方法(b)满足（满足（a)的的 肯定满足（肯定满足（b），且为满足（），且为满足（b）的）的 的的一部分，但满足（一部分，但满足（b）的解是唯一的，所以问题（）的解是唯一的，所以问题（b）的解）的解就是问题（就是问题（a)的解。的解。起作用集方法起作用集方法Remark起作用集方法起作用集方法Questions起作用集方法起作用集方法起作用集方法起作用集方法(
4、*)起作用集方法起作用集方法起作用集方法起作用集方法(*)起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法Questions如何得到如何得到(*)？起作用集方法起作用集方法Answer起作用集方法起作用集方法Questions起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法AlgorithmAlgorithmAlgorithmAlgorithm起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法Example起作用集方法起作用集方法
5、Solution起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法序列二次规划法序列二次规划法（Sequential Quadratic Programming)（约束拟牛顿法约束变尺度法）（约束拟牛顿法约束变尺度法）序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法牛顿法求
6、方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解牛顿法求方程组牛顿法求方程组 的解的解序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法Remark序列二次规划法序列
7、二次规划法Remark序列二次规划法序列二次规划法Example序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法用信赖域方法求解二次规划子问题：用信赖域方法求解二次规划子问题：序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法(*)序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法(1)General Problem (GP)序列二次规划法序列二次规划法
8、 In constrained optimization, the general aim is to transform the problem into an easier sub-problem that can then be solved and used as the basis of an iterative process. 序列二次规划法序列二次规划法A characteristic of a large class of early methods is the translation of the constrained problem to a basic uncons
9、trained problem by using a penalty function for constraints that are near or beyond the constraint boundary. In this way the constrained problem is solved using a sequence of parameterized unconstrained optimizations, which in the limit (of the sequence) converge to the constrained problem. 序列二次规划法序
10、列二次规划法These methods are now considered relatively inefficient and have been replaced by methods that have focused on the solution of the Kuhn-Tucker (KT) equations. The KT equations are necessary conditions for optimality for a constrained optimization problem.序列二次规划法序列二次规划法 If the problem is a so-c
11、alled convex programming problem, then the KT equations are both necessary and sufficient for a global solution point. 序列二次规划法序列二次规划法Referring to GP (1), the Kuhn-Tucker equations can be stated as (2)序列二次规划法序列二次规划法The first equation describes a canceling of the gradients between the objective functi
12、on and the active constraints at the solution point. For the gradients to be canceled, Lagrange multipliers are necessary to balance the deviations in magnitude of the objective function and constraint gradients. 序列二次规划法序列二次规划法Because only active constraints are included in this canceling operation,
13、 constraints that are not active must not be included in this operation and so are given Lagrange multipliers equal to zero. This is stated implicitly in the last two equations of Eq. (2). 序列二次规划法序列二次规划法The solution of the KT equations forms the Basis to many nonlinear programming algorithms. These
14、algorithms attempt to compute the Lagrange multipliers directly. Constrained quasi-Newton methods guarantee super-linear convergence by accumulating second order information regarding the KT equations using a quasi-Newton updating procedure. 序列二次规划法序列二次规划法These methods are commonly referred to as Se
15、quential Quadratic Programming (SQP) methods, since a QP sub-problem is solved at each major iteration (also known as Iterative Quadratic Programming, Recursive Quadratic Programming, and Constrained Variable Metric methods). 序列二次规划法序列二次规划法Sequential Quadratic Programming (SQP) A Quadratic Programmi
16、ng (QP) Subproblem SQP Implementation序列二次规划法序列二次规划法Sequential Quadratic Programming (SQP) A Quadratic Programming (QP) Subproblem SQP Implementation序列二次规划法序列二次规划法Sequential Quadratic Programming (SQP)SQP methods represent the state of the art in nonlinear programming methods. Schittkowski , for exam
17、ple, has implemented and tested a version that outperforms every other tested method in terms of efficiency, accuracy, and percentage of successful solutions, over a large number of test problems. 序列二次规划法序列二次规划法Based on the work of Biggs , Han, and Powell , the method allows you to closely mimic New
18、tons method for constrained optimization just as is done for unconstrained optimization. At each major iteration, an approximation is made of the Hessian of the Lagrangian function using a quasi-Newton updating method. 序列二次规划法序列二次规划法This is then used to generate a QP sub-problem whose solution is us
19、ed to form a search direction for a line search procedure. The general method, however, is stated here. 序列二次规划法序列二次规划法Given the problem description in GP (1) the principal idea is the formulation of a QP sub-problem based on a quadratic approximation of the Lagrangian function. 序列二次规划法序列二次规划法Here yo
20、u simplify Eq. (1) by assuming that bound constraints have been expressed as inequality constraints. You obtain the QP sub-problem by linearizing the nonlinear constraints.序列二次规划法序列二次规划法Sequential Quadratic Programming (SQP) A Quadratic Programming (QP) Subproblem SQP Implementation序列二次规划法序列二次规划法序列二
21、次规划法序列二次规划法This sub-problem can be solved using any QP algorithm. The solution is used to form a new iterate .序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法A nonlinearly constrained problem can often be solved in fewer iterations than an unconstrained problem using SQP. One of the reasons for this is th
22、at, because of limits on the feasible area, the optimizer can make informed decisions regarding directions of search and step length. 序列二次规划法序列二次规划法序列二次规划法序列二次规划法 This was solved by an SQP implementation in 96 iterations compared to 140 for the unconstrained case.序列二次规划法序列二次规划法Sequential Quadratic P
23、rogramming (SQP) A Quadratic Programming (QP) Subproblem SQP Implementation序列二次规划法序列二次规划法The SQP implementation consists of three main stages, which are discussed briefly in the following subsections: Updating of the Hessian matrix of the Lagrangian function Quadratic programming problem solution Li
24、ne search and merit function calculation序列二次规划法序列二次规划法Updating of the Hessian matrix of the Lagrangian function Quadratic programming problem solution Line search and merit function calculation序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法Updating
25、of the Hessian matrix of the Lagrangian function Quadratic programming problem solution Line search and merit function calculation序列二次规划法序列二次规划法Updating of the Hessian matrix of the Lagrangian function Quadratic programming problem solution Line search and merit function calculation序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法
