論文の概要: Implicit Primal-Dual Interior-Point Methods for Quadratic Programming

• arxiv url: http://arxiv.org/abs/2604.00364v1
• Date: Wed, 01 Apr 2026 01:21:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-02 16:44:31.784037
• Title: Implicit Primal-Dual Interior-Point Methods for Quadratic Programming
• Title（参考訳）: 二次計画法における暗黙の2次元内点法
• Abstract要約: そこで本研究では,2次元内点法を用いて2次プログラムを解く方法を提案する。 我々は、ソフト剰余関数が、よく使われる指数写像と比較して、好ましい数値的性質を持つことを証明した。
• 参考スコア（独自算出の注目度）: 11.96478240313977
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces a new method for solving quadratic programs using primal-dual interior-point methods. Instead of handling complementarity as an explicit equation in the Karush-Kuhn-Tucker (KKT) conditions, we ensure that complementarity is implicitly satisfied by construction. This is achieved by introducing an auxiliary variable and relating it to the duals and slacks via a retraction map. Specifically, we prove that the softplus function has favorable numerical properties compared to the commonly used exponential map. The resulting KKT system is guaranteed to be spectrally bounded, thereby eliminating the most pressing limitation of primal-dual methods: ill-conditioning near the solution. These attributes facilitate the solution of the underlying linear system, either by removing the need to compute factorizations at every iteration, enabling factorization-free approaches like indirect solvers, or allowing the solver to achieve high accuracy in low-precision arithmetic. Consequently, this novel perspective opens new opportunities for interior-point methods, especially for solving large-scale problems to high precision.
• Abstract（参考訳）: 本稿では,2次元内点法を用いて2次プログラムを解く手法を提案する。 カルーシュ・クーン・タッカー(KKT)条件における明示的な方程式として相補性を扱う代わりに、構成によって相補性が暗黙的に満足されることを保証する。 これは補助変数を導入し、リトラクション写像を介して双対とスラックスに関連付けることで達成される。 具体的には、よく用いられる指数写像と比較して、ソフトプラス関数が好適な数値特性を持つことを示す。 結果として生じるKKT系はスペクトル的に有界であることが保証され、そのため原始双対法(溶液近傍の条件条件)の最も強い制限が排除される。 これらの属性は、各イテレーションで分解を計算する必要をなくし、間接的な解法のような因数分解のないアプローチを可能にしたり、解法が低精度の算術で高い精度を実現できるようにすることで、根底にある線形システムの解を促進する。 このため、この新たな視点はインテリアポイント法、特に大規模問題を高精度に解くための新たな機会を開放する。

関連論文リスト

• Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates [3.2919103562171865]
  本研究では, パラメータフリーかつ適応的不動点アルゴリズムを開発した。 固定点残差と一意な固定点の距離の両方に対して、明示的な線形収束率を確立する。 いくつかの例における数値実験により、提案アルゴリズムは既存の適応的不動点法と競合し、しばしば優れることを示した。
  論文  参考訳（メタデータ） (2026-08-10T02:25:00Z)
• Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity [10.643433352418915]
  一次非バランス性非コンケーブ最小値再構成の条件境界を均一に拡張した。 双対正則化では、大域的局所論はバイアスとともに議論される。 KKT。
  論文  参考訳（メタデータ） (2026-07-09T21:28:29Z)
• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  等式制約と不等式制約を持つ2次最適化問題の解に対するオンライン統計的推測について検討した。 これらの問題を解決するための逐次プログラミング(SSQP)手法を開発し、目的の近似と制約の線形近似を逐次実行することでステップ方向を計算する。 本手法は,Hjek と Le Cam の意味での最適原始双対制限行列を用いて局所正規性を示す。
  論文  参考訳（メタデータ） (2025-11-27T06:16:17Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• $\ell_0$-Regularized Quadratic Surface Support Vector Machines [0.0]
  カーネルフリーの二次曲面支持ベクトルマシンは、カーネル関数に依存することなく非線形決定境界をモデル化する柔軟性により、近年注目を集めている。 本稿では,モデルパラメータに濃度制約を課すことにより,QSVMのスパース変種を提案する。 我々は,いくつかの実世界のデータセットに対するアプローチを検証し,高い分類性能を維持しながらオーバーフィッティングを低減できることを実証した。
  論文  参考訳（メタデータ） (2025-01-20T04:26:34Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Alternating Iteratively Reweighted $\ell_1$ and Subspace Newton Algorithms for Nonconvex Sparse Optimization [11.56128809794923]
  本稿では,可微分損失関数と非滑らか正規化関数の和を最小化する新しいハイブリッドアルゴリズムを提案する。 臨界点へのグローバル収束を証明し、適切な条件下では、アルゴリズムが既存の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2024-07-24T12:15:59Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints [8.643249539674612]
  本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。 まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。 さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
  論文  参考訳（メタデータ） (2020-06-30T23:49:38Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。