論文の概要: A polynomial-based QCQP solver for encrypted optimization

• arxiv url: http://arxiv.org/abs/2510.17294v1
• Date: Mon, 20 Oct 2025 08:31:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:39.369359
• Title: A polynomial-based QCQP solver for encrypted optimization
• Title（参考訳）: 暗号化最適化のための多項式型QCQPソルバ
• Authors: Sebastian Schlor, Andrea Iannelli, Junsoo Kim, Hyungbo Shim, Frank Allgöwer,
• Abstract要約: 本稿では,加法と乗法のみを用いて,2次制約付き2次最適化問題のクラスを解く新しい方法を提案する。 このアプローチにより、同型暗号方式の能力により、プライベートデータ上の制約付き最適化問題を解くことができる。
• 参考スコア（独自算出の注目度）: 0.7340017786387767
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we present a novel method for solving a class of quadratically constrained quadratic optimization problems using only additions and multiplications. This approach enables solving constrained optimization problems on private data since the operations involved are compatible with the capabilities of homomorphic encryption schemes. To solve the constrained optimization problem, a sequence of polynomial penalty functions of increasing degree is introduced, which are sufficiently steep at the boundary of the feasible set. Adding the penalty function to the original cost function creates a sequence of unconstrained optimization problems whose minimizer always lies in the admissible set and converges to the minimizer of the constrained problem. A gradient descent method is used to generate a sequence of iterates associated with these problems. For the algorithm, it is shown that the iterate converges to a minimizer of the original problem, and the feasible set is positively invariant under the iteration. Finally, the method is demonstrated on an illustrative cryptographic problem, finding the smaller value of two numbers, and the encrypted implementability is discussed.
• Abstract（参考訳）: 本稿では,加法と乗法のみを用いて,2次制約付き2次最適化問題のクラスを解く新しい方法を提案する。 このアプローチは、関係する操作が同型暗号方式の能力と互換性があるため、プライベートデータ上の制約付き最適化問題を解くことができる。 制約付き最適化問題を解くために、次数増加の多項式ペナルティ関数列を導入し、実現可能な集合の境界において十分に急となる。 元のコスト関数にペナルティ関数を加えると、最小化が許容集合に常に存在するような制約のない最適化問題の列が生成され、制約された問題の最小化に収束する。 勾配降下法はこれらの問題に関連する反復列を生成するために用いられる。 アルゴリズムでは、イテレートは元の問題の最小化に収束し、実現可能な集合は反復の下で正に不変であることが示される。 最後に,2つの数値の小さい値を求めるための図解的暗号問題に対して,本手法を実証し,その実装性について考察する。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。 まず、この方法はスティーフェル多様体に拡張される。 また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
  論文  参考訳（メタデータ） (2023-03-29T07:36:54Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.1044138971639734]
  強い凸関数制約を受ける凸関数を最小化するために,高速化された原始双対アルゴリズムを導入する。 特にGoogleのパーソナライズされたPageRank問題では、スパシティ誘導最適化におけるメソッドのパフォーマンスが優れています。
  論文  参考訳（メタデータ） (2022-12-21T16:04:53Z)
• Convex mixed-integer optimization with Frank-Wolfe methods [20.37026309402396]
  混合整数非線形最適化は理論的および計算的課題を示す。 本稿では,凸ノード緩和を用いた分岐結合アルゴリズムに基づいて,これらの問題の解法を提案する。
  論文  参考訳（メタデータ） (2022-08-23T14:46:54Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。