最优化理论与算法第1章:引言

本文的内容主要来自陈宝林的《最优化理论与算法(第2版)》第1章《引言》。

# 1 学科简述

(略)

# 2 线性与非线性规划问题

目标函数和约束函数都是线性的,称为线性规划问题,若含有非线性函数,称为非线性规划问题

满足约束条件的点称为可行点,全体可行点组成的集合称为可行集可行域。如果可行域是整个空间称为无约束问题

定义1.2.1 formula为目标函数,formula为可行域,formula,若formula,则称formulaformulaformula上的全局极小点

定义1.2.2 formula为目标函数,formula为可行域,formula,若formula,则称formulaformulaformula上的局部极小点。其中formula为邻域。

注:全局极小点不需要用到距离和范数,它和函数的最值定义几乎是一样的,只是定义域成了可行域。而局部极小点用到了邻域,需要距离也就是范数,它和函数的极小值定义也几乎是一样的。

# 3 几个数学概念

# 3.1 向量范数和矩阵范数

定义1.3.1 实值函数formula称为向量范数,若满足formula

  1. 严格正定性:formula
  2. 齐次性(线性形):formula
  3. 三角不等式:formula

常见的向量范数有:

  1. formula范数:formula
  2. formula范数:formula
  3. formula范数:formula

注:这里的范数都称为formula-范数,来源于formula。其中formula

定义1.3.2 formulaformula上的范数,若formula,则称这两个范数等价

formula中任何两个范数等价(这里必须是有限维,这个定理的证明我尚不能掌握,需要参考泛函分析)。

定义1.3.3 formula为矩阵,formulaformula上的向量范数,formulaformula上的向量范数,定义矩阵范数formula

注:这里可以想像成矩阵的范数,是其对应的线性映射,能够将一个向量拉长的最大倍数。

定理1.3.1 矩阵范数的性质:

  1. formula
  2. formula
  3. formula
  4. formula

定理1.3.1 (1) 证:

formula

定理1.3.1 (3) 证:

formula

定理1.3.1 (4) 证:

formula

常见的矩阵范数有:

  1. formula
  2. formula,(formula是最大特征值,这被称为谱范数);
  3. formula

注:这里formula矩阵范数就是formula向量范数的组合,我采用形象化的方式来解释这3种范数。先考虑第2个范数,它将球拉伸成椭球,长径拉伸最大值也就是其最大的奇异值;再考虑第1个范数,它将一个立方体拉伸成长方体,其中立方体的顶点是formula,映射完后,相当于挨个取出列向量,求他们的formula范数(求和),再取出最大的;最后考虑第3个范数,它同样将一个立方体拉伸成长方体,其中立方体的顶点是formula,映射完后,相当于将行向量求和,最后取出最大的。

# 3.2 序列的极限

定义1.3.4 formulaformula中的向量序列,formula,若:

formula

则称序列收敛formula,或序列以formula极限,记作formula

序列若存在极限,则任何子序列有相同的极限(选取适当的formula即可证明),序列的极限是唯一的。

序列的极限是唯一的 证:

反证法,若存在两极限,则formula同时formula,且formula。取formula,由假设知道:

formula

定义1.3.5 formulaformula中的向量序列,若存在子序列formulaformula,则称formulaformula的一个聚点

Bolzano–Weierstrass定理formula中有界序列必有聚点,即有界序列必有收敛子列,证明详见波尔查诺-魏尔斯特拉斯定理 - 维基百科,自由的百科全书。这只在有限维实向量赋范空间成立。

定义1.3.6 formulaformula中的向量序列,若:

formula

则称formula柯西序列formula中,柯西序列和收敛数学互为充要条件。

注:柯西序列的定义没有涉及到极限值,这便于完成一些对收敛性的证明。那些所有柯西序列收敛到空间中某点的空间,称为完备空间,比如实数是完备的,有理数是不完备的。完备空间中,柯西序列和收敛序列互为充要条件。不完备空间中,柯西序列是收敛序列的必要条件。

定理1.3.2 formulaformula中的柯西序列,则其聚点为极限点。

注:formula中,收敛序列(即柯西序列)必有唯一聚点,且该聚点为极限点。一个序列可能有多个聚点。

formula

  1. formula中每个收敛序列的极限均在formula,则称formula闭集
  2. formula,则称formula开集,这样的formula称为内点
  3. formula是有界闭集,则称formula紧集

闭集的另一个定义是:一个补集是开集的集合称为闭集。这里集合formula的补集定义为formula

紧集的一个等价定义是:集合中的序列都有收敛子序列。由Bolzano–Weierstrass定理可证formula紧致,当且仅当,formula为有界闭集。

# 3.3 梯度、海森矩阵、泰勒展开式

formula,其中formula。如果formulaformula中的每一点连续,则称formulaformula连续,记作formula。若formula在每一点formula,一阶导数formula存在且连续,则称formulaformula连续可微,记作formula。若formula在每一点formula,二阶导数formula存在且连续,则称formulaformula二次连续可微,记作formula

函数formulaformula梯度为:

formula

函数formulaformula海森矩阵为对称矩阵,如下:

formula

对于二次函数formula

  1. 其梯度:formula
  2. 其海森矩阵:formula

formula上的函数formula

  1. formula,则对任意formula,有一阶泰勒展式:

    formula

  2. formula,则对任意formula,有二阶泰勒展式:

    formula

# 3.4 雅可比矩阵、链式法则和隐函数存在定理

# 3.4.1 雅可比矩阵

考虑向量值函数formula

formula

若对任意formulaformula存在,则其雅可比矩阵为:

formula

也可记作formula

# 3.4.2 链式法则

对于实数空间上的复合向量值函数formula,若formula均可微,则有:

formula

# 3.4.3 隐函数定理

定理 1.3.3 对于formula,定点向量formula,令formula,满足:

  1. formula
  2. formula的某一个邻域中,formula
  3. formula

则存在formula的一个邻域,使得对于邻域中的点formula,唯一存在函数formula,满足:

  1. formula
  2. formula
  3. formula

# 3.5 二次型的正定性与半正定性

正定二次型的定义 对实二次型formula,若:

formula

则称formula正定二次型formula正定矩阵

正定二次型的判断 对于formula,下列命题等价:

  1. formula是正定二次型;
  2. formula是正定矩阵;
  3. formulaformula个顺序主子式都大于零;
  4. formulaformula个特征值都大于零;
  5. 存在可逆矩阵formula,使得formula

半正定二次型的定义 对实二次型formula,若:

formula

则称formula半正定二次型formula半正定矩阵

半正定二次型的判断 对于formula,下列命题等价:

  1. formula是半正定二次型;
  2. formula是半正定矩阵;
  3. formula的所有主子式都大于等于零,且至少有一个等于零;
  4. formulaformula个特征值都大于等于零,且至少有一个等于零。

# 4 凸集和凸函数

# 4.1 凸集

定义1.4.1formula,若formula,则称formula凸集。其中formula称为凸组合

常见的凸集有超平面formula半空间formula射线formula(其中formula为顶点,formula为方向向量)。

formula为凸集,formula,则:

  1. formula为凸集;
  2. formula为凸集;
  3. formula为凸集;
  4. formula为凸集。

凸集的线性组合也是凸集,但凸集的并不是凸集。

定义1.4.2formula,若formula,则称formula。若formula又为凸集,则称formula凸锥

向量集formula的非负线性组合formula

定义1.4.3 有限个半空间的交formula称为多面集,若formula,则多面集成为凸锥。

定义1.4.4formula为非空凸集,formula,若formula,则称formula为凸集formula极点

紧凸集中的点可以表示为极点的线性组合,但对无界集并不成立。

定义1.4.5formula为闭凸集,formula非零,若formula,则称formulaformula方向。又设formulaformula的两个方向,若formula,则称formula是不同的方向。若formula的方向formula不能表示成两个不同方向的正的线性组合,则称formulaformula的极方向。

有界集不存在方向和极方向。

考虑平面直角坐标系中的半平面formula,可以发现有3个极方向,分别是formula,且不存在极点。

特别地,对于formulaformulaformula的方向等价于formula

定理1.4.1 表示定理:设formula为非空多面集(它一定是多面集),则:

  1. 极点集非空且为有限个formula
  2. 极方向为空当且仅当formula有界,formula无界,则有有限个极方向formula
  3. formula当且仅当:

    formula

# 4.2 凸集分离定理

(暂不收录)

# 4.3 凸函数

(暂不收录)

# 4.4 凸函数的判别

(暂不收录)

# 4.5 凸规划

(暂不收录)

2016-2020 Ziping Sun
京ICP备 17062397号