Presentation | 1998/9/22 Solving Non-Linear Programming Problem by Algebraic Computations Kei-ichi SHIRAISHi, Hiroshi KAI, Matu-tarow NODA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Optimization problem / Algebraic computation / Grobner basis |
Paper # | SS98-27 |
Date of Issue |
Conference Information | |
Committee | SS |
---|---|
Conference Date | 1998/9/22(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Software Science (SS) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Solving Non-Linear Programming Problem by Algebraic Computations |
Sub Title (in English) | |
Keyword(1) | Optimization problem |
Keyword(2) | Algebraic computation |
Keyword(3) | Grobner basis |
1st Author's Name | Kei-ichi SHIRAISHi |
1st Author's Affiliation | Department of Computer Science, Ehime University() |
2nd Author's Name | Hiroshi KAI |
2nd Author's Affiliation | Department of Computer Science, Ehime University |
3rd Author's Name | Matu-tarow NODA |
3rd Author's Affiliation | Department of Computer Science, Ehime University |
Date | 1998/9/22 |
Paper # | SS98-27 |
Volume (vol) | vol.98 |
Number (no) | 295 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |