最优化模型与算法-基于Python实现 教案 ch04 对偶理论

对偶理论1．考虑如下优化问题 (4.5.1)其中变量。(1)分析原问题，给出可行集、最优值以及最优解。(2)画出目标函数关于的图像，并在图像上画出可行集、最优值以及最优解。画出时，Lagrange函数关于的图像，验证下界性质：对成立。推导并画出Lagrange对偶函数。（1）找出可行集：要使约束条件成立，需要满足(x-1)(x-5)≤0。这意味着x的取值范围为[1,5]。求解最优值：我们需要找到在可行集内使目标函数最小的点。首先，我们可以计算目标函数的导数：f'(x)=2x-2。将其置零求解：2x-2=0，得到x=1。检查临界点和可行集边界上的目标函数值：当x=1时，f(x)=1²-2(1)+1=0。确定最优解：目标函数在x=1处取得最小值，满足约束条件(x-1)(x-5)≤0。因此，可行集为[1,5]，最优值为f(x)=0，在x=1处取得最小值。综上所述，原问题的可行集为[1,5]，最优值为0，在x=1处取得最优解。（2）略。2．考虑如下凸分段线性函数最小化问题 (4.5.2)其中变量。(1)考虑等式问题 (4.5.3)其中变量，推导出Lagrange对偶问题。(2)将分段线性问题(4.5.1)表述为LP问题并写出LP问题的对偶问题。将LP对偶与(1)中所求得的对偶问题联系起来。（1）略。（2）略。3．设有若干二分类问题的观测样本，考虑线性支持向量机模型： (4.5.4)其中，为参数，为样本点的经验损失，对应于Hinge损失函数，函数为判别函数。(1)将线性支持向量机模型化为凸二次规划模型，并写出该规划模型的对偶问题；(2)结合凸二次规划模型的最优性条件，说明哪些样本对模型起作用，哪些不起作用.(1)将线性支持向量机模型化为凸二次规划模型，并写出该规划模型的对偶问题：我们可以将线性支持向量机模型写成如下的凸二次规划形式：minimize1/2||w||²+C∑i=1^mξisubjecttoyi(w'xi+b)≥1-ξi,i=1,2,...,mξi≥0,i=1,2,...,m其中，变量为w∈R⁴，b∈R，ξi≥0，i=1,2,...,m。对应的拉格朗日函数为：L(w,b,ξ,α,μ)=1/2||w||²+C∑i=1^mξi-∑i=1^mαi[yi(w'xi+b)-1+ξi]-∑i=1^mμiξi其中，αi≥0，i=1,2,...,m，μi≥0，i=1,2,...,m是拉格朗日乘子。接下来，我们需要对拉格朗日函数进行最小化来得到对偶问题。首先，对w、b和ξi分别求导数并令其等于零，得到：∂L/∂w=w-∑i=1^mαiyixi=0，解得w=∑i=1^mαiyixi∂L/∂b=-∑i=1^mαiyi=0，解得∑i=1^mαiyi=0∂L/∂ξi=C-αi-μi=0，解得αi+μi=C，且αi≥0，μi≥0，i=1,2,...,m将上述结果代入拉格朗日函数，得到对偶问题：maximizeL(w*,b*,α)=∑i=1^mαi-1/2∑i=1^m∑j=1^mαiαjyiyjxi'xjsubjectto∑i=1^mαiyi=0,αi≥0,i=1,2,...,m其中，w*=∑i=1^mαiyixi，b*=yi-w'xi(其中i是任意一个满足αi>0的样本点)，变量为α∈Rⁿ，n为样本数。注意，这是一个凸二次规划问题，而且这个问题的解又可以用来求解原始问题中的最优解。(2)结合凸二次规划模型的最优性条件，说明哪些样本对模型起作用，哪些不起作用。根据凸二次规划模型的最优性条件，我们可以得出以下结论：对于所有的正常样本（即yi=+1的样本），当其对应的Lagrange乘子αi>0时，它们将成为决策边界上的支持向量。对于所有的负样本（即yi=-1的样本），当其对应的Lagrange乘子αi>0时，它们也将成为决策边界上的支持向量。对于那些满足0<αi<C的样本，它们不在决策边界上，但会被误分类点所影响，并且起到一定的支持作用。对于那些对应的Lagrange乘子αi=0的样本，它们既不在决策边界上，也不对支持向量产生影响。对于那些对应的Lagrange乘子αi=C的样本，它们可能是异常样本或噪音点。因此，模型中仅有支持向量对模型起作用，非支持向量则不需要考虑。同时，异常样本或噪音点可能会干扰模型的训练，需要特别处理。4．通过引入新变量以及等式约束，推导出下式的对偶问题 (4.5.5)其中。略。5．考虑Lasso模型 (4.5.6)其中，假设模型有唯一解，证明该模型的最优解关于是分片线性的。略。6．考虑QCQP问题 (4.5.7)其中变量。(1)写出最优点和最优值。(2)写出KKT条件。(3)求解Lagrange对偶问题，并说明强对偶性是否成立。(1)最优点x和最优值P：最优点x为(x₁,x₂)=(2,1)，最优值P为2。(2)KKT条件：KKT条件是解凸优化问题的一组必要条件。对于该问题，KKT条件如下：a.平稳性条件（StationarityCondition）：∇f(x)+∑ᵢλᵢ∇hᵢ(x)+∑ⱼμⱼ∇gⱼ(x)=0其中，∇f(x)表示目标函数f(x)关于变量x的梯度；∇hᵢ(x)表示约束条件hᵢ(x)关于变量x的梯度；∇gⱼ(x)表示不等式约束条件gⱼ(x)关于变量x的梯度；λᵢ和μⱼ分别是约束条件hᵢ(x)和gⱼ(x)对应的拉格朗日乘子。b.约束条件满足性条件（PrimalFeasibility）：hᵢ(x)≤0，i=1gⱼ(x)≤0，j=1,2c.对偶互补条件（DualComplementarity）：λᵢ≥0，μⱼ≥0λᵢhᵢ(x)=0，i=1μⱼgⱼ(x)=0，j=1,2d.KKT对偶互补条件（ComplementarySlackness）：λᵢ(hᵢ(x)+0)=0，i=1μⱼ(gⱼ(x)+0)=0，j=1,2(3)求解Lagrange对偶问题和强对偶性说明：根据最优值P的定义，我们可以得到Lagrange函数：L(x,λ,μ)=f(x)+∑ᵢλᵢhᵢ(x)+∑ⱼμⱼgⱼ(x)对于原始问题的约束条件hᵢ(x)≤0(i=1)和gⱼ(x)≤0(j=1,2)，可以分别引入拉格朗日乘子λ₁和μ₁、μ₂。根据Lagrange函数，我们可以得到Lagrange对偶问题：maximizeD(λ,μ)=min_xL(x,λ,μ)subjecttoλ₁≥0,μ₁≥0,μ₂≥0将原始问题代入Lagrange函数，可以得到：L(x,λ,μ)=(x₁²+x₂³-4)+λ₁[(x₁-1)²+(x₂-1)²-4]+μ₁(-x₁)+μ₂(-x₂)最小化Lagrange函数相当