学位论文 > 优秀研究生学位论文题录展示

求解约束非线性规划问题的不可行内点序列二次规划方法

作　者: Bashir
导　师: 梁昔明
学　校: 中南大学
专　业: 计算机应用技术
关键词: 序列二次规划有效集方法二次规划子问题不可行内点法 PID控制器优化
分类号: O221.2
类　型: 硕士论文
年　份: 2009年
下　载: 191次
引　用: 0次
阅　读: 论文下载

内容摘要

各种基于梯度的优化技术在约束非线性规划(NLP)领域遇到了极大的挑战。序列二次规划法(SQP)采用有效集策略求解二次规划(QP)子问题,已被证明它能有效地获得问题的局部最优解。然而,其中最优有效集的有效确定在很大程度上依赖于初始点的合理选择,对于原始有效集方法和对偶有效集方法来说,这一直是一个严重的不足,尤其对具有多个不等式约束的非线性规划问题求解时,这些方法对最优有效集的有效确定显得十分困难。有效集策略最初用于求解线性规划(LP)问题的单纯形算法。本文研究了原始和对偶两类有效集方法(ASM)。由于原始有效集方法仅要求二次规划问题的海森矩阵至少是半正定的,因此它比对偶有效集方法更直观且应用更为广泛。然而,寻找最优有效集时可能陷入无限循环成为原始有效集方法成功求解问题的最大阻碍。对偶有效集方法正好相反,它要求所求问题的QP子问题都是严格凸的(即对应的海森矩阵是正定的)。对于任意给定的可行问题,对偶有效集方法在寻找最优有效集时不仅不会陷入无限循环,而且还具有有限收敛性。但是,对偶有效集方法的主要弊端是它只能应用于凸的二次规划问题。而实际上大多数工程优化问题都是非凸的,当处理带有多个不等式约束的非线性规划问题时,有效集方法通常会出现性能恶化以及过早收敛的现象。为此,本文提出了一种利用不可行内点算法(ⅡPM)求解二次规划子问题的序列二次规划算法(SQP/ⅡPM)。在该算法中,不等式约束被直接求解,从而降低了有效确定最优有效集对初始点选择的依赖性。在第k次迭代中,利用所提出的不可行内点算法求解二次规划子问题得到搜索方向,采用简单线搜索和/或二次搜索并依据ⅡPM算法的终止条件自适应地估计搜索步长,仅当算法ⅡPM求解QP的终止条件满足互补松弛性(即,对偶性度量)时,SQP/ⅡPM算法才使用二次搜索估计搜索步长,也就是说算法ⅡPM求解QP的过程中,原始的或对偶的可行性条件都不需满足。另外,如果线搜索在规定的次数内没有得到一个可接受的搜索步长,SQP/ⅡPM算法也将从线搜索转换到二次搜索以获得一个搜索步长。此外,为了提高算法确定搜索步长的有效性和鲁棒性,并使得在搜索方向上获得尽可能的目标减小且同时避免任何约束违规,论文给出了两类不同的效益函数:一类适合于二次搜索算法,另一类适合线搜索算法。标准序列二次规划算法仅用线搜索估计搜索步长,本文之所以提出结合线搜索和二次搜索的混合步长确定方法,是因为线搜索算法在求解带有多个非线性不等式约束的非线性规划问题时会出现不规则的失败。因此,尽管二次搜索算法的代价较高,但是它可以为搜索步长的成功取得提供保证。因而,本文的混合步长确定方法是为适应两种极小化算法的平衡而提出的。更进一步说,SQP/ⅡPM算法是为求解同时具有等式和不等式约束的二次规划问题而提出的。利用修改拟牛顿方法(BFGS)进行更新,使SQP/ⅡPM算法在每个主迭代中都能够充分自由地接近和更新海森矩阵,从而SQP/ⅡPM算法具有求解凸二次规划和非凸二次规划两类问题的能力。为了克服求解非线性规划问题中所存在的困难,本文基于MATLAB图形用户界面的开发环境为所提出的SQP/ⅡPM算法设计了一个图形用户界面(GUI),并命名为“SQP/ⅡPM优化系统”,该系统通过执行稳健容错操作程序确保安全操作,具有简单清晰的特点,用户友好性强。基准测试数值问题(也就是,约束非线性规划问题)被用来进行算法的性能评估。本文对所提出的SQP/ⅡPM算法与标准序列二次规划算法进行了数值性能比较,试验结果表明,SQP/ⅡPM算法有令人满意的数值性能,它仅需较少的迭代次数和函数估计次数并在显著少的CPU时间内就能收敛到所求问题的最优解。最后,将SQP/ⅡPM算法应用于PID控制器参数优化中,进行了控制系统的工程仿真试验。将由SQP/ⅡPM算法所整定的PID控制器与由经典GPM算法和Ziegler-Nichols(ZN)算法所整定的PID控制器进行了仿真对比,仿真结果表明,由SQP/ⅡPM整定的PID控制器有效避免了由GPM整定的PID控制器所产生的超调量及由ZN整定的PID控制器调节时间过长的问题。因此,本文算法在进行PI/PID控制系统参数优化中具有鲁棒性,有效性和较好的应用前景。

全文目录

ABSTRACT  6-9
摘要  9-13
List of Figures  13-14
List of Tables  14-15
List of Routines  15-22
Chapter 1 Introduction  22-32
  1.0 Background  22
  1.1 General Constrained Nonlinear Problem  22-26
  1.2 Optimization of PID Controllers  26-29
    1.2.1 Parallel PID Structure  27
    1.2.2 Non-interacting Ideal PID Structure  27-28
    1.2.3 Interacting PID Structure  28
    1.2.4 Practical Rules of Tuning  28-29
  1.3 Motivation  29
  1.4 Goal  29-30
  1.5 Thesis Structure  30-32
Chapter 2 SQP for General Constrained Nonlinear Programming  32-53
  2.0 Introduction  32-33
  2.1 Mechanics of the standard SQP algorithm  33-35
    2.1.1 Extension to inequality constrained NLP  34-35
  2.2 Active set method for solving QP subproblems  35-36
    2.2.1 Active set Method  36
  2.3 Primal Active set method  36-42
    2.3.1 Case study  37
    2.3.2 Optimality Conditions for Standard QP  37-38
    2.3.3 Evaluation of Descent Directions  38-39
    2.3.4 Step length Computation  39-40
    2.3.5 Swapping constraint indices from working set W~k  40-41
    2.3.6 Determination of a feasible starting point  41
    2.3.7 Cycling problem in Active set methods  41-42
  2.4 Dual Active set method  42-43
    2.4.1 Case study  42-43
    2.4.2 Termination  43
  2.5 Solutions of Equality Constrained QP Problems  43-49
    2.5.1 Range Space method  44-46
    2.5.2 Null Space method  46-49
  2.6 Demonstration of the standard SQP algorithm-Example 2.1  49-52
  2.7 Remarks  52-53
Chapter 3 The Proposed Infeasible Interior Point Method for QP  53-70
  3.0 Background  53-55
  3.1 Primal-Dual Interior Point Method  55-60
    3.1.1 Primal formulation of IPM  55
    3.1.2 Dual formulation of IPM  55-56
    3.1.3 Optimality conditions for QP problems  56
    3.1.4 Evaluation of Descent Directions  56-57
    3.1.5 Step length and Next point  57-58
    3.1.6 Termination of IIPM algorithm  58-59
    3.1.7 Summary of the proposed Primal-dual IIPM algorithm  59-60
  3.2 BFGS Hessian Update Procedure  60-62
  3.3 Line Search and Quadratic Search algorithms  62-68
    3.3.1 Line Search for minimizing Merit Functions  62-64
    3.3.2 Quadratic Search for minimizing Merit Functions  64-68
  3.4 Remarks  68-70
Chapter 4 The Proposed SQP/IIPM Algorithm  70-83
  4.0 The proposed SQP/IIPM algorithm  70
  4.1 Mechanics of SQP/IIPM algorithm  70-71
  4.2 The choice of Merit function  71-73
    4.2.1 Merit Function for Line Search Algorithm  71-72
    4.2.2 Merit Function for Quadratic Search Algorithm  72-73
  4.3 Termination of SQP/IIPM algorithm  73
  4.4 The complete SQP/IIPM algorithm  73-76
  4.5 Demonstration of SQP/IIPM algorithm-Example 4.1  76-77
  4.6 Remarks  77
  4.7 SQP/IIPM Optimization System GUI  77-83
    4.7.1 Problem Definition M-File  81
    4.7.2 Optimization Options Specifications  81-83
Chapter 5 Performance Evaluation  83-100
  5.0 Numerical optimization-Benchmarking  83-87
  5.1 Optimization method for PI/PID parameter synthesis  87-93
    5.1.1 Optimization of a PI controller for a 1st order system  88-90
    5.1.2 Optimization of a PID controller for a 1st order system  90-92
    5.1.3 Numerical Optimization of a PID controller for a 2nd order system  92-93
  5.2 Optimization of PI/PID Controller parameters-Example  93-98
    5.2.1 1st Order Plant with a PI Controller-Example 5.1  94
    5.2.2 2nd Order Plant with a PID Controller-Example 5.2  94-98
  5.3 Remarks  98-100
Chapter 6 Conclusions and Future Work  100-103
  6.0 Conclusion  100-101
  6.1 Future work  101-103
References and Bibliography  103-109
Acknowledgement  109-110
Research Foundations  110
Papers Published  110

求解约束非线性规划问题的不可行内点序列二次规划方法

内容摘要

全文目录

相似论文