論文の概要: A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization
- arxiv url: http://arxiv.org/abs/2301.04204v1
- Date: Tue, 10 Jan 2023 20:43:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-12 14:38:06.195017
- Title: A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization
- Title（参考訳）: 一般非凸円錐最適化のためのNewton-CGに基づくバリア拡張ラグランジアン法
- Authors: Chuan He, Heng Huang and Zhaosong Lu
- Abstract要約: 本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
- 参考スコア（独自算出の注目度）: 77.8485863487028
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we consider finding an approximate second-order stationary
point (SOSP) of general nonconvex conic optimization that minimizes a twice
differentiable function subject to nonlinear equality constraints and also a
convex conic constraint. In particular, we propose a Newton-conjugate gradient
(Newton-CG) based barrier-augmented Lagrangian method for finding an
approximate SOSP of this problem. Under some mild assumptions, we show that our
method enjoys a total inner iteration complexity of $\widetilde{\cal
O}(\epsilon^{-11/2})$ and an operation complexity of $\widetilde{\cal
O}(\epsilon^{-11/2}\min\{n,\epsilon^{-5/4}\})$ for finding an
$(\epsilon,\sqrt{\epsilon})$-SOSP of general nonconvex conic optimization with
high probability. Moreover, under a constraint qualification, these complexity
bounds are improved to $\widetilde{\cal O}(\epsilon^{-7/2})$ and
$\widetilde{\cal O}(\epsilon^{-7/2}\min\{n,\epsilon^{-3/4}\})$, respectively.
To the best of our knowledge, this is the first study on the complexity of
finding an approximate SOSP of general nonconvex conic optimization.
Preliminary numerical results are presented to demonstrate superiority of the
proposed method over first-order methods in terms of solution quality.
- Abstract（参考訳）: 本稿では,非凸円錐最適化の2次定常点(SOSP)について,非線形等式制約と凸円錐制約の2つの微分可能な関数を最小化することを検討する。
特に, ニュートン共役勾配 (newton-cg) に基づくバリア型ラグランジアン法を提案し, この問題の近似 sosp を求める。
いくつかの穏やかな仮定の下では、本手法は、$\widetilde{\cal o}(\epsilon^{-11/2})$ と$\widetilde{\cal o}(\epsilon^{-11/2}\min\{n,\epsilon^{-5/4}\})$ という、高確率の一般非凸錐最適化の完全内的反復複雑性と、$(\epsilon,\sqrt{\epsilon})$-sosp の演算複雑性を享受できることを示した。
さらに、制約条件の下では、これらの複雑性境界は、それぞれ$\widetilde{\cal o}(\epsilon^{-7/2})$と$\widetilde{\cal o}(\epsilon^{-7/2}\min\{n,\epsilon^{-3/4}\})$に改善される。
我々の知る限りでは、一般的な非凸円錐最適化の近似SOSPを求める複雑さに関する最初の研究である。
提案手法が一階法よりも解品質の点で優れていることを示すために, 予備的な数値計算結果を示す。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - A Newton-CG based augmented Lagrangian method for finding a second-order
stationary point of nonconvex equality constrained optimization with
complexity guarantees [0.5013248430919224]
まず,制約なし最適化の近似SOSPを求めるNewton-CG法を提案する。
次に,非等式制約最適化のラグランジアン近似SOSPを提案する。
また,本論文では提案手法の優位性を実証した。
論文 参考訳（メタデータ） (2023-01-09T01:39:46Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A Newton-CG based barrier method for finding a second-order stationary
point of nonconvex conic optimization with complexity guarantees [0.5922488908114022]
2つの微分可能な関数の交叉を最小限に抑える2階定常点(SOSP)の発見を検討する。
我々の方法は反復であるだけでなく、最もよく知られた複雑性にマッチする$mincal O(epsilon/2)を達成する。
論文 参考訳（メタデータ） (2022-07-12T17:21:45Z) - Accelerated first-order methods for convex optimization with locally
Lipschitz continuous gradient [0.0]
まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。
提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。
提案手法の性能を実証するために,予備的な数値計算結果を示す。
論文 参考訳（メタデータ） (2022-06-02T10:34:26Z) - A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文 参考訳（メタデータ） (2020-06-03T04:00:52Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。