关於 KKT 2 λg(x) = 0 我想在补充一个例子...可以让大家对 KKT 更有直觉一点 前面已经举过 Example1: min x s.t. x^2 - 4 <= 0 在这个例子中 最小值发生在 x = -2 ; 在该点上 λ =/= 0; g(x) = 0 Example2: min x^2 s.t. x^2 - 4 <= 0 直观上可以看出...最小值发生在 x = 0 该点同时也是 min x^2 无限制条件的解 因此...直觉上，就可以感觉得出来 λ 应该要是 0 在 x = 0 点上 λ = 0 ; g(x) =/= 0 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 到此，大家可以想想看... 有没有怎样的例子中...λ会等於0 而且 g(x) 也会等於 0 呢？ 不妨试试看 Example3: min (x-2)^2 s.t. x^2 - 4 <= 0 把限制式拿掉 可以看到 min (x-2)^2 的解...就正好在 x = 2 而 x = 2 这点...也刚好在 g(x) 的边界上 ！！！ 大家可以试着算算看...说不定可以获得一些感觉 希望这三个例子，可以帮助大家对於 KKT 能有更进一步的认识！ ※ 引述《Cayley (水色天蓝)》之铭言： : 其实 RAINDD 讲得很对 : λ的正负号...扮演着极为重要的角色！！ : 简单的尝试看看这题就知道了： : min x : s.t. x^2 - 4 < = 0 : 很值观可以看得出来 : 最大值在 x = 2 最小值在 x = -2 : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : min f(x) : s.t. g(x) < = 0 : 的 KKT Condition 有三组: : (1) dL/dx = 0 : (2) λg(x) = 0 : (3) λ > = 0 : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : 套用到例题中： : f(x) = x : g(x) = x^2 - 4 : L(x) = x + λ( x^2 - 4 ) : (KKT 1) dL/dx = 1 + 2λx = 0 : => x = -1/(2λ) : (KKT 2&3) : λg(x) = 0 => : Case1 : : λ= 0 (内点) & g(x) =/= 0 : λ = 0 => x = -1 / 0 (不存在 / 或是说，超越了 g(x)<0 的限制范围) : (不过，眼尖的人应该不难发现，这个 x = -1/0 = -Inf : 这...正好是无限制条件下 min x 的正解...从这边也可以看出 : 当 λ = 0 时...所解出来的...就正好会是无限制条件的状况...) : Case2 : : λ>0 (边界撞到) & g(x) = 0 : 所以可以把 x = -1/(2λ) 带入 g(-1/(2λ)) = 0 : 可以解出 λ = 1/4 or -1/4 : 分别对应到 x = -2 or 2 : 刚好一个是最大值一个是最小值！ : 这不是巧合...不然 KKT 就不用加上第三条要求 λ > = 0 了 : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : 如果把题目换一换 : min x^2 : s.t. x^2 - 4 < = 0 : L(x) = x^2 + λ( x^2 - 4 ) : (KKT 1) dL/dx = 2x + 2λx = 2x(1+λ) = 0 : => x = 0 or λ = -1 : (KKT 2: λg(x) = 0 ) 告诉我们 : Case1 : : 如果 x = 0 : => g(0) = -4 =\= 0 : => λ = 0 (这代表...在g(x) <= 0 的内点，不在边界) : Case 2: : 如果 λ = -1 =\= 0 (这代表...撞到 g(x) 的边界...不再内点...) : 则 g(x) = 0 => x = 2 or -2 : 事实上...这两个点都是最大值 而非题目要的 最小值！！ : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : 在这两个例子中，我们可以很清楚地感觉到 λ 所扮演的角色 : 当 λ = 0 的时候，就代表 g(x) < = 0 这个限制 : 并不会影响到 f(x) 求极值 : 而当 λ =\= 0 的时候...就代表限制式产生了一些影响力 : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : 真正的解读上...可以从两个方向来思考 : (1) 可以让 f 变更好的方向 : (2) 可以走的方向 : 如果 f 是可微分的，不论单变数或多变数... : 基本上就是 让 < Df , d > 内积小於 0 的方向 d 就是了 : 比方说在第一个例子中 : f(x) = x => Df(x) = 1 : => < 1 , a > = a < 0 : => a < 0 : 意思是说... : ** 只要往左走...就会变小 : 用数学来说就是 ...... f(x+a) < f(x) for some a < 0 : 在第二个例子中 : f(x) = x^2 => Df(x) = 2x : => <2x , a > = 2xa < 0 : => Case 1: x>0 => a<0 / Case 2: x<0 => a > 0 : 和我们所认知的抛物线一样... : 在x<0 的地方要往右走才会变小 / x>0 的地方则往左走 : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : 如果没有限制式的话...也就是说 x 可以是任何实数的话 : 极值始终会满足： ** 没有任何方向可以让 f 变小的那种 x 点！！ : 也就是说 如果 x* 是极小值的话 : 会满足 < Df(x*) , a > = 0 for all (a向量) : 所以 可以导出 Df(x*) = (0向量) : 因此，如果没有限制式的话... : min x 并没有极小值... 因为所有的实数 x 都满足 Df(x) = 1 : 不过...加上限制式...就有极小值罗......！！！ : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : 加上限制式後...就会出现 : f 在 x* 点...有可以变小的方向 ... 但是受到 g 的影响...所以不能走！！！ : 因此...那些点可以走？ 那些点不能走？ ...这就是个有趣的问题了！ : 对於那些 g(x) < 0 的点来说，基本上任何能让 f 变小的方向，都是可以走的！ : 因此，只有在 g(x) = 0 时...会对方向造成限制 : 从上面两个例子的限制式来看 : g(x) = x^2 - 4 : 边界点是 x = 2 or -2 : 计算一下在边界上的微分 : Dg(x) = 2x : => Dg(2) = 4 > 0 and Dg(-2) = -4 < 0 : 不难发现 ....... : 在 g(x*) = 0 这种边界上的点 : 它可以移动的方向 ... 也只有 <Dg(x*) , d > < 0 的 d 方向 : 才会保持 g(x*+d) < g(x*) = 0 的限制式 : 在上面的例子...就是 在 x = 2 时....只能往左移...才会回到 x^2 - 4 < 0 : 另外一边是 在 x = -2 时，因为 Dg(-2) = -4 : => <Dg(-2) , d > = -4d < 0 => d > 0 只能往右移 : 从第一个例子( min x s.t. x^2-4<=0 )来看...就可以看得很清楚了 : 在 x = 2 时，维持 g < 0 的范围的方向是 "向左" : 让 f 变小的方向也是 "向左" ... 因此 f 有方向可以再继续变小 : 但是在 x = -2 的地方，维持 g < 0 的方向是 "向右" : 但是让 f 变小的方向还是 "向左" ... 因此 f 没有方向可以再继续变小 : 也就是达到最小值了！ : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : 最後...严格来说 : 你的题目应该是： : min xy : s.t. : g1(x,y) = -x <= 0 : g2(x,y) = -y <= 0 : h1(x,y) = x^2 + y^2 - 8 = 0 : 或是 : min -xy (就是 max xy 的case) : s.t. : g1(x,y) = -x <= 0 : g2(x,y) = -y <= 0 : h1(x,y) = x^2 + y^2 - 8 = 0 : 也就是说 : 真正的 Lagrange 应该写成 : L1(x,y) = xy + λ1(-x) + λ2(-y) + λ3(x^2 + y^2 - 8 ) : L2(x,y) = -xy + λ1(-x) + λ2(-y) + λ3(x^2 + y^2 - 8 ) : (因为 x =/= 0 ; y =/=0 所以...... : 解的时候要注意： λ1 = 0 ; λ2 = 0 才行！ ... ) : 但这样的话...就会回到原本的 Lagrange : L1(x,y) = xy + 0*(-x) + 0*(-y) + λ3(x^2 + y^2 - 8 ) : L2(x,y) = -xy + 0*(-x) + 0*(-y) + λ3(x^2 + y^2 - 8 ) : 所以...直接用原本的上面两种 Lagrange 也是 ok 的 : ※ 引述《RAINDD (I'm Kenino.)》之铭言： : : 原PO你好，你是初学微积分吗？ : : 这题其实不难，甚至也不需要用到Lagrange Multiplier就可以解了。 : : 我这麽说吧，个人以为困难的地方在於初学时"正确"而且"完整"建立观念。 : : 个人分享一些当初学习时的心得与经验， : : 不敢讲我说得很对，但提出来供你做参考。 : : 1. 首先，先想想，什麽叫最大值？最小值？极大值？极小值？ : : 既然叫"大"、叫"小"，就意味着是经过比较得到的结果。 : : 依我看，你困扰的点在於，经过求解方法得到只有一个极值时， : : 我怎麽知道它是最大或最小？ : : 然而，以这题来看，只有一个极值存在吗？其实还有，只是你缺视了， : : 2. 即使，真的只有一个极值发生时，你又如何得知它是最大、最小值呢？ : : 举个例： y = x^2 - 2x + 3，我们知道 x = 1 时， y 有最小值 2。 : : 如何知道的？用配方法呀，一阶微分求极值点、二阶微分求开口， : : 甚至算几不等式、柯西不等式…等任何可应用的方法， : : 都能帮助找maxima,minima,extrema，且看各凭本事。 : : 3. 再说Lagrange Multiplier方法，▽f = λ * ▽g， : : 联立求解时，常常不是那麽地在意特徵乘数值 λ 。 : : 若你练习的题目做多了，会发现λ值的大小与"+""-"符号， : : 似乎能猜知该点是极大值或是极小值。 : : 而微积分课本也并不讨论λ值与extrema的关连性。 : : 於此，我们并不多做讨论，有兴趣的话不妨自行研究或多找题目练习。 : : 4. 开始解题： : : 依题意，我们先弄清楚目标函数、和限制函数。 : : 目标函数： f(x,y) = x*y : : 限制函数： x^2 + y^2 = 8、 x > 0 、 y > 0 : : {依题意，限制函数为在xy平面上，x^2 + y^2 = 8，且 x > 0 , y > 0 : : 为第一象限的四分之一圆弧曲线。 : : 注意，题目并非x^2 + y^2 ≦ 8，所以并不包含圆内的区间} : : 极值发生的地方：(1)端点 (2)边界上 {勿忘端点} : : (1)端点：(x,y) = (2√2,0) 及 (0,2√2) : : (2)边界上：应用Lagrange Multiplier解得 (x,y) = (2,2)有一极值 : : 代入 (2√2,0)、(0,2√2)、(2,2)求f(x,y)并比较大小， : : 得知最大值为 f(2,2) = 2*2 = 4 : : 最小值为 f(2√2,0) = f(0,2√2) = 0 : : 於此，作答即完成。 : : 若你不放心 4 是否为最大值，就将限制函数x^2 + y^2 = 8参数化再 : : 用单变数函数求极值的方法解看看。 : : 若你能将题目转化成解析几何的意义进一步了解此题那又更好。 : : 5. 补充： : : 若限制函数为：x^2 + y^2 ≦ 8、x>0、y>0 : : 极值发生的地方：(1)端点 (2)边界上 (3)区间内 : : (1)端点有三：(x,y) = (2√2,0)、(0,2√2)、(0,0) : : (2)边界有三：y=0时，0≦x≦2√2、 : : x=0时，0≦y≦2√2、 : : x^2 + y^2 = 8。 : : (3)区间内：解 df/dx = 0 : : df/dy = 0 之联立方程式。 : : 详细的解答内容，就留给你自己发挥罗。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 203.74.126.44