論文の概要: Conditional Gradient Methods for Convex Optimization with General Affine
and Nonlinear Constraints
- arxiv url: http://arxiv.org/abs/2007.00153v3
- Date: Tue, 29 Jun 2021 15:49:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 06:22:15.709804
- Title: Conditional Gradient Methods for Convex Optimization with General Affine
and Nonlinear Constraints
- Title（参考訳）: 一般アフィンおよび非線形制約を用いた凸最適化のための条件勾配法
- Authors: Guanghui Lan, Edwin Romeijn and Zhiqiang Zhou
- Abstract要約: 本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。
まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。
さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
- 参考スコア（独自算出の注目度）: 8.643249539674612
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Conditional gradient methods have attracted much attention in both machine
learning and optimization communities recently. These simple methods can
guarantee the generation of sparse solutions. In addition, without the
computation of full gradients, they can handle huge-scale problems sometimes
even with an exponentially increasing number of decision variables. This paper
aims to significantly expand the application areas of these methods by
presenting new conditional gradient methods for solving convex optimization
problems with general affine and nonlinear constraints. More specifically, we
first present a new constraint extrapolated condition gradient (CoexCG) method
that can achieve an ${\cal O}(1/\epsilon^2)$ iteration complexity for both
smooth and structured nonsmooth function constrained convex optimization. We
further develop novel variants of CoexCG, namely constraint extrapolated and
dual regularized conditional gradient (CoexDurCG) methods, that can achieve
similar iteration complexity to CoexCG but allow adaptive selection for
algorithmic parameters. We illustrate the effectiveness of these methods for
solving an important class of radiation therapy treatment planning problems
arising from healthcare industry. To the best of our knowledge, all the
algorithmic schemes and their complexity results are new in the area of
projection-free methods.
- Abstract（参考訳）: 近年,機械学習と最適化のコミュニティでは,条件勾配法が注目されている。
これらの単純な手法はスパースソリューションの生成を保証することができる。
さらに、完全な勾配の計算がなければ、指数関数的に多くの決定変数が増加する場合でも、大規模な問題を扱うことができる。
本稿では, 一般的なアフィンおよび非線形制約を伴う凸最適化問題を解くための新しい条件勾配法を提案することにより, これらの手法の適用領域を大幅に拡大することを目的とする。
より具体的には、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、${\cal O}(1/\epsilon^2)$反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。
さらに,制約外挿法と2重正規化条件勾配法(coexdurcg法)という,coexcgと同様の反復複雑性を実現するがアルゴリズムパラメータの適応的選択を可能にする新しい手法を開発した。
本研究は,医療産業が抱える放射線治療計画の課題を解決するために,これらの手法の有効性について述べる。
我々の知る限りでは、全てのアルゴリズムスキームとその複雑さは射影のない手法の分野において新しいものである。
関連論文リスト
- Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - A conditional gradient homotopy method with applications to Semidefinite
Programming [1.6369790794838281]
ホモトピーに基づく条件勾配法による凸最適化問題の解法。
我々の理論的複雑さは、最先端のSDPに直面すると競合し、安価なプロジェクションフリーの決定的な利点がある。
論文 参考訳（メタデータ） (2022-07-07T05:48:27Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Continuation Newton methods with deflation techniques for global
optimization problems [3.705839280172101]
最適化問題のグローバルな最小点はエンジニアリングである。
本稿では,この非線形大規模問題に対する新しいメメティックアルゴリズムについて考察する。
我々の数値実験によると、新しいアルゴリズムは制約のない未制約問題に対してうまく機能する。
論文 参考訳（メタデータ） (2021-07-29T09:53:49Z) - On Constraints in First-Order Optimization: A View from Non-Smooth
Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。
提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。
結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文 参考訳（メタデータ） (2021-07-17T11:45:13Z) - Constrained and Composite Optimization via Adaptive Sampling Methods [3.4219044933964944]
本論文の動機は,制約付き最適化問題を解くための適応サンプリング手法を開発することにある。
本論文で提案する手法は、f が凸(必ずしも微分可能ではない)である合成最適化問題 min f(x) + h(x) にも適用できる近位勾配法である。
論文 参考訳（メタデータ） (2020-12-31T02:50:39Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。