Nonsmooth penalty and subgradient algorithms to solve the problem of projection onto a polytope
- PDF / 93,300 Bytes
- 5 Pages / 595.276 x 793.701 pts Page_size
- 19 Downloads / 197 Views
NONSMOOTH PENALTY AND SUBGRADIENT ALGORITHMS TO SOLVE THE PROBLEM OF PROJECTION ONTO A POLYTOPE1 P. I. Stetsyuka and E. A. Nurminskib
UDC 519.8
The least distance problem is considered for a convex hull of a finite family of vectors in a finite-dimensional Euclidian space. It is reduced to an equivalent nonsmooth optimization problem with a directly estimated penalty parameter for which subgradient algorithms with space dilation are proposed. Keywords: projection problem, nonsmooth exact penalty functions, r-algorithms. Problem Statement. We will consider the problem of projecting the origin of coordinates onto a convex polytope. Given a set of n-dimensional vectors X = { x$ 1 , x$ 2 , K , x$ m }, find the vector with the minimum norm in their convex hull (polytope): min || x||2 =
xÎ co ( X )
min | | x| | 2 . m x= å li x$ i ,
(1)
i=1
m
å li =1,
i=1
li ³ 0 , i =1, 2 , K , m
The problem is of interest for many applications and may form the basis to solve a similar problem for polytopes specified in a different way [1]. There is a great variety of algorithms [2] for the projection problem (in statement (1) and others); however, new methods are still developed for many specific applications. There is a need for new methods because of the extremely high dimension of (1) in practical problems of image processing, planning of radiation therapy in medical computer science [3], approximation of geophysical fields [4], etc. The purpose of our study is to set up a family of algorithms to solve problem (1) by the methods of minimization of nonsmooth convex functions with projecting onto a nonnegative orthant. Using the method of nonsmooth penalty functions, we will reduce problem (1) to a nonsmooth extremum problem (minimization of a nonsmooth convex function under constraints on the nonnegativity of variables) and will analyze the choice of the finite penalty constant that provides such equivalence. We will also discuss the application of r-algorithms [5] to solve a nonsmooth extreme problem. Projection as a Quadratic Programming Problem. Let an m´ n-dimensional matrix X be composed of column vectors x$ 1 , x$ 2 , K , x$ m , and an m-dimensional vector l consist of components l 1 , l 2 , K , l m . Then the following quadratic programming problem corresponds to problem (1): m
min || å l i x$ i ||2 = min | | X l | |2 = | | X l* | |2 = | | x * | |2 = d * l
(2)
l
i =1
1
The study was financially supported by the joint Ukrainian-Russian project DFFD–F28.1/005 and RFFI–09–01–90413–Ukr_f_a “Subgradient methods of accelerated convergence in convex programming problems.” a
V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine, [email protected]. bInstitute for Automation and Control Processes, Far Eastern Branch of Russian Academy of Sciences, Vladivostok, Russia, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 59–63, January–February 2010. Original article submitted April 27, 2009. 1060-0396/10/4601-0051
©
2010 Springer Science+Business Me
Data Loading...
