アルゴリズム

3つの数値のアルファ最大プラスベータ最小アルゴリズム



Alpha Max Plus Beta Min Algorithm



解決：

$ max（x、y、z）、 min（x、y、z）、 operatorname {med}（x、y、z）$が実際には$ | max（x、y、z）|であると仮定すると、 | min（x、y、z）|、| operatorname {med}（x、y、z）| $。

本当の証拠ではなく、スケッチだけです。式は$ x、y、z $の順列の下で対称であるため、$ 0 leq x leq y leq z $と仮定します。したがって、$$ sqrt {x ^ 2 + y ^ 2 + z ^ 2} = alpha x + beta y + gammaz。 $$興味があるので 相対的 エラー、単位円上の点を考えてみましょう。 $ z ^ 2 = 1-x ^ 2-y ^ 2 $。エラーは、$ alpha x + beta y + gamma z $と1の間の絶対偏差です。単位円上の条件$ 0 leq x leq y leq z $は、次の条件と同等です$$ 0 leq x leq y \ sqrt {1-x ^ 2-y ^ 2} geq y Leftrightarrow x ^ 2 + 2y ^ 2 leq 1 $$そこで、ミニマックス問題が発生しました$$ begin {aligned} operatorname {minimize} limits _ { alpha、 beta、 gamma} max _ {サブスタック{x geq 0 \ y geq x \ x ^ 2 + 2y ^ 2 leq 1}} big | 1- alpha x- beta y- gamma sqrt {1-x ^ 2- y ^ 2} big | end {aligned} $$それは難しいことです。



私たちはできる 仮定する 最大偏差は3つのコーナーで等しく、内部の極値での偏差とは対照的です。

幾何学的な意味があるため、内部の極値は単純です。これは、$ C = alpha x + beta y + gamma z $で与えられる平面から、球の原点から1を引いた距離（球の半径）までの距離に等しくなります。したがって、極値での偏差は$$ Delta = sqrt { alpha ^ 2 + beta ^ 2 + gamma ^ 2} -1です。$$コーナーでの偏差$（0,0）、、（0 、 frac {1} { sqrt {2}}）、（ frac {1} { sqrt {3}}、 frac {1} { sqrt {3}}））$は簡単に計算されます：$$ Delta_1 = 1- gamma \ Delta_2 = 1- frac { beta + gamma} { sqrt {2}} \ Delta_3 = 1- frac { alpha + beta + gamma} { sqrt {3}} $$ $ Delta = Delta_1 = Delta_2 = Delta_3 $を$ alpha、 beta、 gamma $について解くと、$$ begin {aligned} alpha = frac {1} {4が得られます。 } left（2 sqrt {14 + 6 sqrt {2} +3 sqrt {3}}- left（2 + sqrt {2} right） left（1+ sqrt {3} right ） right）＆ upperx 0.29870618761437979596 \ beta = operatorname {root} _6（1-4 z-14 z ^ 2 + 32 z ^ 3 + 45 z ^ 4-20 z ^ 5-20 z ^ 6 + 4 z ^ 7 + z ^ 8）＆ approx 0.38928148272372526647 \ gamma = operatorname {root} _8（1-4 z-2 z ^ 2 + 20 z ^ 3-3 z ^ 4-32 z ^ 5 + 4 z ^ 6 + 16 z ^ 7 + z ^ 8）＆ upperx 0.93980863517232523127 end {aligned} $$エラー$ 1- gamma $は$ 6 ％$をわずかに上回っています。誤って$ alphaを逆にしたことに注意してください。 beta、 gamma $。その結果は有望に見えますが、間違っている可能性があります。 $ beta $と$ gamma $は2D最適値にかなり近いことに注意してください。



シンプルにしました Mathematica ミニマックス問題を調べるためのスクリプト。ここにあります

[ContourPlot [ [Alpha] x +  [Beta] y +  [Gamma] Sqrt [1-x ^ 2-y ^ 2] -1、{x、0、1}、{y、0、1}を操作します、RegionFunction->関数[{x、y}、x<= y && x^2 + 2 y^2 Range[-0.2, 0.2, 0.01] ] , {{[Alpha], 0.2987061876143797`}, 0, 1}, {{[Beta], 0.38928148272372454`}, 0, 1}, {{[Gamma], .9398086351723256`}, 0, 1}]  
 
 
したがって、提案は正気であり、少なくとも問題の局所最適を見つけたようです。
 
 
  
@uranixで与えられる近似は素晴らしいですが、斜辺が3つの入力の最大値よりも短くなることはないことがわかっているため、わずかに改善できます。
 
したがって、@ uranixによって与えられた素晴らしい定数を借りて、$ 0<=z<=y<=x$：
 
const double alphaMax = 0.9398086351723256、betaMed = 0.38928148272372454、gammaMin = 0.2987061876143797;二重斜辺= Max（x、alphaMax * x + betaMed * y + gammaMin * z）;
これにより、xがyおよびzよりも比較的大きい場合にエラーがクランプされます。エラーが比較的大きく、目立つ一般的な特殊なケース。
 
補足：乗算は定数を使用するため、ビットシフトと加算で近似できます。これは、浮動小数点と乗算にコストがかかる可能性がある組み込みシステムで固定小数点演算を使用する場合に最も役立ちます。