| 講演名 | 1998/9/22 非線形計画問題への代数的算法の応用 白石 啓一, 甲斐 博, 野田 松太郎, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 数理計画法で取り上げる最適化問題の代数的解法を考え, その高速化について検討する。数理計画問題は与えられた制約条件の下で目的関数を最大または最小化する。制約条件や目的関数が多項式で与えられるある種の非線形計画問題を考える。数値的方法では, 場合によっては最適解を検出することが不可能な場合もあり, より安定した代数的解法の確立が望まれる。代数的解法では, 制約条件の不等式集合にスラック変数を導入して, 等式集合に変形し, 目的関数と合わせた連立代数方程式系を解くことになる。この解法としては, 連立代数方程式を1変数代数方程式に帰着させるためのグレブナ基底計算を行う。この計算では, 用いる項順序が大きな役割を果たし, 簡単な辞書式順序(Lex)では多大の計算時間が必要となるが, 全次数逆辞書式順序(DRL)では, かなりの計算時間の節約が可能で, より大規模な問題への適用の可能性もあることが示される。 |
| 抄録(英) | An algebraic method to solve optimization problems are discussed. The problem is to maximize or minimize an objective function under some constraints. Here, we consider the objective function and constraints which are expressed as polynomials. In the algebraic method, the function and constraints are changed by a set of polynomial equations by adding slack variables. The set of polynomial equations is reduced algebraically to a univariate polynomial (algebraic) equation by Grobner basis computations. In the reduction process, a termordering of variables become inportant for the Grobner basis computation. Results by two types of the ordering, the lexicographic (Lex) ordring and the reverse lexicographic (DegRevLex and abbreviate simply DRL) ordering, are discussed. The resulting equation is solved by using algebraic Sturm's theorem. The method is applied to practical examples. |
| キーワード(和) | 最適化問題 / 代数数的算法 / グレブナ基底 |
| キーワード(英) | Optimization problem / Algebraic computation / Grobner basis |
| 資料番号 | SS98-27 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 1998/9/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非線形計画問題への代数的算法の応用 |
| サブタイトル（和） | |
| タイトル（英） | Solving Non-Linear Programming Problem by Algebraic Computations |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最適化問題 / Optimization problem |
| キーワード(2)（和/英） | 代数数的算法 / Algebraic computation |
| キーワード(3)（和/英） | グレブナ基底 / Grobner basis |
| 第 1 著者 氏名（和/英） | 白石 啓一 / Kei-ichi SHIRAISHi |
| 第 1 著者 所属（和/英） | 愛媛大学工学部情報工学科 Department of Computer Science, Ehime University |
| 第 2 著者 氏名（和/英） | 甲斐 博 / Hiroshi KAI |
| 第 2 著者 所属（和/英） | 愛媛大学工学部情報工学部 Department of Computer Science, Ehime University |
| 第 3 著者 氏名（和/英） | 野田 松太郎 / Matu-tarow NODA |
| 第 3 著者 所属（和/英） | 愛媛大学工学部情報工学科 Department of Computer Science, Ehime University |
| 発表年月日 | 1998/9/22 |
| 資料番号 | SS98-27 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 295 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |