kkt條件的matlab仿真,請教關于SVM中KKT條件的推導

KKT條件第一項是說最優點必須滿足所有等式及不等式限制條件,也就是說最優點必須是一個可行解,這一點自然是毋庸置疑的。第二項表明在最優點 x*, ?f 必須是 ?hj 和 ?gk 的線性組合,和都叫作拉格朗日乘子。所不同的是不等式限制條件有方向性,所以每一個 kμ都必須大於或等於零,而等式限制條件沒有方向性,所 以 jλ沒有符號的限制,其符號要視等式限制條件的寫法而定。

設想我們優化如下的目標函數:

minimize? ? f_0(x)

s.t.? ?? ???f_i(x)<=0,??i=1,2,...,m

h_i(x)=0,? ?i=1,2,...,p

我們把這個目標函數稱為原函數

構造該函數的對偶函數如下:

maximize

g(r,v)=inf_x {f_0(x)+sum_{i=1}^m r_i*f_i(x)+sum_{i=1}^p v_i*h_i(x)}

s.t.? ? r_i>=0??i=1,2,...,m

假設x'是原函數的一個可行點(滿足原函數的約束),r',v'是對偶函數的一個可行點

因為r'_i>=0,f_i(x')<=0,所以sum_{i=1}^m r'_i*f_i(x')<=0,同理

sum_{i=1}^p v'_i*h_i(x')=0

因此,我們有,對于任意的滿足原函數約束的x和滿足對偶函數約束的r,v

g(r,v)<={f_0(x)+sum_{i=1}^m r_i*f_i(x)+sum_{i=1}^p v_i*h_i(x)}

<=f_0(x)

記x^* 為原函數的一個最優點,最優值為p^*

r^*,v^*為對偶函數的一個最優點,最優值為d^*

我們有

p^*>=d^*(weak duality)

如果x^*,r^*,v^*能夠使得p^*=d^*成立,

則稱strong duality成立,即

f_0(x^*)=g(r^*,v^*)

現在假設strong duality能夠成立,并且假設x^*是原函數的最優解,r^*,v^*為對偶函數

的一個最優點,那么

f_0(x^*)=g(r^*,v^*)

=inf_x {f_0(x)+sum_{i=1}^m r^*_i*f_i(x)+sum_{i=1}^p v^*_i*h_i(x)}

<=f_0(x^*)+sum_{i=1}^m r^*_i*f_i(x^*)+sum_{i=1}^p v^*_i*h_i(x^*)

<=f_0(x^*)

第一個等式是strong duality,第二行等式是對偶函數的定義,第三行不等式是inf的定

義,第四行不等式是因為r^*_i>=0,f_i(x^*)<=0,h_i(x^*)=0

因此,我們有sum_{i=1}^m r^*_i*f_i(x^*)=0,

因為對每個i, r^*_i*f_i(x^*)<=0,

所以有

r^*_i*f_i(x^*)=0(Complementary slackness)

因為x^*是使得g(r^*,v^*)最小的點,(注意上面的第三行等式成立)

所以g(r^*,v^*)關于x的導數在x^*處為0

f_0'(x^*)+sum_{i=1}^m r^*_i*f_i'(x^*)+sum_{i=1}^p v^*_i*h_i'(x^*)=0

綜上所述我們得到了f_0(x^*)=g(r^*,v^*)的條件:

f_i(x^*)<=0? ???i=1,2,...,m

h_i(x^*)=0? ?? ?i=1,2,...,p

r^*_i>=0? ?? ???i=1,2,...,m

r^*_i*f_i(x^*)=0? ? i=1,2,...,m

f_0'(x^*)+sum_{i=1}^m r^*_i*f_i'(x^*)+sum_{i=1}^p v^*_i*h_i'(x^*)=0

這就是KKT條件~~

以上是摘自Information Retrieval Blog的部分內容,希望對你能有點點啟發~~

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/395617.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/395617.shtml
英文地址,請注明出處:http://en.pswp.cn/news/395617.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

公共wifi做家用_如何在公共網絡上獲得免費的wifi

公共wifi做家用by Kyle McDonald凱爾麥克唐納(Kyle McDonald) 如何在公共網絡上獲得免費的wifi (How to get free wifi on public networks) This short tutorial describes a few methods for gaining access to the internet, a basic human right, from public wireless ne…

python學習之旅

一、入門 1.Python 面向對象編程 2.jquery入門 3.HTMLCSS基礎入門 4.Javascript初步 5.Python語言編程基礎 二、初級階段 1.Git 與 GitHub 2.Python 爬蟲基礎 3.django進階 4.django項目部署 5.ajax入門 6.django基礎 7.Mysql基礎 三、中級階段 1.Linux基礎 2.Python :socket a…

c/c++ 重載運算符 函數調用運算符

重載運算符 函數調用運算符 把一個類的對象a&#xff0c;當成函數來使用&#xff0c;比如a()&#xff0c;所以需要重載operator()方法。重載了函數調用運算符的類的對象&#xff0c;就是函數對象了。 還有什么是函數對象呢&#xff1f;&#xff1f;&#xff1f; lambda是函數對…

matlab 萬能,matlab 萬能實用的線性曲線擬合方法

在科學計算和工程應用中&#xff0c;經常會遇到需要擬合一系列的離散數據&#xff0c;最近找了很多相關的文章方法&#xff0c;在這里進行總結一下其中最完整、幾乎能解決所有離散參數線性擬合的方法第一步&#xff1a;得到散點數據根據你的實際問題得到一系列的散點例如&#…

socket websocket

1.websocket客戶端 websocket允許通過JavaScript建立與遠程服務器的連接&#xff0c;從而實現客戶端與服務器間雙向的通信。在websocket中有兩個方法&#xff1a;      1、send() 向遠程服務器發送數據    2、close() 關閉該websocket鏈接  websocket同時還定義了幾…

javascript原型_JavaScript的原型:古怪,但這是它的工作原理

javascript原型by Pranav Jindal通過普拉納夫金達爾 JavaScript的原型&#xff1a;古怪&#xff0c;但這是它的工作原理 (Prototype in JavaScript: it’s quirky, but here’s how it works) The following four lines are enough to confuse most JavaScript developers:以下…

mysql函數之SUBSTRING_INDEX(str,/,-1)

SUBSTRING_INDEX的用法&#xff1a; ?SUBSTRING_INDEX(str,delim,count) 在定界符 delim 以及count 出現前&#xff0c;從字符串str返回自字符串。若count為正值,則返回最終定界符(從左邊開始) 若為-1則是從后往前截取 SELECT substring_index(Hn_P00001, P, -1) -- 結果是…

mysql8.0主從配置,MySQL 8.0主從服務器(Master-Slave)配置

一、介紹MySQL 主從復制的方式有多種&#xff0c;本文主要演示基于基于日志(binlog)的主從復制方式。MySQL 主從復制(也稱 A/B 復制) 的原理&#xff1a;Master將數據改變記錄到二進制日志(binary log)中&#xff0c;也就是配置文件log-bin指定的文件&#xff0c; 這些記錄叫做…

第十二章 Shell腳本編寫及常見面試題(三)

本章目錄&#xff1a;12.21 FTP下載文件#!/bin/bash if [ $# -ne 1 ]; thenecho "Usage: $0 filename" fi dir$(dirname $1) file$(basename $1) ftp -n -v << EOF # -n 自動登錄 open 192.168.1.10 user admin adminpass binary # 設置ftp傳輸模式為二進制…

亞馬遜面試有幾輪_經過幾個月的Google面試準備,我被亞馬遜錄用

亞馬遜面試有幾輪by Googley as Heck由Googley飾演Heck 經過幾個月的Google面試準備&#xff0c;我被亞馬遜錄用 (After months of preparing for the Google interview, I got hired by Amazon) As you may know, the last 11 months have been very difficult for me. As a …

省選前的考試記錄

日拱一卒功不唐捐 什么沙雕玩意兒 2018.12.24 T1 如果對 \(A\) 數組求出來高度遞減的單調棧的話&#xff0c;會發現只有單調棧里的元素是有用的。因為如果有 \(A[i]<A[j] \And i<j\)&#xff0c;那電梯就可以在帶 \(j\) 上樓的時候順便把 \(i\) 帶上并不會影響結果。所以…

軟件工程課設-----日程管理系統

這學期進行了軟件工程課設&#xff0c;題目是&#xff1a;日程管理系統&#xff08;JavaWeb&#xff09;&#xff0c;為期3周。這三周只有前兩天是企業老師講解是企業老師講解相關的基礎知識(老師講的水平實在是不可恭維。。。。。。)。 多的不多說。直接進行對相關項目的介紹。…

matlab中的神經網絡訓練,MATLAB中的神經網絡訓練

我試圖向前饋送反向傳播&#xff0c;但是在網絡訓練之后&#xff0c;當模擬和打印模擬輸出時&#xff0c;我看不到任何靠近目標的值&#xff0c;但它只是一個數字。代碼如下。什么是錯&#xff0c;什么是問題&#xff1f;前饋反向傳播&#xff1a;>> load(E:/Inputdata.t…

Spring For All 頂級Spring綜合社區服務平臺

Spring For All 玩最純粹的技術&#xff01;做最專業的 Spring 民間組織~ 歡迎加入&#xff1a;http://spring4all.com/ image.png

chromium 桌面_如何使用Chromium和PyInstaller將Web應用程序轉換為桌面應用程序

chromium 桌面Packaging and distributing your app sounds simple in principle. It’s just software. But in practice, it’s quite challenging.打包和分發應用程序在原理上聽起來很簡單。 這只是軟件。 但是在實踐中&#xff0c;這非常具有挑戰性。 I’ve been working …

PHP面向對象(三)

一、繼承概念 繼承性也是面向對象程序設計中的重要特性之一。它是指建立一個新的派生類&#xff0c;從一個先前定義的類中繼承數據和函數&#xff0c;而且可以重新定義新的數據類型和函數&#xff0c;從而建立累的層次或等級關系。 格式&#xff1a;     [修飾符] class 子…

python數據結構的應用場景不包括,Python 數據結構學習

Python 數據結構學習列表list.append(x)在列表的末尾添加一個元素。相當于 a[len(a):] [x] 。list.extend(iterable)使用可迭代對象中的所有元素來擴展列表。相當于 a[len(a):] iterable 。list.insert(i, x)在給定的位置插入一個元素。第一個參數是要插入的元素的索引&#…

[Jinkey 原創]震驚!iOS 系統居然自帶懸浮窗口調試工具

原文鏈接 : 震驚&#xff01;iOS 系統居然自帶懸浮窗口調試工具 —— Jinkey 原創原文作者 : Jinkey1 背景 英文原文&#xff1a;http://ryanipete.com/blog/ios/swift/objective-c/uidebugginginformationoverlay/ 我寫得這個并不是翻譯而是用自己的理解重新表述這個功能&…

盲人編程_盲人如何編碼

盲人編程About one out of every 200 software developers is blind. We know this because Stack Overflow asked 64,000 developers about this a few months ago.每200名軟件開發人員中大約有1名是盲人。 我們之所以知道這一點&#xff0c;是因為幾個月前 Stack Overflow 向…