无导数优化中自校正几何的楔形信赖域方法

摘要

本文研究了求解无约束优化问题和非线性互补问题的无导数方法。
　　无导数最优优化，就是在计算过程中仅仅使用函数值，不使用函数梯度信息的方法。关于无导数方法求解无约束优化问题，目前已经有多种有效的方法求解无约束优化问题。本文考虑基于插值模型的信赖域方法，这类方法中每步迭代中子问题的目标函数是由插值构造，而且需要满足一定条件才能得到较好的迭代点。如何构建合适的插值模型就成了一个难题，目前主要有三种方法:模型改进步，楔形信赖域方法和自校正几何的方法。
　　本文第三章提出一种新的自校正几何方法，并且结合楔形信赖域方法提出了一种求解无约束优化问题的无导数方法。这两种策略较模型改进步而言，不需要取代太多的插值点。新的自校正几何方法采用不同插值点集和信赖域半径更新策略以加速收敛，并且证明了同样满足自校正的性质。此外结合楔形信赖域方法，考虑了新加入点的位置因素。同时避免了楔形信赖域方法单纯考虑位置因素的缺陷。通过数值试验，表明方法比原来的两种方法的计算结果要好。在一般假设条件下，证明方法的收敛性。
　　本文第四章考虑非线性互补问题，利用价值函数，将非线性互补问题转化为无约束优化问题，使用第三章的方法求解。在满足正则性的条件下，算法产生的迭代点列收敛到的稳定点就是原问题的解。数值试验对比陈界山等人的无导数下降法，说明我们的无导数方法需要的函数值计算次数更少。此外，一般的无导数下降法的收敛性要求非线性互补问题严格单调或者单调可行，而我们方法需要的正则性条件较之更弱。

目录

声明

Contents

Abstract

摘要

本文创新点

Chapter 1 Introduction

1．1 The description of the problems

1．2 Why to consider without derivatives

1．3 Research progress：A brief survey of derivative-free optimization

1．4 Main Innovation

Chapter 2 Preliminaries

2．1 Interpolation models

2．1．1 Polynomial interpolation

2．1．2 Lagrange polynomials

2．1．3 ∧-poisedness

2．2 The updating of interpolation set

2．2．1 The geometry-improvement step

2．2．2 Wedge trust region methods

2．2．3 A self-correcting geometry process

Chapter 3 A Self-Correcting Geometry Wedge Trust Region Method for Unconstrained Optimization

3．1 A new self-correcting geometry process

3．2 Algorithm

3．2．1 Form the interpolation models

3．2．2 Solve the subproblem

3．2．3 Stopping criterion

3．2．4 SCGWTR algorithm

3．3 Global convergence

3．4 Numerical experiments

Chapter 4 The Self-Correcting Geometry Wedge Trust Region Method for Nonlinear Complementarity Problems

4．1 Introduction

4．1．1 The common NCP functions

4．1．2 Transform the problems

4．2 Algorithm

4．3 Regularity condition and convergence

4．4 Numerical experiments

Chapter 5 Conclusions and Future Work

Bibliography

Appendix A The function in the numerical experiments

Acknowledgements