論文の概要: Constrained Optimization Involving Nonconvex $\ell_p$ Norms: Optimality
Conditions, Algorithm and Convergence
- arxiv url: http://arxiv.org/abs/2110.14127v1
- Date: Wed, 27 Oct 2021 02:17:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 15:41:50.376703
- Title: Constrained Optimization Involving Nonconvex $\ell_p$ Norms: Optimality
Conditions, Algorithm and Convergence
- Title（参考訳）: 非凸$\ell_p$ノルムを含む制約付き最適化:最適条件,アルゴリズム,収束
- Authors: Hao Wang, Yining Gao, Jiashan Wang, Hongying Liu
- Abstract要約: 我々は $ell_p$ ノルムの次数と $ell_p$ 球の正規錐の次数を計算する。
逐次最適性条件は反復的に重み付けされたアルゴリズムに対して容易に満足できることを示す。
- 参考スコア（独自算出の注目度）: 4.886985244621422
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper investigates the optimality conditions for characterizing the
local minimizers of the constrained optimization problems involving an $\ell_p$
norm ($0<p<1$) of the variables, which may appear in either the objective or
the constraint. This kind of problems have strong applicability to a wide range
of areas since usually the $\ell_p$ norm can promote sparse solutions. However,
the nonsmooth and non-Lipschtiz nature of the $\ell_p$ norm often cause these
problems difficult to analyze and solve. We provide the calculation of the
subgradients of the $\ell_p$ norm and the normal cones of the $\ell_p$ ball.
For both problems, we derive the first-order necessary conditions under various
constraint qualifications. We also derive the sequential optimality conditions
for both problems and study the conditions under which these conditions imply
the first-order necessary conditions. We point out that the sequential
optimality conditions can be easily satisfied for iteratively reweighted
algorithms and show that the global convergence can be easily derived using
sequential optimality conditions.
- Abstract（参考訳）: 本稿では,変数の$\ell_p$ ノルム (0<p<1$) を含む制約付き最適化問題の局所的最小化条件について検討する。
この種の問題は、通常$\ell_p$ノルムがスパース解を促進できるため、幅広い領域に強い適用性を持つ。
しかし、$\ell_p$ のノルムの非滑らかで非リプシッツ性はしばしばこれらの問題を解析し、解くのが難しい。
我々は、$\ell_p$ のノルムの次数と$\ell_p$ のボールの通常の円錐の計算を提供する。
どちらの問題に対しても,制約条件の異なる一階必要条件を導出する。
また、両問題に対する逐次最適条件を導出し、これらの条件が第一次必要条件を意味する条件を研究する。
繰り返し重み付けアルゴリズムでは逐次最適条件が容易に満たせることを指摘し,逐次最適条件を用いて大域収束が容易に導出できることを示す。
関連論文リスト
- SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker
Assumptions [50.20087216230159]
統計的クエリモデルにおける非ガウス成分分析(NGCA)の複雑さについて検討する。
本研究は, NGCAの場合, モーメントマッチング条件のみにおいて, ほぼ最適SQ下限を証明した。
論文 参考訳（メタデータ） (2024-03-07T18:49:32Z) - First-order optimality conditions for non-commutative optimization
problems [0.0]
問題変数、状態および演算子最適条件の小さなバリエーションを通して導出する。
作用素最適条件はカルーシュ=クーン=タッカー条件の非可換類似である。
我々は、非可換作用素最適性の弱い形式がアルキメデス NPO 問題すべてに成り立つことを証明している。
論文 参考訳（メタデータ） (2023-11-30T17:00:06Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave
Minimax Optimization [22.392563619845212]
非コンケーブなミニマックス最適化は、機械学習に広く応用されているため、この10年で大きな注目を集めている。
本稿では,一様かつ二重に勾配のバランスをとることができる新しい単一ループ二元アルゴリズムを提案する。
具体的には、指数$thetain(0,1)$の片側KL条件の下で、DS-GDAは$mathcalO(eps-2$2$1)の結果と収束する。
論文 参考訳（メタデータ） (2022-12-26T00:28:07Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文 参考訳（メタデータ） (2020-10-22T22:54:54Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。