我的問題與此類似，但是如果將絕對差提高到冪“c”（將作為輸入給出），是否有演算法可以找到答案？
例如，給定A = {a1, a2,...., an}并且c它應該找到一個x最小化|a1 ? x|^c |a2 ? x|^c ··· |an ? x|^c。
如果c = 1它是排序陣列的中位數，如果c = 2它是陣列的平均值，但我找不到中位數和平均值之間的聯系，我們可以擴展到c.
uj5u.com熱心網友回復：
我假設這c是一個正整數。
如果它不是整數，則分數冪很難計算。如果它是負數，那么隨著x無窮大（無論哪種方式）結果變為 0，因此沒有全域最小值。如果為0，則x無所謂。所以正整數是唯一有意義的東西。
現在每一項都是一個凸函式。凸函式之和本身就是凸函式。凸函式具有以下性質。假設x < y < z. 如果f(x) = f(z)那么全域最小值在它們之間。如果f(x) = f(y) = f(z)，那是一條直線段。最后，如果f(y) < min(f(x), f(z))那么全域最小值介于x和之間z。
這對于二分搜索的變體來說已經足夠了。
while z - x > some tolerance:
if z-y > y-x:
y1 = (y z) / 2
if f(y1) < f(y):
(x, y, z) = (y, y1, z)
elif f(y1) = f(y):
(x, y, z) = (y1, (2*y1 y)/3, y)
else:
(x, y, z) = (y1, y, z)
else:
y1 = (x y) / 2
if f(y1) < f(y):
(x, y, z) = (x, y1, y)
elif f(y1) = f(y):
(x, y, z) = (y1, (2*y1 y)/3, y)
else:
(x, y, z) = (y1, y, z)
運行時，每次迭代都會將間隔的大小減少到最多為以前的 3/4。因此，您將縮小答案范圍。
如果你特殊情況c = 1，你可以做得更好。二階導數將在任何地方定義并且是一個非遞減函式。這允許您進行二分搜索，但猜測最小值在區間中的哪個位置。如果您靠得很近，您就會知道自己錯在哪里，并且可以對其施加更嚴格的限制。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/312894.html