第四十八章

优化理论的一般结果

48.1优化问题；基本术语

优化理论的主要目标是构造算法来寻找形式问题的解（通常是近似解）。

求u，使u∈u和j（u）=vinf∈u j（v），

其中u是（实数）向量空间v（可能是无限维）的给定子集，j:Ω→r是在v的某些开放子集Ω上定义的函数，因此uΩ。

很明显，infv∈u j（v）表示实数集的最大下界

实数集的最大下界和最小上界。j（u）u∈u。为了确保我们的立场坚定，让我们回顾一下

设x为r的任何非空子集。x下界的集合lb（x）定义为

lb（x）=b∈r b≤x表示所有x∈x。

这样，如果集合x<rx不在下面，这意味着对于每个，那么lb（x）为空。否则，如果Lb（x）是非空的，由于它是有界的，在X的每一个元素上都有一个x∈x，根据实数的一个基本性质，集Lb（x）有一个表示为inf x的最大元素，实数inf x是x的最大下界，一般来说，inf x不是b。拉长到x，但如果是，那么它是x的最小元素。

如果lb（x）=∅，那么x在下面是无界的，inf x是未定义的。在这种情况下（滥用符号），我们写

inf x=−∞。

一千五百二十五

按照惯例，当x=时，我们设置inf∅=+∞。

例如，如果x=x∈r x≤0，那么lb（x）=∅。另一方面，如果x=1/n n∈n−0，那么lb（x）=x∈r x≤0和inf x=0，它不在x中。

同样，x上界的集ub（x）由下式给出

uB（x）=u∈r x≤u表示所有x∈x。

如果x不在上面有界，则ub（x）=∅。否则，如果Ubof x（x.if sup）=6∅，那么它有leastx∈x，那么它是

元素表示supx。因此，supx是x的最小上界，也是x的最大元素。如果ub（x）=

supx=+∞。

按照惯例，当x=∅时，我们设置sup∅−∞。

例如，如果x=x∈r x≥0，则lb（x）=∅。另一方面，如果x−0，则ub（x）=x∈r x≥1且supx=1，不在

元素inf v∈u j（v）只是inf j（v）v∈u。符号j常用来表示infv∈u j（v）。如果函数j不在下面有界，这意味着对于每一个r∈r，都有一些u∈u，这样j（u）<r，那么

文福J（V）=-∞，

γ

我们说我们的最小化问题没有解决方案，或者说它是无界的（下面）。例如，如果v=Ω=r，uv u=（xv）=∈r−∞x.≤0，j（x）=−x，则函数j（x）不在下界，inf∈j

问题是，J可能不属于J（U）U∈U，也就是说，可能无法实现

通过一些元素，我们的最小化问题没有解决的办法，达到了在这个意义上的值，而解决上述问题就在于找到一些（u）=j。如果没有这样的u∈u存在，我们再次说u∈u

最小化问题

求u，使u∈u和j（u）=vinf∈u j（v）

通常以以下更为非正式的方式呈现：

最小化j（v）

（问题m）服从v∈u。

48.1。优化问题.基本术语

一个向量u∈u，使j（u）=infv∈u j（v）常称为j对u的极小值，有些作者用argminv∈u j（v）表示j对u的极小值集，并写出

u∈argminj（v）

Vüu

表示u是一个极小值。当这样一个极小值是唯一的时，通过滥用符号，这个唯一极小值u表示为

u=argminj（v）。

Vüu

我们不喜欢使用这个符号，尽管它似乎已经侵入了文学。

如果我们需要最大化而不是最小化一个函数，那么我们试图找到一些u∈u，这样

j（u）=supj（v）。

Vüu

这里supv∈u j（v）是集合j（u）u∈u的最小上界。用argmaxv∈u j（v）表示j overu的极大值集。

备注：有些作者将扩展实值函数定义为函数f:Ω→r，它允许取其某些参数的值−∞或甚至＋∞。虽然这对于处理需要考虑infv∈u j（v）或supv∈u j（v）的情况比较方便，但这种“函数”实际上是偏函数，我们不喜欢使用扩展实值函数的概念。

在大多数情况下，u被定义为有限约束集的解集，即等式约束（v）=0，或不等式约束（v）≤0，其中，i:Ω→r是一些给定函数。函数j通常被称为优化问题的函数。这是一个有点奇怪的术语，但是如果v是一个函数空间，它是合理的。

以下问题自然会出现：

(1) 关于问题解（m）存在唯一性的结果。在下一节中，我们将在域U或函数J上声明确保解存在的充分条件。

(2) 问题M可能解的刻画，这是任何元素u∈u为问题解的条件。此类条件通常涉及j的导数dju，可能还涉及定义u的函数的导数，其中一些条件在函数i为凸函数时就足够了，

(3) 算法的有效构造，通常是迭代算法，它构造一个极限为解u∈u的u元素的序列（u k）k≥1。因此，有必要了解这种序列何时以及以多快的速度收敛。梯度下降法属于这一类。一般来说，无约束问题（U=Ω=V）比约束问题（U=6 V）更容易处理。

这一章的材料深受Ciarlet的启发[41]。在本章中，假设v是一个有内积h−i的实向量空间。如果v是无限维，那么我们假设它是一个实希尔伯特空间（它是完整的）。和往常一样，我们写Kwant来回顾第47.1节，特别是投影引理和Riesz表示uk=hu，ui1/2，以获得与内积h−、−i相关的范数。读者可以定理。

作为术语，如果u由不等式和等式约束定义为

u=vΩi（v）≤0，i=1，…，m，ψj（v）=0，j=1，…，p，

如果j和所有的函数ψi和ψj都是仿射函数，则问题称为线性（或线性程序），否则称为非线性。如果J的形式

j（v）=hav，vi−hb，vi

当a是一个非零对称半正定矩阵，且约束是仿射矩阵时，该问题称为二次规划问题。如果内积h−，−i是标准欧几里得内积，j也表示为

j（v）=v>av−b>v。

48.2优化问题解的存在性

我们从U是RN的一个封闭但可能是无边界子集的情况开始。在这种情况下，会出现以下类型的函数。

定义48.1.强制实值函数j:v→rv在赋范向量空间上定义，如果limk→∞7 kvkk=∞，则v为

任意序列的iff（vk）k≥1矢量vk∈

klim j（vk）=+∞。

7→∞

例如，函数f（x）=x2+2x是强制的，但仿射函数f（x）=ax+b不是。

命题48.1.强迫u为非空u的闭子集的连续函数是无界的。那么至少有一个元素，让j:rn→r是a

u∈rn使u∈u和j（u）=vinf∈u j（v）。

证据。由于u 6=∅，选取任意u0∈u，由于j是强制的，所以有一些r>0，这样对于所有v∈rn，如果kvk>r，则j（u0）<j（v）。因此，j在集合上最小化。

u0=u v∈rn kvk≤r。

48.2。优化问题解的存在性

由于u是封闭的，并且由于闭球v∈rn kvk≤r是紧的，所以u0是紧的，但是我们知道紧集上的任何连续函数都有一个最小值，这是可以实现的。

以上证明的关键点是U0是紧凑的。为了将命题48.1推广到无穷维向量空间的情形，我们需要一些附加的假设，证明了u和函数j的凸性是充分的。关键是希尔伯特空间的凸集、闭集和有界子集是“弱紧的”。

定义48.2.让V成为希尔伯特空间。如果存在一些u∈v suchthat，则向量u k∈v的序列（uk）k≥1弱收敛。

lim hv，uki=hv，ui表示每个v∈v。K→∞7

回想一下，如果Hibert空间具有可数Hilbert基，则它是可分离的（参见定义A.4）。此外，在欧几里得空间（有限维）中，内积在V与其对偶V之间引起同构。在我们的例子中，我们需要从v到v的同构，这样对于每一个线性形式ω∈v，向量ω]∈v都是由方程ω（v）=hv，ω]i唯一定义的，所有v∈v。

在希尔伯特空间中，对偶空间v 0是所有连续线性形式ω：v→r的集合，v 0和v之间同构]的存在由Riesz表示定理给出；见命题47.8。这个定理允许梯度概念的推广。实际上，如果f:v→r是希尔伯特空间v上定义的一个函数，如果f在某一点u∈v可微，那么根据定义，导数dfu:v→r是一个连续的线性形式，因此根据Riesz表示定理（命题47.8），有一个唯一的向量，表示fu∈使dfu（v）=hv，fui表示所有v∈v。

根据定义，矢量f u是f在u处的梯度。

同样地，由于f的二阶导数d2fu:v→v 0从v×v到r诱导了一个连续对称的双线性形式，因此，根据命题47.9，有一个独特的连续自伴线性映射2fu:v→v，从而

d2fu（v，w）=h 2fu（v），wi表示所有v，w∈v。

地图2fu是hessian的泛化。

下一个定理是关于凸域上定义的凸函数极小值存在的一个相当普遍的结果。这个证据涉及很多，一读就可以省略。

定理48.2。设u为可分离希尔伯特空间v的非空凸闭子集，设j:v→r为凸可微函数，当u为无界时，它是强制的。那么至少有一个元素u∈v，这样

u∈u和j（u）=inf j（v）。

Vüu

证据。正如在48.1命题的证明中，由于函数j是强制的，我们可以假定u是有界的和凸的（然而，如果v是无限维，那么u一般不是紧的）。证据分四步进行。

第1步。考虑一个最小化序列（uk）k≥0，即一个元素序列uk∈v，这样

Uk∈u表示所有k≥0，lim j（Uk）=inf j（v）。

K7→∞V∈U

在这个阶段，infv∈u j（v）=-∞是可能的，但我们会看到这实际上是不可能的。然而，由于u是有界的，所以序列（u k）k≥0是有界的。我们的目标是证明（uk）k≥0的（w）≥0的某些子序列弱收敛。

由于序列（uk）k≥0是有界的，所以存在一些常数c>0，使得所有k≥0的kukk≤c。然后通过柯西-施瓦兹不等式，对于每一个v∈v，我们有

| hv，uki≤kvkkuk≤c kvk，

这表明序列（hv，uki）k≥0是有界的。由于V是一个可分离的希尔伯特空间，在V中有一个密度为V的向量v k∈V的可数族（vk）k≥0。由于序列（hv1，uki）k≥0是有界的（在r中），我们可以找到收敛子序列（hv1，ui1（j）i）j≥0。同样，由于序列（hv2，ui1（j）i）j≥0是有界的，我们可以找到收敛子序列（hv2，ui2（j）i）j≥0，一般来说，由于序列（hvk，uik−1（j）i）j≥0是有界的，我们可以找到收敛子序列（hvk，uik（j）i）j≥0。

我们得到以下无限数组：

考虑“对角”序列（w）≥0

w=ui（），≥0.

我们将证明，对于每一个v∈v，序列（hv，wi）≥0都有一个极限。

通过构造，对于每k≥0，序列（hvk，wi）≥0有一个极限，即序列（hvk，uik（j）i）j≥0的极限，因为序列（i（））≥0是每一个序列（i（j））j≥0的子序列。

选取任意v∈v和任意>0。因为（v k）k≥0在v中是稠密的，所以有一些vk使得

.

48.2。优化问题解的存在性

然后我们有了

| hv，wi−hv，wmi=hv，w−wmi|

=hvk+v−vk，w `−wmi|

=hvk，w−wmi+hv−vk，w−wmi|

≤hvk，wi−hvk，wmi+hv−vk，w−wmi。根据柯西-施瓦兹，由于kw−wmk≤kwk+kwmk≤c+c=2c，

，

所以

.

在元素vk保持不变的情况下，根据前面的一个参数，序列（hvk，wi）≥0收敛，因此它是一个柯西序列。因此有一些“0”（取决于），这样

所有，m≥ 0，

所以我们得到，m≥ 0。

这证明了序列（hv，wi）≥0是柯西序列，因而收敛。通过定义函数g:v→r

g（v）=lim7→∞hv，wi，对于所有v∈v。

由于hv，wi≤kvkkw k≤c kvk，所有`≥0，

我们有

| g（v）≤c kvk，

所以G是一个连续的线性映射。根据Riesz表示定理（命题47.8），有一个唯一的u∈v，这样

g（v）=hv，所有v∈v的ui，

这表明

limhv，w`i=hv，ui表示所有v∈v，

` 7→∞

即序列（u k）k≥0的子序列（w）≥0弱收敛于u∈v。

第2步。证明了序列（w）≥0的“弱极限”u属于u。

考虑u∈v在闭凸集u上的投影pu（u），自w `∈u以来，通过命题47.5（2）和u是凸的闭的事实，我们得到了

hpu（u）−u，w−pu（u）i≥0（对于所有≥0）。

序列（w）≥0到u的弱收敛意味着

0≤limhpu（u）−u，w`−pu（u）i=hpu（u）−u，u−pu（u）i

` 7→∞

=−kpu（u）−uk≤0，

所以kpu（u）−uk=0，这意味着pu（u）=u，所以u∈u。

第3步。我们证明了

J（V）≤极限J（Z`）

` 7→∞

对于每一个序列（z）≥0弱收敛到某个元素v∈v。

既然假设j是可微的和凸的，根据命题39.9（1），我们得到

j（v）+h jv，z−vi≤j（z），所有`≥0，

根据弱收敛的定义

limh合资企业，z`i=h合资企业，vi，

` 7→∞

所以lim`7→∞h jv，z−vi=0，根据liminf的定义，我们得到

J（V）≤极限J（Z`）

` 7→∞

对于每一个序列（z）≥0弱收敛到某个元素v∈v。

第4步。从最小序列（u k）k≥0中提取的子序列（w）≥0的弱极限u∈u满足方程j（u）=inf j（v）。

Vüu

通过步骤（1）和步骤（2），序列（u k）k≥0的子序列（w）≥0弱收敛于某个元素u∈u，因此通过步骤（3）我们得到j（u）≤liminf j（w`）。

`→∞7

另一方面，根据（w）≥0的定义，作为（uk）k≥0的子序列，因为

（j（uk））k≥0收敛于j（v），我们有

j（u）≤lim inf j（w`）=lim j（uk）=inf j（v），

` 7→∞K7→∞V∈U

证明了u∈u达到了u上j的最小值。

注：定理48.2仍然成立，如果我们只假设j是凸的和连续的。它也存在于自反Banach空间中，其中Hilbert空间是一种特殊情况；参见Brezis[31]，推论3.23。

定理48.2是一个相当普遍的定理，它的证明是相当复杂的。对于某种类型的函数j，我们可以得到更容易证明的存在唯一性结果。这一点尤其适用于二次函数。

48.3二次函数的最小值

定义48.3.让V成为一个真正的希尔伯特空间。函数j:v→r的形式称为二次函数。

，

其中：v×v→r是对称连续的双线性形式，h:v→r是连续线性形式。

定义48.3是RN上二次函数概念的自然延伸。实际上，根据47.9，有一个唯一的连续自伴线性映射a:v→v，这样a（u，v）=hau，vi对于所有u，v∈v，

根据Riesz表示定理（命题47.8），有一个唯一的b∈v，这样

h（v）=hb，vi表示所有v∈v。

因此，j可以写成

对于所有的v∈v。（1）

由于a是双线性的，h是线性的，通过命题38.3和38.5，观察到j的导数由

dju（v）=a（u，v）−h（v），对于所有v∈v，

或等同于

dju（v）=hau，vi−hb，vi=hau−b，vi，对于所有v∈v。

因此，j的梯度由

ju=au−b，（2）

是对称的，就像在形式n×n矩阵和b∈rn的二次函数的情况下一样。求二阶导数dj（v）=（1/2）v>av2−jubof>v，其中j在u wea计算

dju+v（w）−dju（w）=a（u+v，w）−h（w）−（a（u，w）−h（w））=a（v，w），

所以

d2ju（v，w）=a（v，w）=hav，wi，

会产生

2ju=a.（3）

我们还将使用以下公式。

提案48.3.如果j是二次函数，那么

.

证据。因为A是对称双线性的，而H是线性的，我们有

由于dju（v）=a（u，v）−h（v）=h au−b，vi和ju=au−b，我们也可以写

，

如要求。

关于二次函数极小值的存在唯一性，我们有如下定理。

定理48.4。给定任何希尔伯特空间v，让j:v→r是形式的二次函数。

.

假设有一个实数α>0，这样

a（v，v）≥αkvk2，所有v∈v.（α）

如果u是v的任何非空的、闭的、凸的子集，那么有一个唯一的u∈u，使得j（u）=inf j（v）。

Vüu

元素u∈u满足条件

a（u，v−u）≥h（v−u），对于所有v∈u.（）

相反地（在上述相同的假设下），如果一个元素u u满足（），那么j（u）=inf j（v）。

Vüu

如果u是v的一个子空间，则上述不等式被方程所代替。

a（u，v）=h（v）表示所有v∈u.（）

证据。关键是双线性形式A实际上是v的内积。这是因为它是正定的，因为（α）意味着

√αkvk≤（a（v，v））1/2，

另一方面，a的连续性意味着

A（V，V）≤Kakkvk2，

所以我们得到

√αkvk≤（a（v，v））1/2≤pkakkvk。

上述还表明，内积A诱导的范数V 7→（A（V，V））1/2等于内积H−、−I on V诱导的范数。因此h相对于标准v→7（a（v，v））1/2仍然是连续的。然后根据Riesz表示定理（命题47.8），有一些独特的c∈v，这样

h（v）=a（c，v）表示所有v∈v。

因此，我们可以将j（v）表示为

.

但是，在u上最小化j（v）等于在v∈u上最小化（a（v−c，v−c））1/2，并且通过投影引理（命题47.5（1）），这相当于在闭凸集u上找到c的投影pu（c）相对于内积a。因此，有一个唯一的u=pu（c）∈u，使j（u）=inf j（v）。

Vüu

同样，根据命题47.5（2），这个唯一元素u∈u的特征是条件

a（u−c，v−u）≥0表示所有v∈u。

自从

A（U−C，V−U）=A（U，V−U）−A（C，V−U）=A（U，V−U）−H（V−U）、

上述不等式等于

a（u，v−u）≥h（v−u），适用于所有v∈u。 如果u是v的子空间，那么根据命题47.5（3），我们有条件 a（u−c，v）=0，对于所有v∈u， 相当于	（三）
a（u，v）=a（c，v）=h（v），对于所有v∈u，	（）
A索赔。

注意双线性形式A的对称性起了关键作用。此外，不平等

a（u，v−u）≥h（v−u），对于所有v∈u

有时被称为变分不等式。

定义48.4.双线性形式a:v×v→r，因此存在一些真正的α>0，

a（v，v）≥αkvk2，所有v∈v

据说是强制性的。

定理48.4是stampacchia定理和lax-milgram定理的特例，当u=v时，其中a是对称双线性形式。一般来说，要证明stampacchia定理，我们需要回忆一下收缩映射定理。

定义48.5.设（e，d）为度量空间。图f:e→e是一个收缩（或收缩映射），如果有一些实数k，如0≤k<1和

d（f（u），f（v））≤kd（u，v）表示所有u，v∈e。

数字k通常被称为lipschitz常数。

第36.10节证明了以下定理；见定理36.54。在许多来源中，也可以在apostol[4]、dixmier[52]或schwartz[146]中找到证据。为了方便读者，我们重述了这个定理。

定理48.5。（收缩映射定理）让（e，d）是一个完整的度量空间。每一个收缩f:e→e都有一个唯一的不动点（即，元素u∈e，使f（u）=u）。

收缩映射定理也称为Banach不动点定理。

定理48.6.形式，和LetContinuous双线性形式（不一定对称），Letj由（Lions–Stampacchia）给出，给定Hilbert空间h∈v，Letv 0是连续线性：v×v→r是

如果a是强制的，那么对于v的每一个非空的、闭的、凸的子集u，都有一个唯一的

u u使得a（u，v u）≥h（v u）对于所有v u.（）

如果a是对称的，那么u∈u是u的唯一元素，因此j（u）=inf j（v）。

Vüu

证据。正如在定义48.3之后所讨论的，在命题47.9中，有一个唯一的连续线性映射a:v→v，这样

a（u，v）=hau，vi表示所有u，v∈v，

在kak=kak=c的情况下，根据Riesz表示定理（命题47.8），存在一个唯一的b∈v，使得h（v）=hb，vi表示所有v∈v。

因此，j可以写成

对于所有v∈v.（1）

因为kak=）kis等于findingak=c，所以我们有kavk≤ku，这样，所有v∈v的akkvk=c kvk。使用（1），不等式（

Hau，v−ui≥hb，v−ui表示所有v∈v。（2）

设ρ>0为稍后确定的常数。则（2）等于

hρb−ρau+u−u，v−ui≤0，对于所有v∈v.（3）

通过投影引理（命题47.5（1）和（2）），（这样3）等于找到u∈u

u=pu（ρb−ρau+u）。（4）

我们得到函数f:v→v的一个固定点，由

f（v）=pu（ρb−ρav+v）。

根据47.6号提案，投影图pu不会增加距离，因此

k f（v1）−f（v2）k≤kv1−v2−ρ（av1−av2）k。

由于a是矫顽力，所以a（v，v）≥αkvk2，

因为a（v，v）=hav，vi我们有

Hav，vi≥αkvk2，对于所有v∈v，（5）

从那以后

Kavk≤c kvk，对于所有v∈v，（6）

我们得到

如果我们选取ρ>0使得ρ<2α/c2，那么

k2=1−2ρα+ρ2c2<1，

然后

k f（v1）−f（v2）k≤k kv1−v2k，（7）

当0≤k<1时，表示u∈u，结束了第一个语句的证明。IFF是一种收缩。根据定理48.5，mapa是alsof，具有唯一的不动点对称性，那么第二个语句只是定理48.4的第一部分。

注：许多物理问题可以用满足某种不等式的未知函数u来表示。

a（u，v−u）≥h（v−u），对于所有v∈u，

对于一些“可接受”函数的集合u，它是闭的和凸的。双线性形式A和线性形式H通常以积分形式给出。上述不等式称为变分不等式。

在u=v的特殊情况下，我们得到了lax-milgram定理。

连续双线性形式（不一定对称），Lettheorem 48.7。（lax-milgram定理）给定希尔伯特空间h∈vv0为连续线性，设a:v×v→r为

形式，并让j

如果a是强制的，这意味着存在一些α>0，这样

a（v，v）≥αkvk2，对于所有v∈v，

48.4。椭圆函数则有一个唯一的u∈v，这样

a（u，v）=h（v）表示所有v∈v。

如果a是对称的，那么u∈v是v的唯一元素，因此j（u）=inf j（v）。

VⅤ

Lax-Milgram定理在求解线性椭圆偏微分方程中起着重要作用；见Brezis[31]。

我们现在考虑各种各样的方法，称为梯度降阶，来求某些函数类型的极小值。

48.4椭圆函数

我们首先定义椭圆函数的概念，它概括了由对称正定矩阵定义的二次函数的概念。椭圆函数很好地适应了本节所描述的迭代方法的类型，并很好地用于分析这些方法的收敛性。

定义48.6.给定希尔伯特空间v，如果函数j:v→r在v上是连续可微的，并且如果有一个常数α>0，那么它被称为椭圆函数。

h jv−ju，v−ui≥αkv−uk2，所有u，v∈v。

下面的命题收集了椭圆函数的性质，这些性质稍后将用于分析各种梯度下降方法的收敛性。

定理48.8。让V成为希尔伯特空间。

(1) 一个椭圆函数j:v→r是严格凸的和强制的。此外，它满足身份

对于所有u，v∈v。

(2) 如果u是希尔伯特空间v的非空凸闭子集，如果j是椭圆函数，那么问题（p）

寻找U

使u∈u和j（u）=inf j（v）v∈u

有独特的解决方案。

(3) 假设集合u是凸的，函数j是椭圆的。那么元素u∈u是问题（p）的解，如果且仅当它满足条件时

h ju，v−ui≥0，对于每个v∈u

一般情况下，或

如果u=v，ju=0

(4) 函数j在v中是二次可微的，是椭圆的，如果且仅当

h 2ju（w），wi≥αkwk2，所有u，w∈v。

证据。（1）由于j是一个C1函数，根据泰勒公式，在m=0的情况下，我们得到了一个积分余数（定理38.25）。

因为j是椭圆的

利用不等式

对于所有u，v∈v，

根据39.9（2）号提案，自

j（v）>j（u）+h ju，v−ui表示所有u，v∈v，v 6=u，

函数j是严格凸的。这是强制性的，因为（使用柯西-施瓦茨）

，

当kvk趋向于＋∞时，项（变为＋∞）。

48.4。椭圆函数

(2) 由于（1）函数j是强制的，根据定理48.2，问题（p）有一个解。由于J是严格凸的，根据定理39.11（2），它有一个唯一的极小值。

(3) 这些只是定理39.11（3，4）的条件。

(4) 如果j是两倍可微的，我们在第38.5节中表明

D

从那以后

d2ju（w，w）=h 2ju（w），wi

dju+θw（w）=h ju+θw，wi dju（w）=h ju，wi，

既然j是椭圆的，对于u，w∈v，我们可以写

相反，假设条件

h 2ju（w），wi≥αkwk2，对于所有u，w∈v

持有。如果我们通过定义函数g:v→r

g（w）=h jw，v−ui=djw（v−u）=dv−uj（w），

其中u和v是v中的固定矢量，那么我们有dgu+θ（v−u）（v−u）=dv−ug（u+θ（v−u））=dv−udv−uj（u+θ（v−u））=d2ju+θ（v−u）（v−u，v−u）

我们可以把泰勒-麦克劳林公式（定理38.24，m=0）应用到g，我们得到

H合资公司−JU，V−Ui=G（V）−G（U）

=dgu+θ（v−u）（v−u）（0<θ<1）

=d2ju+θ（v−u）（v−u，v−u）

=h 2ju+θ（v−u）（v−u），v−ui≥αkv−uk2，

这表明j是椭圆的。

推论48.9。如果j:rn→r是由

（其中a是对称的n×n矩阵，h−，−i是标准欧几里德内积），则j是椭圆iff，a是正定的。

这是定理48.8的结果，因为

h 2ju（w），wi=haw，wi≥λ1 kwk2

式中，λ1是a的最小特征值；见命题16.24（瑞利-里兹，第一卷）。注意，根据命题16.24（瑞利-里兹，第一卷），我们也有以下推论。推论48.10。如果j:rn→r是由

则h 2ju（w），wi≤λn kwk2

式中，λn是a的最大特征值；

以上事实稍后会有用。

同样，给出了在希尔伯特空间V上定义的二次函数j，其中

，

根据定理48.8（4），函数j是椭圆的，如果有一些α>0，那么

h 2ju（v），vi=a（v，v）≥αkvk2，所有v∈v。

这正是定理48.4中使用的假设（α）。

48.5无约束问题的迭代法

现在我们将描述解决无约束最小化问题的方法，即在整个空间v上找到函数j的最小值（或极小值）。这些方法是迭代的，这意味着在给定初始向量u0的情况下，我们构造了一个序列（u k）k≥0，它收敛到函数j的最小u。

关键步骤是从UK定义UK+1，第一个想法是将问题简化为一个简单的问题，即最小化单个（实）变量的函数。为此，我们需要执行两个步骤：

48.5。无约束问题的迭代法

(1) 在英国找到一个下降方向，这是一个非零矢量dk，通常由j在不同点的梯度决定。下降方向dk必须满足h juk，dki<0的不等式。

(2) 精确直线搜索：沿直线通过UK并与dk方向平行，求j函数的最小约束值。这意味着找到一个真正的ρk∈r（取决于UK和Dk），这样

j（uk+ρkdk）=inf j（uk+ρdk）。罗普R

这个问题只有在ρk是唯一的情况下才成功，在这种情况下，我们设置

UK+1=UK+ρkdk。

这个步骤通常被称为行搜索或行最小化，而ρk被称为stepsize参数。见图48.1。

图48.1：设j:r2→r为其图形由粉色表面表示的函数。给定xy平面上的点uk和dk的方向，我们首先计算uk+1，然后计算uk+2。

提案48.11。如果j是形式的二次椭圆函数

，

然后给定dk，在步骤（2）中有一个唯一的ρk解线性搜索。

证据。这是因为，根据48.3号提案，我们

，

由于a（dk，dk）>0（因为j是椭圆的），当导数为零时，ρ的上述函数有一个唯一的极小值，即

ρa（dk，dk）+h juk，dki=0.

由于步骤（2）通常过于昂贵，因此另一种方法是

（3）回溯线搜索：选取两个常数α和β，使0<α<1/2和0<β<1，并设置t=1。给定dk在UK∈dom（j）的下降方向，

而j（uk+tdk）>j（uk）+αth juk，dki不：=βt；ρk=t；uk+1=uk+ρkdk。

由于dk是一个下降方向，我们必须有h j uk，dki<0，因此对于t足够小的条件j（uk+tdk）≤j（uk）+αth juk，dki将保持，搜索将停止。可以看出，出口不等式j（uk+tdk）≤j（uk）+αth juk，dki对所有t∈（0，t0）都适用，对于某些t0>0。因此，回溯线搜索以满足ρk=1或ρk∈（βt0，t0）的步长ρk停止。必须小心，使UK+ρkdk∈dom（j）。更多详情，见Boyd和Vandenberghe[29]（第9.2节）。

我们现在考虑一种最简单的选择下降方向的方法，在V=RN的情况下，即以循环的方式选择坐标轴的方向。这种方法叫做松弛法。

如果我们写信

，

然后，通过自上而下求解以下方程组，根据UK计算Uki+1的分量：

j（uk1+1，uk2，uk3，…，ukn）=inf j（λ，uk2，uk3，…，ukn）λ∈r j（uk1+1，uk2+1，uk3，…，ukn）=inf j（uk1+1，λ，uk3，…，ukn）λ∈r

…

J（UK1+1，…，UKn+1−1，UKn+1）=λinf∈RJ（UK1+1，…，Unk+1−1，λ）。

48.5。无约束问题的迭代法

编写上述系统的另一种更具信息性的方法是定义向量uk；i

英国；0=（UK1，UK2，…，UKN）英国；1=（UK1+1，UK2，…，UKN）

…

英国；I=（UK1+1，…，UKI+1，UKI+1，…，UKN）

…

英国；N=（UK1+1，UK2+1，…，UKN+1）。

注意，UK；0=UK和UK；n=UK+1。那么我们的最小化问题可以写成

j（uk；1）=inf j（uk；0+λe1）λ∈r

…

j（uk；i）=infrj（uk；i−1+λei）λ∈

…

j（uk；n）=λinf∈rj（uk；n−1+λen），

式中，ei表示Rn中的第i个规范基向量。如果j是可微的，那么求最小值的必要条件也足够了，如果j是凸的，那么方向导数djv（ei）都是零，也就是说，h jv，ei i=0 i=0，…，n。

以下关于松弛方法收敛性的结果在Ciarlet[41]中得到证明（第8章，定理8.4.2）。

提案48.12。如果函数j:rn→r为椭圆，则松弛法收敛。

注：命题48.12的证明采用定理48.8。RN的有限维数也起着至关重要的作用。函数j的可微性也是至关重要的。如果j不可微，则可给出方法永久循环的示例；见Ciarlet[41]（第8章，第8.4节）。命题48.12的证明产生了一个关于ku-ukk错误的先验界。如果j是二次函数

其中a是对称正定矩阵，则jv=av−b，因此上述针对UK+1的求解方法成为求解线性系统的高斯-赛德尔法；见第9.3节（第一卷）。

我们现在讨论梯度法。

48.6无约束问题的梯度下降法

这些方法背后的直觉是，如果在每个迭代步骤中差异j（uk）−j（uk+1）尽可能大，迭代方法的收敛性应该更好。为了实现这一点，自然选择下降方向是梯度向量juk的相反方向。这种选择是有理由的，因为我们可以写

和Lim.

如果juk=06，函数j变化的一阶部分在绝对值上以k juk k k w k（由柯西-施瓦兹不等式）为界，如果juk和w共线，则相等。

梯度下降法选择下降方向为dk=−juk，这样我们得到了uk+1=uk−ρk juk，

其中，我们在变量ρk前面放置一个负号，作为下降方向与梯度方向相反的提示；标量ρk应为正值。

选择ρk有四种标准方法：

(1) 具有固定步长参数的梯度法。这是最简单和最便宜的方法，包括对所有迭代使用相同的常数ρk=ρ。

(2) 变步长参数梯度法。在该方法中，参数ρk在迭代过程中根据不同的准则进行调整。

(3) 具有最优步长参数的梯度法，也称欧氏范数的最速下降法。这是方法2的一个版本，其中ρk由以下行搜索确定：

j（uk−ρk juk）=inf j（uk−ρjuk）。

罗普R

只有当上述最小化问题有唯一解时，优化问题才能成功。

(4) 带回溯线搜索的梯度下降法。在该方法中，通过执行回溯线搜索来获得步进参数。

对于具有最优参数的梯度法的收敛性，我们得到了以下有用的结果。

提案48.13。设j:rn→r为椭圆函数。然后采用最优步长参数的梯度法收敛。

48.6。无约束问题的梯度下降法

证据。由于j是椭圆的，根据定理48.8（3），函数j有一个唯一的最小u，其特征是ju=0。我们的目标是证明用最优参数梯度法构造的序列（u k）k≥0从任意初始向量u0开始收敛到u。在不丧失一般性的情况下，我们可以假设所有k的uk+1=6 uk和juk=06，因为否则，该方法将以有限的步骤收敛。

第1步。显示任意两个连续下降方向是正交的，并且

.

设k:r→r为下式给出的函数

⑨k（ρ）=j（uk−ρjuk）。

根据定理48.8（2），由于函数k是严格凸的和强制的，它有一个唯一的最小ρk，它是方程K（ρ）=0的唯一解。按链式法则

⑨0K（ρ）=djuk−ρjuk（−juk）

=−H JUK−ρJUK，JUKI，

既然UK+1=UK−ρK JUK，我们得到

H JUK+1，JUKI=0，

说明两个连续下降方向是正交的。

由于UK+1=UK−ρK JUK，我们假设UK+1=6 UK，我们有ρK=06，我们也得到H JUK+1，UK+1−UKI=0。

根据定理48.8（1）的不等式，我们得到

.

第2步。显示limk7→∞kuk−uk+1K=0。

由步骤1证明的不等式可知，序列（j（u k））k≥0是递减的，且在其下有界（j（u），其中u是j的最小值），因此它收敛，我们得出结论：

lim（j（uk）−j（uk+1））=0，

K7→∞

加上前面的不等式表明

Lim Kuk−UK+1K=0.K7→∞

第3步。展示一下。

使用连续下降方向的正交性，通过柯西-施瓦兹我们

，

以便

.

第4步。显示limk7→∞k jukk=0。

由于序列（j（uk））k≥0是递减的，而功能性j是强制的，因此序列

（在UK的紧致子集上均匀连续）k≥0必须有界。根据假设，推导式rn；这里我们使用的事实是dj是连续的，所以它是有限维的。因此，我们推断每一次

但是通过定义算子范数和使用柯西-施瓦兹不等式

但我们也有，所以

从那以后

然后

，

利用这个事实

，

我们得到

lim k jukk=0.

K7→∞

48.6。无约束问题的梯度下降法

第5步。最后证明了序列（uk）k≥0的收敛性。

因为j是椭圆的，既然j u=0（因为u是j对rn的最小值），我们有

αkuk−uk2≤h juk−ju，uk−ui

=H JUK，英国−Ui

≤K Jukkkuk−英国。

因此，我们得到

，（b）

既然我们展示了

我们发现序列（u k）k≥0收敛于最小值u。

注：与前面的命题一样，有限维假设是至关重要的。证明提供了错误kuk-uk的先验界限。

如果j是椭圆二次函数

，

我们可以用下降方向juk和juk+1的正交性来计算ρk。

实际上，我们有jv=av−b，所以

0=H_juk+1，juki=ha（uk−ρk（auk−b））−b，auk−bi，

会产生

，wk=auk−b=juk。

因此，迭代方法的步骤采用以下形式：

(1) 计算矢量

(2) 计算标量

.

(3) 计算下一个向量uk+1

UK+1=UK−ρkwk。

当给定向量w的aw的计算量较低时，这种方法特别有意义，如果a是稀疏的，则是这种情况。

对于这个方法的一个特殊的例子，我们使用sheuchuk提供的例子，即

如图48.2所示，这个二次椭球在

（2、−2）。为了通过最佳步进尺寸的梯度下降找到这个最小值。

图48.2：椭球体。

参数，我们选择一个起点，saywk=j（−2、−2）=（−12、−8）。请注意，UK=（−2、−2），并计算搜索方向

垂直于适当的椭圆水平曲线；见图48.3。接下来，我们沿着等式图48.4和48.5给出的线执行线搜索。特别是，我们发现−8x+12y=−8并确定ρk。参见

.

这反过来又给了我们新的观点

，

图48.3：水平曲线和相关梯度向量场j（x，y）=（3x+2y−2,2x+6y+8）。

我们沿着梯度方向j（2/25，−46/75）继续这个过程。=

（使用方向向量−224/75112/25对搜索行进行双曲线搜索）。观察wk）=有一个梯度向量，它是perpen j（−2、−2）=（−12−8）8；参见图x+12y。=-

48.5.几何上，该程序对应于平面相交-

2x+8y形成抛物线

f（x）=25/6x 2−2/3xx−24，然后定位/25；见图48.6。在31次迭代之后，这个过程稳定了顶点的坐标，当nf0（x）=0时，即当lize到点（2，−2）时，我们知道这是二次椭球的唯一最小值。

Boyd和Vandenberghe[29]（第9.3.1节）在严格凸假设下证明了梯度法与回溯线搜索的收敛性。关于这种方法和欧几里得范数的最陡下降法的更多细节，可在[29]中找到（第9.3节）。

48.7变步长梯度下降收敛

给出了变步长参数梯度法收敛的充分条件。除了要求j是椭圆函数外，我们在j的梯度上加了一个李普希兹条件，这一次空间v可以是无限维。

提案48.14。设j:v→r为α>0和m>0上定义的连续可微函数，这样

希尔伯特空间v。假设存在两个常量

h jv−ju，v−ui≥αkv−uk2，对于所有u，v∈v，

图48.4：水平曲线和红色搜索线

方向J（−2、−2）=（−12、−8）

以及利普希茨条件

k jv−juk≤m k v−uk适用于所有u，v∈v。

如果存在两个实数a，b∈r，那么

对于所有k≥0，

然后变步长参数梯度法收敛。此外，还有一些常数β>0（取决于α，m，a，b），这样

β<1且k uk−uk≤βk ku0−uk，

式中，u∈m是j的唯一极小值。

证据。根据假设，函数j是椭圆的，所以根据定理48.8（2），它有一个唯一的极小值u，其特征是ju=0。既然UK+1=UK−ρK JUK，我们可以

UK+1−U=（UK−U）−ρkh juk−jui.（）

利用不平等

H JUK−JU，UK−Ui≥αkuk−UK2

和

K JUK−JUK≤M Kuk−UK，

图48.5：让Uk=（−2、−2）。当沿着红色搜索线遍历时，我们寻找绿色垂直梯度向量。这个梯度向量出现在UK+1=（2/25，−46/75）处，它提供了一个最小的ρk，因为它在搜索线上没有非零投影。假设ρk>0，那么

考虑函数

t（ρ）=m2ρ2−2αρ+1。

它是一个抛物线，与y轴相交，y=1，ρ=0，ρ=α/m2的最小值，ρ=2α/m2的值y=1，见图48.7。因此，如果我们选取a、b和ρk，那么

，

我们保证，对于ρ∈[a，b]我们有

t（ρ）1/2=（m2ρ2−2αρ+1）1/2≤（max t（a），t（b））1/2=β<1.

然后通过诱导得到k uk+1−uk≤βk+1 ku0−uk，

这证明了收敛性。

注：在48.14号提案的证明中，V是完整的这一事实起着关键作用。如果j是两倍可微的，假设

k jv−juk≤m k v−uk，所有u，v∈v

图48.6：平面−8x+12y=−8和椭球体交叉点的两个视图。点UK+1是抛物线交点的最小值。

可以表示为

对于Rn上定义的二次椭圆函数，

j（v）=hav，vi−hb，vi，

上限2α/m2可以得到改善。在这种情况下，我们有

jv=av−b，

我们知道我们α=λ1和m=λn做了这个工作，其中，λ1是a的特征值，而λn是a的最大特征值，因此我们可以选择a，b，这样

.

由于UK+1=UK−ρK JUK和JUK=AUK−B，我们有

UK+1−U=（UK−U）−ρK（AUK−AU）=（I−ρKA）（UK−U），

图48.7：用于证明命题48.14的抛物线t（ρ）。

所以我们得到

kuk+1−uk≤ki−ρkak2 kuk−uk。

但是，由于i−ρka是对称矩阵，所以ki−ρkak2是其特征值的最大绝对值，因此ki−ρkak2≤max 1，1−ρkλn。

函数μ（ρ）=max 1−ρλ1，1−ρλn

是一个分段仿射函数，很容易看出，如果我们选取a，b这样

，

然后

最大μ（ρ）≤最大μ（a），μ（b）<1.ρ∈[a，b]

因此，上限2λ1/λ2n可替换为2/λn，后者通常要大得多。ρk的“好”选择是2/（λ1+λn）（与第一个版本的λ1/λ2n相反）。在这种情况下

，

所以我们得到

条件2（a）−1

，

条件2（a）+1

其中cond2（a）=λn/λ1是矩阵a相对于光谱范数的条件数。由此可见，A的条件数越大，方法的收敛速度越慢。这并不奇怪，因为我们已经知道，涉及病态矩阵（条件数较大的矩阵）的线性系统是有问题的，并且容易出现数值不稳定性。解决这个问题的一种方法是使用一种称为预处理的方法。

我们只描述了最基本的梯度下降方法。有许多变体，我们只提到其中的一些方法。

定标方法是以−ρkdk juk为下降方向，其中dk是一些适当选择的对称正定矩阵。

在外推梯度法中，Uk+1由

UK+1=UK−ρK JUK+βK（UK−UK−1）。

另一个选择阶梯大小的规则是阿米乔规则。

这些方法和其他方法在Berstekas[17]中进行了详细讨论。

Boyd和Vandenberghe讨论了除欧几里得规范外各种类型规范的最陡下降方法；见Boyd和Vandenberghe[29]（第9.4节）。这是简要的总结。

48.8任意范数的最陡下降

其目的是使H_juk，dki尽可能地为负。为了使问题合理化，我们必须限制dk的大小，或者用dk的长度来规范化。

让k成为关于rn的任何规范。从第一卷第13.7节回忆起，双重规范的定义如下：

KYKD=SUP HX，Yi。

kx∈r=1N×k

定义48.7.归一化最陡下降方向（相对于标准k k k）是任何单位向量dnsd，k，它达到reals h juk，di kdk=1集的最小值。

根据定义，kdnsd，kk=1。

非标准化最陡下降方向dsd，k定义为

Dsd，k=k Jukkkd Dnsd，k.

可以看出，H JUK、DSD、KI=−（K JUKKD）2；

见Boyd和Vandenberghe[29]（第9.4节）。

最陡下降法（相对于标准k k k）包括以下步骤：给定起点u0∈dom（j）do：

重复

48.8。任意范数的最陡下降

(1) 计算最陡下降方向dsd，k。

(2) 行搜索。执行精确或回溯线搜索以查找ρk。

(3) 更新。UK+1=UK+ρkdsd，k.

直到满足停止标准。

如果k k是` 2-范数，那么我们马上就会看到dsd，k=−juk，因此在这种情况下，该方法与第48.6节（3）和（4）开头定义的欧几里得范数的最陡下降法一致。

如果p是对称正定矩阵，很容易看出kzkp=（z>pz）1/2=是范数。然后可以看出，归一化的最陡下降方向是

，

双范数是，关于k k p的最陡下降方向由dsd，k=−p−1 juk给出。

明智地选择p可以加快梯度下降法的收敛速度；见Boyd和Vandenberghe[29]（第9.4.1节和第9.4.4节）。

如果k k是1-范数，那么可以证明dnsd，k的确定如下：设为

k jukk=（juk）i的任何索引。然后

无穷大

，

式中，ei是第i个规范基向量，以及

.

更多详情，见Boyd和Vandenberghe[29]（第9.4.2节和第9.4.4节）。Boyd和Vandenberghe[29]（第9.4.3节）也表明，对于任何范数k k和任何严格凸函数j，最陡下降法收敛。

梯度下降法设计的主要目标之一是保证收敛因子尽可能小，这意味着该方法收敛速度越快。机器学习一直是找到这种方法的催化剂。Strang[166]中讨论的方法（第六章第4节）包括在梯度中添加动量项。在该方法中，Uk+1和Dk+1由以下方程组确定：

当然，诀窍是选择ρ和β的方式是使收敛因子尽可能小。如果j由二次函数给出，比如（1/2）u>au-b>u，那么

juk+1=auk+1−b，因此我们得到一个线性系统。结果表明，该方法的收敛速度由A的最大和最小特征值决定，Strang在2×2矩阵的情况下讨论了该问题。收敛速度明显加快。

另一种方法称为Nesterov加速。在这种方法中，

UK+1=UK+β（UK−UK−1）−ρJUK+γ（UK−UK−1）、

其中β、ρ、γ为参数。有关详细信息，请参见Strang[166]（第六章第4节）。

LAX还讨论了使用切比雪夫多项式根选择步骤ρk的其他方法；见LAX[110]，第17章，第2-4节。

第40.2节中描述的牛顿方法的一种变体可用于求属于某类严格凸函数的函数的最小值。该方法是对称正定矩阵p诱导范数的特例，即p=2j（x），j在x处的Hessian。

48.9牛顿求最小值的方法

如果j:Ω→r是一个凸函数，定义在Rn的某个开子集Ω上，它是两次可微的，如果它的hessian 2j（x）是所有x∈Ω的对称正定的，那么根据命题39.10（2），函数j是严格凸的。在这种情况下，对于任何x∈Ω，我们得到由上一节中定义的p=2j（x）引起的二次范数，由下式给出

kuk 2j（x）=（u>2j（x）u）1/2.

这个二次范数的最陡下降方向由下式给出

dnt=−（2j（x））−1 jx。

由2j（x）定义的二次范数的dnt范数由下式给出：

定义48.8.给定上述函数j:Ω→r，对于任何x∈Ω，牛顿阶跃dnt由dnt=−（2j（x））−1 jx定义，

牛顿减量λ（x）的定义如下：

.

48.9。牛顿求最小值的方法

注意

h jx，dnti=（jx）>（−（2j（x））−1 jx）=−λ（x）2.

如果jx=06，我们得到λ（x）=06，那么h jx，dnti<0，dnt确实是下降方向。数字h jx，dnti是在回溯行搜索期间显示的常量。

牛顿阶跃和牛顿减量的一个很好的特点是它们是仿射不变量。这意味着，如果t是一个可逆矩阵，如果我们用g（y）=j（ty）定义g，如果与j相关的牛顿阶跃用dj、nt表示，同样，与g相关的牛顿阶跃用dg、nt表示，那么在Boyd和Vandenberghe[29]中（第9.5.1节），dg、nt=t−1dj、nt，

所以x+dj，nt=t（y+dg，nt）。

类似的性质也适用于牛顿减量。

牛顿法由以下步骤组成：给定起点U0∈Dom（J），公差>0 do：

重复

(1) 计算牛顿阶跃和减量dnt，k=−（2j（uk））−1 juk和λ（uk）2=（juk）>（2j（uk））−1 juk。

(2) 停止标准。如果退出。

(3) 行搜索。执行精确或回溯线搜索以查找ρk。

(4) 更新。UK+1=UK+ρkdnt，k.

请注意，这基本上是第48.8节中使用牛顿步进作为搜索方向的下降程序，但在计算搜索方向而不是更新后（非常小的差异）检查停止标准。

Boyd和Vandenberghe[29]对牛顿方法的收敛性进行了深入分析（第9.5.3节）。该分析是在以下假设下进行的：

(1) 函数j:Ω→r是一个凸函数，定义在Rn的某个开子集Ω上，它是两次可微的，其hessian 2j（x）对所有x∈Ω都是对称正定的。这意味着有两个常数m>0和m>0，因此对于所有x∈Ω，这意味着2j（x）的特征值属于

至[m，m]。

(2) Hessian是Lipschitzian，这意味着有一些l≥0，这样

对于所有x，y∈Ω。

结果表明，牛顿方法的迭代分为两个阶段，取决于k jukk2≥η或k juk2<η，其中，η是一个依赖于m，l的数，以及在回溯线搜索中使用的常数α，且η≤m2/l。

(1) 第一阶段，称为阻尼牛顿阶段，发生时k jukkk2≥η。在这个阶段，程序可以选择一个步长ρk=t<1，并且有一些常数γ>0，这样

J（Uk+1）−J（Uk）≤−γ。

(2) 第二阶段，称为正交收敛阶段或纯牛顿阶段，发生时k jukkk2<η。在这个阶段，总是选择步长ρk=t=1，我们已经

.（1）

如果用p表示f的最小值，那么阻尼牛顿步数最多为

.

方程（1）和η≤m2/l的事实表明，如果k jukkk2<η，那么

ε。通过归纳，我们得出

，（2）

因此（由于η≤m2/l和k jukkk2<η，我们得到（l/m2）k jukkk2<（l/m2）η≤1），所以

（3）

Boyd和Vandenberghe[29]中（第9.1.2节）表明，假设意味着

.

因此，通过（3），我们

.（4）

方程（4）表明，四次收敛阶段的收敛速度非常快。如果我们让

，

48.9。牛顿求最小值的方法，即方程（4），意味着我们必须在不超过

迭代。“对数”这个词在变为零时增长得非常缓慢，实际上，它可以被视为常量，比如说五次或六次（六次迭代的精度大约为

总之，求j的最小值所需的牛顿迭代次数近似为

.

Boyd和Vandenberghe[29]（第9.5.4节）中给出了牛顿方法的应用实例以及对其效率的进一步讨论。基本上，牛顿方法比梯度法或最陡下降法收敛速度更快。它的主要缺点是形成和存储黑森方程的成本，以及计算牛顿阶跃的成本，这需要求解一个线性系统。

上述牛顿法收敛性分析存在两个主要缺点。第一个是实践性的。复杂度估计涉及到常数m、m和l，这在实践中几乎是未知的。因此，所需步骤的数量上的界限几乎从未具体知道。

第二个缺点是虽然牛顿方法本身是仿射不变量，但收敛性的分析很大程度上取决于坐标系的选择。如果坐标系改变，常数m，m，l也会改变。这可以被视为一个美学问题，但如果能给出一个独立于仿射坐标变化的收敛性分析，那就更好了。

Nesterov和Nemirovski在函数上发现了一个允许仿射变收敛分析的条件。不幸的是，这种被称为自我和谐的特性并不是很直观。

定义48.9.在r上定义的（部分）凸函数f是自协和的，如果

| f00（x）≤2（f00（x））3/2表示所有x∈r。

在RN上定义的（部分）凸函数f是自协和的，如果对于每一个非零v∈RN和所有x∈RN，函数t 7→j（x+tv）是自协和的。

由于f000=0，仿射函数和凸二次函数具有明显的自协和性。有许多更有趣的自协和函数，例如函数x 7→−logdet（x），其中x是对称正定矩阵。

Boyd和Vandenberghe[29]（第9.6节）广泛讨论了自洽性。自协和的要点是，对于一类严格凸的自协和函数，可以给出一个坐标系不变收敛的证明。Boyd和Vandenberghe[29]中给出了该证明（第9.6.4节）。给定一个起始值u0，我们假设子级集x∈rn j（x）≤j（u0）是闭合的，j在下面是有界的。然后有两个参数η和γ，但仅取决于行搜索中涉及的参数α、β，这样：

(1) 如果λ（uk）>η，则

J（Uk+1）−J（Uk）≤−γ。

(2) 如果λ（uk）≤η，则回溯线搜索选择t=1，我们得到

2λ（Uk+1）≤（2λ（Uk））2.

因此，对于所有的`≥k，我们有

.

最后，最多可达到精度>0

迭代，其中α和β是行搜索中涉及的常量。这个界限显然独立于所选的坐标系。

与直觉相反，由梯度的对立面给出的下降方向dk=−juk并不总是最佳的。在下一节中，我们将看到如何选择更好的方向；这是共轭梯度的方法。

48.10无约束问题的共轭梯度法

由Hestenes和Stiefel（1952）提出的共轭梯度法是一种适用于椭圆二次函数j:rn→r的梯度下降法，由

，

其中a是n×n对称正定矩阵。虽然它是一种迭代方法，但它最多只需要N个步骤就可以结束。

与往常一样，共轭梯度法从一些任意的初始向量u0开始，然后通过一系列迭代步骤进行，生成（更好和更好）最优向量u的近似值uk最小化j。在迭代步骤中，需要确定两个向量：

(1) 下降方向dk。

(2) 下一个近似值UK+1。要找到UK+1，我们需要找到步长ρk>0，然后UK+1=UK−ρkdk。

通常情况下，通过沿dk方向执行线搜索来找到ρk，即我们将ρk作为实数，从而最小化函数ρ7→j（uk-ρdk）。

我们在命题48.13中看到，在最优步长参数的梯度法执行过程中，任何两个连续下降方向都是正交的。共轭梯度法的一个新的扭曲是，在给定u0，u1，…，uk的情况下，得到下一个近似值uk+1作为问题的解，该问题的解是在仿射子空间uk+gk上最小化j，其中gk是由梯度所跨越的rn的子空间。

ju0，ju1，…，juk.

我们可以假设ju=06代表=0，…，k，因为该方法在juk=0时终止。先验子空间gk的维数≤k+1，但我们可以看到它实际上有维数k+1。然后我们有了

，

我们的最小化问题是找到UK+1这样

UK+1∈UK+GK和J（UK+1）=∈JV∈UK+GKJ（V）。

在具有最佳步长参数的梯度法中，下降方向dk与梯度_juk成正比，但在共轭梯度法中，dk等于由dk-1的某个倍数校正的_juk。

共轭梯度法优于具有最佳步长参数的梯度法，原因如下：

(a) 梯度jui和juj对于所有i，j都是正交的，其中0≤i<j≤k。这意味着如果jui=06对于i=0，…，k，那么向量jui是线性无关的，因此该方法最多停止n个步骤。

(b) 如果我们写∆=u+1−u=−ρd，共轭梯度法的第二个显著事实是，向量∆满足以下条件：

ha∆，∆i i=0 0≤i<≤k。

向量∆和∆i被称为相对于矩阵A（或A-共轭）的共轭。因此，如果∆=06代表=0，…，k，那么向量∆`是线性无关的。

(c) 从dk计算dk+1和计算ρk有一个简单的公式。

我们现在证明上述事实。我们从（a）开始。

提案48.15。假设jui=06，对于i=0，…，k。那么最小化问题，找到uk+1，这样

UK+1∈UK+GK和，

有一个独特的解决方案，梯度jui和juj对所有i，j和

0≤i<j≤k。

证据。仿射空间u+g是闭的凸的，由于j是二次椭圆函数，它是强制的严格凸的，因此根据定理48.8（2），它在u+g中有一个唯一的极小值。这个最小u+1也是问题的最小值，找到u+1这样

u+1∈u+g和j（u+1）=inf j（u+v），v∈g

既然g是向量空间，根据定理39.8，我们必须

dju（w）=0表示所有w∈g，

那就是

h ju，wi=0表示所有w∈g。

由于g’的范围是（ju0，ju1，…，ju`），我们得到

h ju，juji=0，0≤j<，

既然这个值为`=0，…，k，我们得到

h jui，juji=0，0≤i<j≤k，

这显示了命题的第二部分。

作为命题48.15的推论，如果jui=06代表i=0，…，k，那么向量jui是线性无关的，gk的维数为k+1。因此，共轭梯度法的终止步骤最多为n步。下面是一个问题的例子，对于这个问题，具有最佳步长参数的梯度下降不会在有限的步数内收敛。例48.1。设j:r2→r为

，

其中0<α1<α2。J的最小值达到（0,0）。除非初始向量）具有等于0的性质，否则我们认为具有最佳步长参数的梯度下降不会在有限步数内收敛。注意

.

因此，在给定UK的情况下，寻找ρk和UK+1的线搜索得到UK+1=（0,0），如果存在一些ρ∈r，那么

而且。

因为α1=6α2，所以只有当其中一个=0时才有可能。刚才给出的公式

提案48.14收益率

，

这意味着如果=0和=0，那么=0和=0，那么该方法将永远从任何初始向量运行），这样=0和，

我们现在证明（b）。

提案48.16。假设jui=06，对于i=0，…，k，并让∆=u+1−u，对于=0，…，k。然后∆=06，对于=0，…，k，和

ha∆，∆i i=0，0≤i<≤k。

矢量∆0，…，∆k是线性无关的。证据。因为j是二次函数，我们有

jv+w=a（v+w）−b=av−b+aw=jv+aw.

接下来是

ju+1=ju+∆=ju+a∆，0≤≤k.（1）

根据48.15号提案，自

h jui，juji=0，0≤i<j≤k，

我们得到

0=h ju+1，jui=k juk2+ha∆，jui，=0，…，k，

根据假设jui=06，i=0，…，k，我们推断

∆=06，=0，…，K.

如果k≥1，对于i=0，…，-1和≤k，我们也有

0=h ju+1，juii=h ju，juii+ha∆，juii=ha∆，juii.

由于∆j=uj+1−uj∈gj和gj的范围是（ju0，ju1，juj），我们得到

ha∆，∆ji=0，0≤j<≤k。

对于命题的最后一个陈述，让w0，w1，…，wk是任意k+1非零向量，这样

hawi，wji=0，0≤i<j≤k。

我们认为w0，w1，…，wk是线性无关的。

如果我们有一个线性相关性=0，那么我们有

.

由于a是对称正定的（因为j是二次椭圆函数），wj=06，所以j=0，…，k必须有λj=0，因此向量w0，w1，…，wk是线性无关的。

评论：

(1) 由于a是对称正定的，双线性映射（u，v）7→hau，vi是RN上的内积h−、−ia。因此，两个矢量u，v相对于矩阵a（或a-共轭）是共轭的，这意味着hau，vi=0，iff u和v相对于内积h−、−ia是正交的。

(2) 通过选择下降方向为−JUK，最优步长参数的梯度下降法将水平集U J（U）=J（UK）视为球体。共轭梯度法更为精细，通过共轭方向的概念，考虑了水平集u j（u）=j（uk）的“几何”。

(3) 共轭方向的概念起源于射影二次曲线和四次曲线理论，其中a是2×2或3×3矩阵，u和v是共轭iff u>av=0。

(4) 术语共轭梯度有些误导。共轭方向不是梯度，而是下降方向。

通过定义向量∆=u+1−u`，我们可以写

`

∆=xδi jui，0≤`≤k.（2）

i＝0

以矩阵形式，我们可以写

，

这意味着δ`=06代表=0，…，k。

鉴于上述事实，由于∆和d是共线的，因此可以方便地将下降方向d写为

“1”

d=xλ i jui+ju，0≤≤k.（3）

i＝0

我们的下一个目标是计算Uk+1，假设系数λk i已知为i=0，…，k，然后找到λki的简单公式。问题归结为找到ρk，这样

j（uk−ρkdk）=inf j（uk−ρdk），ρ∈r

然后Uk+1=Uk−ρkdk。实际上，2），因为

，

我们一定有

和。（4）

值得注意的是，系数λki和下降方向dk可以使用以下公式轻松计算。

提案48.17。假设jui=06代表i=0，…，k。如果我们写

“1”

d=xλ i jui+ju，0≤≤k，

i＝0

然后我们有了

证据。由于（4），我们有∆k=δk k kkdk，δkk=06，（根据命题48.16），我们有

ha∆，∆i i=0，0≤i<≤k。

通过（1），我们得到ju+1=ju+a∆`，由于a是对称矩阵，我们得到

0=hadk，∆i=hdk，a∆ i=hdk，ju+1−jui，

对于`=0，…，K−1。自从

K—1

dk=xλki jui+juk，

i＝0

我们有

.

由于根据命题48.15，梯度jui是成对正交的，因此上述方程得出

，

简单的诱导产生

.

因此，使用（3）我们

！

这就是证据的结论。

它还需要计算ρk，这是直线搜索的解。

j（uk−ρkdk）=inf j（uk−ρdk）。罗普R

因为j是二次函数，所以留给读者的基本计算表明，要最小化的函数是

，

当其导数为零时，得到其极小值，即：

.（5）

总之，共轭梯度法求椭圆二次函数的最小u

通过计算矢量U1，d1，…，uk−1，dk−1，uk的序列，从任意矢量U0开始，用d0=ju0。

如果ju0=0，则算法以u=u0终止。否则，对于k≥0，假设jui=06，对于i=1，…，k，计算

.

如果juk+1=0，那么algorihm以u=uk+1终止。

如前所示，该算法在最多n次迭代中终止。

例48.2。让我们以第48.6节的例子为例，应用共轭梯度法。回想一下

注意jv=（3x+2y−2,2x+6y+8）

通过设置初始化过程

U0=（−2、−2），D0=JU0=（−12、−8）

步骤1涉及计算

观察到ρ0和u1与具有最佳步长参数的梯度下降情况完全相同。差异在于d1的计算。正如我们将看到的，这种变化将在收敛到唯一最小U=（2，−2）时产生巨大的差异。我们继续使用共轭梯度法，并将步骤2计算为

由于ju2=0，该过程分两步结束，而不是使用最佳步长参数进行梯度下降所需的31步。

Hestenes和Stiefel认识到，方程（6）可以通过在一个向量（即dk）上只对矩阵A进行一次评估，从而提高计算效率。其理念是感应式计算UK。

由于（1）和（4），我们得到了ju+1=ju+a∆=ju−ρkadk，梯度ju`+1可以迭代计算：

j0=au0−b

ju+1=ju−ρkadk.

从48.17号提案开始

由于dk−1是梯度的线性组合jui，i=0，…，k−1，它们都是与juk正交的，我们有

.

习惯上引入术语Rk定义为

JUK=AUK−B（7）

称之为剩余。共轭梯度法包括以下步骤。我们从任何向量u0开始初始化该方法，并设置

D0=R0=AU0−B。

主要迭代步骤为（k≥0）：

.

注意，有些作者将剩余Rk定义为Rk=b−auk，下降方向dk定义为−dk。在这种情况下，第二个方程变成

UK+1=UK+ρkdk。

由于d0=r0，方程式

Rk+1=Rk−ρkadk dk+1=Rk+1−βk+1dk

通过归纳，暗示子空间gk的跨度为（r0，r1，…，rk），而（d0，d1，…，dk）的跨度为

（R0，AR0，A2R0，…，AKR0）。

这样的子空间称为krylov子空间。

如果我们将误差Ek定义为Ek=Uk−U，那么e0=U0−U和ae0=au0−au=au0−b=d0=r0，然后因为

UK+1=UK−ρkdk

我们看到Ek+1=Ek−ρkdk。

由于dk属于（r0，ar0，a2r0，…，akr0）和r0=ae0所跨越的子空间，我们看到dk属于（ae0，a2e0，a3e0，…，ak+1e0）所跨越的子空间，然后通过归纳，我们看到ek+1属于（e0，ae0，a2e0，a3e0，…，ak+1e0）所跨越的子空间。这意味着存在一个次数≤k的多项式pk，使得pk（0）=1和

Ek=pk（a）e0.

这是一个重要的事实，因为它允许对共轭梯度法的收敛性进行分析；见Trefethen和Bau[171]（第38课）。因此，由于a是对称正定的，我们知道hu，via=hav，ui是rn上的内积，其相关范数用kvka表示。然后观察，如果e（v）=v−u，则

KE（V）K2A=哈弗−Au，V−Ui

=hav，vi−2hau，vi+hau，ui

=hav，vi−2hb，vi+hb，ui=2j（v）+hb，ui。

由此可知，V=UK使UK−1+GK−1上的Ke（V）kA最小化，因为UK将UK−1+GK−1上的J最小化。因为k=pk（a）e0对于某些多项式pk的次数≤k，这样pk（0）=1，如果我们让pk是次数≤k的多项式p（t）的集合，这样p（0）=1，那么我们有

kekka=pinf∈pk kp（a）e0ka。

因为A是对称正定矩阵，它有实正特征值λ1，…，λn，并且有一个特征向量h1，…，hn的正交基，所以如果我们写。然后我们有了

和

.

这些方程意味着

.

可以看出，共轭梯度法需要n3加，n3乘，和

2n个分区。

理论上，这比Cholesky方法所要求的基本操作数量要差。尽管共轭梯度法似乎不是全矩阵的最佳方法，但它通常优于稀疏矩阵的其他方法。其原因是矩阵A只出现在矢量ADK的计算中。如果矩阵A是带状的（例如，三对角），计算ADK是非常便宜的，不需要存储整个矩阵A，在这种情况下，共轭梯度法是快速的。此外，尽管理论上可能需要最多n次迭代，但在实践中，在迭代次数较少的情况下可能会发生收敛。

利用不等式

，

通过选择p作为移位的切比雪夫多项式，可以证明

，

式中，κ=cond2（a）；见Trefethen和Bau[171]（第38课，定理38.5）。因此，共轭梯度法的收敛速度由比值决定。

磷

条件2（a）−1 p，条件2（a）+1

式中，cond2（a）=λn/λ1是矩阵a的条件数，由于a是正定的，因此λ1是其最小特征值，而λn是其最大特征值。

上述事实导致预处理过程，该方法包括用“等效”矩阵替换线性系统ax=b的矩阵，例如m−1a（因为m是可逆的，系统ax=b等于系统m−1ax=m−1b），其中m的选择使m−1a iS仍然是对称正定的，其条件数小于A；见Trefethen和Bau[171]（第40讲）和Demmel[49]（第6.6.5节）。

共轭梯度法可以推广到非二次函数。阶梯尺寸参数ρk仍由线搜索确定，该线搜索包括查找ρk，以便

j（uk−ρkdk）=inf j（uk−ρdk）。罗普R

这比在二次型情况下要困难得多，而且一般不能保证ρk是唯一的，因此需要一些选择ρk的标准。然后

UK+1=UK−ρkdk，

下一个下降方向可以通过两种方式选择：

(1) （波拉克-里比）

，

(2) （弗莱彻-里夫斯）

.

连续梯度不再是正交的，因此这些方法可能永远运行。有各种充分的收敛准则。实际上，polak–ribi’ere方法收敛得更快。不再保证这些方法收敛到全局最小值。

48.11约束优化的梯度投影法

我们现在考虑在希尔伯特空间v的非空的凸的闭子集u上求凸函数j:v→r的最小值的问题。根据定理39.11（3），函数j在u∈u iff处有一个最小值。

dju（v-u）≥0，所有v∈u，

可以表示为

h ju，v−ui≥0，对于所有v∈u。

另一方面，通过投影引理（命题47.5），向量u∈u是元素w∈v对u的投影的条件是

所有v∈u的hu−w，v−ui≥0。

这些条件显然是相似的，我们可以使这个类比更加精确，如下所示。如果pu:v→u是u上的投影图，我们有以下等价链：

u∈u和j（u）=vinf∈u j（v）iff u∈u和h ju，v−ui≥0，对于每个v∈u，iff

u∈u和hu−（u−ρju），对于每v∈u和每ρ>0，v−ui≥0，iff u=pu（u−ρju），对于每ρ>0。

换句话说，对于每一个ρ>0，u∈v是函数g:v→u的不动点，由

g（v）=pu（v-ρjv）。

48.11.约束优化的梯度投影

以上建议用连续逼近法求收缩映射不动点的u，即给定任意初始u0∈v来定义序列。

（uk）k≥0，使得uk+1=pu（uk−ρk juk），

其中参数ρk>0在每个步骤中选择。此方法称为带可变StepSize参数的ProjectedGradient方法。如果u=v，那么这就是变步长的梯度法。关于该方法的收敛性，我们得到如下结果。

提案48.18。设j:v→r为希尔伯特空间v上定义的一个连续可微函数，设u为v的非空、凸、闭子集。假设存在两个常数α>0和m>0，这样

h jv−ju，v−ui≥αkv−uk2，对于所有u，v∈v，

和

k jv−juk≤m k v−uk适用于所有u，v∈v。

如果有两个真正的修女a，b∈r这样

对于所有k≥0，

然后将变步长参数投影梯度法收敛。此外，还有一些常数β>0（取决于α，m，a，b），这样

β<1且k uk−uk≤βk ku0−uk，

式中，u∈m是j的唯一极小值。

证据。对于每一个ρk≥0，定义函数gk:v→u

gk（v）=pu（v-ρk jv）。

根据命题47.6，投影图pu有Lipschitz常数1，因此利用假设在命题中存在的不等式，我们得到

如在命题48.14的证明中，我们知道，如果a和b满足条件0<a≤

，然后有一些β，这样

所有k≥0为1。

由于最小点u∈u是所有k的gk的不动点，通过让v1=uk和v2=u，我们得到

k u k+1−uk=k gk（uk）−gk（u）k≤βkuk−uk，

证明了序列（uk）k≥0的收敛性。

对于椭圆二次函数

在RN上定义，只要选择了a、b和ρk，就可以立即对命题48.14证明后的推理进行调整，以证明收敛发生。

.

在理论上，命题48.18给出了投影梯度法收敛性的保证。不幸的是，由于有效地计算投影pu（v）通常是不可能的，所以命题48.18的实际应用范围相当有限。一个例外是u是闭合区间的积（其中ai=−∞或bi=+∞是可能的）。在这种情况下，不难证明

尤其是，如果

如果

是RN上的椭圆二次函数。那么向量）是根据）给出的。

48.12约束优化的惩罚方法

在v=rn的情况下，处理约束优化的另一种方法是通过添加惩罚函数将域u合并到目标函数j中。

48.12条。约束优化的惩罚方法

定义48.10.给定RN的非空闭凸子集u，如果ψ是凸的且连续的且满足以下条件，则函数ψ：rn→r称为u的惩罚函数：

ψ（v）≥0，对于所有v∈rn，ψ（v）=0 iff v∈u。

下面的命题表明，惩罚函数的使用将一个约束优化问题简化为一系列无约束优化问题。

提案48.19。设j:rn→r为连续的、强制的、严格的凸函数，u为rn的非空的、凸的、闭的子集，ψ：rn→r为u的惩罚函数，设为

对于所有的v∈rn。

然后，对于每个人，都存在一个独特的元素，这样

.

此外，如果u∈u是j在u上的唯一极小值，那么j（u）=infv∈u j（v），那么

证据。观察到，既然j是强制的，既然ψ（v）≥0对于所有v∈rn，并且，我们已经）对于所有的也是强制的。因为j是严格凸的，并且是凸的，所以立即检查它也是严格凸的。然后通过48.1命题（即J和J是严格凸的事实），J有一个唯一的极小值u∈u，J有一个唯一的极小值。

因为ψ（u）=0 iff u∈u，而ψ（v）≥0对于所有v∈rn，我们有），并且因为u是j的极小值，所以我们得到

，

也就是说，

.（1）

因为j是强制的，所以族是有界的。通过紧致性（因为我们在rn中），存在一个子序列（带lim）=0和一些元素u0∈rn，这样

.

根据（1）中证明的不等式和j的连续性，我们得出：

.（2）

根据）和（1）的定义，我们

，

由于序列（收敛，数字）是独立于i的有界的，因此，由于lim=0，并且由于函数ψ是连续的，我们有

，

由此可见，u0∈u，因为（2）我们有j（u0）≤j（u），而且既然u，u0∈u和u都是j在u上的唯一极小值，我们必须有u0=u，所以u0是j在u上的唯一极小值，但是整个家族（收敛到u，因为我们可以对eve使用与上述相同的论据序列号（.

注意凸函数ψ：rn→r是自动连续的，因此连续性假设是多余的。

作为48.19号提案的一个应用，如果u

u=v∈rn _i（v）≤0，i=1，…，m，

式中，式中，函数i:rn→r为凸函数，取ψ为下式给出的函数。

.

在实践中，罚函数法的适用性受到有效构造“好”函数ψ（如可微函数）的困难的限制。注意，在上述示例中，函数ψ不可修改。更好的惩罚功能是

.

另一种处理约束优化问题的方法是使用对偶性。第49章对这种方法进行了研究。

48.13总结

本章的主要概念和结果如下：

• 最小化，最小化。

• 强制功能。

48.13条。总结

• 二次函数的极小值。

• 狮子和雄蕊的定理。

• lax–milgram定理。

• 椭圆函数。

• 下降方向，精确线搜索，回溯线搜索。

• 放松的方法。

• 梯度下降。

• 具有固定步长参数的梯度下降法。

• 变步长参数梯度下降法。

• 欧几里得范数的最速下降法。

• 带回溯线搜索的梯度下降法。

• 标准化最陡下降方向。

• 不正常的最陡下降方向。

• 最陡下降法（相对于标准k k k）。

• 动量项。

• 牛顿方法。

• 牛顿台阶。

• 牛顿减量。

• 阻尼牛顿相位。

• 四次收敛相位。

• 自协和函数。

• 共轭梯度法。

• 投影梯度法。

• 处罚方法。