Штрафна функція максимуму в лінійному програмуванні: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160
A linear program can be equivalently reformulated as an unconstrained nonsmooth minimization problem, whose objective is the sum of the original objective and a penalty function with a sufficiently large penalty parameter. The article presents two methods for choosing this parameter. The first one a...
Gespeichert in:
| Datum: | 2021 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2021
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/220 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479601620451328 |
|---|---|
| author | Stetsyuk, Petro Fischer, Andreas Khomiak, Olha |
| author_facet | Stetsyuk, Petro Fischer, Andreas Khomiak, Olha |
| author_institution_txt_mv | [
{
"author": "Petro Stetsyuk",
"institution": "Інститут кібернетики імені В.М. Глушкова НАН України, Проспект Академіка Глушкова, 40, 03187, Київ"
},
{
"author": "Andreas Fischer",
"institution": "Інститут обчислювальної математики технічного університету Дрездена, 01062, Дрезден, Німеччина"
},
{
"author": "Olha Khomiak",
"institution": "Інститут кібернетики імені В.М. Глушкова НАН України, Проспект Академіка Глушкова, 40, 03187, Київ"
}
] |
| author_sort | Stetsyuk, Petro |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2021-09-14T06:28:40Z |
| description | A linear program can be equivalently reformulated as an unconstrained nonsmooth minimization problem, whose objective is the sum of the original objective and a penalty function with a sufficiently large penalty parameter. The article presents two methods for choosing this parameter. The first one applies to linear programs with usual linear inequality constraints. Then, we use a corresponding theorem by N.Z. Shor on the equivalence of a convex program to an unconstrained nonsmooth minimization problem. The second method is for linear programs of a special type. This means that all inequalities are of the form that a linear expression on the left-hand side is less or equal to a positive constant on the right-hand side. For this special type, we use a corresponding theorem of B.N. Pshenichny on establishing a penalty parameter for convex programs. For differently sized linear programs of the special type, we demonstrate that suitable penalty parameters can be computed by a procedure in GNU Octave based on GLPK software.
References
Eremin, I. I. (1967). Method of the penalties in convex programming. Doklady Academy Nauk USSR, 173(4), 748–751.
Polyakova, L. N. (2000). Nonsmooth Penalty Functions. IFAC Proceedings Volumes, 33(16), 287-291. DOI https://doi.org/10.1016/s1474-6670(17)39644-1
Shor, N. Z. (1985). Minimization methods for nondifferentiable functions. Springer-Verlag, Berlin.
Shor, N. Z. (1998). Nondifferentiable optimization and polynomial problems. Kluwer Academic Publishers, Dordrecht.
Pshenichnyi, B. N. (1983). The Linearization Method. Nauka, Moscow. (in Russian)
Eaton, J. W., Bateman, D., Hauberg, S. (2008). GNU Octave Manual Version 3. Network Theory Ltd.
Stetsyuk, P., Fischer, A. (2017). Shor's r-algorithms and octave-function ralgb5a. In: International Conference “Modern Informatics: Problems, Achievements and Prospects for Development”. V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv, 143–146. (in Russian).
|
| doi_str_mv | 10.15407/fmmit2021.33.156 |
| first_indexed | 2026-06-09T01:08:52Z |
| format | Article |
| fulltext | |
| id | oai:ojs2.www.fmmit.lviv.ua:article-220 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:08:52Z |
| publishDate | 2021 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2202021-09-14T06:28:40Z Maximum Penalty Function in Linear Programming: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 Штрафна функція максимуму в лінійному програмуванні: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 Stetsyuk, Petro Fischer, Andreas Khomiak, Olha метод штрафних функцій функція максимуму задача лінійного програмування GNU Octave Penalty Functions method maximum function linear program problem GNU Octave A linear program can be equivalently reformulated as an unconstrained nonsmooth minimization problem, whose objective is the sum of the original objective and a penalty function with a sufficiently large penalty parameter. The article presents two methods for choosing this parameter. The first one applies to linear programs with usual linear inequality constraints. Then, we use a corresponding theorem by N.Z. Shor on the equivalence of a convex program to an unconstrained nonsmooth minimization problem. The second method is for linear programs of a special type. This means that all inequalities are of the form that a linear expression on the left-hand side is less or equal to a positive constant on the right-hand side. For this special type, we use a corresponding theorem of B.N. Pshenichny on establishing a penalty parameter for convex programs. For differently sized linear programs of the special type, we demonstrate that suitable penalty parameters can be computed by a procedure in GNU Octave based on GLPK software. References Eremin, I. I. (1967). Method of the penalties in convex programming. Doklady Academy Nauk USSR, 173(4), 748–751. Polyakova, L. N. (2000). Nonsmooth Penalty Functions. IFAC Proceedings Volumes, 33(16), 287-291. DOI https://doi.org/10.1016/s1474-6670(17)39644-1 Shor, N. Z. (1985). Minimization methods for nondifferentiable functions. Springer-Verlag, Berlin. Shor, N. Z. (1998). Nondifferentiable optimization and polynomial problems. Kluwer Academic Publishers, Dordrecht. Pshenichnyi, B. N. (1983). The Linearization Method. Nauka, Moscow. (in Russian) Eaton, J. W., Bateman, D., Hauberg, S. (2008). GNU Octave Manual Version 3. Network Theory Ltd. Stetsyuk, P., Fischer, A. (2017). Shor's r-algorithms and octave-function ralgb5a. In: International Conference “Modern Informatics: Problems, Achievements and Prospects for Development”. V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv, 143–146. (in Russian). Задачу лінійного програмування (ЛП-задачу) можна переформулювати як еквівалентну задачу безумовної мінімізації негладкої штрафної функції з досить великим параметром штрафу. У статті представлені два способи вибору цього параметра. Перший застосовується до ЛП-задач із звичайними лінійними нерівностями. Потім використовується відповідна теорема Н.З. Шора про еквівалентність задачі опуклого програмування та задачі безумовної негладкої мінімізації. Другий спосіб ‒ для ЛП-задач особливого типу. Це означає, що всі нерівності мають вигляд, де лінійний вираз в лівій частині менше або дорівнює додатній константі в правій частині. Для цього особливого типу використовується відповідна теорема Б.М. Пшеничного про встановлення штрафного параметра для задачі опуклого програмування. Для ЛП-задач різного розміру спеціального типу показано, що відповідні параметри штрафу можуть бути обчислені за допомогою процедури в GNU Octave на основі програмного забезпечення GLPK. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2021-09-06 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/220 10.15407/fmmit2021.33.156 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 33 (2021): Physico-mathematical modeling and informational technologies, 2021, Issue 33; 156-160 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 33 (2021): Фізико-математичне моделювання та інформаційні технології, 2021, Вип. 33; 156-160 2617-5258 1816-1545 10.15407/fmmit2021.33 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/220/210 Авторське право (c) 2021 Petro Stetsyuk, Andreas Fischer, Olha Khomiak (Автор) |
| spellingShingle | метод штрафних функцій функція максимуму задача лінійного програмування GNU Octave Stetsyuk, Petro Fischer, Andreas Khomiak, Olha Штрафна функція максимуму в лінійному програмуванні: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 |
| title | Штрафна функція максимуму в лінійному програмуванні: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 |
| title_alt | Maximum Penalty Function in Linear Programming: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 |
| title_full | Штрафна функція максимуму в лінійному програмуванні: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 |
| title_fullStr | Штрафна функція максимуму в лінійному програмуванні: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 |
| title_full_unstemmed | Штрафна функція максимуму в лінійному програмуванні: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 |
| title_short | Штрафна функція максимуму в лінійному програмуванні: Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 |
| title_sort | штрафна функція максимуму в лінійному програмуванні: fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160 |
| topic | метод штрафних функцій функція максимуму задача лінійного програмування GNU Octave |
| topic_facet | метод штрафних функцій функція максимуму задача лінійного програмування GNU Octave Penalty Functions method maximum function linear program problem GNU Octave |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/220 |
| work_keys_str_mv | AT stetsyukpetro maximumpenaltyfunctioninlinearprogrammingfizmatmodelinftehnol202133156160 AT fischerandreas maximumpenaltyfunctioninlinearprogrammingfizmatmodelinftehnol202133156160 AT khomiakolha maximumpenaltyfunctioninlinearprogrammingfizmatmodelinftehnol202133156160 AT stetsyukpetro štrafnafunkcíâmaksimumuvlíníjnomuprogramuvannífizmatmodelinftehnol202133156160 AT fischerandreas štrafnafunkcíâmaksimumuvlíníjnomuprogramuvannífizmatmodelinftehnol202133156160 AT khomiakolha štrafnafunkcíâmaksimumuvlíníjnomuprogramuvannífizmatmodelinftehnol202133156160 |