論文の概要: A Newton-CG based augmented Lagrangian method for finding a second-order
stationary point of nonconvex equality constrained optimization with
complexity guarantees
- arxiv url: http://arxiv.org/abs/2301.03139v1
- Date: Mon, 9 Jan 2023 01:39:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-10 16:33:20.975574
- Title: A Newton-CG based augmented Lagrangian method for finding a second-order
stationary point of nonconvex equality constrained optimization with
complexity guarantees
- Title(参考訳): 複雑性保証付き非凸等式制約最適化の2次定常点を求めるNewton-CGによる拡張ラグランジアン法
- Authors: Chuan He, Zhaosong Lu and Ting Kei Pong
- Abstract要約: まず,制約なし最適化の近似SOSPを求めるNewton-CG法を提案する。
次に,非等式制約最適化のラグランジアン近似SOSPを提案する。
また,本論文では提案手法の優位性を実証した。
- 参考スコア(独自算出の注目度): 0.5013248430919224
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we consider finding a second-order stationary point (SOSP) of
nonconvex equality constrained optimization when a nearly feasible point is
known. In particular, we first propose a new Newton-CG method for finding an
approximate SOSP of unconstrained optimization and show that it enjoys a
substantially better complexity than the Newton-CG method [56]. We then propose
a Newton-CG based augmented Lagrangian (AL) method for finding an approximate
SOSP of nonconvex equality constrained optimization, in which the proposed
Newton-CG method is used as a subproblem solver. We show that under a
generalized linear independence constraint qualification (GLICQ), our AL method
enjoys a total inner iteration complexity of $\widetilde{\cal
O}(\epsilon^{-7/2})$ and an operation complexity of $\widetilde{\cal
O}(\epsilon^{-7/2}\min\{n,\epsilon^{-3/4}\})$ for finding an
$(\epsilon,\sqrt{\epsilon})$-SOSP of nonconvex equality constrained
optimization with high probability, which are significantly better than the
ones achieved by the proximal AL method [60]. Besides, we show that it has 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}\})$ when the GLICQ does not hold. To
the best of our knowledge, all the complexity results obtained in this paper
are new for finding an approximate SOSP of nonconvex equality constrained
optimization with high probability. Preliminary numerical results also
demonstrate the superiority of our proposed methods over the ones in [56,60].
- Abstract(参考訳): 本稿では,非凸等性制約付き最適化の2次定常点(sosp)を求める。
特に,制約のない最適化の近似 sosp を求めるnewton-cg 法を提案し,newton-cg 法 [56] よりもかなり複雑であることを示す。
そこで本研究では,非凸等性制約付き最適化の近似 sosp を求めるために,newton-cg を用いた拡張ラグランジアン (al) 法を提案する。
一般化線形独立制約資格 (glicq) の下では、al法では、$\widetilde{\cal o}(\epsilon^{-7/2})$ と$\widetilde{\cal o}(\epsilon^{-7/2}\min\{n,\epsilon^{-3/4}\})$(\epsilon,\sqrt{\epsilon})$-sosp の非凸等化制限付き最適化が高確率で実現されており、これは近位al法 [60] によって達成されたものよりもかなり良い。
さらに、グリックが成立しない場合、全内的反復複雑性は$\widetilde{\cal o}(\epsilon^{-11/2})$であり、演算複雑性は$\widetilde{\cal o}(\epsilon^{-11/2}\min\{n,\epsilon^{-5/4}\})$であることを示した。
我々の知る限り、この論文で得られた複雑さの結果は、高い確率で非凸等式制約付き最適化の近似SOSPを見つけるために新しいものである。
また, [56,60] の手法よりも提案手法の方が優れていることを示す。
関連論文リスト
- Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。
本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
論文 参考訳(メタデータ) (2023-09-04T19:47:04Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳(メタデータ) (2023-06-30T20:36:44Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - 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) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳(メタデータ) (2020-06-24T04:41:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。