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

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

问题定义

多元二次多项式，维度为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} 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

其中a_{i,j}为二次项系数，共有n^2项，1 le i,j le n，且所有的a不全为0，即exists a_{i,j} ne 0; b_k为一次项系数，共n项，1 le k le n; c为常数项。

记 f({bf{x}}) = {[{x_1},{x_2}, cdots ,{x_n}]^T} ，则上述函数可以写作二次型的形式：

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

转化过程中bf{A},bf{b}满足： {bf{A} } 为n阶对称方阵，{ { bf { A } } _ { i , j } } = { a _ { i , j } } 因为exists a_{i,j} ne 0，bf{A}不为零矩阵 bf{b}_i=b_i

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

f({bf{x} }) = frac{1}{2}{bf{x^TAx} } - { {bf{b} }^{bf{T} } }{bf{x} } {bf{c} }

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

简要分析

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

需要解决的问题

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

exists

0 人点赞