Radiotekhnika
Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS


Тел.: +7 (495) 625-9241

 

Primal and dual forms for the atomic optimization method and 1D problems

Keywords:

V. V. Pozdyayev – Ph.D. (Phys.-Math.), Associate Professor, Arzamas Polytechnic Institute (branch NSTU). E-mail: vitalybolnokin@yandex.ru; d.i.mutin@mail.ru


Optimization problems with polynomial objective function and polynomial scalar or matrix inequality (PI/PMI) constraints are considered. A framework has been proposed that further transforms the existing moment theory based method of PI/PMI solution, and allows to construct equivalent solution algorithms working in the augmented original search space instead of the moment space. The equivalence here implies that the new optimization method is to find an r-atomic measure whose support set is the set of global optima, hence the name “atomic optimization”. The new optimization method provides a way of solving PI/PMI problems that has much lower computational cost than the original moment theory based method while keeping its key benefits for the given class of problems. In this paper, optimization problems with polynomial objective function and inequality constraints are considered with the purpose of extending the atomic optimization method by enabling it to solve primal-dual forms of said problems’ linear matrix inequality (LMI) relaxations. We show how the primal-dual form of a linear matrix inequality relaxation can be modified in a way that preserves its compatibility with the atomic optimization framework. By applying the search space transformation and eliminating all references to the intermediate (moment) space we obtain a system ready for application of various interior-point methods. For 1D problems and same-dimension search space transformations, an atom space based equivalent of a primal-dual LMI relaxation is constructed. This equivalent problem can be directly solved within the existing atomic optimization framework by using primal-dual semidefinite programming methods. This study provides a starting point for further research of atomic primal-dual forms.
References:

  1. Pozdyaev V.V. Atomnaya optimizacziya, chast' 1: transformacziya prostranstva poiska i odnomerny'e zadachi // Upravlenie bol'shimi sistemami. 2011. № 36. S. 39–80.
  2. Pozdyaev V.V. Atomnaya optimizacziya, chast' 2: mnogomerny'e zadachi i polinomial'ny'e matrichny'e neravenstva // Upravlenie bol'shimi sistemami. 2013. № 43. S. 95–123.
  3. Henrion D., Lasserre J.-B. Detecting global optimality and extracting solutions in GloptiPoly // Positive polynomials in control. 2005. P. 1–18.
  4. Henrion D., Lasserre J.-B. Convergent relaxations of polynomial matrix inequalities and static output feedback // Trans. Automatic Control. IEEE. 2006. V. 51. № 2. P. 192–202.
  5. Lasserre J.-B. Global optimization with polynomials and the problem of moments // SIAM Journal on Optimization. 2001. V. 11. № 3. P. 796–817.
  6. Nemirovski A. Lecture notes. Interior point polynomial time methods in convex programming. 2004. URL: http://www2.isye.gatech.edu/ nemirovs/Lect_IPM.pdf
  7. Nesterov Y., Nemirovskii A. Interior-point polynomial algorithms in convex programming. SIAM. 1994.
  8. Vandenberghe L., Boyd S. Semidefinite Programming // SIAM Review. 1994. V. 38. P. 49–95.

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio