論文の概要: An Online Algorithm for Chance Constrained Resource Allocation
- arxiv url: http://arxiv.org/abs/2303.03254v1
- Date: Mon, 6 Mar 2023 16:17:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 15:30:56.832254
- Title: An Online Algorithm for Chance Constrained Resource Allocation
- Title（参考訳）: 資源割当を制約するオンラインアルゴリズム
- Authors: Yuwei Chen, Zengde Deng, Yinzhi Zhou, Zaiyi Chen, Yujie Chen, Haoyuan
Hu
- Abstract要約: 本稿では,オンライン資源配分問題 (RAP) を確率制約で検討する。
私たちの知る限りでは、オンラインRAP問題に制約が導入されるのはこれが初めてです。
- 参考スコア（独自算出の注目度）: 10.791923293928987
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the online stochastic resource allocation problem (RAP)
with chance constraints. The online RAP is a 0-1 integer linear programming
problem where the resource consumption coefficients are revealed column by
column along with the corresponding revenue coefficients. When a column is
revealed, the corresponding decision variables are determined instantaneously
without future information. Moreover, in online applications, the resource
consumption coefficients are often obtained by prediction. To model their
uncertainties, we take the chance constraints into the consideration. To the
best of our knowledge, this is the first time chance constraints are introduced
in the online RAP problem. Assuming that the uncertain variables have known
Gaussian distributions, the stochastic RAP can be transformed into a
deterministic but nonlinear problem with integer second-order cone constraints.
Next, we linearize this nonlinear problem and analyze the performance of
vanilla online primal-dual algorithm for solving the linearized stochastic RAP.
Under mild technical assumptions, the optimality gap and constraint violation
are both on the order of $\sqrt{n}$. Then, to further improve the performance
of the algorithm, several modified online primal-dual algorithms with heuristic
corrections are proposed. Finally, extensive numerical experiments on both
synthetic and real data demonstrate the applicability and effectiveness of our
methods.
- Abstract（参考訳）: 本稿では,オンライン確率的資源配分問題(RAP)を確率制約で検討する。
オンラインRAPは0-1整数線形計画問題であり、リソース消費係数とそれに対応する収益係数を列で表す。
カラムが露見されると、対応する決定変数は、将来の情報なしで瞬時に決定される。
さらに、オンラインアプリケーションでは、リソース消費係数は予測によって得られることが多い。
不確実性をモデル化するために、私たちは機会制約を考慮に入れます。
私たちの知る限りでは、オンラインRAP問題に制約が導入されるのはこれが初めてです。
不確実変数がガウス分布を知っていれば、確率RAPは整数二階錐の制約を伴う決定論的だが非線形問題に変換できる。
次に、この非線形問題を線形化し、線形化確率RAPを解くためのバニラオンライン原始双対アルゴリズムの性能を解析する。
穏やかな技術的仮定の下では、最適性ギャップと制約違反はともに$\sqrt{n}$の順序である。
次に, アルゴリズムの性能をさらに向上させるために, ヒューリスティック補正を施したオンライン原始アルゴリズムを複数提案する。
最後に,合成データと実データの両方について広範な数値実験を行い,本手法の適用性と有効性を示した。
関連論文リスト
- Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。
本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。
2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文 参考訳（メタデータ） (2024-09-24T04:39:47Z) - Offline Policy Optimization in RL with Variance Regularizaton [142.87345258222942]
定常分布補正を用いたオフラインRLアルゴリズムの分散正則化を提案する。
Fenchel双対性を用いることで、分散正規化器の勾配を計算するための二重サンプリング問題を回避することができることを示す。
オフライン分散正規化アルゴリズム(OVAR)は,既存のオフラインポリシー最適化アルゴリズムを拡張できる。
論文 参考訳（メタデータ） (2022-12-29T18:25:01Z) - Learning-Augmented Algorithms for Online Linear and Semidefinite
Programming [9.849604820019394]
Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。
SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。
予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
論文 参考訳（メタデータ） (2022-09-21T19:16:29Z) - Online Contextual Decision-Making with a Smart Predict-then-Optimize
Method [4.061135251278187]
資源制約を考慮したオンライン文脈決定問題について検討する。
本稿では,「スマート予測-then-(SPO)」法に基づく予測ステップと,ミラー降下に基づく2つの更新ステップを混合するアルゴリズムを提案する。
提案手法の全体的な収束速度はオンラインミラー降下の$mathcalO(T-1/2)$収束に依存することを示す。
論文 参考訳（メタデータ） (2022-06-15T06:16:13Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-02-09T19:22:34Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Stochastic Online Linear Regression: the Forward Algorithm to Replace
Ridge [24.880035784304834]
オンラインリッジ回帰とフォワードアルゴリズムに対して高い確率的後悔境界を導出する。
これにより、オンライン回帰アルゴリズムをより正確に比較し、有界な観測と予測の仮定を排除できる。
論文 参考訳（メタデータ） (2021-11-02T13:57:53Z) - A spectral algorithm for robust regression with subgaussian rates [0.0]
本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。
目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
論文 参考訳（メタデータ） (2020-07-12T19:33:50Z) - Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。
近勾配法はOWL回帰を解くための標準手法として用いられる。
未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
論文 参考訳（メタデータ） (2020-06-29T23:35:53Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。