離散凸解析(<特集>最適化の数理)
スポンサーリンク
概要
- 論文の詳細を見る
A theory of "discrete convex analysis" is developed for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, subgradients, the Fenchel min-max duality, separation theorems and the Lagrange duality framework for convex/nonconvex optimization. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms. This paper extends our understanding of the relationship between convex functions and submodular functions investigated in the eighties by A. Frank, S. Fujishige, L. Lovasz and others, and also explores a novel duality framework in nonlinear integer programming.
- 日本応用数理学会の論文
- 1996-12-16
著者
-
室田 一雄
京都大学
-
室田 一雄
京都大学数理解析研究所
-
室田 一雄
Department Of Mathematical Informatics Graduate School Of Information Science And Technology Univers
関連論文
- A survey on convergence theorems of the dqds algorithm for computing singular values
- Solving Sparse Semidefinite Programs by Matrix Completion (Part II) (Mathematical Science of Optimization)
- Solving Sparse Semidefinite Programs by Matrix Completion (Part I) (Mathematical Science of Optimization)
- 特異値計算アルゴリズムdqds法の収束定理 (計算科学の基盤技術としての高速アルゴリズムとその周辺)
- 特異値計算アルゴリズムdqds法の理論保証付き超2次収束シフト戦略(理論)
- On Convergence of the dqds and mdLVs Algorithms for Computing Matrix Singular Values(Mathematical Sciences for Large Scale Numerical Simulations)
- Sinc-Gauss Sampling Formula(Mathematical Sciences for Large Scale Numerical Simulations)
- 特異値計算のためのdqds法とmdLVs法の収束性について(理論)
- Gauss核サンプリング公式の複素関数論による誤差評価(理論)
- 連続/離散ハイブリッドM凸関数に関する一考察
- 電気抵抗回路に基づくグラフ上の半教師付き学習機械(テーマセッション,文字認識・文書理解)
- Electric Network Kernel for Support Vector Machines(SVM)
- Electric Network Kernel for Support Vector Machines (Decision Theory and Optimization Algorithms)
- 2段階アルゴリズムによるSVMの解法
- 連続/離散ハイブリッド凸最適化とその最適性規準
- 2段階アルゴリズムによるSVMの解法 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
- 半正定値計画法に対する主双対内点法の群対称性 (数理最適化の理論とアルゴリズム)
- 付値マトロイドの理論 : 多項式行列の組合せ構造
- Computing the Combinatorial Canonical Form of a Layered Mixed Matrix
- ロバスト混合整数計画に対するBenders分解法(応用)
- 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
- Scaling Algorithms for M-convex Function Minimization (Mathematical Optimization Theory and its Algorithm)
- M凸関数の最小化に対するスケーリングアルゴリズムとその実験的評価(組合せ)
- スケーリング技法を用いたM凸関数の最小化アルゴリズム
- Quasi M-convex Functions and Minimization Algorithms (Algorithm Engineering as a New Paradigm)
- Extension of M-convexity and L-convexity to Polyhedral Convex Functions : Extended Abstract (Continuous and Discrete Mathematics for Optimization)
- 一般化ポリマトロイド上のM凸関数(組合せ最適化(3))
- 組合せ最適化と凸解析(文献賞)
- 組合せ論的緩和法 : 組合せ最適化技法による代数計算(組合せ最適化)
- L凸関数に対する離散ヘッセ行列(離散最適化)
- M凸劣モジュラ流問題に対する容量スケーリング法
- M凸劣モジュラ流問題に対する容量スケーリングアルゴリズム(最適化(1))
- 電気抵抗回路に基づくグラフ上の半教師付き学習機械(テーマセッション,文字認識・文書理解)
- 回転変位を持つ対称構造物のブロック対角化手法〔英文〕
- 回転変位を持つ対称構造物のブロック対角化手法--理論編
- 回転変位を持つ対称構造物のブロック対角化手法--数値解析編
- 非解析的な関数を用いた変数変換型数値積分公式
- 非解析的な関数を用いた変数変換型数値積分公式について(並列数値計算アルゴリズムとその周辺)
- 最適化算法と高速自動微分法について(数値解析と科学計算)
- 高速微分法における変数消去のグラフ論的考察
- Voronoi線図を構成する逐次添加型算法の改良と諸算法の実験的比較
- 多変数多項式行列の構造的弱既約性と構造的可制御性判定への応用
- Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
- 多項式行列に対する組合せ論的緩和法の実現について(組合せ最適化)
- 分割行列の階層的分解(II) : 同値変換(離散数学)
- 分割行列の階層的分解(I) : 相似変換(離散数学)
- 数理経済学と離散最適化の新たな出会い
- 不可分財をもつ経済均衡のM凸劣モジュラ流による定式化 (数理最適化の理論とアルゴリズム)
- "一般性"を仮定した分割行列に関する最大最小定理とDulmage-Mendelsohn型分解(組合せ最適化)
- 独立マッチングの基本構造に関する一定理(組合せ最適化)
- Rigorous Proof of Cubic Convergence for the dqds Algorithm for Singular Values
- 離散凸解析(Discrete Convex Analysis)((離散可積分系と離散解析)
- 離散凸解析 : 組合せ最適化における凸性
- 離散凸解析(最適化の数理)
- マトロイドと凸解析(最適化の数理における離散と連続構造)
- Millerの後退漸化式法再考(数値計算アルゴリズムの現状と展望II)
- F.シャトラン/伊理正夫・伊理由美訳, 行列の固有値, シュプリンガー・フェアラーク東京, 1993, 344 pp.
- A note on the dqds algorithm with Rutishauser's shift for singular values
- 2-D-8 離散ヘッセ行列と凸拡張可能性に関する注意(最適化)
- 代用電荷法におけるスキームの「不変性」について
- 離散システムの不変な階層構造を求めて : グラフからマトロイドへ
- Applied Mathematical Series 51, 52, Singularity and Groups in Bifurcation Theory, Vol. 1, Vol. 2, Vol. 1: M. Golubitsky, D. G. Schaeffer, 1985, 463pp., / Applied Mathematical Series 51, 52, Singularity and Groups in Bifurcation Theory, Vol. 1, Vol. 2, Vol
- 数値計算技術の現状-6完-
- 数値計算技術の現状-5-
- 数値計算技術の現状-4-(講座)
- 数値計算技術の現状-3-(講座)
- 数値計算技術の現状-2-
- 数値計算技術の現状-1-
- 1-D-9 半正定値離散ヘッセ行列をもつ離散非凸関数の構成(離散最適化(2))
- 離散凸解析から見たDijkstra法
- 1-C-9 離散凸解析を利用したコールセンターのシフトスケジューリング(離散最適化(1))
- 離散凸最適化ソルバとデモンストレーションソフトウェア