物理学者ニュートンが300年前に考案して現代でも実用されるアルゴリズム「ニュートン法」がアップデートされる

2025年04月29日 15時00分 サイエンス

by Alexander Borek

約300年前に物理学者のアイザック・ニュートンが考案した「ニュートン法」は、現代でも物流や金融工学、コンピュータビジョン、純粋数学など多岐にわたる分野で重要な役割を果たしているアルゴリズムです。これまでさまざまな数学者がこのニュートン法の改良に苦心しており、近年の研究でついにアップデートされたと科学系ニュースサイトのQuanta Magazineが紹介しています。

Implementable tensor methods in unconstrained convex optimization | Mathematical Programming

https://link.springer.com/article/10.1007/s10107-019-01449-1

Three Hundred Years Later, a Tool from Isaac Newton Gets an Update | Quanta Magazine

https://www.quantamagazine.org/three-hundred-years-later-a-tool-from-isaac-newton-gets-an-update-20250324/ ニュートン法は最適化を求めるために使われるアルゴリズムの一種で、いろんな法則の「一番低い場所」や「一番良い答え」を見つけるための数学の道具といえます。

1680年頃にニュートンは、ある点x₀における関数ｆ(x)の傾きを示す一次導関数ｆ'(x)と、曲率を示す二次導関数ｆ''(x)を用いてテイラー展開することで、x₀の周辺で元の関数ｆ(x)と近似する二次関数「ｆ(x₀)＋ｆ'(x₀)*(x－x₀)＋(1/2)ｆ''(x₀)*(x－x₀)²」を導出できることに気付きました。この二次関数で最小値を取るようなx₁で再び同じように近似を行い、さらにその二次関数で最小値を取るようなx₂で近似を行い……というように反復することで元の関数ｆ(x)の最小値に迫るというのがニュートン法です。

ニュートン法は数学の世界の中だけではなく、私たちの日常生活を支える多くの技術や問題解決に深く関わっています。例えばGPSのナビゲーションでは、最短経路を見つける際、様々な道路の組み合わせの中から最も時間や距離が短くなるルートを計算する必要があります。この「最適化問題」の解決にニュートン法のような数値解析手法が使われています。 また、金融の世界でも重要な役割を果たしています。投資家が株式や債券などを組み合わせる際、リスクを最小化しながら利益を最大化するポートフォリオを作る時にニュートン法が応用されています。加えて、銀行がローンの金利を計算する際にも似たような数学的手法が使われています。 さらに、自動運転車の技術開発もニュートン法の恩恵を受けています。カメラやセンサーから入ってくる大量の情報を処理し、「これは歩行者か、それとも電柱か」といった判断をする際の画像認識では、多くの変数を持つ関数の最適化を効率的に行うためにニュートン法のようなアルゴリズムが役立っています。ほかにも、カメラの自動フォーカス機能やオンラインショッピングサイトのおすすめ機能、さらには気象予報モデルの計算など、様々な場面でニュートン法の考え方が活かされています。

ニュートン法の最大の強みは、その「二次収束」と呼ばれる性質です。これは反復するたびに解の誤差が指数関数的に減少することを意味し、勾配降下法のようなアルゴリズムよりも少ない回数で解に到達できます。しかし、ニュートン法には「すべての関数に対して効率的に機能するわけではない」という弱点があり、特に複雑な非凸関数において課題があります。そこで数学者たちは長年にわたり、効率性を維持しながらも適用範囲を広げる方法を研究してきました。

19世紀にはロシアの数学者パフヌティ・チェビシェフが、3次方程式を用いて関数を近似するニュートン法の変種を提案しましたが、チェビシェフのアルゴリズムは単一変数の関数にしか適用できませんでした。

2021年には、ロシアの数学者であるユーリ・ネステロフ氏が任意の数の変数を持つ関数を3次方程式で効率的に近似する方法を証明しました。これは大きな前進でしたが、4次以上の高次方程式への拡張は実現できなかったとのこと。 2024年、プリンストン大学のアミール・アリ・アフマディ教授と彼の元学生であるアブラール・チョードリー氏、ジェフリー・チャン氏の研究チームは、「半正定値計画法」という最適化技術を駆使して、テイラー展開に「ちょっとした調整」を加えることを思いつきました。

アフマディ教授らの手法は、関数が1つの谷だけを持つ「凸性」と、関数が複数式の2乗の和として表せる「二乗和表現可能性」という2つの重要な数学的特性を持つように微調整するというものです。つまり、「高次の近似を使いたいけど計算が難しい」という問題を、「高次の近似を少し調整して計算しやすくする」という発想で解決したというわけです。

この発見により、三次、四次、さらには五次以上の高次テイラー展開を用いた近似が可能になり、収束速度も格段に向上したとのこと。二次近似では誤差が二次収束し、三次近似では誤差が三次収束するというように、より少ない繰り返し計算で正確な答えに到達できるようになりました。 記事作成時点では、ニュートン法は計算コストが高いため、機械学習のような大規模な実用問題では依然として勾配降下法が優先されています。しかし、「私たちの考案したアルゴリズムは理論上、明らかに高速です。計算技術の進歩と並行して、この理論的優位性が実用面でも10～20年後には発揮される可能性があります」とアフマディ教授は予測しています。