Gradient projection: simplifying minimization area by affine transform
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2024.2.09Keywords:
gradient projection, minimization, affine transformationAbstract
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.
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.