Properties of the Quadratic Transformation of Dual Variables
We investigate a solution of a convex programming problem with a strongly convex objective function based on the dual approach. A dual optimization problem has constraints on the positivity of variables. We study the methods and properties of transformations of dual variables that enable us to obtai...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/3/148 |
| _version_ | 1797613968002383872 |
|---|---|
| author | Vladimir Krutikov Elena Tovbis Anatoly Bykov Predrag Stanimirovic Ekaterina Chernova Lev Kazakovtsev |
| author_facet | Vladimir Krutikov Elena Tovbis Anatoly Bykov Predrag Stanimirovic Ekaterina Chernova Lev Kazakovtsev |
| author_sort | Vladimir Krutikov |
| collection | DOAJ |
| description | We investigate a solution of a convex programming problem with a strongly convex objective function based on the dual approach. A dual optimization problem has constraints on the positivity of variables. We study the methods and properties of transformations of dual variables that enable us to obtain an unconstrained optimization problem. We investigate the previously known method of transforming the components of dual variables in the form of their modulus (modulus method). We show that in the case of using the modulus method, the degree of the degeneracy of the function increases as it approaches the optimal point. Taking into account the ambiguity of the gradient in the boundary regions of the sign change of the new dual function variables and the increase in the degree of the function degeneracy, we need to use relaxation subgradient methods (RSM) that are difficult to implement and that can solve non-smooth non-convex optimization problems with a high degree of elongation of level surfaces. We propose to use the transformation of the components of dual variables in the form of their square (quadratic method). We prove that the transformed dual function has a Lipschitz gradient with a quadratic method of transformation. This enables us to use efficient gradient methods to find the extremum. The above properties are confirmed by a computational experiment. With a quadratic transformation compared to a modulus transformation, it is possible to obtain a solution of the problem by relaxation subgradient methods and smooth function minimization methods (conjugate gradient method and quasi-Newtonian method) with higher accuracy and lower computational costs. The noted transformations of dual variables were used in the program module for calculating the maximum permissible emissions of enterprises (MPE) of the software package for environmental monitoring of atmospheric air (ERA-AIR). |
| first_indexed | 2024-03-11T07:03:00Z |
| format | Article |
| id | doaj.art-e6dfa253d9e44ba2b6db74090874c7c4 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-11T07:03:00Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-e6dfa253d9e44ba2b6db74090874c7c42023-11-17T09:09:13ZengMDPI AGAlgorithms1999-48932023-03-0116314810.3390/a16030148Properties of the Quadratic Transformation of Dual VariablesVladimir Krutikov0Elena Tovbis1Anatoly Bykov2Predrag Stanimirovic3Ekaterina Chernova4Lev Kazakovtsev5Laboratory “Hybrid Methods of Modeling and Optimization in Complex Systems”, Siberian Federal University, 79 Prosp. Svobodny, Krasnoyarsk 660041, RussiaInstitite of Informatics and Telecommunications, Reshetnev Siberian State University of Science and Technology, 31 Krasnoyarskii Rabochii Prospekt, Krasnoyarsk 660037, RussiaInstitute of Computational Technologies SB RAS, 21 Rukavishnikov Street, Kemerovo 650025, RussiaLaboratory “Hybrid Methods of Modeling and Optimization in Complex Systems”, Siberian Federal University, 79 Prosp. Svobodny, Krasnoyarsk 660041, RussiaDepartment of Applied Mathematics, Kemerovo State University, 6 Krasnaya Street, Kemerovo 650043, RussiaLaboratory “Hybrid Methods of Modeling and Optimization in Complex Systems”, Siberian Federal University, 79 Prosp. Svobodny, Krasnoyarsk 660041, RussiaWe investigate a solution of a convex programming problem with a strongly convex objective function based on the dual approach. A dual optimization problem has constraints on the positivity of variables. We study the methods and properties of transformations of dual variables that enable us to obtain an unconstrained optimization problem. We investigate the previously known method of transforming the components of dual variables in the form of their modulus (modulus method). We show that in the case of using the modulus method, the degree of the degeneracy of the function increases as it approaches the optimal point. Taking into account the ambiguity of the gradient in the boundary regions of the sign change of the new dual function variables and the increase in the degree of the function degeneracy, we need to use relaxation subgradient methods (RSM) that are difficult to implement and that can solve non-smooth non-convex optimization problems with a high degree of elongation of level surfaces. We propose to use the transformation of the components of dual variables in the form of their square (quadratic method). We prove that the transformed dual function has a Lipschitz gradient with a quadratic method of transformation. This enables us to use efficient gradient methods to find the extremum. The above properties are confirmed by a computational experiment. With a quadratic transformation compared to a modulus transformation, it is possible to obtain a solution of the problem by relaxation subgradient methods and smooth function minimization methods (conjugate gradient method and quasi-Newtonian method) with higher accuracy and lower computational costs. The noted transformations of dual variables were used in the program module for calculating the maximum permissible emissions of enterprises (MPE) of the software package for environmental monitoring of atmospheric air (ERA-AIR).https://www.mdpi.com/1999-4893/16/3/148convex programmingstrongly convex functionsnonlinear programmingdual problemsubgradientsubgradient methods |
| spellingShingle | Vladimir Krutikov Elena Tovbis Anatoly Bykov Predrag Stanimirovic Ekaterina Chernova Lev Kazakovtsev Properties of the Quadratic Transformation of Dual Variables Algorithms convex programming strongly convex functions nonlinear programming dual problem subgradient subgradient methods |
| title | Properties of the Quadratic Transformation of Dual Variables |
| title_full | Properties of the Quadratic Transformation of Dual Variables |
| title_fullStr | Properties of the Quadratic Transformation of Dual Variables |
| title_full_unstemmed | Properties of the Quadratic Transformation of Dual Variables |
| title_short | Properties of the Quadratic Transformation of Dual Variables |
| title_sort | properties of the quadratic transformation of dual variables |
| topic | convex programming strongly convex functions nonlinear programming dual problem subgradient subgradient methods |
| url | https://www.mdpi.com/1999-4893/16/3/148 |
| work_keys_str_mv | AT vladimirkrutikov propertiesofthequadratictransformationofdualvariables AT elenatovbis propertiesofthequadratictransformationofdualvariables AT anatolybykov propertiesofthequadratictransformationofdualvariables AT predragstanimirovic propertiesofthequadratictransformationofdualvariables AT ekaterinachernova propertiesofthequadratictransformationofdualvariables AT levkazakovtsev propertiesofthequadratictransformationofdualvariables |