解可分约束优化问题的有效数值方法

摘要

可分优化在压缩感知、信号处理、图像处理和统计等方面都有着广泛的应用。随着跨学科研究的发展，越来越多的实际问题都可以归结为可分优化问题，它已逐渐成为数学规划领域中一个非常活跃的研究方向。因此，对这些问题提出一些有效的算法是很有意义的。
　　本文针对带有一般约束的可分优化问题提出了几种有效的数值方法，我们在信赖域的框架下着重研究了非凸可分优化问题和带有一般约束并且目标函数的导数不可获取的可分问题。
　　首先，我们针对带有线性等式约束的非凸可分离问题提出了一种结构信赖域算法。在每次迭代中，将新的试探步分解成其法向量和切向量分别进行计算。考虑到问题具有可分的结构，对信赖域半径的更新我们采用结构信赖域的方法。我们分析了算法的全局收敛性，初步的数值试验也表明该算法是可行的。
　　进一步，我们考虑带有一般等式约束的非凸可分问题，提出了一个结合过滤集技术的交替结构信赖域算法。特别地，新的迭代步由Gauss-Seidel迭代过程产生，其步长由信赖域参数控制。在算法中我们使用了过滤集技术，过滤集中的元素由两部分组成:一个目的是使得迭代点可行，另一个目的是使得迭代点最优。我们在一些适当的条件下证明了算法的全局收敛性。数值结果表明，新的算法可以有效地求解带有一般等式约束的非凸优化问题。
　　无导数优化方法已受到人们越来越多的关注，基于插值的信赖域方法是一类重要的无导数优化算法。在本文中，我们针对带有一般等式约束并且目标函数的导数不可获取的可分问题提出了一种无导数信赖域算法。在每次迭代中，我们利用牛顿插值围绕当前迭代构造一个目标函数的二次插值模型，新的迭代点通过在信赖域内极小化模型函数的增广拉格朗日函数产生。同时利用过滤集技术来确保算法最终产生可行的最优点。在一些适当的条件下我们证明了该算法具有全局收敛性。

目录

声明

Contents

论文创新点

摘要

Abstract

Chapter 1 Introduction

1．1 Motivation and related approaches

1．1．1 Noneonvex separable optimization problems

1．1．2 Separable optimization problems with unavailable derivatives

1．2 Organization of the thesis

Chapter 2 Preliminaries

2．1 The basic trust-region algorithm

2．2 The notion of a filter

2．3 Basic materia for derivative-free optimization

2．3．1 Basic concepts in polynomial interpolation

2．3．2 Lagrange polynomials

2．3．3 Polynomial interpolation models

Chapter 3 A Structured Trust Region Method for Nonconvex Programming with Separable Structure

3．1 Introduction

3．2 Structured trust region algorithm

3．2．1 The model

3．2．2 Computing the trial step

3．2．3 A structured trust region algorithm

3．3 Convergence analysis

3．4 Numerical experiments

3．5 Summary

Chapter 4 An Alternating Structured Trust Region Algorithm for Separable Optimization Problems with Nonconvex Constraints

4．1 Introduction

4．2 An alternating structured trust region algorithm

4．2．1 The model functions

4．2．2 Compute the new iterate and sufficient model decrease

4．2．3 The filter as a criterion to accept trial points

4．2．4 An alternating structured trust region algorithm

4．3 Convergence analysis

4．4 Numerical experiments

4．5 Summary

Chapter 5 A Derivative-Free Trust Region Algorithm for Constrained Optimization with Separable Structure

5．1 Introduction

5．2 The trust-region framework and polynomial interpolation

5．2．1 The trust-region framework

5．2．2 Newton interpolation

5．2．3 Improve the geometry of interpolation sets

5．2．4 The filter as a criterion to accept tdal points

5．3 A derivative-free trust region algorithm

5．4 Convergence analysis

5．5 Summary

Chapter 6 Conclusions and Future Work

Bibliography

Publications

Acknowledgements