二次型优化问题 - 1 - 问题描述

刺骨的言语ヽ痛彻心扉 2022-11-13 14:25 179阅读 0赞

> 在各种场景可能都会遇到需要求解多元二次函数极值的问题，本系列文章介绍相关的计算方法，核心内容为共轭梯度法。
> 
> 本文介绍问题定义。

### 问题定义 ###

*  多元二次多项式，维度为 n n n，那么可以用以下公式描述该函数：

f ( x 1 , x 2 , x 3 , . . . , x n ) = a 1 , 1 x 1 2 + a 1 , 2 x 1 x 2 + a 1 , 3 x 1 x 3 + ⋯ + a 1 , n x 1 x n + a 2 , 1 x 2 x 1 + a 2 , 2 x 2 2 + a 2 , 3 x 2 x 3 + ⋯ + a 2 , n x 2 x n + ⋯ + a n , n x n 2 + b 1 x 1 + b 2 x 2 + ⋯ + b n x n + c f(\{x\_1\},\{x\_2\},\{x\_3\},...,\{x\_n\}) = \{a\_\{1,1\}\}x\_1^2 + \{a\_\{1,2\}\}\{x\_1\}\{x\_2\} + \{a\_\{1,3\}\}\{x\_1\}\{x\_3\} + \\cdots + \{a\_\{1,n\}\}\{x\_1\}\{x\_n\} + \{a\_\{2,1\}\}x\_2\{x\_1\} + \{a\_\{2,2\}\}\{x\_2^2\} + \{a\_\{2,3\}\}\{x\_2\}\{x\_3\} + \\cdots + \{a\_\{2,n\}\}\{x\_2\}\{x\_n\} + \\cdots + \{a\_\{n,n\}\}x\_n^2+\{b\_1\}x\_1+\{b\_2\}x\_2+\\cdots+\{b\_n\}x\_n+c f(x1,x2,x3,...,xn)=a1,1x12\+a1,2x1x2\+a1,3x1x3\+⋯\+a1,nx1xn\+a2,1x2x1\+a2,2x22\+a2,3x2x3\+⋯\+a2,nx2xn\+⋯\+an,nxn2\+b1x1\+b2x2\+⋯\+bnxn\+c

> 其中 a i , j a\_\{i,j\} ai,j为二次项系数，共有 n 2 n^2 n2项， 1 ≤ i , j ≤ n 1 \\le i,j \\le n 1≤i,j≤n，且所有的 a a a不全为0，即 ∃ a i , j ≠ 0 \\exists a\_\{i,j\} \\ne 0 ∃ai,j=0;
> 
>  b k b\_k bk为一次项系数，共 n n n项， 1 ≤ k ≤ n 1 \\le k \\le n 1≤k≤n;
> 
>  c c c为常数项。

*  记  f ( x ) = \[ x 1 , x 2 , ⋯   , x n \] T f(\{\\bf\{x\}\}) = \{\[\{x\_1\},\{x\_2\}, \\cdots ,\{x\_n\}\]^T\} f(x)=\[x1,x2,⋯,xn\]T ，则上述函数可以写作二次型的形式：

f ( x 1 , x 2 , x 3 , . . . , x n ) = f ( x ) = x T A x + b T x + c f(\{x\_1\},\{x\_2\},\{x\_3\},...,\{ x\_n\}) = f(\{\\bf\{x\}\}) = \{\\bf\{x^T\} \}\\bf\{A\}\{\\bf\{x\} \} + \{ \{\\bf\{b\} \}^T\}\{\\bf\{x\} \} + c f(x1,x2,x3,...,xn)=f(x)=xTAx\+bTx\+c

> 转化过程中 A , b \\bf\{A\},\\bf\{b\} A,b满足：
> 
>  A \{\\bf\{A\} \} A 为 n n n阶对称方阵， A i , j = a i , j \{ \{ \\bf \{ A \} \} \_ \{ i , j \} \} = \{ a \_ \{ i , j \} \} Ai,j=ai,j
> 
> 因为 ∃ a i , j ≠ 0 \\exists a\_\{i,j\} \\ne 0 ∃ai,j=0， A \\bf\{A\} A不为零矩阵
> 
>  b i = b i \\bf\{b\}\_i=b\_i bi=bi

*  为了后续计算简便，我们将二次型稍作改动：

f ( x ) = 1 2 x T A x − b T x + c f(\{\\bf\{x\} \}) = \\frac\{1\}\{2\}\{\\bf\{x^TAx\} \} - \{ \{\\bf\{b\} \}^\{\\bf\{T\} \} \}\{\\bf\{x\} \} + \{\\bf\{c\} \} f(x)=21xTAx−bTx\+c

*  我们的目标就是寻找该函数的极值点的坐标，我们把该目标称为 x ∗ \\bf\{x^\*\} x∗。

### 简要分析 ###

*  当前问题其实就是多元二次方程极值求解的问题
 *  此类函数在函数定义域内处处连续可导
 *  极值点必然处于导数为0的位置

### 需要解决的问题 ###

*  同一个多元二次方程表示成二次型的参数 A , b , c \\bf\{A\},\\bf\{b\},\\bf\{c\} A,b,c是否唯一，如果不唯一该如何设置，为什么如此设置
 *  该问题是否存在导数为0的点
 *  导数为0的点如何求解
 *  导数为0的点是否就是极值点
 *  对于给定的二次型如何判断是否可优化
 *  对于可优化的二次型都有什么方法寻找极值点
 *  寻找极值点的方法们都有哪些优缺点，为什么需要提出共轭梯度法
 *  代数解法，梯度下降法介绍与分析
 *  共轭梯度法介绍与分析
 *  共轭梯度法的相关证明