数值优化基础-Introduction

• 数值优化背景

在日常生活中，人们在处理许多问题时候，都会考虑一个最优化的结果，比如如何在给定的资源下，最大限度地利用这些资源，来创造更多的财富，在给定的时间内，如何分配任务优先级，以便在有限的时间或者更宽泛的资源概念下，获得最大的价值实现。数值优化也由于生产生活的需要应运而生。在人类的发展过程中，无论工业，商业，都在运用优化的方法和思想，处理现实生活中遇到的问题。经过漫长的发展，数值优化基本方法显示在下方的优化树中。

• 数值优化主要问题

1. 最大最小值问题

2. 连续和离散问题

3. 无条件和有条件问题

4. 线性和非线性编程

5. 凸优化和非凸优化问题

6. 全局和局部优化解问题

• 数值优化的基本概念

1. 线性组合(linear combination)，仿射组合(affine combination)，圆锥组合(conical combination)，凸组合(convex combination)

 

                                                                     

上式是一个关于x的线性组合，如果,那么x是一个仿射组合；

如果都不小于0，那么x是一个圆锥组合；

如果并且都不小于0，那么x是一个凸组合。

• 凸函数(convex function)

根据函数f定义：如果一个函数满足：

那么函数f被称之为凸函数。

凸函数的定义还有许多，可以以这个定义为基础，进行推导，这里不赘述。

• 微积分(Calculus)

1. 收敛速率（rate of convergence）
2. Lipschitz 连续性
3. 单值函数（single valued fucntion）:导数和Hessian矩阵；中值定理和泰勒定理
4. 向量函数：导数和Jacobian矩阵
5. 特征值和特征向量；奇异值分解；LU分解；子空间

• 收敛速率

是一个收敛于的序列

这里给一个简单定义：

那么序列的收敛速率为r。

• Lipschitz连续性

如果一个函数在集合N上被称为Lipschitz连续，那么存在这样的一个常数L，使得：

• 向量和矩阵范数

向量L0范数：

向量L1范数：

向量L2范数：

向量∞范数:

矩阵A范数：

矩阵A Frobenius(2)范数:  

• 奇异性和病态问题

如果一个矩阵A 是奇异的(不可逆的)，当且仅当其满足以下任一条件：

A有一个0特征值

A有一个0奇异值

A的null空间非空： 

A的判别式为0

方阵A的条件数：

如果条件数很大的话，那么称矩阵A 是病态的。

当然了非方阵矩阵依旧可以计算条件数，只不过比较复杂一些，这里就不赘述了。有兴趣的可以翻阅相关资料。