線性不可控演算法

『壹』 分類演算法怎樣分為 線性分類 和非線性分類

• 線性演算法

  線性演算法的定義：在計算復雜性理論，一個被稱為線性時間或 Ο(n)時間的演算法，表示演算法解題所需時間正比於輸入資料的大小，通常以n表示。

這可以理解為，如果所需時間正比於輸入資料的大小，那就是一個線性演算法，類似於中學時學過的一次函數的函數圖象

• 非線性演算法

  非線性演算法一般有O(NlogN),O(N^2)等等。這些非線性演算法所需的時間和輸入資料大小不成正比，故函數圖象應不會是一條直線，所以這些演算法不是線性分類，即非線性分類。

『貳』 請問多目標線性規劃的常用求解演算法有哪些呢

多目標決策方法

多目標決策方法是從20世紀70年代中期發展起來的一種決策分析方法。決策分析是在系統規劃、設計和製造等階段為解決當前或未來可能發生的問題，在若干可選的方案中選擇和決定最佳方案的一種分析過程。在社會經濟系統的研究控制過程中我們所面臨的系統決策問題常常是多目標的，例如我們在研究生產過程的組織決策時，既要考慮生產系統的產量最大，又要使產品質量高，生產成本低等。這些目標之間相互作用和矛盾，使決策過程相當復雜使決策者常常很難輕易作出決策。這類具有多個目標的決策總是就是多目標決策。多目標決策方法現已廣泛地應用於工藝過程、工藝設計、配方配比、水資源利用、環境、人口、教育、能源、企業高速武器系統設計和評價、經濟管理等領域。
多目標決策主要有以下幾種方法：
（1）化多為少法：將多目標問題化成只有一個或二個目標的問題，然後用簡單的決策方法求解，最常用的是線性加權和法。
（2）分層序列法：將所有目標按其重要性程度依次排序，先求出第一個最重要的目標的最優解，然後在保證前一目標最優解的前提下依次求下一目標的最優解，一直求到最後一個目標為止。
（3）直接求非劣解法：先求出一組非劣解，然後按事先確定好的評價標准從中找出一個滿意的解。
（4）目標規劃法：對於每一個目標都事先給定一個期望值，然後在滿足系統一定約束條件下，找出與目標期望值最近的解。
（5）多屬性效用法：各個目標均用表示效用程度大小的效用函數表示，通過效用函數構成多目標的綜合效用函數，以此來評價各個可行方案的優劣。
（6）層次分析法：把目標體系結構予以展開，求得目標與決策方案的計量關系。
（7）重排序法：把原來的不好比較的非劣解通過其他辦法使其排出優劣次序來。
（8）多目標群決策和多目標模糊決策等。

『叄』 關於線性回歸演算法還可以解決日常生活中哪些問題

趨勢線
一條趨勢線代表著時間序列數據的長期走勢。它告訴我們一組特定數據（如GDP、石油價格和股票價格）是否在一段時期內增長或下降。雖然我們可以用肉眼觀察數據點在坐標系的位置大體畫出趨勢線，更恰當的方法是利用線性回歸計算出趨勢線的位置和斜率。

流行病學
有關吸煙對死亡率和發病率影響的早期證據來自採用了回歸分析的觀察性研究。為了在分析觀測數據時減少偽相關，除最感興趣的變數之外,通常研究人員還會在他們的回歸模型里包括一些額外變數。例如，假設我們有一個回歸模型，在這個回歸模型中吸煙行為是我們最感興趣的獨立變數，其相關變數是經數年觀察得到的吸煙者壽命。研究人員可能將社會經濟地位當成一個額外的獨立變數，已確保任何經觀察所得的吸煙對壽命的影響不是由於教育或收入差異引起的。然而，我們不可能把所有可能混淆結果的變數都加入到實證分析中。例如，某種不存在的基因可能會增加人死亡的幾率，還會讓人的吸煙量增加。因此，比起採用觀察數據的回歸分析得出的結論，隨機對照試驗常能產生更令人信服的因果關系證據。當可控實驗不可行時，回歸分析的衍生，如工具變數回歸，可嘗試用來估計觀測數據的因果關系。

金融
資本資產定價模型利用線性回歸以及Beta系數的概念分析和計算投資的系統風險。這是從聯系投資回報和所有風險性資產回報的模型Beta系數直接得出的。

經濟學
線性回歸是經濟學的主要實證工具。例如，它是用來預測消費支出，固定投資支出，存貨投資，一國出口產品的購買，進口支出，要求持有流動性資產，勞動力需求、勞動力供給。

『肆』 非線性最優化的不同演算法各適用於什麼情況

1 無約束非線性最優化問題常用演算法：
梯度法（最速下降法）、共軛梯度法、變尺度法和步長加速法。其中，前三個要用到函數的一階導數或二階導數，適用於函數表達式導數存在且求導簡單的情況，而步長加速法則相反，適用於函數表達示復雜，甚至無解析表達式，或導數不存在情況。
2 約束非線性最優化問題常用演算法：
按照是否化成無約束問題可分為 可行方向法、制約函數法（外點法和內點法），其中內點法適用於目標函數在可行域外性質復雜情況，外點法則相反。後者根據罰函數或障礙函數的構造不同，又有不同的變形。

『伍』 線性演算法是指什麼樣演算法請舉幾個例子。類似於進化演算法就是指遺傳演算法，人工免疫演算法等。

這里說的線性演算法應該是從時間復雜度方面來說的，相對於進化演算法的話。
即在線性時間或 Ο（n）時間內能求得問題最優解的演算法，統稱為線性演算法。比如說動態規劃法、分治法、回溯法、遞歸法等。
供參考

『陸』 什麼是線性規劃問題，及有那些相關概念如何解決

線性規劃問題的數學模型的一般形式（1）列出約束條件及目標函數
（2）畫出約束條件所表示的可行域
（3）在可行域內求目標函數的最優解 [編輯本段]線性規劃的發展法國數學家 J.- B.- J.傅里葉和 C.瓦萊－普森分別於1832和1911年獨立地提出線性規劃的想法，但未引起注意。
1939年蘇聯數學家Л.В.康托羅維奇在《生產組織與計劃中的數學方法》一書中提出線性規劃問題，也未引起重視。
1947年美國數學家G.B.丹齊克提出線性規劃的一般數學模型和求解線性規劃問題的通用方法──單純形法，為這門學科奠定了基礎。
1947年美國數學家J.von諾伊曼提出對偶理論,開創了線性規劃的許多新的研究領域，擴大了它的應用范圍和解題能力。
1951年美國經濟學家T.C.庫普曼斯把線性規劃應用到經濟領域，為此與康托羅維奇一起獲1975年諾貝爾經濟學獎。
50年代後對線性規劃進行大量的理論研究，並涌現出一大批新的演算法。例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規劃的靈敏度分析和參數規劃問題，1956年A.塔克提出互補鬆弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解演算法等。
線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、隨機規劃和非線性規劃的演算法研究。由於數字電子計算機的發展，出現了許多線性規劃軟體，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變數的線性規劃問題。
1979年蘇聯數學家L. G. Khachian提出解線性規劃問題的橢球演算法，並證明它是多項式時間演算法。
1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間演算法。用這種方法求解線性規劃問題在變數個數為5000時只要單純形法所用時間的1/50。現已形成線性規劃多項式演算法理論。50年代後線性規劃的應用范圍不斷擴大。 建立線性規劃模型的方法 [編輯本段]線性規劃的模型建立從實際問題中建立數學模型一般有以下三個步驟；
1.根據影響所要達到目的的因素找到決策變數；
2.由決策變數和所在達到目的之間的函數關系確定目標函數；
3.由決策變數所受的限制條件確定決策變數所要滿足的約束條件。
所建立的數學模型具有以下特點：
1、每個模型都有若干個決策變數（x1,x2,x3……，xn），其中n為決策變數個數。決策變數的一組值表示一種方案，同時決策變數一般式非負的。
2、目標函數是決策變數的線性函數，根據具體問題可以是最大化（max）或最小化（min），二者統稱為最優化（opt）。
3、約束條件也是決策變數的線性函數。
當我們得到的數學模型的目標函數為線性函數，約束條件為線性等式或不等式時稱此數學模型為線性規劃模型。
例：
生產安排模型：某工廠要安排生產Ⅰ、Ⅱ兩種產品，已知生產單位產品所需的設備台時及A、B兩種原材料的消耗，如表所示，表中右邊一列是每日設備能力及原材料供應的限量，該工廠生產一單位產品Ⅰ可獲利2元，生產一單位產品Ⅱ可獲利3元，問應如何安排生產，使其獲得最多？
解：
1、確定決策變數：設x1、x2為產品Ⅰ、Ⅱ的生產數量；
2、明確目標函數：獲利最大，即求2x1+3x2最大值；
3、所滿足的約束條件：
設備限制：x1+2x2≤8
原材料A限制：4x1≤16
原材料B限制：4x2≤12
基本要求：x1,x2≥0
用max代替最大值，s.t.（subject to 的簡寫）代替約束條件，則該模型可記為：
max z=2x1+3x2
s.t. x1+2x2≤8
4x1≤16
4x2≤12
x1,x2≥0 [編輯本段]線性規劃的解法求解線性規劃問題的基本方法是單純形法，現在已有單純形法的標准軟體，可在電子計算機上求解約束條件和決策變數數達 10000個以上的線性規劃問題。為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方法、分解演算法和各種多項式時間演算法。對於只有兩個變數的簡單的線性規劃問題，也可採用圖解法求解。這種方法僅適用於只有兩個變數的線性規劃問題。它的特點是直觀而易於理解，但實用價值不大。通過圖解法求解可以理解線性規劃的一些基本概念。
對於一般線性規劃問題：
Min z=CX
S.T.
AX =b
X>=0
其中A為一個m*n矩陣。
若A行滿秩
則可以找到基矩陣B，並尋找初始基解。
用N表示對應於B的非基矩陣。則規劃問題1可化為：
規劃問題2：
Min z=CB XB+CNXN
S.T.
B XB+N XN = b (1)
XB >= 0, XN >= 0 (2)
(1)兩邊同乘於B-1，得
XB + B-1 N XN = B-1 b
同時，由上式得XB = B-1 b - B-1 N XN，也代入目標函數，問題可以繼續化為：
規劃問題3：
Min z=CB B-1 b + ( CN - CB B-1 N ) XN
S.T.
XB+B-1N XN = B-1 b (1)
XB >= 0, XN >= 0 (2)
令N:=B-1N，b:= B-1 b，ζ= CB B-1b，σ= CN - CB B-1 N，則上述問題化為規劃問題形式4：
Min z= ζ + σ XN
S.T.
XB+ N XN = b (1)
XB >= 0, XN >= 0 (2)
在上述變換中，若能找到規劃問題形式4，使得b>=0，稱該形式為初始基解形式。
上述的變換相當於對整個擴展矩陣（包含C及A） 乘以增廣矩陣 。所以重在選擇B，從而找出對應的CB。
若存在初始基解
若σ>= 0
則z >=ζ。同時，令XN = 0，XB = b，這是一個可行解，且此時z=ζ，即達到最優值。所以，此時可以得到最優解。
若σ >= 0不成立
可以採用單純形表變換。
σ中存在分量<0。這些負分量對應的決策變數編號中，最小的為j。N中與j對應的列向量為Pj。
若Pj <=0不成立
則Pj至少存在一個分量ai，j為正。在規劃問題4的約束條件（1）的兩邊乘以矩陣T。
T=
則變換後，決策變數xj成為基變數，替換掉原來的那個基變數。為使得T b >= 0，且T Pj=ei（其中，ei表示第i個單位向量），需要：
l ai，j>0。
l βq+βi*(-aq,j/ai,j)>=0，其中q!=i。即βq>=βi/ ai,j * aq,j。
n 若aq,j<=0，上式一定成立。
n 若aq,j>0，則需要βq / aq,j >=βi/ ai,j。因此，要選擇i使得βi/ ai,j最小。
如果這種方法確定了多個下標，選擇下標最小的一個。
轉換後得到規劃問題4的形式，繼續對σ進行判斷。由於基解是有限個，因此，一定可以在有限步跳出該循環。
若對於每一個i，ai,j<=0
最優值無界。
若不能尋找到初始基解
無解。
若A不是行滿秩
化簡直到A行滿秩，轉到若A行滿秩。 [編輯本段]線性規劃的應用在企業的各項管理活動中,例如計劃、生產、運輸、技術等問題,線性規劃是指從各種限制條件的組合中,選擇出最為合理的計算方法,建立線性規劃模型從而求得最佳結果

『柒』 機器學習故事匯-線性回歸演算法

機器學習故事匯-線性回歸演算法
今天咱們要來嘮的是機器學習中最基本也是最重要的演算法之一線性回歸，正當此時迪哥正在前往銀行的路上，准備辦理貸款（低保），到了之後銀行問了我兩件事，年齡和工資都多少呀？（特徵）當得到了結果後告訴我我們只能貸給你100塊，別問為什麼！機器算的！（機器你拿毛線算的100快？）

這個圖就是機器如何進行預測的（回歸）它會根據一票子兄弟貸款的歷史數據（年齡和工資分別對應於X1與X2）找出來最好的擬合線（面）來進行預測，這樣你的數據來了之後直接帶入進去就可以得出來該給你多少錢了。

我們用兩個參數來分別對應於工資和年齡，控制它們對結果的影響大小，這里做了一個整合是把偏置項和權重參數項放到了一起（加了個X0讓其都等於1）
要想讓銀行能開的下去，那就得少遇到點麻煩，迪哥這么大碗就給我100塊（真實的指標應該為200塊）肯定是要砸場子的，所以我們的目標是要讓得到的預測值跟真實值越接近越好。

既然說到誤差了，咱們就來好好嘮一下，首先銀行的目標得讓誤差越小越好，這樣才能夠使得我們的結果是越准確的。那麼這個誤差有什麼規律可循嗎？

咱們先來說說這個誤差為啥會服從高斯分布呢，這個事就得從我們是怎麼認為一個事發生的概率來說了，正常情況下你去銀行貸款差不多都是一個符合你的數字吧，極小的情況下能出現類似迪哥的情況（100塊都不給我），還是極小的情況下能像對待馬雲似的給你幾個億吧，所以銀行給你貸款的誤差項理論上都是在較小范圍內浮動的，要麼多了一點，要麼少了一點。所以我們認為該誤差是可以服從高斯分布的（正太分布）。
那為啥會獨立呢？獨立的意思就是說迪哥來貸款了，恰好馬雲也來了，但是我倆不認識啊（其實他認識我，我不認識他），所以我倆在貸款的時候不會因為馬雲而對我產生什麼影響，也不會因為我對馬雲產生什麼影響，這就是獨立！
同分布又是啥呢？我和馬雲來的是一家銀行吧，這家銀行的系統只有一個，所以它在預測的時候是按照同樣的方式來的，這就是我們的數據是在同一個分布下去建模的。

既然誤差服從了高斯分布我們就把它進行展開，上式的意思就是我去貸款，在它這兩組參數的控制下得到的貸款金額恰好是等於真實情況下就該給我這么多錢的概率。（預測值和真實值對應的可能性大小）那麼我們當然希望這個概率越大越好呀，越大代表越准確呀。

（怎麼又來了一堆數學。。。沒人數學就不是機器學習啦）咱們繼續來看，咋又突然出來了個似然函數呀，咱們先來說一說它是個什麼東西。比如說你今天去賭場了，然後你不知道能不能贏錢，你就在門口蹲著，出來一個人你就問一下，哥們贏錢了嗎（然後挨了一頓揍），連續出來5個人都告訴你贏錢了，那麼你就會認為我去賭錢也肯定會贏錢。這個的意思就是要利用樣本數據去估計你的參數應該是什麼，使得估計出來的參數盡可能的滿足（擬合）你的樣本。
對數似然它的意思和目標很簡單，就是為了簡單求解，所以把比較復雜的乘法運算轉換成了比較簡單的加法運算。

一頓化簡，其實就是把原式給展開了，然後我們的目標是要求最大值吧（什麼樣的參數能夠使得跟我數據組合完之後是真實值的概率越大越好），對於化簡後的結果左邊是一個常數不用去管，右邊是一個恆正的（因為有平方項）但是前面還有一個負號呀，讓這樣的數什麼時候能取最大值呀？只有負號後面的取最小值才可以呀！
到這里我們終於推導出來了，銀行只需要做一件事就可以了，那就是最小化這個函數（目標函數），其實說白了就是要讓我們的預測值和真實值之間的差異越小越好，這就是最小二乘法！

接下來就是如何求解呢？通常我們去求偏導就可以了，因為極值點通常都是在偏導處取得，對我們的目標函數求偏導，並且讓其等於0，這樣我們就能找到最終參數的解應該是什麼了！到這里小夥伴們可能感覺到竟然真能求出這個解，那這個解不就是我們想要的參數嘛，得到了它銀行就有救啦！
至此我們通過了一系列的推導得出了線性回歸的最終解法，但是這個解可以說是數學上的一個巧合，並不是所有問題都可以直接求解的，下回咱們再談談如何間接的求最優解~

『捌』 線性回歸演算法原理（越詳細越好）

線性回歸是利用數理統計中的回歸分析，來確定兩種或兩種以上變數間相互依賴的定量關系的一種統計分析方法之一，運用十分廣泛。

分析按照自變數和因變數之間的關系類型，可分為線性回歸分析和非線性回歸分析。

如果在回歸分析中，只包括一個自變數和一個因變數，且二者的關系可用一條直線近似表示，這種回歸分析稱為一元線性回歸分析。如果回歸分析中包括兩個或兩個以上的自變數，且因變數和自變數之間是線性關系，則稱為多元線性回歸分析。

我們以一簡單數據組來說明什麼是線性回歸。假設有一組數據型態為y=y(x)，其中

x={0,1,2,3,4,5},y={0,20,60,68,77,110}

如果我們要以一個最簡單的方程式來近似這組數據，則非一階的線性方程式莫屬。先將這組數據繪圖如下

圖中的斜線是我們隨意假設一階線性方程式y=20x，用以代表這些數據的一個方程式。以下將上述繪圖的MATLAB指令列出，並計算這個線性方程式的y值與原數據y值間誤差平方的總合。

>>x=[012345];

>>y=[020606877110];

>>y1=20*x;%一階線性方程式的y1值

>>sum_sq=sum(y-y1).^2);%誤差平方總合為573

>>axis([-1,6,-20,120])

>>plot(x,y1,x,y,'o'),title('Linearestimate'),grid

如此任意的假設一個線性方程式並無根據，如果換成其它人來設定就可能採用不同的線性方程式；所以我們須要有比較精確方式決定理想的線性方程式。我們可以要求誤差平方的總合為最小，做為決定理想的線性方程式的准則，這樣的方法就稱為最小平方誤差(leastsquareserror)或是線性回歸。MATLAB的polyfit函數提供了從一階到高階多項式的回歸法，其語法為polyfit(x,y,n)，其中x,y為輸入數據組n為多項式的階數，n=1就是一階的線性回歸法。polyfit函數所建立的多項式可以寫成

從polyfit函數得到的輸出值就是上述的各項系數，以一階線性回歸為例n=1，所以只有二個輸出值。如果指令為coef=polyfit(x,y,n)，則coef(1)=,coef(2)=,...,coef(n+1)=。注意上式對n階的多項式會有n+1項的系數。我們來看以下的線性回歸的示範：

>>x=[012345];

>>y=[020606877110];

>>coef=polyfit(x,y,1);%coef代表線性回歸的二個輸出值

>>a0=coef(1);a1=coef(2);

>>ybest=a0*x+a1;%由線性回歸產生的一階方程式

>>sum_sq=sum(y-ybest).^2);%誤差平方總合為356.82

>>axis([-1,6,-20,120])

>>plot(x,ybest,x,y,'o'),title('Linearregressionestimate'),grid

[編輯本段]線性回歸擬合方程

一般來說，線性回歸都可以通過最小二乘法求出其方程，可以計算出對於y=bx+a的直線，其經驗擬合方程如下：

『玖』 MATLAB 對 不可控線性系統 PID控制參數 的整定

肯定可以，你這個是最簡單的一個高階線性系統。