論文の概要: An Efficient Multilevel Preconditioned Nonlinear Conjugate Gradient Method for Incremental Potential Contact
- arxiv url: http://arxiv.org/abs/2604.19892v1
- Date: Tue, 21 Apr 2026 18:13:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-25 12:34:33.652109
- Title: An Efficient Multilevel Preconditioned Nonlinear Conjugate Gradient Method for Incremental Potential Contact
- Title（参考訳）: インクリメンタル電位接触に対する高能率多重条件非線形共役勾配法
- Authors: Yu Zhang, Xing Shen, Kemeng Huang, Wei Chen, Yin Yang, Taku Komura, Tiantian Liu, Xingang Pan,
- Abstract要約: インクリメンタル電位接触(IPC)は、交差のないシミュレーションを保証するが、高い計算コストに悩まされる。
非線形最適化のための階層型プレコンディショニングのパワーを解放するMAS-PNCGを提案する。
我々は、PNCG探索方向を、事前条件付き勾配と事前方向を最適に組み合わせたヘッセン対応の2D部分空間に置き換える。
- 参考スコア（独自算出の注目度）: 39.88919534724513
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Incremental Potential Contact (IPC) guarantees intersection-free simulation but suffers from high computational costs due to the expensive Hessian assembly and linear solves required by Newton's method. While Preconditioned Nonlinear Conjugate Gradient (PNCG) avoids Hessian assembly, it has historically struggled with poor convergence in stiff, contact-rich scenarios due to the lack of effective preconditioners; simple Jacobi preconditioners fail to capture the global coupling, while advanced hierarchy-based preconditioners like Multilevel Additive Schwarz (MAS) are computationally prohibitive to rebuild at every nonlinear iteration. We present MAS-PNCG, a method that unlocks the power of hierarchical preconditioning for nonlinear optimization. Our key technical innovation is a Sparse-Input Woodbury update algorithm that incrementally adapts the fine-level MAS components to rapidly evolving contact sets. This bypasses the need for full preconditioner rebuilds, reducing maintenance cost to near-zero while capturing the complex spectral properties of the contact system. Furthermore, we replace heuristic PNCG search directions with a Hessian-aware 2D subspace minimization that optimally combines the preconditioned gradient and previous direction. We also apply a fast per-subdomain conservative CCD method that ensures penetration-free trajectories while avoiding overly restrictive global step sizes. Experiments demonstrate that our MAS-PNCG outperforms state-of-the-art Newton-PCG solvers, GIPC and StiffGIPC, both preconditioned with MAS up to 5.66$\times$ and 2.07$\times$ respectively.
- Abstract（参考訳）: インクリメンタル電位接触(IPC)は、交差のないシミュレーションを保証するが、高価なヘッセン組立とニュートン法で必要とされる線形解法により、高い計算コストに悩まされる。
プレコンディション付き非線形共役勾配 (PNCG) はヘッセン組立を回避しているが、歴史的に効率的なプレコンディショナーの欠如により、厳密で接触に富んだシナリオの収束に苦慮しており、単純なヤコビ事前条件器はグローバル結合を捉えることができず、Multilevel Additive Schwarz (MAS) のような階層に基づく先進的なプレコンディショナーは、全ての非線形反復において計算学的に禁止されている。
非線形最適化のための階層型プレコンディショニングのパワーを解放するMAS-PNCGを提案する。
我々の重要な技術的革新はスパース入力ウッドベリー更新アルゴリズムであり、細粒度MASコンポーネントを急速に進化するコンタクトセットに漸進的に適応する。
これは、完全なプレコンディショナーの再構築の必要性を回避し、コンタクトシステムの複雑なスペクトル特性を捉えながら、メンテナンスコストをほぼゼロに削減する。
さらに,ヒューリスティックなPNCG探索方向を,既定勾配と先行方向を最適に組み合わせたヘッセン式2次元部分空間最小化に置き換える。
また, 過度に制限されたグローバルステップサイズを回避しつつ, 透過性のない軌道を確実にする, サブドメインごとの高速な保守的CCD手法を適用した。
実験により、我々のMAS-PNCGは、それぞれ5.66$\times$と2.07$\times$にMASをプリコンディションした、最先端のNewton-PCGソルバ、GIPC、StiffGIPCより優れていることが示された。
関連論文リスト
- Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization [0.0]
マットロイド制約の下でのサブモジュールは、センシング、データマージ、アクティブラーニング、リソース割り当てなどの応用において、最適化の基本的な問題である。
textitATCG(underlineAdaptive underlineThresholded underlineThresholded underlineThresholded underlineGreedy)を提案する。
CIFAR-10動物データセットを用いたクラスバランス型プロトタイプ選択問題の実験
論文 参考訳（メタデータ） (2026-04-03T19:32:39Z) - GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs [7.079949618914198]
ブランチ・アンド・バウンド(BnB)フレームワークは、パースペクティブ・リラクゼーションを使って最適性を証明できる。
これらの緩和を解く既存の手法は計算集約的であり、スケーラビリティを制限している。
我々は線形収束性と計算効率の両立した近位フレームワークを開発する。
論文 参考訳（メタデータ） (2026-03-01T22:26:09Z) - Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
分散サーバ(DFL)はクライアント・クライアント・アーキテクチャへの依存をなくす。
非滑らかな正規化はしばしば機械学習タスクに組み込まれる。
本稿では,これらの問題を解決する新しいDNCFLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-17T08:32:25Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Curvature-Informed SGD via General Purpose Lie-Group Preconditioners [6.760212042305871]
曲率情報を利用して勾配降下(SGD)を加速する新しい手法を提案する。
提案手法は,行列フリープレコンディショナーと低ランクプレコンディショナーの2つのプレコンディショナーを含む。
プレコンディショニングされたSGD(PSGD)は、ビジョン、NLP、RLタスクにおいてSoTAよりも優れていることを示す。
論文 参考訳（メタデータ） (2024-02-07T03:18:00Z) - PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates [17.777466668123886]
PROMISE ($textbfPr$econditioned $textbfO$ptimization $textbfM$ethods by $textbfI$ncorporating $textbfS$calable Curvature $textbfE$stimates)はスケッチベースの事前条件勾配アルゴリズムである。
PROMISEには、SVRG、SAGA、およびKatyushaのプレコンディション版が含まれている。
論文 参考訳（メタデータ） (2023-09-05T07:49:10Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Learning to Optimize Non-Rigid Tracking [54.94145312763044]
我々は、堅牢性を改善し、解法収束を高速化するために学習可能な最適化を採用する。
まず、CNNを通じてエンドツーエンドに学習された深い特徴にアライメントデータ項を統合することにより、追跡対象をアップグレードする。
次に,プレコンディショニング手法と学習手法のギャップを,プレコンディショナを生成するためにトレーニングされたConditionNetを導入することで埋める。
論文 参考訳（メタデータ） (2020-03-27T04:40:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。