簡介

本算法用來求解凸函數(shù)極值點(diǎn)的問題，由我在寫ACM習(xí)題時(shí)想到，在網(wǎng)上并未找到這樣的算法，拿出來給大家分享一下，如果網(wǎng)上沒有的話，我決定給它起名叫做 CSF迭代法，如果這個(gè)算法早已經(jīng)存在，那就當(dāng)看個(gè)笑話吧。

by 蔡少斐 西安交大 軟件53

算法步驟

確定一個(gè)常數(shù)n，表示區(qū)間的劃分粒度，以及一個(gè)常數(shù)eps表示精度。

先從定義域[l,r]中等差地取出n個(gè)點(diǎn),x1,x2,...,xn。

x1=l+(r?l)n+1,xi=xi?1+r?ln+1

計(jì)算f(x1),...,f(xn)，挑選出使得f(xt)最大的點(diǎn)xt。

判斷定義域區(qū)間長度是否小于eps，若是執(zhí)行6，否則執(zhí)行5。

把定義域縮小到[xt?1,xt+1]，執(zhí)行2。

x0=l,xn+1=r

輸出xt

算法證明

用反證法：假設(shè)存在一次迭代，使得極值點(diǎn)不在[xt?1,xt+1]里面，那么設(shè)這個(gè)極值點(diǎn)為xp，并且有xp>xt+1，那么可以知道區(qū)間[xt?1,xt+1]是單調(diào)遞增的。也就是說f(xt+1)>f(xt)，因此我們在算法的第2個(gè)步驟時(shí)將選擇xt+1而不是xt，矛盾。
因而極值一定在我們所迭代的區(qū)間內(nèi)。

算法復(fù)雜度分析

設(shè)區(qū)間長度為len,劃分粒度為n，精度要求為eps，遞歸深度為dep
可以列出遞歸方程如下：
T(len)=n+T(len(n+1)/2)
其中滿足方程：
(2n+1)deplen=eps
解得：
O(len)=nlogepslen2n+1

特殊性

如果令劃分粒度n=2的話，等價(jià)于三分算法。

算法實(shí)現(xiàn)

double csf(double l,double r,int n = 2,double eps = 0.001){ static const double INF = 1e9;double x;while(r - l > eps){double step = (r-l)/(n+1);double mx = -INF;for(double i = l+step;i < r;i += step) if(mx < f(i)) mx = f(i),x = i;l = x-step;r = x+step;}return x; }

參數(shù)分析

函數(shù)總共有4個(gè)參數(shù)l,r,n,eps,其中有3個(gè)參數(shù)l,r,eps都是給定的。
總是選取l=?10000000，r=10000000

當(dāng)選取eps=0.001時(shí)候

當(dāng)選取eps=0.000001的時(shí)候

結(jié)論

n選取4或6<script type="math/tex" id="MathJax-Element-37">6</script>的時(shí)候函數(shù)效果較好。

實(shí)驗(yàn)代碼

#include <bits/stdc++.h> using namespace std; double f(double x){return -(x-5)*(x-786); } int cnt; double csf(double l,double r,int n = 2,double eps = 0.001){ static const double INF = 1e9;double x;while(r - l > eps){double step = (r-l)/(n+1);double mx = -INF;for(double i = l+step;i < r;i += step) if(mx < f(i)) mx = f(i),x = i,cnt++;l = x-step;r = x+step;}return x; } int main(){freopen("1.csv","w",stdout);for(int i = 2;i <= 100;i+=1) {cnt = 0;double x = csf(-10000000,10000000,i,0.000001);printf("%d,%d\n",i,cnt);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的求凸函数极值 CSF迭代法(雾)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。