第四十九章 非线性优化导论 在第39章中，我们研究了确定赋范向量空间e的某些开子集Ω上的函数j:Ω→r定义u在由等式约束定义的子集Ω中何时具有局部极值的问题，即 u=x∈Ω_i（x）=0，1≤i≤m， 式中，函数i:Ω→r是连续的（通常是可微的）。定理39.3给出了拉格朗日乘子的一个必要条件。在第39.3节中，我们假定u是Ω的凸子集；然后定理39.8给出了一个必要的条件，即如果存在dju，函数j:Ω→r对于u具有局部最小值，即 dju（v−u）≥0，所有v∈u。 我们的第一个目标是找到一个必要的标准，使函数j:Ω→r在一个子集u上有一个最小值，即使这个子集不是凸的。这可以通过在点u∈u引入“切锥”的概念来实现。 我们的方法非常受Ciarlet[41]的启发，因为我们发现它是更直接的方法之一，而且它足够通用，可以容纳Hilbert空间。非线性优化和凸优化的领域非常广泛，关于这一问题的书籍很多。我们推荐（按字母顺序）Bertsekas[16、17、18]、Bertsekas、Nedi’c和 Ozdaglar[19]、Boyd和Vandenberghe[29]、Luenberger[113]和Luenberger和Ye[114]。 49.1可行方向的锥体 设v为赋范向量空间，设u为v的非空子集。对于任意点u∈u，考虑任意收敛序列（u k）k≥0的向量uk∈u以u为极限，其中 一千五百八十一 Uk=6u，所有k≥0，看“单位和弦”的顺序。 . 这个序列可以永远振荡，也可以有一个极限，一个单位向量w∈v。在 b第二种情况下，所有λ>0的非零矢量λw都属于称为 B可行的方向在U。首先，我们需要定义圆锥的概念。 定义49.1.给定（实）向量空间v，非空子集c v是顶点为0的锥（简称为锥），如果对于任意v∈v，如果v∈c，那么对于所有λ>0（λ∈r），则为λv∈c。对于任何u∈v，具有顶点u的圆锥体是形式u+c=u+v v∈c的任何非空子集，其中c是具有顶点0的圆锥体；见图49.1。
图49.1：设c为通过平面z=1中（0,0,1）的大胆橙色曲线确定的圆锥体。那么u+c，其中u=（0.25,0.5,0.5），是c通过向量u的仿射平移。 观察顶点为0（或u）的圆锥体不一定是凸形的，0不一定属于c（或。u不一定属于u+c（尽管在可行方向c（u）的圆锥体中，我们有0∈c（u））。作为圆锥的条件仅表明，如果非零矢量V属于C，则开放射线λvλ>0（resp.仿射开射线u+λvλ>0）也属于c。
定义49.2.设v为赋范向量空间，设u为v的非空子集。对于任意点u∈u，在u处可行方向的锥c（u）是0的并集，并且所有非零向量w∈v的集合存在一些收敛序列（u k）k≥0的向量，因此 （1）所有k≥0时，Uk∈U和Uk=6u，limk7→∞Uk=U。 ，w=0.6 条件（2）也可以表示为：有一个序列（δk）k≥0的向量δk∈v，这样 . 图49.2说明了w在c（u）中的构造。
图49.2：设u为r2中带紫红色点u∈u的粉红色区域。对于u中收敛到u的点的任何序列（u k）k≥0，形成和弦uk−u，并以极限构造红色矢量w。 显然，U处可行方向的锥c（u）是一个顶点为0的锥，U+c（u）是一个顶点为U的锥。显然，在U上有条件意味着c（u）是一个凸锥是可取的。这些条件将在稍后给出。 观察U处可行方向的锥c（u）包含U到U中所有曲线γ的U处速度矢量。如果γ：（-1,1）→U是γ（0）=U的曲线，如果γ0（u）=06存在，则U中有一个序列（u k）k≥0的矢量收敛到U，如定义49.2所示，其中对于reals tk>0的某些序列（tk）k≥0，Uk=γ（tk），因此limk→∞7 tk=0，因此 ， 我们得到 . 有关R2中本段的说明，请参见图49.3。
图49.3：设u为r2中的紫色区域，u为u边界上的指定点。图（i）说明了通过u的两条曲线和两个序列（u k）k≥0收敛到u。弦Uk−u的极限对应于适当曲线的切线向量。图（ii.）说明了可行方向的半平面c（u）。 例49.1。在v=r2中，让和由下式给出 _（u1，u2）=−u1−u2（u1，u2）=u1（u21+u22）−（u21−u22）、 让 u=（u1，u2）∈r2_1（u1，u2）≤0，_2（u1，u2）≤0。 区域U如图49.4所示，并以方程_1（u1，u2）=0给出的曲线为界，即−u1−u2=0，坡度线−1穿过原点，曲线由方程给出）=0，节点立方体穿过原点。我们 通过让u2=tu1得到曲线的参数定义，我们发现 . t处的切向量由（）给出，其中
和 . 节点立方体通过t=±1的原点，对于t=−1，切向量是（1、−1），对于t=1，切向量是（−1、−1）。原点可行方向C（0）的锥体由下式给出： c（0）=（u1，u2）∈r2 u1+u2≥0，u1≥u2。 这不是凸锥，因为它包含由线u2=u1和u2=−u1所描绘的扇形，也包含由矢量（−1,1）支持的光线。 可行方向锥的两个重要性质如下所示。 提案49.1.设u为赋范向量空间v的任何非空子集。 (1) 对于任意u∈u，在u处可行方向的锥c（u）是闭合的。 (2) 设j:Ω→r为在包含u的开子集Ω上定义的函数。如果j在点u∈u处对集u具有局部最小值，并且如果存在于u处，则 对于所有v∈u+c（u）。 证据。（1）让（w n）n≥0是收敛到极限w∈v的向量序列wn∈c（u）。我们可以假设w=06，因为0∈c（u）的定义，因此我们也可以假设w n=06对于所有n≥0。根据定义，对于每n≥0，在v和一些wn=06中有一个向量序列（unk）k≥0，这样 (1) 所有k≥0时，unk∈u和unk=6u，limk7→∞unk=u。 （一） （二） 图49.4：图（i）将u表示为阴影灰色区域，该区域位于直线y=-x和节点立方体之间。图（ii.）显示了可行方向的圆锥体c（0），作为绿松石三角形圆锥体和绿松石的结合，即定向射线（−1,1）。 (2) 有一个序列（δkn）k≥0的向量δkn∈v，这样 . 设为实数0的序列，这样lim=0（例如， +1））。由于每个固定n的序列（unk）和（δkn）的收敛性， 存在一个整数k（n），这样 . 考虑序列（.我们有 ，全部 我们可以写 . 由于limk7→∞（wn/kwnk）=w/kwk，我们得出w∈c（u）。见图49.5。 （2）设w=v−u为圆锥体c（u）中的任何非零矢量，设（u k）k≥0为u−u中的矢量序列，以便
图49.5：设u为R2中的薄荷绿区域，其中u=（0,0）。设（w n）n≥0为沿上虚线收敛到w的向量（点）序列，根据橙色虚线纵曲线，选择合适的向量（点），在u中构造出深绿色曲线，该曲线通过u，在u处具有相切向量成比例。到W (1) limk7→∞UK=U. (2) 有一个序列（δk）k≥0的向量δk∈v，这样 ， (3) j（u）≤j（u k），所有k≥0。 既然j在u上是可微的，我们有 ，（） 对于某些序列（比如lim=0.因为是线性和连续的， ， （）意味着 ， 具有 . 因为是连续的，所以我们得到了limk7→∞ηk=0。但是，如果0，那么对于k足够大，表达式将是负数，并且由于uk=6u，表达式（）也将是负数，这是一个矛盾。 从现在开始，我们假设u是由一组不等式定义的，也就是说 u=x∈Ω_i（x）≤0，1≤i≤m， 式中，函数i:Ω→r i iare连续（且通常可微分）。正如我们前面所解释的（x）=0被视为两个不等式的结合，一个等式约束 _i（x）≤0和−_i（x）≤0。稍后我们将看到，当函数i是凸的时，因为 −目前我们不会。_i不一定是凸的，希望单独处理平等约束，但 49.2有效约束和合格约束 我们的下一个目标是找到Conethis的充分条件，我们假设函数c（u）是凸的，对于任何u∈u，对于i，函数c（u）在u是可微的，结果是约束 _i，重要的是那些_i（u）=0的约束，即紧的约束，或者如我们所说，是活动的。 定义49.3.给定m函数，在某向量空间v的某个开子集oz上定义了i:oz→r，让u是由 u=x∈Ω_i（x）≤0，1≤i≤m。 对于任何u∈u，如果i（u）=0，则称约束i在u处处于活动状态，否则在u处处于非活动状态，如果i（u）<0。 如果在u处有一个约束，则这对应于u位于u的一块边界上，该边界由一些方程_i（u）=0确定；见图49.6。定义49.4.对于任何u∈u，用 u=x∈Ω_i（x）≤0，1≤i≤m， 我们将i（u）定义为一组索引 i（u）=i 1，…，m _i（u）=0 约束处于活动状态。我们将集合c（u）定义为 c（u）=v∈v（i）u（v）≤0，i∈i（u）。由于每个（i）u是一个线性形式，子集
是通过原点的半空间的交集，所以它是一个凸集，显然它是一个圆锥体。如果i（u）=∅，则c（u）=v。
图49.6：设u为介于曲线y=x2和y2=x之间的浅紫色平面区域。图（i）说明了由等式y−x2=0和y2−x=0给出的边界点（1,1）。可行方向锥体c（1，1）的仿射平移，用边与边界曲线相切的粉红色三角形表示。图（ii.）说明了等式y2−x=0给出的边界点（1/4,1/2）。c（1/4,1/2）的仿射平移是以y2=x到（1/4,1/2）的切线为界的淡紫色半空间。 由超平面从原点切出的C（U）形H多面体的特殊类型称为H锥。可以看出，每个h-锥都是多面体锥（也称为v-锥），反之亦然。证据是不平凡的；见Gallier[74]和Ziegler[189]。我们将很快证明，我们总是包含c（u）c（u）。 但是，可以严格包含，如示例49.1所示。实际上，对于u=（0,0），我们有i（0,0）=1,2，从 ， 我们有（=0 0），因此c（0）=（u1，u2）∈r2 u1+u2≥0，如中所示。 图49.7.
图49.7：对于u=（0,0），c（u）是由u1+u2≥0给出的海绿半空间。这半空间严格包含c（u），即将绿松石三角锥和定向射线结合起来（−1,1）。 以下定义中所述的条件是充分的条件，这意味着C（u）=C（u），正如我们接下来要证明的那样。 定义49.5.对于任何u∈u，用 u=x∈Ω_i（x）≤0，1≤i≤m， 如果函数在u上是可微的（事实上，我们只对i∈i（u）），我们说约束在u上是合格的，如果下列条件成立： (a) 约束i是所有i∈i（u）的仿射，或 (b) 存在一些非零向量w∈v，使得以下条件适用于所有i∈i（u）：
（ii）如果i不是仿射词，则（ 条件（b）（i i）意味着u不是每个i∈i（u）的一个临界点，因此，在πi的零轨迹中，u处没有奇点。直观地说，如果约束在u处合格，那么u靠近u的边界表现“良好”。 图49.6所示边界点合格。注意 u=x∈r2 _1（x，y）=y2−x≤0，⑨2（x，y）=x2−y≤0。对于u=（1,1），i（u）=1,2， −1）确保（和（满足定义49.5的条件（b））。对于1 1），w=（1,0）将满足条件（b）。 在实施例49.1中，在原点处不限定约束（u1，u2）=0，因为 0）；事实上，原点是自交集。在下面的示例中，原点是 也是一个奇点，但原因不同。 例49.2。考虑由以下两条曲线确定的区域u r2： （u1，u2）=u2−max（0，u31）（u1，u2）=u41−u2. 我们有i（0,0）=1,2，从（和（ ，我们有c（0）=（u1，u2）∈r2 u2=0，但约束条件是 （0,0）不合格，因为不可能同时（0和 0，所以实际上c（0）=（u1，u2）∈r2 u1≥0，u2=0是严格包含的 C（0）；见图49.8。 提案49.2.让你成为这一组的任何一个点 u=x∈Ω_i（x）≤0，1≤i≤m， 式中，Ω是赋范向量空间v的一个开子集，并假设函数i在u处是可微的（事实上，我们只对i∈i（u））。那么以下事实成立： (1) 在u处可行方向的圆锥体c（u）包含在凸圆锥体c（u）中；即 是， c（u）c（u）=v∈v（_i 0）u（v）≤0，i∈i（u）。 (2) 如果约束在u上是合格的（并且所有i/∈i（u）的函数在u上是连续的，如果我们只假设所有i∈i（u）在u上是可微的，那么 c（u）=c（u）。 证据。（1）对于每一个i∈i（u），由于所有v∈u和i（u）=0的i（v）≤0，函数−i对于u在u处有一个局部最小值，因此根据命题49.1（2），我们 （−_0i）u（v）≥0，对于所有v∈c（u）， 对于所有的v∈c（u）和所有的i∈i（u），这相当于（i）u（v）≤0，也就是说，u∈c（u）。 （2）（a）首先，让我们假设，对于每一个i∈i（u），i是仿射的。回想一下，所有v∈v，其中hi是一个线性形式，ci∈r，因此，任何点的线性映射的导数都是其自身， ）对于所有的v∈v。 φ（u，u 1 2） 图49.8：图（i）和（ii）说明了与实施例49.2相关的紫色月亮形区域。图（i.）还说明了可行方向的圆锥体c（0），而图（ii.）说明了c（0）在c（0）中的严格包容。 选取任意一个非零w c（u），这意味着（0代表所有i i（u）。对于（reals 0的）任何序列，如lim=0，让（uk）k≥0为 V中的矢量由
对于所有k≥0和limk7→∞uk=u，我们都有uk=0。此外，由于所有i/∈i的函数是连续的，我们有 0>_i（u）=lim_i（uk），k7→∞ 既然_i是仿射的，而_i（u）=0对于所有i∈i，我们有_i（u）=hi（u）+ci=0，所以
这就意味着，对于所有的K来说，UK∈U足够大。自从 对于所有k≥0， 我们得出结论w∈c（u）。见图49.9。
图49.9：设u为以线y=0、x=0和y=-x+1为界的桃形三角形。让u满足仿射约束_（x，y）=y+x-1。由于=（1 1），设置w=（−1、−1），并沿线路u+tw接近u。 （2）（b）现在让我们考虑这样一种情况：对于某些i∈i（u），某些函数_i不是仿射函数。设w=06是v中的某个向量，这样定义49.5的条件（b）成立，即：对于所有i∈i（u），我们有（i）（i）u（w）≤0。 （ii）如果_i不是仿射词，则（i）u（w）<0。 选取任意非零向量v∈c（u），这意味着（i）u（v）≤0表示所有i∈i（u），并让δ>0为任意正实数，这样v+δw=06。对于（reals 0的）任何序列，如lim=0，让（uk）k≥0是由 . 我们有u k k≥0和limk7→∞uk=u。此外，由于 对于所有i/∈i（u），函数_i是连续的，我们有 0>_i（u）=lim_i（u k）代表所有i/∈i（u）。（1）k→∞7 前一种情况下的方程（0）表明，对于所有i∈i（u），因此，i是仿射的，因为（i）u（v）≤0，（i）u（w）≤0和0，我们有 0表示所有i∈i（u）和i词缀。（2） 此外，由于_i是可微的，且_i（u）=0表示所有i∈i（u），如果_i不是仿射词，我们有
当limkuk−uk7→0ηk（uk−u）=0时，如果我们写αk=kuk−ukηk（uk−u），我们有
当limk7→∞αk=0，且由于（i）u（v）≤0，我们得出 ）对于所有i i（u）和_i不仿射。（3） 方程（1）、（2）、（3）表明，Uk∈U对K足够大，其中in（3），自 （ωi0）u（w）<0和δ>0，即使αk>0，当limk→∞7αk=0时，我们将有δ（ω0i）u（w）+αk<0表示k足够大，Thuslarge足够大。 自从 - 对于所有k≥0的情况，我们认为v+δw∈c（u）对于δ>0足够小。但现在顺序 （Vn）n≥0，由
收敛到v，对于n足够大，vn∈c（u）。由于在49.1（1）命题中，锥c（u）是封闭的，因此我们得出v∈c（u）。见图49.10。 在所有情况下，我们证明了如权利要求所述的c（u）c（u）。 在m仿射约束aix≤bi的情况下，对于某些线性形式ai和某些bi∈r，对于任意点u∈rn，使得aiu=bi对于所有i∈i（u），锥c（u）由所有v∈rn组成，这样aiv≤0，那么u+c（u）由所有点u+v组成，这样 ai（u+v）≤bi代表所有i∈i（u）， 它是由超平面切割出的圆锥体，确定由m约束aix≤bi定义的多面体的某个面。 我们现在准备证明非线性优化的一个最重要的结果。 49.3卡鲁什-库恩-塔克条件 如果域u是由满足弱可微条件的不等式约束定义的，并且在u处的约束是合格的，那么函数j在u∈u处有一个局部极小值的必要条件涉及广义拉格朗日乘子。证据使用了法卡斯引理的一个版本。事实上，所述的必要条件下一个适用于无限维向量空间，因为有一个farkas-lemma版本适用于真实的希尔伯特空间，但是我们将满足于有限维赋范向量空间的版本。关于更一般的版本，见定理47.11（或Ciarlet[41]，第9章）。 我们将使用以下版本的farkas-lemma。
图49.10：让你成为R2的粉色休息室。让u满足非仿射约束（u）。在半空间（0）中选择向量v和w。图（i.）沿u+t（δw+v）线接近u，表明v+δw∈c（u）为固定δ。图（ii.）按紫色向量接近v的顺序改变δ，即δ→∞。 提案49.3.（farkas-lemma，版本i）让a是一个实的m×n矩阵，让b∈rm是任意向量。线性系统ax=b不存在x≥0的解，如果存在一些非零线性形式y∈（rm），那么和yb<0。 我们将使用一个反正数得到的farkas引理的版本，即：如果对所有线性形式y∈（rm）表示y b≥0，那么线性系统ax=b一些 溶液x≥0。 实际上，使用应用于欧几里得向量空间的farkas-lemma版本更方便（内积表示H−、−I）。这个版本也适用于无限维实希尔伯特空间；见定理47.11。回想一下，在欧几里得空间V中，内积在V和V 0之间产生同构，即V上连续线性形式的空间。在我们的例子中，我们需要从v 0到v的同构]定义为，对于每一个线性形式ω∈v 0，向量ω∈v都是由方程唯一定义的。 ω（v）=hv，ω]i表示所有v∈v。 在RN中，RN与（RN）之间的同构等于转置：如果y∈（RN）是线性形式，v∈RN是向量，那么 YV=V>Y>。 内部产品的farkas–minskowski lemma版本如下。 提案49.4.（farkas–minkowski）让v是有限维的欧几里得空间，内积为h−、−i（更一般地说，是希尔伯特空间）。对于M向量的任意有限族（a1，…，am）ai∈v和任意向量b∈v，对于任意V∈v， 如果hai，vi≥0，i=1，…，m表示hb，vi≥0， 然后存在λ1，…，λm∈r，这样 对于i=1，…，m，λi≥0， 也就是说，b属于多面体圆锥（a1，…，am）。 命题49.4是定理47.11的特例，它适用于实希尔伯特空间。我们现在可以证明下面的定理。 定理49.5。设_i:Ω→r为定义在有限维欧几里得向量空间v（更一般地说，为实希尔伯特空间v）的某些开子集Ω上的m约束，设j:Ω→r为某种函数，设u为 u=x∈Ω_i（x）≤0，1≤i≤m。 对于任何u∈u，让 i（u）=i 1，…，m _i（u）=0， 并假设所有i∈i（u）的函数在u上是可微的，所有i/∈i（u）的函数在u上是连续的。如果j在u上是可微的，在u上对u有一个局部极小值，如果约束在u上是合格的，那么在所有i∈i（u）上都存在一些标量λi（u）∈r，这样 ，且所有i∈i（u）≥0。 上述条件称为karush–kuhn–tucker最优条件。同样，根据梯度，上述条件表示为 ju+xλi（u）（i）u=0，所有i∈i（u）≥0。 i∈i（u） 证据。根据49.1（2）号提案，我们 0表示所有w∈c（u），（1） 根据命题49.2（2），我们得到c（u）=c（u），其中 ，（2） 所以（1）可以表示为：对于所有w∈v， 如果w∈c（u），那么， 或 如果所有i∈i（u）为0，则。（3） 在同构下，向量（是梯度ju，因此 ，（4） 矢量（（i）u）是梯度（i）u，因此 （_0i）u（w）=hw，（i）ui.（5） 利用方程（4）和（5），方程（3）可以写成：对于所有w∈v， 如果Hw，−（i）ui≥0，则Hw，jui≥0。（6） 根据farkas-minkowski命题（49.4号命题），对于所有i∈i（u），存在一些sacalarsλi（u），使得λi（u）≥0和 ju=xλi（u）（−（i）u）时， i∈i（u） 那就是 ju+xλi（u）（_i）u=0， i∈i（u） 利用同构的逆（线性），我们得到 ju0+xλi（u）（i）u=0， i∈i（u） 如要求。 由于约束是形式_i（x）≤0的不等式，有一种表达karush–kuhn–tucker最优性条件的方法，通常缩写为kkt条件，其方式不明确指代索引集i（u）： ，（KKT1） 和 （KKT2） 事实上，如果我们有严格的不等式_i（u）<0（约束_i在u处是不活动的），因为所有的项λi（u）_i（u）都是非正的，我们必须有λi（u）=0；也就是说，我们只需要考虑所有i∈i（u）的λi（u）。用（kkt2）表示条件的另一种方法是 λi（u）_i（u）=0，λi（u）≥0，i=1，…，m.（kkt） 换言之，对于任何i 1，…，m，如果直径i（u）<0，则λi（u）=0；即， • 如果约束i在u处无效，则λi（u）=0。 相反，如果λi（u）=06，则i（u）=0；即， • 如果λi（u）=06，则约束i在u处激活。 （kkt02）中的条件称为补充松弛条件。 标量λi（u）通常称为广义拉格朗日乘子。如果v=rn，则定理49.5的必要条件表示为不可知项（u1，…，un）中的方程和不等式系统∈rn和（： . 例49.3。设j，和_为r上定义的函数 j（x）=x_1（x）=-x_2（x）=x−1. 在这种情况下，u=x∈r−x≤0，x−1≤0=[0,1]。 由于约束是仿射的，它们自动地被限定为任何u∈[0,1]。上述方程组和不等式变成 1−λ1+λ2=0−λ1X+λ2（x−1）=0−x≤0 x−1≤0λ1，λ2≥0。 第一个等式意味着λ1=1+λ2。然后第二个相等变成 −（1+λ2）x+λ2（x−1）=0， 这意味着λ2=−x。由于0≤x≤1，或等于−1≤−x≤0，且λ2≥0，我们得出结论，λ2=0且λ1=1是与x=0相关的解，j（x）=x大于[0,1]的最小值。观察情况X=1对应于最大值而不是最小值J（X）=X超过[0,1]。 注：除非i∈i（u）的线性形式（i）u是线性无关的，否则λi（u）一般不唯一。另外，如果i（u）=0，则kkt条件减小为0。这并不奇怪，因为在这种情况下，u属于u的相对内部。 如果约束都是仿射等式约束，那么kkt条件就简单了一点。我们很快就会考虑这个问题。 非亲约束条件在实际应用中很难（如果不可能）使用，因为它们依赖于u∈u和导数（i）u，因此需要找到更简单的条件。幸运的是，如果非亲函数i是凸的，这是可能的。 定义49.6.设uΩV为 u=x∈Ω_i（x）≤0，1≤i≤m， 式中，Ω是欧几里得向量空间V的开子集。如果函数ωi:Ω→r为凸函数，则我们认为，如果满足以下条件，则约束是合格的： (a) 约束_i是所有i=1，…，m和u=6∅的仿射，或 (b) 有一些向量v∈Ω，使得以下条件适用于i=1，…，m： (i) _i（v）≤0. (ii) 如果_i不是仿射词，则_i（v）<0。 上述条件称为斯莱特条件。 条件（b）（i）也意味着u具有非空的相对内部。如果Ω是凸的，那么U也是凸的。这是因为，对于所有u，v∈Ω，如果u∈u和v∈u，即，对于i=1，…，m，则为i（u）≤0和i（v）≤0，因为函数i是凸的，对于所有θ∈[0,1]我们有 _i（（1−θ）u+θv）≤（1−θ）_i（u）+θ_i（v），因为_i是凸形的 ≤0，因为1−θ≥0，θ≥0，_i（u）≤0，_i（v）≤0， 任何凸集的交集都是凸的。 很重要的一点是要注意，非亲等同性约束_i（u）=0从未被限定。 实际上，_i（u）=0相当于_i（u）≤0和−_i（u）≤0，因此，如果这些约束是合格的，并且如果_i不是仿射的，则存在一些非零矢量v∈Ω，这样，_i（v）<0和−_i（v）<0都是不可能的。因此，通常假定等式约束是仿射的。 对于凸函数给出的约束，下面的定理给出了定理49.5的更灵活的版本。此外，如果函数j也是凸的，那么kkt条件也是局部极小的充分条件。 定理49.6。设_i:Ω→r为m凸约束，定义在一些开凸子集上。 有限维欧几里得向量空间v的Ω（更一般地说，是实希尔伯特空间v），设j:Ω→r为某个函数，设u为 u=x∈Ω_i（x）≤0，1≤i≤m， 设u∈u为任意点，使得函数i和j在u上是可微的。 (1) 如果j在u上有一个局部最小值，并且约束是合格的，那么存在一些标量λi（u）∈r，这样KKT条件成立：
和
同样，根据梯度，上述条件表示为 ， 和
(2) 相反，如果j对u的约束是凸的，并且存在标度（λ1，…，λm）∈使得kkt条件成立，则函数j在u处具有（全局）最小值。 关于美国。 证据。（1）只要证明凸约束符合49.6的定义，那么它们就符合49.5的定义，因为在这种情况下，我们可以应用定理49.5。 如果v∈Ω是一个向量，这样定义49.6的条件（b）成立，如果v=6 u，对于任何i∈i（u），因为i（u）=0，并且既然i是凸的，根据命题39.9（1）， ， 所以如果我们让w=v−u，那么 ， 这表明，根据定义49.5，根据定义49.6中的条件（b），i∈i（u）的非亲约束_i是合格的。 如果v=u，那么，其中，i（u）=0的约束条件i必须是仿射的（否则，定义49.6的条件（b）（ii）将是错误的），在这种情况下，我们可以选择w=0。 （2）设v为凸子集u中的任意点，因为 i=1，…，m，我们有0，利用这个事实
如果i/∈i（u），我们有λi=0，如果i∈i（u），我们有
如果i/∈i（u），λi=0，如果i∈i（u），i（u）=0
）（提案39.9）（1）
）（根据KKT条件）
）（根据第39.9（1）号提案，
这表明u确实是j对u的（全局）最小值。
需要注意的是，当约束、定义域Ω和目标函数j都是凸的时，如果kkt条件适用于某些u∈u和一些
，那么定理49.6就意味着j在u处对u有一个（全局）最小值，独立于对约束条件的任何假设。
上述定理建议引入
，
用λ=（λ1，…，λm）。函数l称为最小化问题（p）的拉格朗日：
将j（v）减至最小，以_i（v）≤0，i=1，…，m为准。
定理49.6的KKT条件意味着，对于任何u∈u，如果向量λ=（λ1，…，λm）已知，并且u是u上j的最小值，那么
.
拉格朗日方法将约束“吸收”到新的目标函数l中，并将函数j的约束最小值的求解问题简化为函数l（v，λ）的无约束最小值的求解问题。这是拉格朗日对偶的要点，将在下一节中讨论。
在实践中经常出现的情况是约束条件i是仿射的情况。如果是这样，m约束aix≤bi可以用矩阵形式表示为ax≤b，其中a是m×n矩阵，其中ith行是行向量ai。定理49.6的KKT条件产生以下推论。
提案49.7。如果u是由
u=x∈Ωax≤b，
式中，Ω是Rn的开凸子集，a是m×n矩阵，如果j在u处可微，j在u处有局部极小值，则存在一些向量λ∈Rm，这样
ju+a>λ=0
λi≥0，如果aiu
如果目标函数为c>x，等式约束为ax=b的原线性规划和目标函数为b>y，不等式约束为a>y≥c的对偶规划都有内部可行点x和y，这意味着x>0和s>0（其中s=a>y−c）。然后，上述方程组具有唯一的解，使得x是fμon u的唯一最大化器；见Matousek和Gardner[120]（第7.2节，引理7.2.1）。
第49.9号提案的一个特别重要的应用是，当Ω=Rn时。
49.4平等约束最小化
在本节中，我们考虑以下程序（P）：
使j（v）最小化，服从av=b，v∈rn，
其中j是凸可微函数，a是秩m
其中p是一个n×n对称的半正定矩阵，在这种情况下q∈rn和r∈r。 jx=px+q， 所以可行性方程变成 AX＝B px+q+a>λ=0，
49.4。矩阵形式的等式约束极小化 （KKT公式） 线性系统的矩阵通常称为KKT矩阵。注意，在命题41.3中已经遇到了用不同的符号表示的KKT矩阵；在这里我们有p=a−1、a=b>、q=b和b=f。 如果kkt矩阵是可逆的，那么它的唯一解（x，λ）会产生唯一的最小问题x（p）。如果kkt矩阵是奇异的，但系统（kkt eq）是可解的，那么任何解（x，λ）都会产生问题（p）的最小x。 如果系统（kkt eq）不可解，那么我们声称程序（p）在下面是无界的。这可以用第一卷第29.7节所示的事实来证明，线性系统bx=c没有解，如果有一些y，b>y=0，y>c=06。如有必要，将y更改为−y，我们可以假设y>c>0。我们将这一事实应用于线性系统（kkt eq），所以b是对称的kkt矩阵，我们得到存在v∈rn和λ∈rm的条件，这样 pv+a>λ=0，a v=0，−q>v+b>λ>0。 由于m×n矩阵a具有秩m和b∈rm，系统a x=b是可解的，因此对于任何可行的x0（即ax0=b），由于a v=0，向量x=x0+tv也是所有t∈r的可行解，利用pv=−a>λ，v>p=−λ>a，av=0的事实， ，p是对称的，我们有 j（x0+t v）=j（x0）+（v>px0+q>v）t+（1/2）（v>pv）t2 =J（X0）+（x>0 pv+q>v）t−（1/2）（λ>av）t2 =J（X0）+（−X>0 A>λ+Q>V）T=J（X0）-（B>λ−Q>V）T， 由于−q>v+b>λ>0，当t变为+∞时，上述表达式变为−∞。 确定KKT矩阵是否可逆显然很重要。确实有这样的标准，如博伊德和范登伯格[29]所指出的（第10章，练习10.1）。 提案49.10。KKT矩阵的可逆性
相当于以下条件： (1) 对于所有x∈rn，如果ax=0且x=06，则x>px>0，即p在a的核上是正定的。 (2) a和p的核只有0个共同点（（kera）（kerp）=0）。 (3) 有一些n×（n-m）矩阵f，使得im（f）=ker（a）和f>pf是对称正定的。 (4) 有一些对称半正定矩阵q，使得p+a>qa是对称半正定的。事实上，Q=I有效。 证明草图。回想一下第一卷5.14号命题，如果一个方阵b的核被约化为0等价，那么对于所有x，如果bx=0，那么x=0。假设条件（1）成立。我们有 敌我识别 .（） 我们推断 v>pv+v>a>w=0， 从那以后 v>a>w=（av）>w=0w=0， 我们得到v>pv=0。由于条件（1）成立，由于v∈kera，我们推断v=0。那么a>w=0，但由于m×n矩阵a具有秩m，n×m矩阵a>也具有秩m，因此其列是线性无关的，因此w=0。因此，KKT矩阵是可逆的。 相反，假设KKT矩阵是可逆的，但条件（1）的假设失败。这意味着有一些v=06，使得av=0和v>pv=0。我们声称pv=0。这是因为如果p是一个对称的半正定矩阵，那么对于任何v，我们都有v>pv=0 iff pv=0。 如果pv=0，那么显然v>pv=0，那么假设相反，即v>pv=0。自从 p是一个对称的半正定矩阵，它可以对角化为 P=R>∑R， 其中r是正交矩阵，∑是对角矩阵 ∑=diag（λ1，…，λs，0，…，0）、 式中，s为p的秩，且λ1≥······························则v>pv=0等于 V>R>∑Rv=0， 等价的 （RV）>是∑RV=0。 49.4。等式约束最小化 如果我们写rv=y，那么我们有 ， 由于i=1，…，s的λi>0，这意味着i=1，…，s的yi=0。因此，如权利要求所述，∑y=∑rv=0，所以pv=r>∑rv=0。由于v=06，向量（v，0）是方程（）的一个非平凡解，是KKT矩阵可逆性假设的矛盾。 观察到我们证明了av=0和pv=0，iff av=0和v>pv=0，因此我们很容易得到条件（2）等于kkt矩阵的可逆性。第（3）和（4）部分留作练习。 特别是，如果p是正定的，那么命题49.10（4）适用，正如我们从命题41.3中已经知道的那样。在这种情况下，我们可以用消去法求x。我们得到 x=−p−1（a>λ+q），其中λ=−（ap−1a>）−1（b+ap−1q）。 在实践中，我们不反转P和AP−1a>。相反，我们解线性系统 PZ= Q Pe=A> （ae）λ=−（b+az） px=−（a>λ+q）。 观察（ap−1a>）-1是KKT矩阵中p的舒尔补体。 由于KKT矩阵是对称的，如果它是可逆的，我们可以用第一卷的命题7.6把它转换成ldl>形式。这种方法只有在问题很小或a和p很稀疏时才实用。 如果kkt矩阵是可逆的，但p不是，那么我们可以使用涉及命题49.10的技巧。我们找到一个对称的半正定矩阵q，使得p+a>qa是对称的正定矩阵，由于kkt系统的解（v，w）应该是av=b，我们也有一个>qav=a>qb，所以kkt系统等于 ， 由于p+a>qa是对称正定的，我们可以用消去法来解这个系统。 解决问题（p）的另一种方法是使用第48.9节中描述的牛顿方法的变体来处理等式约束。Boyd和Vandenberghe[29]对此方法进行了广泛讨论（第10章，第10.2-10.4节）。 此方法有两种变体： (1) 第一种方法，称为可行的起始牛顿法，假设起始点U0是可行的，这意味着AU0=B。牛顿阶跃dnt是可行的方向，这意味着adnt=0。 (2) 第二种方法称为不可行的起始牛顿法，它不假定起始点U0是可行的，这意味着AU0=B可能不成立。这个方法比其他方法要复杂一些。 我们只简要讨论了可行的启动牛顿法，让读者参考Boyd和Vandenberghe[29]（第10章，第10.3节）讨论不可行的启动牛顿法。 牛顿阶跃dnt是线性系统的解。 . 牛顿减量λ（x）在第48.9节中定义为 . 等约束牛顿法（有可行起点）包括以下步骤：给定起点U0∈Dom（J），AU0=B，公差>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. 牛顿方法要求KKT矩阵是可逆的。在一些温和的假设下，牛顿方法（以可行的起点）收敛；见Boyd和Vandenberghe[29]（第10章，第10.2.4节）。 我们现在给出一个例子来说明命题49.7，即支持向量机（简称SVM）。 49.5。硬边支持向量机；第一版 49.5硬边支持向量机；版本I 在本节中，我们将描述以下分类问题，或者更准确地说，分离问题（分为两类）。假设在RN中有两个非空不相交的有限集，即p蓝点和q红点vj qj=1（为了简单起见，可以假设这些点在平面中，即n=2）。我们的目标是找到方程w>x−b=0的超平面h（其中w∈rn是一个非零向量，b∈r），这样所有的蓝点ui都在h确定的两个开半空间中的一个，所有的红点vj都在h确定的另一个开半空间中；见图49.11。
图49.11:SVM分离问题的两个示例。左图为R2中的SVM，右图为R3中的SVM。 在不丧失一般性的情况下，我们可以假定 对于i=1，…，w>ui−b>0，对于j=1，…，p w>vj−b<0，q。 当然，分离蓝色和红色的点可能是不可能的，如图49.12所示，对于线段（u1，u2）和（v1，v2）相交的四个点。如果存在一个分离蓝点和红点两个子集的超平面，我们就说它们是线性可分离的。 备注：写m=p+q。读者应该知道，在机器学习中，分类问题通常定义如下。我们将m所谓的类标签yk=±1分配给数据点，这样每个蓝点ui的yi=+1，每个红点vj的yp+j=-1，我们用xk表示m点，其中xk=uk代表k=1，…，p和xk=vk−p代表k=p+1，…，p+q。然后分类约束可以是bE写为 yk（w>xk−b）>0，对于k=1，…，m。
图49.12：两个不可能找到分离红点和蓝点的紫色超平面的例子。 成对的集合（x1，y1），…，（xm，ym）称为一组训练数据（或训练集）。 在续集中，我们不使用上述方法，我们将坚持我们的两个子集：P蓝点和Q红点。 由于两个子集之间存在无穷多的超平面（如果两个子集确实是线性可分的），我们想提出一个选择此类超平面的“好”准则。 Vapnik（见Vapnik[176]）主张的观点是考虑从所有点到超平面h的距离d（ui，h）和d（vj，h），并选择一个超平面h，使这些距离中的最小值最大化。在机器学习中，这种策略被称为寻找最大边缘超平面，或硬边缘支持向量机，听起来确实更令人印象深刻。 由于方程w>x−b=0的点x到超平面h的距离为 ，
（其中kwk=√w>w是w的欧几里得范数），可以方便地暂时假定kwk=1，因此d（x，h）=w>x−b。 见图49.13。然后按照我们的签名约定 49.5。硬边支持向量机；第一版
图49.13：在r3中，从一个点到平面w>x−b=0的距离由投影到法向w的距离给出。 d（ui，h）=w>ui−b i=1，…，p d（vj，h）=w>vj+b j=1，…，q. 如果我们让 δ=最小d（ui，h），d（vj，h）1≤i≤p，1≤j≤q， 那么超平面h的选择应该是 w>ui−b≥δi=1，…，p −w>vj+b≥δj=1，…，q， 这样δ>0是最大的。距离δ称为与超平面h相关的裕度，这确实是将两类分离问题表示为线性目标函数j（δ，w，b）=δ，仿射和二次约束（svmh1）的优化问题的一种方法： δ最大化
观察到问题（SVMH1）有一个最优解δ>0，如果两个子集是线性可分的。我们使用了约束kwk≤1而不是kwk=1，因为前者是合格的，而后者则不是。但如果（w，b，δ）是一个最优解，那么kwk=1，如下面的命题所示。 提案49.11。如果（w，b，δ）是问题（svmh1）的最优解，特别是δ>0，那么我们必须得到kwk=1。 证据。首先，如果w=0，那么我们得到两个不等式 −b≥δ，b≥δ， 这意味着b≤−δ和b≥δ对于某些正δ是不可能的。但是，如果w=06和kwk<1，将不等式的两边除以kwk<1，我们会得到更好的解（w/kwk，b/kwk，δ/kwk），因为kwk<1意味着δ/kwk>δ。 我们现在证明，如果两个子集是线性可分的，那么问题（SVMH1）具有唯一的最优解。 定理49.12。如果p蓝点和q红点vj qj=1的两个不相交的子集是线性可分的，那么问题（svmh1）有一个唯一的最优解，该解由方程w>x−b=0的超平面组成，将两个具有最大边缘δ的子集分离。此外，如果我们将c1（w）和c2（w）定义为 c1（w）=min w>ui 1≤I≤P c2（w）=max w>vj， 1≤J≤Q 那么w是函数的唯一最大值 ρ（w）=c1（w）−c2（w）2 由不等式给出的Rn的凸子集u上
和 . 证据。我们的证明改编自Vapnik[176]（第10章，定理10.1）。对于任何分离超平面h，因为 d（ui，h）=w>ui−b d（vj，h）=w>vj+b i=1，…，p j=1，…，q，
因为到h的最小距离是δ=min d（ui，h），d（vj，h）1≤i≤p，1≤j≤q =min w>ui−b，−w>vj+b 1≤i≤p，1≤j≤q =min min w>ui−b 1≤i≤p，min−w>vj+b 1≤j≤q =min min w>ui 1≤i≤p−b，min−w>vj 1≤j≤q+b =min min w>ui 1≤i≤p−b，−max w>vj 1≤j≤q+b =最小c1（w）−b、−c2（w）+b， 为了使δ最大，我们必须 在这种情况下， 因此，当ρ（w）=（c1（w）−w>cx2（−w））b=0/2最大相关时，确实获得了最大裕度δ。 在u上，相反地，很容易看出方程的任何超平面，其中w最大，ρ在u上，b=（c1（w）+c2（w））/2是一个最优解。 这仍然需要证明一个最优的分离超平面存在并且是唯一的。由于单位球是紧致的，u（如定理49.12所定义）是紧致的，并且由于函数wwe必须具有7→ρ（w）是连续的，所以它在somekw0k=1时达到最大值，否则，根据命题49.11，w0中使用的推理，kw0k≤1。实际上，W0/KW0K是一个更好的解决方案。因此，w0在u的边界上，但是ρ是一个凹函数（作为仿射函数的一个中值），所以如果它有两个不同的极大值w0和with=1，这将是全局极大值，因为u也是凸的，所以我们将 ）然后ρ沿着段（）也有相同的值，并且 尤其是在（2，U的内点，一个矛盾。 我们可以继续上面的公式（svmh1），但是有一种方法可以重新表述这个问题，使约束都是仿射的，这可能更可取，因为它们将自动被限定。 49.6硬边支持向量机；第二版 由于δ>0（否则数据将不可分为两个不相交的集合），我们可以将仿射约束除以δ得到 w0>ui−b0≥1−w0>vj+b0≥1 i=1，…，p j=1，…，q， 除了现在，w0不一定是单位向量。为了得到到超平面h的距离，我们需要除以kw0k，然后我们得到 i=1，…，p j=1，…，q， 这意味着从数据点到超平面的最短距离为1/kw0k，因此我们希望最大化1/kw0k，即最小化kw0k，因此我们得到以下优化问题（svmh2）： 硬边SVM（SVMH2）： 最小化
目标函数j（w）=1/2kwk2是凸的，因此命题49.7适用，并给出了在kkt条件下具有最小值的必要和充分条件。首先要注意，平凡解w=0是不可能的，因为蓝色约束是 −b≥1， 即b≤−1，红色约束为 b≥1， 但这些都是矛盾的。我们的目标是找到w和b，以及可选的δ。我们首先在下面的示例中演示了四个步骤。 假设p=q=n=2，那么我们有两个蓝点 ， 两个红点 ， 和w>=（w1，w2）。 第一步：用矩阵形式写约束。让 （m） 约束变成 （c） 第二步：用矩阵形式写出目标函数。 （o） 第3步：应用49.7号提案，用λ和μ来求解w。我们得到 ，即 . 然后 ， 这意味着 （1） 关于 _1+_2−λ1−λ2=0。（2） 步骤4：使用（1）重写（c）处的约束。尤其是 . 用“block”格式重写前一个公式给出了 ， 它的定义是 产量 .（3） 现在让我们考虑一下一般情况。 第一步：用矩阵形式写约束。首先，我们将约束重写为 i=1，…，p j=1，…，q， 得到（p+q）×n+1）矩阵c和向量d∈rp+q ， 所以不等式约束的集合是
第二步：矩阵形式的目标函数由 . 注意，对应的矩阵是对称的半正定矩阵，但它不可逆。因此，函数j是凸的，但不是严格凸的。这将在查找问题的双重功能时造成一些小麻烦。 第三步：如果我们引入广义拉格朗日乘子λ∈Rp和∈Rq，根据命题49.7，第一个KKT条件是 ， λ≥0，μ≥0。根据实施例38.4的结果， 所以我们得到 也就是说， . 因此， （1） 和 .（2） 步骤4：使用（1）重写约束。将上述w表达式插入 我们得到的约束 ， 所以如果x是n×（p+q）矩阵 ， 我们得到 上述不等式用矩阵形式表示为 ； 也就是说， .（3） 等价地，第i个不等式是 PQ −xu>i ujλj+xu>i vkμk+b+1≤0 i=1，…，p， J=1 K=1 （p+j）th不等式是
我们也有λ≥0，μ≥0。此外，如果第i个不等式为非激活状态，则λi=0，如果（p+j）th不等式为非激活状态，则μj=0。既然约束是仿射的，既然j是凸的，如果我们能找到λ≥0，_≥0，和b，从而满足（3）中的不等式，并且当相应的约束不活动时，λi=0和_j=0，那么根据命题49.7，我们得到了一个最优解。 备注：第二个KKT条件可写为 ＝0； 也就是说， . 因为（2）说，第二项是零，到（）我们得到 . 因此，我们得到了kwk2在λ和μ方面的简单表达式。 i-th不等式为主动且（p+j）th不等式为主动的向量ui和vj称为支持向量。对于不是支持向量的每个向量ui或vj，相应的不等式都是非活动的，因此λi=0和μj=0。因此，我们看到只有支持向量有助于求解。如果我们能猜出哪些向量ui和vj是支持向量，也就是那些λi=06和μj=06的向量，那么对于每个支持向量ui，我们有一个方程 ， 对于每个支持向量vj，我们有一个方程 ， 对于所有非支持向量，λi=0且μj=0，因此，与方程（2）一起，我们有一个方程和变量数目相等的线性系统，如果分离问题有解，该线性系统是可解的。因此，原则上我们可以通过解线性系统来找到λ、μ和b。 注：我们可以先解出λ和μ（通过去掉b），再通过（1），既然w=06，则至少有一些非零的λi0和一些非零的μj0，因此相应的不等式为方程。 ， 因此b是以λ和μ表示的 . 利用拉格朗日对偶，我们可以解出λ和μ，但通常b不确定，所以我们用上述方法求b。 在上面的不确定过程中，我们猜测哪些向量是支持向量是不实际的。稍后我们将看到，求解λ和μ的实用方法包括最大化拉格朗日对偶。 如果w是一个最优解，那么δ=1/kwk是从支持向量到方程w>x−b=0的分离超平面hw，b的最短距离。如果我们考虑方程的两个超平面hw，b+1和hw，b-1 W>X−B−1=0和W>X−B+1=0， 那么hw，b+1和hw，b-1是平行于超平面hw，b的两个超平面，它们之间的距离为2δ。此外，hw，b+1包含支持向量ui，hw，b−1包含支持向量vj，并且在包含分离超平面hw，b的两个超平面之间的开放区域中没有数据点ui或vj（boyd和vandenberghe称为“板”；见[29]第8.6节）。这种情况如图49.14所示。
图49.14：在r3中，硬边svmh2的解是夹在红色平面w>x−b+1=0和蓝色平面w>x−b−1=0之间的紫色平面，每个平面都包含适当的支持向量ui和vj。 即使p=1，q=2，解也不明显。在飞机上，有四种可能：（1）如果U1在段上（v1，v2），则没有解决方案。 (2) 如果u1在v1和v2确定的直线上的投影h在v1和v2之间，即h=（1−α）v1+α2v2，其中0≤α≤1，则它是平行于v2−v1且与u和v1和v2等距的直线，如图49.15所示。 (3) 如果u1在v1和v2确定的直线上的投影h在v2的右边，即h=（1−α）v1+α2v2，α>1，则它是直线段的平分线（u1，v2）。 (4) 如果u1在v1和v2确定的直线上的投影h在v1的左侧，即h=（1−α）v1+α2v2，α<0，则它是直线段的平分线（u1，v1）。
图49.15：紫色线是等腰三角形高度的平分线，以满足硬边SVMH2的方式将两个红色点与蓝色点分开。 如果p=q=1，我们可以显式地找到一个解。然后（2）产生 λ=μ， 如果我们猜测约束是活动的，那么相应的等式约束是 ， 所以我们得到 （−u>u+u>v）λ+b+1=0 （u>v−v>v）λ−b+1=0， 把我们找到的两个方程加起来 ， 那就是 通过从第二个方程式中减去第一个方程式，我们发现 会产生 . 然后通过（1）我们得到 . 我们很容易证实
是u和v之间平分线超平面的方程；见图49.16。 U
图49.16：在r3中，点u和v的硬边svmh2的解是u-v的紫色垂直平面平分线。 在下一节中，我们将推导本节讨论的优化问题的对偶。我们还将考虑一个更灵活的解决方案，涉及软利润。 49.7拉格朗日对偶和鞍点 在本节中，我们研究了解决最小化问题（P）的方法： 将j（v）减至最小，以_i（v）≤0，i=1，…，m为准。 结果表明，在一定条件下，原问题（P）称为原问题，在另一个问题（D）的帮助下，可以分两个阶段解决，称为对偶问题。对偶问题（d）是一个涉及函数g的最大化问题，称为拉格朗日。
对偶的，它是通过将问题（p）的拉格朗日L（v，μ）最小化到变量v∈rn上，保持μ固定得到的，其中由 ， 用。 该方法的两个步骤是： (1) 通过对V∈Ω求L（V，μ）的最小值，保持μ固定的最小化问题，明确地求出双函数μ7→g（μ）。这是一个无约束的最小化问题（带有v∈Ω）。如果幸运的话，我们可以找到一个独特的最小值uμ，这样g（μ）=l（uμ，μ）。稍后我们将讨论唯一性问题。 (2) 解决求函数μ7→g（μ）最大值的最大化问题。这基本上是一个不受约束的问题，除了 . 如果步骤（1）和（2）成功，在函数j和约束条件（例如，如果它们是凸的）的某些适当条件下，对于步骤（2）中获得的任何解，步骤（1）中获得的向量uλ是问题（p）的最佳解。这在定理49.16中得到证明。 为了证明定理49.16，这是我们的主要结果，我们需要两个涉及鞍点概念的独立兴趣的中间技术结果。 在由不等式约束定义的域u上，函数j:Ω→r的局部极小值是与j相关的拉格朗日l（v，礹）的鞍点和约束礹i。然后，在一些温和的假设下，最小化问题的解集（p） 最小化j（v） 以“i（v）≤0，i=1，…，m为准 与拉格朗日鞍点的第一个参数集重合 . 这在定理49.14中得到了证明。为了证明定理49.16，我们还需要49.13这个鞍点的基本性质。 定义49.7.设l:Ω×m→r为一组形式Ω×m上定义的函数，其中Ω和m是两个赋范向量空间的开子集。如果u是函数l（−λ）的最小值，则a点（u，λ）∈Ω×m为l的鞍点：Ω→r由v 7给出→l（v，λ）为所有v∈Ω和λ固定值，且λ是函数l（u，−）的最大值：m→r由μ7给出→l（u，μ）为所有μ∈m和u固定值；等价地， sup l（u，μ）=l（u，λ）=inf l（v，λ）。祭m v∈Ω 注意，参数u和λ的顺序很重要。第二个集合m是广义乘数的集合，这就是为什么我们使用符号m的原因。通常。 马鞍点通常被描述为山口，这解释了术语；见图49.17。然而，这有点误导，因为其他情况是可能的；见图49.18。
图49.17：函数l（u，λ）=u2-λ2的鞍点l（u，λ）的三维再现。平面x=u提供最大值作为向下开口抛物线的顶点，而平面y=λ提供最小值作为向上开口抛物线的顶点。 提案49.13。如果（u，λ）是函数l:Ω×m→r的鞍点，则 SUP INF L（V，μ）=L（U，λ）=INF SUP L（V，μ）。礿∈M V∈欧V∈欧礿礿M 证据。首先，我们证明以下不等式始终成立： SUP INF L（V，μ）≤INF SUP L（V，μ）。（1）霏
（二） 图49.18：设Ω=[t，0,0]0≤t≤1且m=[0，t，0]0≤t≤1。在图（i）中，L（u，λ）是向前顶点为鞍点的蓝色斜四边形。在图（ii.）中，L（u，λ）是完全由鞍点组成的平面绿色矩形。 选取任意w∈Ω和任意ρ∈m，通过inf（最大下界）和sup（最小上界）的定义，我们得到 inf l（v，ρ）≤l（w，ρ）≤sup l（w，μ）。V∈Ω∈M 可能出现infv∈Ωl（v，ρ）=-∞或sup∈m l（w，µ）=+∞的情况，但这不是问题。自从
右手边独立于ρ，它是所有ρ的左手边的上界，所以 SUP INF L（V，μ）≤SUP L（W，μ）。 礿∈M V∈Ω礿∈M 由于左侧独立于w，因此它是所有w右侧的下限，因此我们得出（1）： . 为了得到反不等式，我们使用（u，λ）是鞍点的事实，因此 inf sup l（v，礹）≤sup l（u，礹）=l（u，礹）v∈Ω礹礹m礹礹m 和 ， 这意味着inf sup l（v，μ）≤sup inf l（v，μ），（2） V∈Ω∈M∈M V∈Ω 根据需要。 现在我们回到我们的主要最小化问题（P）： 将j（v）减至最小，以i（v）≤0，i=1，…，m为准， 式中，j:Ω→r和约束搋i:Ω→r是在一些有限维欧几里得向量空间v（更一般地说，是一个实希尔伯特空间v）的一些开子集Ω上定义的一些函数。 定义49.8.上面定义的最小化问题（p）的拉格朗日是由 ， 使用礹=（礹1，…，礹m）。数字μi称为广义拉格朗日乘数。 下面的定理表明，在适当的条件下，问题（p）的每一个解u是拉格朗日L鞍点（u，λ）的第一个参数，反之，如果（u，λ）是拉格朗日L的鞍点，则u是问题（p）的解。 定理49.14。考虑上面定义的问题（p），其中j:Ω→r和约束揷i:Ω→r是在一些有限维欧几里得向量空间v（更一般地说，是一个实希尔伯特空间v）的一些开子集Ω上定义的一些函数。以下事实成立。 是与问题（p）相关的拉格朗日l的鞍点， 那么u∈u，u是问题（p）的解，j（u）=l（u，λ）。 （2）如果Ω是凸的（开的），如果函数_i（1≤i≤m）和j在点u∈u处是凸的且可微的，如果约束是合格的，并且如果u∈u是问题（p）的最小值，则存在一些向量，使得对是拉格朗日l的鞍点。 证据。（1）由于（u，λ）是l的鞍点，我们有sup，这意味着l（u，μ）≤l（u，λ），这意味着 ， 也就是说， 0代表所有人。 如果我们让每个μi足够大，那么μi−λi>0，并且如果我们有_i（u）>0，那么术语（μi−λi）_i（u）可以任意地变大和变正，因此我们得出_i（u）≤0，对于i=1，…，m，并且因此，对于=0，我们得出结论： 然而，由于λi≥0且_i（u）≤0，（因为u∈u），我们得到0。把这两个不等式结合起来表明 .（1） 这表明j（u）=l（u，λ）。因为不等式l（u，λ）≤l（v，λ）是 ， 通过（1）我们获得 ）对于所有V∈Ω ）对于所有v∈u（因为_i（v）≤0且λi≥0）， 这表明u是u上j的最小值。 （2）满足应用定理49.6（1）所需的假设。因此，如果u∈u是问题（p）的解，则存在一些向量，使得kkt条件成立： =0和。 第二个方程得出 ， 也就是说， L（u，μ）≤L（u，λ）表示所有（2） （由于_i（u）≤0作为u∈u），并且由于函数v 7→j（v）+pi=1λi_i（v）=l（v，λ）是凸函数的和，根据定理39.11（4），第一个方程是存在最小值的充分条件。因此， l（u，λ）≤l（v，λ）对于所有v∈Ω，（3） 并且（2）和（3）表明（u，λ）是L的鞍点。 为了回顾我们刚刚证明的，在一些温和的假设下，最小化问题的解集（P） 将j（v）减至最小，以_i（v）≤0，i=1，…，m为准 与拉格朗日鞍点的第一个参数集重合 ， 对于任何问题（p）的最优u∈u，我们得到j（u）=l（u，λ）。 因此，如果我们知道这些鞍点的某些特殊的第二个参数λ，那么约束问题（p）将被无约束问题（pλ）所取代： 求uλ∈Ω，使l（uλ，λ）=inf l（v，λ）。V∈Ω 我们如何找到这样一个元素？ 为此，请记住，对于鞍点（uλ，λ），根据命题49.13，我们有 ， 因此，我们很自然地引入了 ， 那么λ就是这个问题的一个解。 找到这样的 g（λ）=sup g（μ）， 礿r+m 相当于最大化问题（d）： 最大g（μ）取决于。 定义49.9.给定最小化问题（P） 将j（v）减至最小，以_i（v）≤0，i=1，…，m为准， 式中，j:Ω→r和约束搋i:Ω→r是在某些有限维欧几里得向量空间v（更一般地说，是实希尔伯特空间v）的某些开子集Ω上定义的一些函数，其函数由下式给出： ， 称为拉格朗日对偶函数（或简单的对偶函数）。问题（d） 最大g（μ）取决于 称为拉格朗日对偶问题。问题（P）通常被称为原始问题，（D）是对偶问题。变量μ称为双变量。变量 如果g（μ）被定义为（不是g的最大值），则称其为双重可行的，我们称其为双重最优或最佳拉格朗日乘数。 自从 ， 函数g（礿）=infv∈Ωl（v，礿）是一些礿的仿射函数的点态中值，因此它是凹的，即使礿i不是凸的。与原始问题相比，对偶问题的一个主要优点是它是一个凸优化问题，因为我们希望最大化凹目标函数g（从而最小化−g，凸函数），并且约束μ≥0是凸的。在许多实际情况下，双函数g确实可以计算出来。 严格地说，我们应该提到，双函数g实际上是一个偏函数，因为当map v→7 l（v，μ）在下面无界时，它取−∞值。 实施例49.5。考虑线性规划（P） 使c>v最小化，以av≤b，v≥0为准， 其中a是m×n矩阵。约束v≥0重写为−vi≤0，因此我们引入拉格朗日乘数，我们得到拉格朗日 L（V，礹，礹）=C>V+礹>（AV−B）−礹>V =−b>礹+（c+a>礹礹）>v. 线性函数v 7→（c+a>μ−ν）>v在下面是无界的，除非c+a>μ−ν=0，所以双函数g（μ，ν）=infv∈rn l（v，μ，ν）是由以下公式给出的： ν+c=0， . G的域是的一个子集。 观察函数g的值g（祡），当它被定义时，独立于第二个参数。由于我们对最大化g感兴趣，这建议引入单参数μ的函数gb，由 GB（μ）=-B>μ， 它是为所有人定义的。 当然，sup）和sup）通常是不同的，但请注意 ）如果存在一些这样的情况，则a>μ−ν+c=0 iff a>μ+c≥0。因此，找到sup）相当于约束问题（d1） 最大化−b>μ受试者A>μ≥−c，μ≥0。 上述问题是线性规划（P）的对偶问题。 综上所述，初等问题（p）的对偶函数g通常包含定义其域的隐藏不等式约束，有时可以使这些域约束ψ1（μ）≤0，…，ψp（μ）≤0显式，以定义仅依赖于变量q<m的新函数gb。并定义了所有这些变量的值，用约束问题（d1）代替最大化问题（d），找到sup。 使gb（μ）最大化，以ψi（μ）≤0，i=1，…，p. 问题（d1）不同于双程序（d），但它相当于（d）的最大化问题。
49.8弱、强二元性 对偶函数g的另一个重要性质是它为目标函数j的值提供了一个下限。 g（μ）≤l（u，μ）≤j（u），对于所有u∈u和所有u，（†） 因为μ≥0和i（u）≤0，对于i=1，…，m，so . 如果原问题（p）有一个最小值表示p，而对偶问题（d）有一个最大值表示d，则上述不等式意味着 D≤P（†W） 被称为弱二元性。等价地，对于对偶问题的每一个最优解λ和原问题的每一个最优解u，我们得到 G（λ）≤J（U）。（†W0） 特别是，如果p=−∞，这意味着原始问题在下面是无界的，那么对偶问题是不可行的。相反，如果d=+∞，这意味着上面的对偶问题是无界的，那么原始问题是不可行的。 定义49.10.差P−D≥0称为最优对偶间隙。如果二元间隙为零，即p=d，那么我们说强二元性成立。 即使对偶间隙是严格正的，不等式（†w）也有助于找到一个初等问题的最优值的下界，这是很难解决的，因为对偶问题总是凸的。 如果原问题和对偶问题是可行的，并且最优值p和d是有限的，并且p=d（没有对偶间隙），那么互补松弛条件适用于不等式约束。 提案49.15。（互补松弛度）给定最小化问题（p） 最小化j（v） 以“i（v）≤0，i=1，…，m”为准， 它的双重问题（D） 最大g（μ） 从属于， 如果（p）和（d）都是可行的，u∈u是（d）的最优解，j（u）=g（λ），那么 . 换言之，如果约束i在u处无效，则λi=0。 证据。因为j（u）=g（λ），我们有 ！ 根据G的定义 ）最大下界是一个下界 ）由于λi≥0，因此i（u）≤0。 这意味着 回到例子49.5，我们看到弱对偶表示，对于原问题（p）的任何可行解u，也就是说，一些u∈rn这样 Au≤B，U≥0， 对于对偶问题（d1）的任何可行解，即： a>礹≥−c，礹≥0， 我们有 −B>祆≤C>U。 实际上，如果u和λ是最优的，那么我们从定理46.7中知道强对偶性成立，即−b>μ=c>u，但是这个事实的证明是不平凡的。 下面的定理建立了原问题（P）和对偶问题（D）解之间的联系。它也为二元间隙为零提供了充分的条件。 定理49.16。考虑最小化问题（P）： 最小化j（v） 以“i（v）≤0，i=1，…，m”为准， 其中，在有限维欧几里得向量空间v（更一般地说，是真实的希尔伯特空间v）的一些开子集Ω上定义了函数j和ξi。 （1）假设函数i:Ω→r是连续的，并且对于每个函数， 问题（pμ）： 使L（V，μ）最小化，以V∈Ω为准， 具有唯一的溶液uμ，使l（uμ，μ）=inf l（v，μ）=g（μ），v∈Ω 并且函数礹7→u礹是连续的（开）。那么函数g是可微的 对所有人，以及 全部ξ∈rm。 如果λ是问题（d）的任何解： 最大g（μ） 从属于， 则相应问题（pλ）的解uλ为问题（p）的解。 （2）假设问题（P）有一个解u∈u，且Ω为凸（开），函数i（1≤i≤m）和j在u处是凸的和可微的，并且约束是合格的。那么问题（d）有一个解，j（u）=g（λ）；也就是说，对偶间隙为零。 证据。（1）我们的目的是证明对于问题（d）的任何解λ，该对（uλ，λ）是L的鞍点，根据定理49.14（1），该点uλ∈u是问题（p）的解。 因为是问题（d）的解，由g（λ）的定义和uλ满足 问题（pλ），我们得到g（λ）=inf l（v，λ）=l（uλ，λ）， V∈Ω 这是表征鞍点的两个方程之一。为了证明表征鞍点的第二个方程， sup l（uμ，μ）=l（uλ，λ） 礿r+m 我们首先证明函数g是可微的，以便能够应用定理39.8得出结论，因为g在λ处有一个最大值，也就是说，−g在 最小值为λ，然后为0。事实上，我们证明了 ）全部ξ∈Rm.（导数） 考虑任何两点，μ和。根据u的定义，我们有 L（U礹，礹）≤L（U礹+ξ，礹） 也就是说 ，（1） 且Since）和g（μ+ξ）=l（uμ+ξ，μ+ξ）= ）我们有 .（2） 因为（1）可以写为 ， 通过在上述不等式的两边加上）并使用（2），我们得到 .（3） 根据uμ+ξ的定义，我们有 L（U祄+祄，祄+祄）≤L（U祄，祄+祄） 也就是说 .（4） 这可以写为 ， 通过对上述不等式的两边加上（2），我们得到 .（5） 通过把（3）和（5）放在一起，我们得到 .（6） 因此有一些θ∈[0,1]这样 . 因为根据假设，函数礹7→u礹（从至礹）和礹i:礹→r是连续的，对于任何我们都可以写 ，带LIM，（7） 对于任何k k标准的rm。方程（7）表明g对任何一个都是可微的，并且 ）全部ξ∈Rm.（8） 实际上，有一个小问题，即导数的概念是为一个在开放集上定义的函数定义的，但不是开放的。困难只出现在确保导数是唯一的，但是在我们的例子中，我们对导数有一个唯一的表达式，所以在定义导数方面没有问题。还有一个潜在的问题，那就是我们要应用定理39.8来得出结论，因为g在λ处有一个最大值，也就是说，−g在λ处有一个最小值，那么 0代表所有人，（9） 但定理39.8的假设要求函数的域是开放的。幸运的是，对定理39.8的证明的仔细研究表明，证明仍然成立。因此，（8）认为，定理39.8是有效的，这反过来意味着 全部为0，（10） 其中，使用（8）中给出的g0λ表达式得出 ，全部。（11） 由于（11），我们得到 ， 对所有人来说，那就是， L（uλ，μ）≤L（uλ，λ），全部，（12） 这意味着第二个不平等 sup l（u祄，祄）=l（u祄，祄） 礿r+m 说明（uλ，λ）是鞍点。因此，（uλ，λ）是L的鞍点，如权利要求所述。 （2）假设正好是定理49.14（2）所要求的假设，因此有一些假设（u，λ）是拉格朗日l的鞍点，根据定理49.14（1），我们得到j（u）=l（u，λ）。根据49.13号提案，我们 ， 可以重写为 j（u）=g（λ）=sup g（μ）。 礿r+m 换句话说，问题（d）有一个解，j（u）=g（λ）。 注：注意定理49.16（2）可能已经由定理49.14（2）得到，但对偶函数g尚未定义。如果（u，λ）是拉格朗日L（定义在Ω上）的鞍点，那么根据命题49.13，向量λ是问题（d）的解。相反，在定理49.16第（1）部分的假设下，如果λ是问题（d）的解，则（uλ，λ）是l的鞍点。因此，在上述假设下，对偶问题（d）的解集与在某种意义上，这个结果是定理49.14所述结果的“对偶”，即问题（p）的解集与l的鞍点（u，λ）的第一个参数集u相一致。 非正式地，在定理49.16（1）中，假设说，如果g（μ）可以“很好地计算”，在这个意义上，存在l（v，μ）（与v∈Ω）的唯一极小uμ，这样g（μ）=l（uμ，μ），并且如果可以确定g（μ）（与）的最大λ，则uλ产生j的最小值，也就是说，p=j（uλ）。如果约束是合格的，并且函数j和i是凸的和可微的，那么由于KKT条件成立，对偶间隙为零；即， g（λ）=l（uλ，λ）=j（uλ）。 实施例49.6。回到示例49.5，我们考虑了线性程序（P） 使c>v最小化，以av≤b，v≥0为准， 对于m×n矩阵，拉格朗日L（祆，ν）由下式得出： L（V，礹，礹）=-B>礹+（C+A>礹礹）>V， 我们发现双函数g（μ，ν）=infv∈rn l（v，μ，ν）是由 ν+c=0，g（，ν）= . 定理49.16（1）的假设当然失败了，因为存在无穷多的uμ，ν∈rn，使得g（祆，ν）=infv∈rn l（v，祆，ν）=l（uμ，ν，祆，ν）。因此，对偶函数G对于寻找原问题（P）的解没有帮助。正如我们前面所看到的，如果我们考虑修正对偶问题（d1），那么强对偶性成立，但这并不符合定理49.16，并且需要一个不同的证明。 因此，我们有一些反直觉的情况，即拉格朗日对偶的一般理论不适用于线性规划，至少直接适用于线性规划，这一事实在许多论述中没有得到充分强调。需要对二元性进行单独的处理。 与需要单独处理的线性规划不同，定理49.16适用于包含凸二次目标函数和一组仿射不等式约束的优化问题。所以在某种意义上，凸二次规划比线性规划简单！ 实施例49.7。考虑二次目标函数
其中a是对称正定的n×n矩阵，b∈rn，约束为形式的仿射不等式约束。 cv≤d， 其中c是m×n矩阵，d∈rm。目前，我们不假定c有秩m，因为a是对称正定的，j是严格凸的，正如命题所暗示的那样。 39.9（见示例39.1）。这个二次优化问题的拉格朗日由
由于a是对称正定的，根据命题41.2，函数v 7→l（v，μ）对于线性系统的解uμ具有唯一的最小值。 av=b−c>μ； 也就是说， Uμ=A−1（B−C>μ）。 这表明问题（pμ）有一个独特的解决方案，该解决方案持续依赖于μ。那么对偶问题的任何解λuλ=a−1（b−c>λ）都是原问题的最优解。 我们计算g（μ）如下：
因为a是对称正定的，所以矩阵ca-1c>是对称半正定的。由于a−1也是对称正定的，因此，μ>ca−1c>μ=0 iff（c>μ）>a−1（c>μ）=0 iff c>μ=0表示μ=0，也就是说，kerc>=（0），相当于im（c）=rm，即，如果c具有秩m（在这种情况下，m≤n）。因此，ca−1c>是对称正定的，iff c具有秩m。
在定理48.8之后，我们证明了函数v 7→（1/2）v>av是椭圆的，iff a是对称正定的，定理48.8证明了椭圆函数是强制的，这是定理48.4中使用的假设。因此，根据定理48.4，如果不等式cx≤d有解，则原问题有唯一解。在这种情况下，因此，根据定理49.16（2），函数−g（μ）总是有一个最小值，如果c具有秩m，则该最小值是唯一的。当c具有秩
49.9。显式处理等式约束，则问题（p）的最小uλ由下式给出： uλ=a−1（b−c>λ）。 如果c的秩小于m，那么我们可以通过求约束集为 −Ca−1c>祄+Ca−1b−d=0， 使用标准方法添加非负松弛变量ξ1，…，ξm和最大化−（ξ1+····+ξm）。 49.9明确处理平等约束 有时需要明确地处理平等约束（例如，博伊德和范登伯格就是这样做的，见[29]）。唯一的区别是，与等式约束相关联的拉格朗日乘数不需要是非负的，如我们现在所示。考虑优化问题（p 0） 最小化j（v） 以“i（v）≤0，i=1，…，m为准 ψj（v）=0，j=1，…，p. 我们将每一个等式约束ψj（u）=0视为不等式ψj（u）≤0和−ψj（u）≤0的连接，并将拉格朗日乘数关联起来。假设约束是合格的，根据定理49.5，KKT条件是 ， 和 ， 当λ≥0，ν+≥0，ν−≥0时。由于ψj（u）=0，对于j=1，…，p，这些方程可以改写为 ， 和
当λ≥0，ν+≥0，ν−≥0时，如果我们引入了νj=νj+−νj−我们得到了具有显式等式约束的程序的以下kkt条件： ， 和
当λ≥0且ν∈rp任意时。 现在我们假设函数i和ψj是凸的。正如我们刚刚在定义49.6之后所解释的那样，非财务平等约束永远都是不合格的。因此，为了将定理49.6推广到显式等式约束，我们假定等式约束ψj是仿射的。 定理49.17。设ωi:Ω→r为m凸不等式约束，ψj:Ω→r为p仿射等式约束，定义在有限维欧几里得向量空间v（更一般地说，是实希尔伯特空间v）的一些开凸子集Ω上，设j:Ω→r为某种函数，设u为 u=x∈Ωi（x）≤0，ψj（x）=0，1≤i≤m，1≤j≤p， 设u∈u为任意点，使得在u处函数i和j是可微的，函数ψj是仿射的。 (1) 如果j在u处对u有局部最小值，并且约束条件是合格的，则存在一些向量和ν∈rp，使得kkt条件成立： ， 和
同样，根据梯度，上述条件表示为
和
49.9。显式处理相等约束 (2) 相反，如果j对u的约束是凸的，并且存在向量，并且v∈rp使得kkt条件成立，那么函数j对u具有（全局）最小值。 问题（p 0）的拉格朗日L（v，λ，ν）定义为 ， 式中，式中v∈rp. 函数由
称为拉格朗日对偶函数（或对偶函数），对偶问题（d0）是 最大g（祡），以。 观察拉格朗日乘子v不限于非负。 定理49.14和定理49.16立即推广到问题（p 0）。我们只陈述了49.16的新版本，留下了49.14定理的新版本作为练习。 定理49.18。考虑最小化问题（p 0）： 最小化j（v） 以“i（v）≤0，i=1，…，m为准 ψj（v）=0，j=1，…，p. 其中，在有限维欧几里得向量空间V（更一般地说，是实希尔伯特空间V）的一些开子集Ω上定义了函数j，i，而函数ψj是仿射函数。 （1）假设函数_i:Ω→r是连续的，并且对于每个v∈r p，问题（p祆，ν）： 使L（V，礹，礹）最小化，以V∈Ω为准， 有一个独特的溶液u礹，使l（u礹，礹，礹）=inf l（v，礹，礹）=g（礹，礹），v∈Ω 并且函数（μ，ν）7→uμ，ν是连续的（在所有和所有的可微上），并且
）那么函数g是
对于所有ξ∈Rm和所有ζ∈Rp。 如果（λ，η）是问题（d）的任何解： 最大g（礹，礹） 从属于， 则相应问题（pλ，η）的解uλ，η为问题（p 0）的解。 （2）假设问题（p 0）有一个解u∈u，且Ω是凸的（开的），函数i（1≤i≤m）和j是凸的，在u处可微，并且约束是合格的。那么问题（d0）有一个解，j（u）=g（λ，η）；也就是说，对偶间隙为零。 在下一节中，我们推导了第49.6节（硬边值支持向量机）优化问题的对偶函数和对偶程序，它同时包含不等式和等式约束。我们还导出了与双程序相关的KKT条件。 49.10硬边支持向量机的对偶 回想一下硬边界SVM问题（SVMH2）： 最小化
我们分六步进行。 第一步：用矩阵形式写约束。 不等式约束写为
第49.10条。硬边支持向量机的对偶，其中c是（p+q）×（n+1）矩阵c，d∈rp+q是由 . 如果x是n×（p+q）矩阵，由 ， 然后 如此 第二步：用矩阵形式写出目标函数。 目标函数由 . 注意，对应的矩阵是对称的半正定矩阵，但它不可逆。因此，函数j是凸的，但不是严格凸的。 第三步：用矩阵形式写拉格朗日。 如例49.7所示，我们得到拉格朗日 ， 也就是说， . 步骤4：找到双函数g（λ，μ）。 为了找到对偶函数g（λ，μ），我们需要使l（w，b，λ，μ）对w和b最小化，为此，由于目标函数j是凸的，并且由于rn+1是凸的和开的，我们可以应用定理39.11，它给出了求最小值的必要和充分条件。L（w，b，λ，μ）相对于w和b的梯度为
最小值的必要和充分条件是 lw，b=0， 会产生 （1） 和 .（2） 第二个方程可以写为 .（3） 将w从（1）插回拉格朗日，使用（2）我们得到 ；（4） 当然。实际上，严格的g（λ，μ）只在方程的超平面与由λ≥0，μ≥0给出的Rp+Q中的凸八分之一的交集上定义，因此对于所有的情况，我们都有
−∞否则。 注意条件 PQ 十倍 λi=μj i=1 j=1 是实施例49.6的条件（2），这并不奇怪。 第49.10条。硬边支持向量机的对偶 第五步：以矩阵形式编写双程序。 在定义域上最大化双函数g（λ，礹）等同于受约束的最大化。 PQ 十倍 λi=μj，i=1 j=1 因此，我们将双方案制定为： 最大化受试者
或者等价的， 最小化 PQ 十倍 λi=μj i=1 j=1 λ≥0，μ≥0。 双程序的约束比约束简单得多。
因为这些约束已经被包含矩阵x>x的对偶程序的目标函数gb（λ，ν）“吸收”，矩阵x>x是对称的半正定的，但一般不可逆。 第六步：解决双方案。 此步骤涉及使用通常基于梯度下降的数值程序来查找λ和μ。一旦确定了λ和μ，w由（1）确定，b根据第49.6节中的事实确定，其中至少存在一些i0，以便λi0>0和一些j0，以便μj0>0。 评论： (1) 由于约束是仿射的，目标函数是凸的，根据定理49.18（2），对偶间隙为零，因此对于j（w，b）=（1/2）w>w的任何最小w和g的任何最大（λ，μ），我们得到 . 但是（1） ， 所以 我们得到 ， 所以 ， 会产生 上述公式见Vapnik[176]（第10章第1节）。 (2) 计算对偶程序的拉格朗日，推导该拉格朗日的KKT条件，具有一定的指导意义。 等价于条件−ρ霏λ≤≥R00，引入拉格朗日乘子作为等式约束，形成等价于−λ≤0的拉格朗日，条件及霏0as福利 作为乘数 . 因此，KKT条件是 ，（4）
对于i=1，…，p和βj，μj=0，对于j=1，…，q。
但是（4）等于
，
这正是将α≥0和β≥0作为松弛变量添加到实施例49.6的不等式（3）中的结果，即
，
使它们相等，其中ρ起b的作用。
当约束为仿射时，对偶函数g（λ，ν）可以用目标函数j的共轭表示。
49.11共轭函数和勒让德对偶函数
共轭函数的概念可以追溯到勒让德，在古典力学中将拉格朗日函数转化为哈密顿函数中起着重要作用；见阿诺德[5]（第3章，第14和15节）。
定义49.11.设f:a→r是在rn的某个子集a上定义的函数。函数f的共轭f是由定义的偏函数f：rn→r。
.
当f可微时，函数的共轭也被称为费歇尔共轭或勒让德变换。
作为y中仿射函数族的点态上确界，共轭函数f是凸的，即使原函数f不是凸的。根据F的定义，我们有
f（x）+f（y）≥hx，yi=x>y，
无论何时定义左侧。以上就是费歇尔不等式（如果f是可微的，则称为杨氏不等式）。
如果f:a→r是凸的（所以a是凸的），如果epi（f）是闭合的，那么可以证明f=f。特别是，如果a=rn，这是真的。
F的域可以很小，即使F的域很大。例如，如果f:r→raxis，那么−b给出的仿射函数在unlessf（xy）==a a x上是无界的，所以+b（a，b∈r），那么函数x→7 yx−
f（y）=（-b，如果y=a
+∞否则。
f的域也可以大于f的域；参见示例49.8（3）。
在优化中出现的许多函数的共轭在Boyd和Vandenberghe中得到；见[29]第3.3节。我们提到了一些将在本章中使用的内容。
实施例49.8。
(1) 如果其导数为零，则称为负对数：f（x）=−logx，其中dom（y≥0，whenf）=y
因此，如果Kykd>1，最后一项变为+∞，但如果Kykd≤1，则其最大值为0。 一 . (7) 范数平方：d表示Rn上的任何范数k k，其中dom（f）=Rn。自从 | Y>X≤KXKKYK，我们有 Y>X−（1/2）KXK2≤KYKD KXK−（1/2）KXK2。 右侧是d 2 kxk的二次函数，在kxk=kyk时达到最大值，最大值为（1/2）（kyk）。因此
对于所有的x，这表明 . 根据对偶范数的定义，由于单位球是紧的，对于任何y∈rn，都有一些ykd x∈rn，使得kxk=1，y>x=kykd，所以两边乘以 k我们得到
对于z=kykd x，因为kxk=1，我们有kzk=kykd kxk=kykd，所以我们得到 ， 这表明达到了上限（1）。因此， ， 和dom（f）=rn。 (8) 对数和表达式函数：，其中x=（x1，…，xn）∈rn。为了确定得到g（x）=y>x−f（x）在x∈r上的最大值的n y∈rn的值，我们计算了它的梯度，发现 . 因此，（y1，…，yn）必须满足方程组 （三） 条件=1显然是必要的，条件y i>0对于i=1，…，n也是必要的。相反，如果1>y=1和y>0，那么xj=logyi对于i=1，…，n是一个解。因为（）意味着 ，（） 我们得到 作者（） 因为。 因此，如果定义了f（y），那么。如果我们同意0log0= 0，那么这是一个简单的练习（或者，参见Boyd和Vandenberghe[29]，第3.3节，示例3.25），证明 如果1>y=1且y≥0 ∞否则。 因此，我们得到了限制在域1>y=1和y≥0的负熵。 如果f:rn→r是凸的且可微的，那么x最大化x>y−f（x）iff x最小 −x>y+f（x）iff fx=y， 所以f（y）=（x）>fx−f（x）。因此，如果我们能解出这个方程 fz=y 对于z给定y，则我们得到f（y）。 可以证明，如果f是二次可微的，严格凸的，超线性的，这意味着 ， 然后有一个唯一的xy，这样fxy=y，所以 ， f与 . 现在我们回到优化问题。提案49.19。考虑问题（p） 使j（v）最小化，以av≤b为准 cv=d， 带仿射不等式和等式约束（带∈Rm，D∈Rp）。双函数g（λ，ν）由m×n矩阵、c、p×n矩阵给出。 G（λ，ν）=（−b>λ−d>ν−j（−a>λ−c>ν）如果−a>λ−c>ν∈dom（j）， −∞否则， 对于全部和全部，其中j是j证明的共轭。与上述程序相关联的拉格朗日是
定义为with和ν∈rp. g（λ，ν）=−b>λ−d>ν+vinf∈rn（j（v）+（a>λ+c>ν）>v）=−b>λ−d>ν−vsup∈rn（−（a>λ+c>ν）>v−j（v）） =−b>λ−d>ν−j（−a>λ−c>ν）。 因此，对于所有v∈rp，我们有 G（λ，ν）=（−b>λ−d>ν−j（−a>λ−c>ν）如果−a>λ−c>ν∈dom（j）， −∞否则， 如要求。 作为49.19号提案的应用，请考虑以下例子。 实施例49.9。考虑以下问题： 最小化kvk，以av=b为准， 其中k k是RN的任何规范。利用实例49.8（6）的结果，我们得到 ， 也就是说， D g（ν）=≤1 . 在k k=k k2的特殊情况下，我们也有k kd=k k2。 另一个有趣的应用是熵最小化问题。 实施例49.10。考虑以下被称为熵最小化的问题： 减少 以ax≤b为准 1>x=1， 式中dom（f）=x∈rn x≥0。通过例子49.8（3），负熵函数ulogu的共轭为ev−1，因此我们很容易看到 ， 在RN上定义。命题49.19暗示熵最小化问题的对偶函数g（λ，μ）由下式给出： ， 程序是：对于所有和所有的∈r，其中ai是a的第i列，它遵循对偶 最大化以λ≥0为准。 我们可以通过在变量上最大化来简化这个问题，对于固定的λ，当导数为零时，目标函数最大化，也就是说， ， 会产生 . 通过将上述值插回对偶的目标函数，我们得到以下程序： 最大化以λ≥0为准。 熵最小化问题是定理49.17适用的另一个问题，因此可以用对偶程序来解决。实际上，原始程序的拉格朗日由 . 利用凸性的二阶导数准则，我们发现L（x，λ，μ）严格凸于且在其下有界，因此它有一个唯一的最小值，该最小值是通过将梯度lx设置为零得到的。我们有
因此，通过将lx设置为0，我们得到
Xi= E-（（an）＞La~（+）+ 1），i＝1，…，n（*）
根据定理49.17，由于目标函数是凸的，并且约束是仿射的，如果原始函数有一个解，那么对偶也有一个解，并且λ和μ构成了对偶的最优解，那么（）中方程给出的x=（x1，…，xn）是原始函数的最优解。
Boyd和Vandenberghe给出了其他示例；见[29]第5.1.6节。
从第49.5节推导问题的对偶函数（SVMH1）涉及一种类似的推理。
实施例49.11。考虑硬利润问题（SVMH1）：
最大化δ
从属于
w>ui−b≥δ−w>vj+b≥δ i=1，…，p j=1，…，q
kwk2≤1，
转换为以下最小化问题：
最小化−2δ
从属于
我们用2δ替换了δ，因为这样可以更容易地找到一个很好的几何解释。回想49.5节，问题（svmh1）有一个最优解iffδ>0，在这种情况下kwk=1。 对应的拉格朗日函数是
接下来要找到双函数g（λ，μ，γ），我们需要将l（w，b，δ，λ，μ，γ）对w，b和δ最小化，因此它对w，b和δ的梯度必须为零。这意味着 ， 会产生 . 注意，我们没有计算关于w的偏导数，因为它不会由于kwk2这个术语的存在而产生任何有用的信息（而不是 我们的最小化问题归结为： ！ 如果 示例49.8（6）−∞否则 =自且γ>0 当γ=0时，立即验证上述公式仍然正确。因此 G（λ，μ，γ）= 从那时起，双重职业- 2 2克，最大g（λ，μ，γ）等于 最大化受试者 ，
第49.12条。获得更有用的双程序的一些技术 等价的 最小化 . 几何上，with=1且λ≥0是uis的凸组合，=1且μ≥0是vjs的凸组合，因此对偶程序是最小化多面体conv（u1，…，up）（uis的凸壳）和多面体conv（v1，…，vq）（凸壳在VJ中）。由于两个多面体都是紧凑的，因此两者之间的距离最短。实际上，有一些顶点ui，如果p（ui）是它在conv（v1，…，vq）上的投影（hilbert空间理论存在），那么线段的长度（ui，p（ui））是两个多面体之间的最短距离（同样，也有一些顶点vj，如果p（vj）是它的投影。作用于conv（u1，…，up），则线段的长度（vj，p（vj））是两个多面体之间的最短距离。 如果两个子集是可分离的，在这种情况下，问题（svmh1）有一个最优解δ>0，因为目标函数是凸的，凸约束kwk2≤1是合格的，因为δ可能是负的，根据定理49.16（2），对偶间隙为零，因此δ是最小距离赌注的一半在两个凸多面体conv（u1，…，up）和conv（v1，…，vq）之间；见图49.19。 需要注意的是，约束kwk≤1给出了对偶问题的一个公式，该公式具有良好的几何解释的优势：找到凸多面体conv（u1，…，up）和conv（v1，…，vq）之间的最小距离。不幸的是，这个公式对于实际解决这个问题并不有用。然而，如果使用等效约束kwk2（=w>w）≤1，那么对偶问题作为求解工具更有用。 在第54章中，我们考虑了点集u1，…，up和v1，…，vq不可线性分离的情况。 49.12获得更有用的双重计划的一些技术 在某些情况下，重新表述原始优化问题以获得更有用的对偶问题是有利的。Boyd和van提出了三种不同的重组方案。-
图49.19：在r2中，uis的凸面外壳，即蓝色六边形，与vjs的凸面外壳（即红色正方形）分离，通过紫色超平面（线），紫色超平面（线）是ui和v1之间蓝色线段的垂直平分线，其中蓝色线段是最短的di。两个凸多边形之间的站姿。 登堡；见[29]第5.7节： (1) 引入新变量和相关的等式约束。 (2) 将目标函数替换为原始函数的递增函数。 (3) 使显式约束隐式化，即将它们合并到目标函数的域中。 我们只提供（1）和（2）的插图，并请读者参考Boyd和Vandenberghe[29]（第5.7节）了解更多这些技术的示例。考虑无约束程序： 最小化f（ax+b） 其中a是m×n矩阵，b∈rm。当满足零对偶间隙的条件时，拉格朗日是 L（x）=F（ax+b） 所以对偶函数g是一个常数函数，其值为 g=inf f（ax+b），x∈rn 这根本没用。 第49.12条。获得更有用的双程序的一些技术 让我们把问题重新表述为 最小化f（y）取决于 ax+b=y， 引入了新变量y∈rm和等式约束ax+b=y，这两个问题显然是等价的。重新表述问题的拉格朗日是 L（x，y，μ）=f（y）+μ>（ax+b−y） 式中，μ∈Rm。为了找到双函数g（μ），我们将x和y上的l（x，y，μ）最小化。将x上的l（x，y，μ）最小化，我们看到g（μ）=-∞除非a>μ=0，在这种情况下，我们只剩下 g（μ）=b>μ+inf（f（y）−μ>y）=b>μ−inf（μ>y−f（y））=b>μ−f（μ）， Y 式中，f是f的共轭形式，因此双程序可以表示为 最大化b>μ−f（μ）取决于 a>μ=0。 这种对偶公式比原程序的对偶公式更有用。 实施例49.12。作为一个具体的例子，考虑以下无约束程序： 减少 其中，ai是rn中的列向量。我们通过引入新的变量和等式约束重新表述问题，如下所示： 减少 从属于 ax+b=y， 其中a是n×n矩阵，其列为向量ai和b=（b1，…，bn）。由于通过示例49.8（8），对数和表达式函数的共轭为 如果1>礹=1且礹≥0，否则， 重新表述的问题的对偶可以表示为 最大化 从属于 1>μ=1 a>μ=0μ≥0， 熵最大化问题。 例49.13。同样的无约束范数最小化问题 最小化kax−bk， 其中k k是rm上的任何范数，具有一个常数的对偶函数，并且不有用。这个问题可以重新表述为 最小化KYK 从属于 ax−b=y。 通过实施例49.8（6），范数的共轭由下式给出： Kyk=（+0∞如果其他Kykd≤，1 因此，重新制定的计划的双重目标是： 最大化b>μ受试者 Kµkd≤1 a>μ=0。 下面是（2）的一个例子，用原始函数的递增函数替换目标函数。 实施例49.14。实施例49.13的最小范数可以重新表述为 最小化 ax−b=y。
这个程序显然等同于原来的程序。通过实施例49.8（7），平方范数的共轭由下式给出： ， 因此，重新制定的计划的双重性是 最大化受试者 a>μ=0。 请注意，该对偶与实施例49.13中获得的对偶不同。 例49.13中的对偶程序的目标函数是线性的，但我们有非线性约束kμkd≤1。另一方面，例49.14的对偶程序的目标函数是二次的，而其约束是仿射的。我们有其他的例子来权衡程序（svmh2）（二次目标函数，仿射约束）和（svmh1）（线性目标函数，一个非线性约束）。 有时，用该约束的递增函数替换约束也很有帮助；例如，使用约束1而不是kwk2≤1。 在第52章中，我们从不同的角度重新讨论了解决第一卷第21.1节中考虑的超定或欠定线性系统ax=b的问题。 49.13 Uzawa方法 让我们回到最小化问题上来。 最小化j（v） 以“i（v）≤0，i=1，…，m”为准， 其中，在有限维欧几里得向量空间v（更一般地说，是真实的希尔伯特空间v）的一些开子集Ω上定义了函数j和ξi。像往常一样，让 u=v v i（v）≤0，1≤i≤m。 如果函数j满足命题48.18的不等式，并且如果函数_i是凸的，理论上投影梯度法收敛到j在u上的唯一极小值。不幸的是，通常不可能计算投影图pu:v→u。另一方面，拉格朗日对偶函数的域 ， 在哪里？
是我们问题的拉格朗日。现在投影P+来自非常简单，即 （p+（λ））i=最大λi，0，1≤i≤m。 因此，投影梯度法应适用于对偶问题（d）： 最大g（μ）取决于。 如果定理49.16的假设成立，则对偶程序（d）的解λ产生原问题的解uλ。 Uzawa方法本质上是一种固定步长的梯度法，适用于对偶问题（D）。然而，它被设计来产生一个原始问题的解决方案。 Uzawa的方法： 给定一个任意的初始向量k∈v。构造了两个序列（λk）k≥0和（uk）k≥0，用和u 假设已知λ0，λ1，…，λk，则Uk和λk+1的确定如下：Uk是最小化问题的唯一解，求Uk∈v这样 和 其中，ρ>0是适当选择的参数。 回想一下，在定理49.16的证明中，我们证明了（导数），即 ， 这意味着（gλk）i=i（英国）。则（uz）中的第二个方程对应于梯度投影步骤λk+1=p+（λk+ρgλk）。 请注意，因为问题是最大化问题，所以我们使用正符号而不是负符号。Uzawa的方法确实是一种梯度法。 基本上，Uzawa方法将约束优化问题替换为一系列包含（原始）问题拉格朗日的无约束优化问题。 有趣的是，在某些假设下，可以证明近似解（k）k≥0的序列不收敛。当约束k）k≥0在u上收敛到j的极小u时，我们证明了这一结果，即使序列ωi是仿射的。 （% 定理49.20。假设j:rn→r是一个椭圆函数，这意味着j在rn上是连续可微的，并且有一些常数α>0，这样 h jv−ju，v−ui≥αkv−uk2，对于所有u，v∈rn， 而u是一个非空闭凸子集，由 u=v∈rn cv≤d， 其中c是实m×n矩阵，d∈rm。如果标量ρ满足条件 ， 当kck2是c的谱范数时，Uzawa方法计算的序列（u k）k≥0收敛到j的唯一极小u∈u。 此外，如果c有秩m，则序列（λk）k≥0收敛到对偶问题（d）的唯一最大化子。 证明。 第1步。我们建立了J在U上的唯一极小u∈u的代数条件，其中（u，λ）是一个鞍点。 由于j是椭圆的，u是非空闭凸的，根据定理48.8，函数j是严格凸的，因此它有一个唯一的极小值u∈u。由于j是凸的，约束是仿射的，根据定理49.16（2），对偶问题（d）至少有一个解。根据定理49.14（2），有一些（u，λ）是拉格朗日L的鞍点。 ⑨（v）=（（v），…，m（v））=cv-d， 那么拉格朗日L（v，μ）可以写成 . 自从 l（u，λ）=inf l（v，λ），v∈rn 根据定理39.11（4），我们必须 ju+c>λ=0，（1） 从那以后 g（λ）=l（u，λ）=sup l（u，μ）， 礿r+m 根据定理39.11（3）（由于函数g的最大化等价于−g的最小化），我们必须 0代表所有人， 如前所述，gλ=（u），我们得到 h（u），μ−λi≤0（2） 如第48.18号提案的证明中所述，（2）可表示为每ρ>0： hλ−（λ+ρ（u）），所有的μ−λi≥0，（2） 这表明，可以将λ视为矢量λ+ρⅧ（u）上的投影。总之，我们得到了方程 . 第2步。我们建立了乌扎瓦方法在（uz）和λk迭代过程中出现的最小化问题的唯一解Uk的代数条件。 观察拉格朗日L（v，μ）作为v的函数（严格凸函数和仿射函数之和）是严格凸的。在定理48.8（1）的证明中，使用柯西-施瓦兹，我们有 ， 当kvk趋向于＋∞时，这个项变为＋∞，所以 L（V，μ）是V的强制函数。因此，最小化问题发现UK这样
有一个独特的解决方案UK∈RN。根据定理39.11（4），矢量Uk必须满足方程 juk+c>λk=0，（3） 从乌扎瓦方法的定义来看 λk+1=p+（λk+ρ_（uk）），（4） 我们得到了方程 . 第3步。通过减去（†1）和（†2）的两个方程中的第一个，我们得出 juk−ju+c>（λk−λ）=0， 通过减去（†1）和（†2）两个方程中的第二个方程，并使用命题47.6，我们得到 . 总之，我们证明了 . 第4步。序列（u k）k≥0到u的收敛性。 将（†）中不平等的两边平方，我们得到 . 使用（†）中的方程和不等式 ， 我们得到
因此，如果 ， 我们有 ，对于所有k≥0.（5） 通过（5），序列（是不递增的，并且在0以下有界，因此它- Verges，这意味着 ， 从那以后 ， 我们也有 . 所以如果 然后是0，我们得出结论 ， 也就是说，序列（u k）k≥0收敛于u。 第5步。如果c有秩m，则序列（λk）k≥0到λ的收敛性。 由于序列（是非递增的，因此序列（λk）k≥0是有界的，因此它有一个收敛子序列（λi（k））i≥0，其极限是一些。由于j0是连续的，到（†2），我们已经 ju+c>λ0=lim（jui（k）+c>λi（k））=0.（6）i7→∞ 如果c的秩为m，则im（c）=rm，相当于ker（c>）=（0），因此c>是内射的，因为（†1）我们也有ju+c>λ=0，我们得出λ0=λ的结论。上述推理适用于（λk）k≥0的任何子序列，因此（λk）k≥0收敛于λ。在特殊情况下，其中j是椭圆二次函数 ， 其中a是对称正定的，通过（†2）uzawa方法的迭代给出 auk−b+c>λk=0λki+1=最大（λk+ρ（cuk−d））i，0，1≤i≤m。定理49.20表示，如果 ， 式中，λ1是 如果我们用第一个方程来求解英国，我们得到 λk+1=p+（λk+ρ（−ca−1c>λk+ca−1b−d））（7） 在示例49.7中，我们证明了双函数g的梯度由下式给出： g礹=cu礹−d=−ca−1c>礹+ca−1b−d， 因此（7）可以写成λk+1=p+（λk+ρgλk）； 由此可见，Uzawa方法确实是一种固定步长的梯度法，适用于双程序。
第49.14条。总结 49.14总结 本章的主要概念和结果如下： • 可行方向的圆锥体。 • 圆锥体具顶点。 • 活动和非活动约束。 • 美国的限制条件。 • 法卡斯·莱玛。 • Farkas–Minkowski Lemma。 • 卡鲁什-库恩-塔克最优条件（或KKT条件）。 • 补充松弛条件。 • 广义拉格朗日乘子。 • 限定凸约束。 • 极小问题的拉格朗日。 • 等式约束最小化。 • KKT矩阵。 • 具有等式约束的牛顿方法（可行起点和不可行起点）。 • 硬边支持向量机 • 培训数据 • 线性可分离的点集。 • 最大边缘超平面。•支持向量 • 鞍点。 • 拉格朗日对偶函数。 • 拉格朗日双程序。 • 二元性差距。 • 弱二元性。 • 强大的二元性。 • 处理拉格朗日方程中的相等常数。 • 硬边SVM（SVMH2）的对偶。 • 共轭函数和勒让德对偶函数。 • 硬边双SVM（SVMH1）。 • 乌扎瓦的方法。
若有收获，就点个赞吧
0 人点赞
