論文の概要: Convex mixed-integer optimization with Frank-Wolfe methods
- arxiv url: http://arxiv.org/abs/2208.11010v6
- Date: Thu, 18 Jul 2024 09:10:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-20 00:32:05.337034
- Title: Convex mixed-integer optimization with Frank-Wolfe methods
- Title（参考訳）: Frank-Wolfe法による凸混合整数最適化
- Authors: Deborah Hendrych, Hannah Troppens, Mathieu Besançon, Sebastian Pokutta,
- Abstract要約: 混合整数非線形最適化は理論的および計算的課題を示す。
本稿では,凸ノード緩和を用いた分岐結合アルゴリズムに基づいて,これらの問題の解法を提案する。
- 参考スコア（独自算出の注目度）: 20.37026309402396
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Mixed-integer nonlinear optimization encompasses a broad class of problems that present both theoretical and computational challenges. We propose a new type of method to solve these problems based on a branch-and-bound algorithm with convex node relaxations. These relaxations are solved with a Frank-Wolfe algorithm over the convex hull of mixed-integer feasible points instead of the continuous relaxation via calls to a mixed-integer linear solver as the linear minimization oracle. The proposed method computes feasible solutions while working on a single representation of the polyhedral constraints, leveraging the full extent of mixed-integer linear solvers without an outer approximation scheme and can exploit inexact solutions of node subproblems.
- Abstract（参考訳）: 混合整数非線形最適化は、理論的および計算的課題の両方を示す幅広い種類の問題を含む。
本稿では,凸ノード緩和を用いた分岐結合アルゴリズムに基づいて,これらの問題の解法を提案する。
これらの緩和は、混合整数線型解法を線形最小化オラクルとして呼び出すことで連続的な緩和ではなく、混合整数可能点の凸殻上のフランク・ウルフアルゴリズムによって解決される。
提案手法は多面体制約の1つの表現に取り組みながら実現可能な解を計算し、外部近似スキームを使わずに混合整数線形解法の全範囲を活用でき、ノードサブプロブレムの不正確な解を活用できる。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Oracle Complexity of Single-Loop Switching Subgradient Methods for
Non-Smooth Weakly Convex Functional Constrained Optimization [12.84152722535866]
目的関数が弱凸あるいは弱凸である非制約最適化問題を考える。
そこで本研究では,一階調律であり,実装が容易な段階的手法について考察する。
論文 参考訳（メタデータ） (2023-01-30T22:13:14Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Sparse Signal Reconstruction for Nonlinear Models via Piecewise Rational
Optimization [27.080837460030583]
劣化した信号を非線形歪みと限られたサンプリングレートで再構成する手法を提案する。
本手法は,不正確な適合項と罰則として定式化する。
シミュレーションの利点の観点から,この問題の活用方法を示す。
論文 参考訳（メタデータ） (2020-10-29T09:05:19Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳（メタデータ） (2020-10-23T05:24:05Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
非剛体形状マッチングのための凸混合整数プログラミングの定式化。
効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
論文 参考訳（メタデータ） (2020-02-28T09:54:06Z) - Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion
and Strong Solutions to Variational Inequalities [14.848525762485872]
非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。
これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
論文 参考訳（メタデータ） (2020-02-20T17:12:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。