7.9最优化修正

凸分析

1. 函数的一阶性质

• 海瑟矩阵：

$${▽}^{2}f(x)=\left[\begin{array}{cccc}\frac{{\partial }^{2}f(x)}{\partial x_1^2}& \frac{{\partial }^{2}f(x)}{\partial x_1\partial x_2}& \cdots & \frac{\partial f^2(x)}{\partial x_1\partial x_n}\\ \frac{{\partial }^{2}f(x)}{\partial x_2\partial x_1}& \frac{{\partial }^{2}f(x)}{{\partial }^2{x}_2}& \cdots & \frac{{\partial }^{2}f(x)}{\partial x_2\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f(x)}{\partial x_n\partial x_1}& \frac{{\partial }^{2}f(x)}{\partial x_n\partial x_2}& \cdots & \frac{{\partial }^{2}f(x)}{\partial x_n^2}\end{array}\right]$$

• 雅可比矩阵：向量值函数$F(x)=(f_1(x),f_2(x),\cdots ,f_m(x){)}^T$，则$JF(x)=\left[\begin{array}{cccc}\frac{\partial f_1(x)}{\partial x_1}& \frac{\partial f_1(x)}{\partial x_2}& \cdots & \frac{\partial f_1(x)}{\partial x_n}\\ \frac{\partial f_2(x)}{\partial x_1}& \frac{\partial f_2(x)}{\partial x_2}& \cdots & \frac{\partial f_2(x)}{\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial f_m(x)}{\partial x_1}& \frac{\partial f_m(x)}{\partial x_2}& \cdots & \frac{\partial f_m(x)}{\partial x_n}\end{array}\right]$
• 链式法则：$若F:{\mathbb{R}}^n\to {\mathbb{R}}^m，G:{\mathbb{R}}^m\to {\mathbb{R}}^q均为连续可微函数，定义H:{\mathbb{R}}^n\to {\mathbb{R}}^q为H(x)=G(F(x))，则JH(x)=JG(F(x))JF(x)，▽H(x)=▽F(x)▽G(F(x))$
• 泰勒展开： $f:{\mathbb{R}}^n\to {\mathbb{R}}^m连续可微，则在\overline{x}有一阶泰勒展式：f(x)=f(\overline{x})+▽f(\overline{x}{)}^T(x-\overline{x})+o(\Vert x-\overline{x}\Vert )$。若$f:{\mathbb{R}}^n\to {\mathbb{R}}^m$二阶连续可微，则在$\overline{x}$有二阶泰勒展式：$f(x)=f(\overline{x})+▽f(\overline{x}{)}^T(x-\overline{x})+\frac{1}{2}(x-\overline{x}{)}^T{▽}^{2}f(x)(x-\overline{x})+o(\Vert x-\overline{x}{\Vert }^2)$
• Lipschitz连续：设$f$连续可微，若存在常数$L>0对\forall x,y\in domf:=\{x\in {\mathbb{R}}^n:f(x)<+\infty \}$有：$\Vert ▽f(x)-▽f(y)\Vert \le L\Vert x-y\Vert$则称$f$是$L-光滑函数$。 -$\begin{array}{rl}& 性质：\\ & 1.二次上界：若domf为凸集，则：f(y)\le f(x)+▽f(x{)}^T(y-x)+\frac{L}{2}\Vert y-x{\Vert }^2\forall x,y\in domf\\ & 2.domf={\mathbb{R}}^n,且存在一个全局极小点x^{\ast },则对\forall x\in {\mathbb{R}}^n有：\frac{1}{2L}\Vert ▽f(x){\Vert }^2\le f(x)-f(x^{\ast })\end{array}$

2.广义实值函数与适当函数

• $\overline{\mathbb{R}}=\mathbb{R}\cup \{\pm \infty \}，称映射f:\mathbb{R}\to \overline{\mathbb{R}}为广义实值函数$
• 给定广义实值函数$f:\mathbb{R}\to \overline{\mathbb{R}}和非空集合\mathcal{X},如果存在x\in \mathcal{X},使得f(x)<+\infty ,且\forall x\in \mathcal{X},有f(x)>-\infty ,则称f关于集合\mathcal{X}是适当的$

3.凸函数的定义和性质

• 定义：$若对所有x,y\in domf和0\le \theta \le 1有f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y),则f为凸函数$;若$对所有x,y\in domf和0\le \theta \le 1有f(\theta x+(1-\theta )y)>\theta f(x)+(1-\theta )f(y),则f为严格凸函数$

• 下水平集，闭函数与下半连续函数：设广义实值函数 $f:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ .

  • $f$ 的 $\alpha$ -下水平集: $C_{\alpha }=\{x\mid f\left(x\right)\le \alpha \}$ .
  • $f$ 的上方图: $\mathrm{epi}f=\left\{\left(x,t\right)\in {\mathbb{R}}^{n+1}\mid f\left(x\right)\le t\right\}$ .
  • $f$ 为闭函数: $\mathrm{epi}f$ 为闭集.
  • $f$ 为下半连续函数: 对任意的 $x\in {\mathbb{R}}^n$ ,有 $\underset{y\to x}{\mathrm{liminf}}f\left(y\right)\ge f\left(x\right)$ .
  • $等价命题：$设广义实值函数 $f:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ ,则下列命题等价: $1.f\left(x\right)$ 的任意 $\alpha$ -下水平集都是闭集; $2.f\left(x\right)$ 是下半连续的; $3.f\left(x\right)$ 是闭函数.
  • $下半连续函数的性质：$ 1. 加法: 若 $f$ 与 $g$ 均为适当的下半连续函数,且 $\mathrm{dom}f\cap \mathrm{dom}g\ne \varnothing$ , 则 $f+g$ 也是下半连续函数. 2. 仿射函数的复合: 若 $f$ 为下半连续函数,则 $f\left(Ax+b\right)$ 也为下半连续函数; 3. 上确界: 若 $f_{\lambda },\lambda \in \Lambda$ 均为下半连续函数,则 $\underset{\lambda \in \Lambda }{\sup }{f}_{\lambda }\left(x\right)$ 也为下半连续函数.

• 凸函数的性质：

  • Jensen不等式: 设 $f$ 是凸函数,则对于 $1\le i\le m,x_i\in \mathrm{dom}f$ $0\le {\theta }_i\le 1$ 且 $\sum _{i=1}^m{\theta }_i=1$ ,有：
  $$f\left(\sum _{i=1}^m{\theta }_i{x}_i\right)\le \sum _{i=1}^m{\theta }_{i}f\left(x_i\right)$$
  • 概率Jensen 不等式: 设 $f$ 是凸函数,则对任意随机变量$z$ , $f\left(\mathbf{E}z\right)\le \mathbf{E}f\left(z\right)$
  • 设 f : ${\mathbb{R}}^n\to (-\infty ,+\infty ]$ 为凸函数,则 $f$ 在$int\mathrm{dom}f$ 连续.

• 凸函数的判定：

  • 函数 $f\left(x\right)$ 为凸函数当且仅当其上方图epi $f$ 是凸集.

  • 设 $f$ 为可微函数且 $\mathrm{dom}f$ 是凸集,则 $f$ 是凸函数当且仅当

  $$f\left(y\right)\ge f\left(x\right)+\nabla f{\left(x\right)}^{\top }\left(y-x\right)\forall x,y\in \mathrm{dom}f(1).$$ $${\left(\nabla f\left(x\right)-\nabla f\left(y\right)\right)}^{\top }\left(x-y\right)\ge 0,\forall x,y\in \mathrm{dom}f(2).$$

  $f$ 是严格凸函数当且仅当(1)或(2)对所有 $x,y\in \mathrm{dom}f$ 且 $x\ne y$ 严格成立 设 $f$ 为定义在凸集上的二阶连续可微函数,则 $f$ 是凸函数当且仅当

  $${\nabla }^{2}f\left(x\right)\succcurlyeq 0\forall x\in \mathrm{dom}f.$$

  如果 ${\nabla }^{2}f\left(x\right)\succ 0\forall x\in \mathrm{dom}f$ ,则 $f$ 是严格凸函数.

• 强凸函数：

  • 定义：$若存在常数m>0,使得g(x)=f(x)-\frac{m}{2}\Vert x{\Vert }^2为凸函数，则f为强凸函数。$
  • 充要条件：$f可微且domf为凸集，则f强凸的充要条件为：(▽f(x)-▽f(y){)}^T(x-y)\ge m\Vert x-y{\Vert }^2,\forall x,y\in domf$
  • 二次下界：$f的所有\alpha -下水平集有界，f(y)\ge f(x)+▽f(x{)}^T(y-x)+\frac{m}{2}\Vert x-y{\Vert }^2$

• 保凸函数运算：$f,f_1,f_2,\cdots ,f_m$为凸函数，则${\alpha }_1{f}_1+{\alpha }_2{f}_2({\alpha }_1,{\alpha }_2\ge 0);f(Ax+b);max\{f_1,\cdots ,f_m\};g(x)=\underset{y\in c}{\inf }f(x,y)(c为凸集);g(x)=\underset{y\in \mathcal{A}}{\sup }f(x,y)为凸集$

4.共轭函数

• 定义：适当函数$f$的共轭函数：$f^{\ast }\left(y\right)=\underset{x\in \mathrm{dom}f}{\sup }\left\{y^{T}x-f\left(x\right)\right\}.$
• 凸性：$f^{\ast }恒为凸函数,无论f是否是凸函数.$
• Fenchel不等式：$f\left(x\right)+f^{\ast }\left(y\right)\ge x^{T}y$

5.方向导数

• 对于凸函数 $f$ ,给定点 $x_0\in \mathrm{dom}f$ 以及方向 $d\in {\mathbb{R}}^n$ , 其方向导数定义为

$$\partial f\left(x_0;d\right)=\underset{t>0}{\inf }\frac{f\left(x_0+td\right)-f\left(x_0\right)}{t}.$$

对于可微函数, $\partial f\left(x_0;d\right)=\nabla f{\left(x_0\right)}^{\mathrm{T}}d$ .

• 方向导数有限: 设 $f\left(x\right)$ 为凸函数, $x_0\in \mathrm{int}\mathrm{dom}f$ ,则对 $\forall d\in {\mathbb{R}}^n$ , $\partial f\left(x_0;d\right)$ 有限.
• 方向导数和次梯度: 设 $f:{\mathbb{R}}^n\to (-\infty ,+\infty ]$ 为凸函数, $x_0\in \mathrm{int}\mathrm{dom}f$ ,则对 $\forall d\in {\mathbb{R}}^n$ ,有

$$\partial f\left(x_0;d\right)=\underset{g\in \partial f\left(x_0\right)}{\max }{g}^{\mathrm{T}}d.$$

6.次梯度

• 定义：设$f$为适当凸函数，$x\in domf$，若向量$g\in {\mathbb{R}}^n$满足$f\left(y\right)\ge f\left(x\right)+g^{\mathrm{T}}\left(y-x\right)\forall y\in \mathrm{dom}f则称g为函数f在点x处的一个次梯度$；$\partial f\left(x\right)=\left\{g\in {\mathbb{R}}^n\mid f\left(y\right)\ge f\left(x\right)+g^{\mathrm{T}}\left(y-x\right),\forall y\in \mathrm{dom}f\right\}为f在点x处的次微分$

• 存在性：设$f为凸函数，若x\in intdomf,则\partial f\ne \varphi$

• 性质：

  • 设 $f$ 是凸函数,则对 $\forall x\in \mathrm{dom}f,\partial f\left(x\right)$ 是闭凸集(可能为空集).
  • 设 $f$ 是凸函数,则对 $\forall x\in \mathrm{intdom}f,\partial f\left(x\right)$ 是非空有界集.
  • 设凸函数 $f\left(x\right)$ 在 $x_0\in \mathrm{intdom}f$ 处可微,则 $\partial f\left(x_0\right)=\left\{\nabla f\left(x_0\right)\right\}$ .
  • 次梯度的单调性 设 $f:{\mathbb{R}}^n\to \mathbb{R}$ 是凸函数, $x,y\in \mathrm{dom}f$ ,则
  $${\left(u-v\right)}^T\left(x-y\right)\ge 0,\forall u\in \partial f\left(x\right),\forall v\in \partial f\left(y\right).$$
  • 次梯度的连续性 设 $f\left(x\right)$ 是闭凸函数且 $\partial f\left(\bar{x}\right)\ne \varnothing$ . 若
  $$\underset{k\to \infty }{\lim }{x}^k=\bar{x},g^k\in \partial f\left(x^k\right)\text{ 且 }\underset{k\to \infty }{\lim }{g}^k=\bar{g},$$

  则 $\bar{g}\in \partial f\left(\bar{x}\right)$ .

• 计算：

  • 凸函数的非负线性组合: 设 ${\alpha }_1,{\alpha }_2\ge 0$ ,凸函数 $f_1,f_2$ 满 足 $\mathrm{int}\mathrm{dom}{f}_1\cap \mathrm{dom}{f}_2\ne \varnothing$ ,若
  $$f\left(x\right)={\alpha }_1{f}_1\left(x\right)+{\alpha }_2{f}_2\left(x\right),x\in \mathrm{dom}{f}_1\cap \mathrm{dom}{f}_2$$

  则 $f\left(x\right)$ 的次微分

  $$\partial f\left(x\right)={\alpha }_1\partial f_1\left(x\right)+{\alpha }_2\partial f_2\left(x\right).$$
  • 线性变量替换: 设 $h$ 为适当凸函数, $f\left(x\right)=h\left(Ax+b\right)$ . 若存 在 $x^{♯}\in {\mathbb{R}}^m$ 使得 $A{x}^{♯}+b\in \mathrm{int}\mathrm{dom}h$ ,则
  $$\partial f\left(x\right)=A^{\mathrm{T}}\partial h\left(Ax+b\right),\forall x\in \mathrm{int}\mathrm{dom}f.$$
  • 两个函数之和的次梯度 (Moreau-Rockafellar定理). 设 $f_1,f_2:{\mathbb{R}}^n\to (-\infty ,+\infty ]$ 是凸函数,则 对任意的 $x_0\in {\mathbb{R}}^n$ ，
  $$\partial f_1\left(x_0\right)+\partial f_2\left(x_0\right)\subseteq \partial \left(f_1+f_2\right)\left(x_0\right).$$

  若 $\mathrm{int}\mathrm{dom}{f}_1\cap \mathrm{dom}{f}_2\ne \varnothing$ ,则对任意的 $x_0\in {\mathbb{R}}^n$ ,

  $$\partial \left(f_1+f_2\right)\left(x_0\right)=\partial f_1\left(x_0\right)+\partial f_2\left(x_0\right).$$

7. 非凸函数的次微分

• 设 $f:{\mathbb{R}}^n\to (-\infty ,+\infty ]$ 为适当、下半连续函数. 对给定的 $x\in \mathrm{dom}f$ ,满足如下条件的所有向量 $u\in {\mathbb{R}}^n$ 的集合定义为 $f$ 在点 $x$ 处的Fréchet 次微分:

$$\underset{y\to x,y\ne x}{\mathrm{liminf}}\frac{f\left(y\right)-f\left(x\right)-u^{\top }\left(y-x\right)}{\parallel y-x\parallel },$$

记为 $\hat{\partial }f\left(x\right)$ ; 若 $x\notin \mathrm{dom}f$ ,定义 $\hat{\partial }f\left(x\right)=\varnothing$ .

• $f$ 在点 $x$ 处的极限次微分(或Mordukhovich次微分,或简称为次微分):

$$\partial f\left(x\right)=\left\{u\in {\mathbb{R}}^n\mid \exists x^k\to x,f\left(x^k\right)\to f\left(x\right),u^k\in \hat{\partial }f\left(x^k\right),u^k\to u\right\}.$$

最优性条件

1. 最优解存在性：

• 设 $f:\mathcal{X}\to (-\infty ,+\infty ]$ 是恰当且闭的,则 ${\mathrm{argmin}}_{\mathcal{X}}f$ 为非空紧集,若如下任一条件成立: (1) $\mathrm{dom}f=\{x\in X:f\left(x\right)<+\infty \}$ 是有界的; (2) $\exists \alpha$ 使得下水平集 ${\mathrm{C}}_{\alpha }=\{x\in \mathcal{X}:f\left(x\right)<\alpha \}$ 非空有界; (3) $f$ 是强制的,i.e., $\left\{x^k\right\}\subseteq \mathcal{X},x^k\to +\infty \Rightarrow \underset{k\to \infty }{\lim }f\left(x^k\right)=+\infty$

2. 最优解唯一性：

• 强拟凸函数: 给定非空凸集 $X$ 与函数 $f:X\to (-\infty ,+\infty ]$ ,若对任意的$x\ne y$ 以及 $\lambda \in \left(0,1\right)$ ,均有: $f\left(\lambda x+\left(1-\lambda \right)y\right)<\max \{f\left(x\right),f\left(y\right)\}$则称 $f$ 为 $X$ 上的强拟凸函数.
• 给定非空凸紧集 $X\subseteq {\mathbb{R}}^n$ ,设 $f:X\to (-\infty ,+\infty ]$ 是适当、闭、强拟凸函数,则 ${\mathrm{argmin}}_{x}f$ 为单点集,i.e.,存在唯一的 $x^{\ast }$ 满足:

$$f\left(x^{\ast }\right)<f\left(x\right),\forall x\in \mathcal{X}\setminus \left\{x^{\ast }\right\}$$

3. 无约束优化最优性条件

• 下降方向：设 $\bar{x}\in {\mathbb{R}}^n$ 是任一给定向量, $d\in {\mathbb{R}}^n$ 且 $d\ne 0$ . 若存在 $\delta >0$ ,对任意 $\lambda \in \left(0,\delta \right)$ ,有 $f\left(\bar{x}+\lambda d\right)<f\left(\bar{x}\right)$ ,则称 $d$ 为函数 $f$ 在点 $\bar{x}$ 处的一个下降方向.${\mathbf{d}}^T\nabla f\left(x\right)<0\Rightarrow \mathbf{d}$ 是 $f$ 在 $x$ 处的下降方向
• 一阶必要性条件：若 $x^{\ast }\in {\mathbb{R}}^n$ 是无约束优化问题的一个局部最优解,则有:

$$\nabla f\left(x^{\ast }\right)=0.$$

• 二阶必要性条件：若 $x^{\ast }\in {\mathbb{R}}^n$ 是无约束优化问题的一个局部最优解,则有:$\nabla f\left(x^{\ast }\right)=0$ 且 ${\nabla }^{2}f\left(x^{\ast }\right)$ 为半正定矩阵.
• 二阶充分性条件：若 $x^{\ast }\in {\mathbb{R}}^n$ 满足 $\nabla f\left(x^{\ast }\right)=0$ 且 ${\nabla }^{2}f\left(x^{\ast }\right)$ 为正定矩阵. 则 $x^{\ast }$ 是无约束优化问题的一个严格局部最优解.
• 特别的： 若无约束优化问题(1) 的目标函数 $f$ 是连续可微的凸函数,则 $x^{\ast }\in {\mathbb{R}}^n$ 是凸优化的全局最优解当且仅当 $\nabla f\left(x^{\ast }\right)=0$ ；
• 非光滑优化最优性条件：
  • 一阶充要条件：若无约束优化问题(1) 的目标函数 $f$ 是适当凸函数,则 $x^{\ast }\in \mathrm{dom}f$是凸规划的全局最优解当且仅当 $0\in \partial f\left(x^{\ast }\right)$ . 一阶充要条件
  • 一阶必要条件：设优化问题(1) 的目标函数 $f$ 是适当下半连续的,若 $x^{\ast }\in \mathrm{dom}f$ 是问题(1)的一个局部最优解,则 $0\in \hat{\partial }f\left(x^{\ast }\right)\subseteq \partial f\left(x^{\ast }\right)$ .
• 复合优化最优性条件：
  • 数学模型： $\underset{x\in {\mathbb{R}}^n}{\min }\psi \left(x\right)=f\left(x\right)+h\left(x\right)$其中 $f\in C^1$ (可能非凸), $h$ 为适当闭函数（可能非光滑）.
  • 一阶必要性条件： 若 $x^{\ast }\in \mathrm{dom}\psi$ 是复合优化问题(2) 的一个局部最优解,则:

$$-\nabla f\left(x^{\ast }\right)\in \partial h\left(x^{\ast }\right).$$

数值迭代算法概述

1.全局收敛与局部收敛

• 收敛：设 $S^{\ast }$ 是最优化问题的某种解集合, $A$ 为某种算法. 给定集合 $Y$ ,若对于任意初始点 $x_0\in Y$ ,算法 $A$ 产生的迭代点列 $\left\{x_k\right\}$ 中任一收敛子列的极限都属于 $S^{\ast }$ ,则称算法 $A$ 在 $Y$ 上收敛.
• 全局收敛：若集合 $Y$ 可以任意选取 (无需限定在解集合很小的邻域内),则相应的收敛性为全局收敛性 (global convergence) ;
• 局部收敛：若集合 $Y$ 只能取接近解集合的点集,则相应的收敛性为局部收敛性 (local convergence).

2.子序列收敛与全序列收敛

• 算法 $A$ 产生的迭代点列 $\left\{x_k\right\}$ 中任一收敛子列的极限点都属于解集 $S^{\ast }$ ,则称为子序列收敛 (subsequence convergence),若 $x_k\to x^{\ast }\in S^{\ast }$ ,则称为全序列收敛(whole sequence convergence).

3.收敛速度

• 定义1：设点列 $\left\{x_k\right\}$ 收敛到 $x^{\ast }$ ,若存在实数 $p\ge 0,r\ge 1$ ,使得$\underset{k\to +\infty }{\lim }\frac{\Vert \begin{array}{c}{x}_{k+1}-x^{\ast }\end{array}\Vert }{{\Vert \begin{array}{c}{x}_k-x^{\ast }\end{array}\Vert }^r}\le p<+\infty$则称点列 $\left\{x_k\right\}$ 以 $Q-r$ 阶收敛速率收敛到 $x^{\ast }$ .
  • $Q$ -次线性收敛: $r=1,p=1$
  • $Q$ -线性收敛: $r=1,p\in \left(0,1\right)$
  • $Q$ -超线性收敛: $r=1,p=0$
  • $Q-$ 二次收敛: $r=2,p>0$
• 定义2：设点列 $\left\{x_k\right\}$ 收敛到 $x^{\ast }$ ,若存在实数 $\alpha >0,q\in \left(0,1\right)$ ,使得$\Vert \begin{array}{c}{x}_k-x^{\ast }\end{array}\Vert \le \alpha q^k,=:t_k\text{ Q-线性收敛到 0 }$则称点列 $\left\{x_k\right\}$ 以 $R$ -线性收敛到 $x^{\ast }$ . 若存在实数 $\alpha >0$ ,以及收敛到 0 的正数列 $\left\{q_k\right\}$ ,使得$\Vert \begin{array}{c}{x}_k-x^{\ast }\end{array}\Vert \le \alpha \prod _{i=1}^k{q}_i,=:t_k\text{ Q-超线性收敛到 0 }$则称点列 $\left\{x_k\right\}$ 以 $R$ -超线性收敛到 $x^{\ast }$ . 同级收敛速度Q-收敛速率快于R-收敛速率

3. 迭代复杂度

设某一算法求解 $\underset{x\in {\mathbb{R}}^n}{\min }f\left(x\right)$ 产生的迭代点列 $\left\{x_k\right\}$ 收敛到最优解 $x^{\ast }$ , 若存在实数 $c,r>0$ ,使得$f\left(x_k\right)-f\left(x^{\ast }\right)\le \frac{c}{k^r}\forall k>0$则称该算法是 $O\left(\frac{1}{k^r}\right)$ 阶收敛到 $x^{\ast }$ .

• 若需要算法满足精度 $f\left(x_k\right)-f\left(x^{\ast }\right)\le \epsilon$ ,只需令 $\frac{c}{k^r}\le \epsilon$ ,从而得到 $k\ge \frac{c^{1/r}}{{\epsilon }^{1/r}}$ . 因此该优化算法对应的迭代次数复杂度为 $N\left(\epsilon \right)=\mathcal{O}\left(\frac{1}{{\epsilon }^{1/r}}\right)$
• $r$ 越大,收敛越快,复杂度越低,算法越好.

4. 二次终止性

若某个算法对任意的严格凸二次函数, 从任意的初始点出发, 都能经有限步迭代达到其极小值点, 则称该算法具有二次终止性.

5.空间复杂性与时间复杂性

• 定义：描述算法的存储要求和运行时间要求, 分为算法的空间复杂性和算法的时间复杂性. 利用算法需要的初等运算次数表示算法的时间复杂性.
• 多项式时间算法：求解实例 $I$ 的算法的基本运算总次数 $C\left(I\right)$ 是实例输入长度 $L\left(I\right)$ 的一个函数, 该函数被另一个函数 $g$ 控制,即存在一个函数 $g$ 和一个常数 $\alpha$ ,使得

$$C\left(I\right)\le \alpha g\left(L\left(I\right)\right)$$

若 $g$ 为多项式函数,则称该算法对实例 $\mathbf{I}$ 是多项式时间的算法; 若对于这类问题的任意实例 $\mathbf{I}$ 是多项式时间的算法,则称该算法为求解这一类问题的多项式时间算法.类似地可以定义的指数时间算法.