Gradient projection: simplifying minimization area by affine transform

Authors

  • Igor Spectorsky Educational and Research Institute for Applied System Analysis of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine https://orcid.org/0000-0003-4863-7986

DOI:

https://doi.org/10.20535/SRIT.2308-8893.2024.2.09

Keywords:

gradient projection, minimization, affine transformation

Abstract

One of the classical problems of optimization theory in a finite-dimensional space is to find a minimum of a function on a nonempty set. Usually, finding the precise solution to this task analytically requires a lot of computational resources or is even impossible at all. So, approximate methods are used most often in practical cases. One of the simplest and the most well-known among such approximate methods for unconditional optimization is the method of gradient descent; its generalization for conditional optimization was found in 1964, the method of projected gradient. For some simple sets (line segment, parallelepiped, ball), the projection of the point on the set can be easily found by an explicit formula. However, for more complicated sets (e.g., an ellipse), projecting becomes a separate task. Nevertheless, sometimes computing projection can be simplified by affine transform; e.g., an ellipse can be transformed into a ball by affine (moreover, by linear) transformation. The paper aims to simplify the problem of minimizing function on the set by changing the condition set by affine transform F(x)= Ax+b, where A is a non-degenerated square matrix, and b is a fixed vector of proper dimension.

Author Biography

Igor Spectorsky, Educational and Research Institute for Applied System Analysis of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv

Candidate of Physical and Mathematical Sciences (Ph.D.), an associate professor at the Department of Mathematical Methods of System Analysis of Educational and Research Institute for Applied System Analysis of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine.

References

Andersen Ang, “Projected Gradient Algorithm,” Mathématique et recherche opérationnelle, 2021. Available: https://angms.science/doc/CVX/CVX_PGD.pdf

Sébastien Bubeck, “Convex Optimization: Algorithms and Complexity,” Foundations and Trends in Machine Learning, vol. 8, no. 3-4, pp. 232–357, 2015. doi: 10.1561/2200000050

H. Jongen, K. Meer, and E. Triesch, Optimization Theory. New York, Boston, Dordrechr, London, Moscow: Kluwer Academic Publisher, 2007, 443 p.

A. Sukharev, A. Timokhov, and V. Fedorov, Course Optimization Methods. M.: Nauka, 2005, 368 p.

F.P. Vasil’ev, Numerical Methods for Solving Extremal Problems. M.: Nauka, 1988, 552 p.

Y. Nesterov, Introductory Lectures on Convex Optimization. Boston, Dordrechr, London: Kluwer Academic Publisher, 2004, 236 p.

A. Goldstein, “Convex programming in Hilbert space,” Bulletin of the American Mathematical Society, no. 70, pp. 709–710, 1964.

M.P. Moklyachuk, Foundations of Convex Analysis: Textbook. Kyiv: TViMS, 2004, 240 p.

A. Ahmadi, Characterizations of convex functions, strict and strong convexity, optimality conditions for convex problems. 2021. Available: http://www.princeton.edu/~aaa/Public/Teaching/ORF523/ORF523_Lec7.pdf

R. Rockafellar, Convex Analysis. Princeton: Princeton University Press, 2015, 472 p.

Downloads

Published

2024-06-28

Issue

Section

Mathematical methods, models, problems and technologies for complex systems research