最も近い 最も遠い 最も広い

科学分野:

• 最適化アルゴリズム
• 計算式幾何学
• コンベックス分析

背景:

• コンパクトな凸集合の直径と最遠の点の決定は,最適化における基本的な問題である.
• フランク・ウォルフのような既存のアルゴリズムは,非凸な問題のローカルマキシマに閉じ込められる.

研究 の 目的:

• コンパクトな凸集合の直径と最遠点を計算するための新しいアルゴリズムを提案し,テストする.
• グラデントベースのアルゴリズムの局所的な最大値の制限を克服するホモトピーの方法の有効性を調査する.

主な方法:

• フランク・ウルフと予測されたグラデント上昇アルゴリズムの構築とテスト.
• ホモトピーの方法を開発し,徐々に球をターゲットセットに変形させる.
• 凸の円と球の交差点,および凸のサブレベルセットのサポート関数の計算.

主要な成果:

• フランク・ウォルフとプロジェクテッド・グラデント・アセンスのアルゴリズムは,テストされたコンパクト・コンベックス・セットで比較可能な性能を示している.
• ホモトピー法を使用しない場合,フランク-ウォルフアルゴリズムはより高い信頼性を示します.
• ホモトピーメソッドは,投影されたグラデント上昇アルゴリズムを強化し,故障から回復することができます.

結論:

• フランク・ウォルフとプロジェクテッド・グラデント・アセンスは,直径と最遠点の計算に有効である.
• ホモトピーの方法は,予測されたグラデントの上昇を大幅に改善し,その頑丈性を高めます.
• この研究は,幾何学的な最適化問題に対する洗練されたアルゴリズムのアプローチに貢献しています.