{'fraction_non_alphanumeric': 0.05699852979982659, 'fraction_numerical': 0.011723903946922003, 'mean_word_length': 3.781542898341745, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Adaptive Partial Linearization Method for Optimization Problems on Product Sets

We suggest an adaptive version of a partial linearization method for composite optimization problems. The goal function is the sum of a smooth function and a non necessary smooth convex separable function, whereas the feasible set is the corresponding Cartesian product. The method consists in selective component-wise steps together with a special control of a tolerance sequence. This technique is destined to reduce the computational expenses per iteration and maintain the basic convergence properties. We also establish its convergence rates and describe some examples of applications. Preliminary results of computations illustrate usefulness of the new method.


Introduction
It has been designed a great number of iterative methods for solving various optimization problems. The custom optimization problem consists in finding an element in a feasible set X ⊆ R N that yields the minimal value of some goal function µ : R N → R on X. For brevity, we write this problem as min x∈X → µ(x). (1) It is well known that problems with the convex smooth goal function and convex feasible set constitute one of the most investigated classes in optimization; see e.g. [1,2]. The conditional gradient method is one of the oldest methods in this field. It was first suggested in [3] for the case when the goal function is quadratic and the feasible set is polyhedral and further was developed by many authors; see e.g. [4,1,5,6,2]. We recall that the main idea of this method consists in linearization of the goal function. That is, given the current iterate x k ∈ X, one finds some solution y k of the problem and defines p k = y k − x k as a descent direction at x k . Taking a suitable stepsize λ k ∈ (0, 1], one sets x k+1 = x k + λ k p k and so on. During rather long time, this method was not considered as very efficient due to its relatively slow convergence in comparison with Newton and projection type methods. However, it has gained a great amount of attention very recently due to several features significant for many applications, where huge dimensionality and inexact data create certain drawbacks for more rapid methods. Moreover, in the case of a polyhedral feasible set its auxiliary problem (2) appears simpler than those in the other methods, and its solution yields usually so-called sparse approximations; see e.g. [7,8,9] and the references therein. It should be noted that a great number of applications reduce to problem (1), where f : R N → R is a smooth, but not necessary convex function, and h : R N → R is not necessary smooth, but rather simple and convex function. The appearance of the nonsmooth term is caused by regularization or exact penalty techniques; see e.g. [2,10]. In this case one can apply the partial linearization (PL for short) method from [11] (see [12,13] for further development), where problem (2) is replaced with the following: The usefulness of this approach becomes clear if problem (1), (3) is (partially) decomposable, which is typical for very large dimensional problems. For instance, let where x i ∈ X i . Then (4) becomes equivalent to several independent problems of the form In case h ≡ 0, this decomposition method was considered in [14]. However, even solution of all the partial problems of form (5) may appear too expensive. A randomized block-coordinate variant of the conditional gradient method was rather recently proposed in [15]. A general scheme of block-descent methods for such problems was given in [16].
We recall for instance that various engineering problems based on the so-called group LASSO regression method have this format (see [17,18]), as well as many problems of network resource allocation in wireless multi-user interfering systems (see [19]). We give several additional examples of such decomposable applied problems in Section 6.
The main goal of this paper is to suggest a modification of PL methods for decomposable composite optimization problems of form (1), (3), which maintains the basic convergence properties, but enables one to reduce the computational expenses per iteration. We follow the approach suggested in [20] for regularized splitting methods. The main difference of this method consists in utilizing PL technique without any regularization in order to simplify the auxiliary problem, but this implies the dis-continuity of the descent mapping and requires new substantiation schemes. We take the inexact Armijo type linesearch rule, which makes our method different from those in [11,13] even in the non-decomposable case.
In what follows, we denote by R s the real s-dimensional Euclidean space, all elements of such spaces being column vectors represented by a lower case Roman alphabet in boldface, e.g. x. We use superscripts to denote different vectors, and subscripts to denote different scalars or components of vectors. For any vectors x and y of R s , we denote by x, y their scalar product, i.e., and by x the Euclidean norm of x, i.e., x = x, x . We denote by R s + the non-negative orthant in R s , i.e. R s Given a function f : R s → R, we can define its domain For any set X, Π(X) denotes the family of all nonempty subsets of X.

Problem formulation and preliminary properties
We first formulate a partitionable optimization problem of form (1), (3). We set N = {1, . . . , N} and suppose that there exists a partition where X i is a non-empty, convex, and compact set in R N i for i = 1, . . . , n. Then, where h i : R N i → R is convex, proper, lower semi-continuous, and domh i ⊇ X i for i = 1, . . . , n. Then the function h is also convex, proper, and lower semi-continuous and we can define its subdifferential So, our problem (1), (3), (6)- (7) is rewritten as Its solution set will be denoted by X * and the optimal value of the function by µ * , i.e.
We suppose that the function f : R N → R is smooth, but not necessary convex. Set g(x) = f ′ (x), then From the assumptions above it follows that the function µ is directionally differentiable at each point x ∈ X, that is, its directional derivative with respect to any vector d is defined by the formula: see e.g. [21]. We need the optimality condition for problem (8).
In what follows, we denote by X 0 the solution set of MVI (10) and call it the set of stationary points of problem (8).
For each point x ∈ X we can define a point y(x) = (y 1 (x), . . . , y n (x)) ⊤ ∈ X such that This MVI gives a necessary and sufficient optimality condition for the optimization problem: where for i = 1, . . . , n; cf. (4). Under the above assumptions the point y(x) exists, but is not defined uniquely in general, hence we can define the set Y (x) of these points at x, thus defining the set-valued mapping x → Y (x). Observe that all the components of y(x) can be found independently, i.e. (12)-(13) is equivalent to n independent optimization problems of the form min for i = 1, . . . , n and y i (x) just solves (14). Therefore, where each set Y i (x) is non-empty, convex, and compact. Moreover, if we set for any y(x) = (y 1 (x), . . . , y n (x)) ⊤ ∈ Y (x). We can choose the most suitable format for the definition of a point of Y (x). We recall that given a set V ⊆ R s , a set-valued mapping Q : V → Π(R s ) is said to be closed on a set W ⊆ V , if for each pair of sequences {u k } → u, {q k } → q such that u k ∈ W and q k ∈ Q(u k ), we have q ∈ Q(u).
We also need continuity type properties of the marginal functions.
Lemma 1 (a) The function ϕ : R N → R is lower semi-continuous on X; Proof. Assertion (a) has been proved in [13,Lemma 4]. To obtain (b), take sequences Since g is continuous and h is lower semi-continuous, taking the limit k → ∞ gives We now show that ϕ can serve as a gap function for problem (8).
We see that the value ϕ(x) can serve as accuracy measure at a point x. We establish now a useful descent property. Define for brevity I = {1, . . . , n}.
Lemma 2 Take any points x ∈ X, y(x) ∈ Y (x) and an index s ∈ I. If Proof. Due to the definition of d and (9), we have for any b s ∈ ∂h s (x s ). It follows that hence (15) holds true.

The descent method with inexact line-search
Denote by Z + the set of non-negative integers. The basic cycle of the descent PL method with inexact line-search for MVI (10) is described as follows.
Step 1: where y s = y s (x k ) ∈ Y s (x k ) and go to Step 3. Otherwise (i.e. when ϕ i (x k ) < δ for all i ∈ I) go to Step 2.
Step 2: Set z = x k and stop.
Step 3: Determine m as the smallest number in Z + such that set λ k = θ m , x k+1 = x k + λ k d k , and k = k + 1. The iteration is complete.

Lemma 3
The line-search procedure in Step 3 is always finite.
Proof. If we suppose that the line-search procedure is infinite, then for m → ∞, hence, by taking the limit we have We recall that a single-valued mapping p : R s → R s is said to be uniformly continuous on a set V ⊂ R s , if for any number ε > 0 there exists a number τ > 0 such that p(x) − p(y) < ε for each pair of points x, y ∈ V with x − y < τ . Our convergence analysis will be based on the following property.
Proposition 3 Suppose in addition that the gradient map g : R N → R N is uniformly continuous on X. Then the number of iterations in Basic cycle (PL) is finite.
Besides, the sequence {x k } is bounded and must have limit points, Suppose that the sequence {x k } is infinite. Since the set I is finite, there is an index s k = s, which is repeated infinitely. Take the corresponding subsequence {k l }. We intend to evaluate the difference µ(x k l + λ k l d k l ) − µ(x k l ), but we temporarily remove these indices for more convenience. Then, using the mean value theorem and convexity of h i , we have Due to the uniform continuity of g, there exists a number λ ′ > 0 such that if λ ≤ λ ′ , hence λ k l ≥λ > 0 by the stepsize rule in Basic cycle (PL), which contradicts (17).
The whole method involves the upper level whose iterations (stages) contain Basic cycle (LP) with decreasing values of δ.
Method (Upper level). Choose a point z 0 ∈ X and a sequence {δ l } ց 0.
At the l-th stage, l = 1, 2, . . ., we have a point z l−1 ∈ X and a number δ l . Apply Basic cycle (LP) with x 0 = z l−1 , δ = δ l and obtain a point z l = z as its output.
Theorem 1 Suppose in addition that the gradient map g : R N → R N is uniformly continuous on X. Then the sequence {z l } generated by the method with Basic cycle (LP) has limit points, all these limit points are solutions of MVI (10). Besides, if f is convex, then lim l→∞ µ(z l ) = µ * ; (18) and all the limit points of {z l } belong to X * .
Proof. Following the proof of Proposition 3, we see that Besides, the sequence {z l } is bounded and must have limit points. Take an arbitrary limit pointz of {z l }, then lim t→∞ z lt =z.
In case h ≡ 0, the method is a new decomposable version of the conditional gradient method. Although the dimensions N i can be arbitrary, we think that the proposed PL method may have preferences, in particular, over the method from [20], in case when N i > 1 and all the sets X i are polyhedrons. Also, it may have preferences over the usual conditional gradient and partial linearization methods if the number of subsets n is rather large.

Remark 1
The initial boundedness requirement for the feasible set X was made in Section 2 only for more simplicity of exposition and can be replaced with proper coercivity assumptions. In fact, instead of compactness of each set X i we can require their closedness and add e.g. the following conditions.
(C1) For each i ∈ I and for each sequence {u l i } such that u l i ∈ X i and { u l i } → ∞ as l → ∞, we have {h i (u l i )/ u l i } → +∞. (C2) For each sequence {u l } such that u l ∈ X and { u l } → ∞ as l → ∞, we have {µ(u l )} → +∞.
Then (C1) provides existence of a solution of auxiliary problem (12)-(13), moreover, the sequence {d k } is bounded if so is {x k }. From (C2) it follows that µ * > −∞, problems (8) and (10) have solutions, and that the sequence {x k } is bounded. Therefore, all the assertions of Section 3 remain true.
Also, we supposed that domh i ⊇ X i for i = 1, . . . , n only for more simplicity of exposition. Set It suffices to assume D = ∅. Then we should only take the initial point z 0 ∈ D. Let us first consider the convex case where the function f is convex. Then, we can replace (16) with the following:

Modifications of the linesearch procedure
Since the trial point x k + θ m d k has the shift from x k only in d k s , it can be implemented independently of other variables. From (19) it now follows that and (16) holds true. It easy to see that all the assertions of Section 3 remain true for this version. Moreover, we can utilize even a pre-defined stepsize in the Lipschitz gradient case. Let us suppose that partial gradients of the function f are Lipschitz continuous, i.e., for i ∈ I and any vector d = (d 1 , . . . , d n ) ⊤ ∈ R N . Clearly, this property holds if the gradient of f is Lipschitz continuous with some constant L > 0, then L i ≤ L for each i ∈ I. It is known that any function φ having the Lipschitz continuous gradient satisfies the inequality Similarly, for any vectors x and d, we have It follows that (16) holds with λ k ≥ min{1, θλ (s) (x k )} > 0. Moreover, we can simply set λ k = λ (s) (x k ) > 0, and all the assertions of Proposition 3 and Theorem 1 remain true for this version. This modification reduces the computational expenses essentially since calculations of the goal function values are not necessary and we can calculate values of the partial gradients g i and functions h i only for necessary separate components. Clearly, the adaptive PL method admits other modifications and extensions, e.g. selection of a group of indices in I instead of only one component. These opportunities make the method very flexible and suitable for parallel and distributed computations applicable for very high-dimensional optimization problems; see e.g. [22,16,8,10].

Convergence rates
In this section, we give some convergence rates for the adaptive PL method. We suppose that all the basic assumptions of Section 2 hold, but will also utilize some additional conditions.
We first establish the finite termination property under the following sharp solution condition, which modifies those in [2, Chapter 7, §1, Section 3] and [23, Section 2.2].
There exist a number τ > 0 and a pointx ∈ X such that Theorem 2 Let a sequence {z l } be generated by the method with Basic cycle (LP).
Suppose that the function f is convex, its gradient is Lipschitz continuous with constant L < ∞, and that the sharp solution condition holds. Then there exists a stage number t such that X * = Y (z t ).
Proof. First we note that the sharp solution condition impliesx ∈ X 0 , and, by convexity, X 0 = X * ; see Proposition 1. Next, if there exists some other pointx ∈ X, which provides the sharp solution condition, then, again by convexity, we must have which is a contradiction. Hence, X * = {x}. From the sharp solution condition for any point x ∈ X we have for l large enough. It follows that there exists a number t such that Y (z t ) = {x}.
In the method, each stage contains a finite number of iterations of the basic cycle. Therefore, it seems suitable to derive its complexity estimate, which gives the total amount of work of the method. We now suppose in addition that the function f is convex and its partial gradients satisfy Lipschitz continuity conditions with constants L i for each i ∈ I. Then it was shown in Section 4 that we can take the stepsize where see (20). We take the value Φ(x) = µ(x) − µ * as an accuracy measure for our method. In other words, given a starting point z 0 and a number ε > 0, we define the complexity of the method, denoted by V (ε), as the total number of iterations at l(ε) stages such that l(ε) is the maximal number l with Φ(z l ) ≥ ε, hence, where V l denotes the total number of iterations at stage l. We proceed to estimate the right-hand side of (22). To change δ l , we apply the geometric rate: δ l = ν l δ 0 , l = 0, 1, . . . ; ν ∈ (0, 1), δ 0 > 0. (23) By (16), we have hence, in view of (21), we obtain Under the above assumptions, for some x * ∈ X * it holds that Using this estimate in (24) gives Besides, since ε ≤ Φ(z l ) ≤ nδ l = nδ 0 ν l , we have ν −l(ε) ≤ nδ 0 /ε. (22), we obtain

Combining both the inequalities in
We have obtained the complexity estimate.
Theorem 3 Let a sequence {z l } be generated by the method with Basic cycle (LP).
Suppose that the function f is convex and its partial gradients satisfy Lipschitz continuity conditions with constants L i for each i ∈ I. Then the method has the complexity estimate We observe that the order of the estimates is similar to that in the usual conditional gradient methods under the same assumptions; see e.g. [4,1,2].

Some examples of applications
We intend now to give some examples of applied problems which reduce to decomposable composite optimization problems of form (8), where utilization of the proposed adaptive PL method may give certain preferences.

Selective classification problems
One of the most popular approaches to data classification is support vector machine techniques; see e.g. [24,25]. The simplest linear support vector machine problem for data classification consists in creating an optimal hyperplane separating two convex hulls of a collection of known points x i ∈ R m , i = 1, . . . , l attributed to previous data observations with different labels y i ∈ {−1, +1}, i = 1, . . . , l, where m is the number of features. That is, the distance between the hyperplane and each convex hull should be as long as possible. This separation of the feature space enables us to classify new data points. However, this requirement appears too strong for real problems where the so-called soft margin approach, which minimizes the penalties for mis-classification, is utilized. This problem can be formulated as the optimization problem where L is a loss function and C > 0 is a penalty parameter. The usual choice is L(z; y) = max{0; 1 − yz} and p is either 1 or 2. Taking p = 2, we can rewrite this problem as In this formulation, each observation i is attributed to some data point x i , however, it seems worthwhile to use sets here since any object may be often represented by some set of features, this is also the case for noisy observations; see [26]. So, let object i be represented by a set X i ∈ R m . Suppose it is the convex hull of the points x ik , k = 1, . . . , t, which thus have the same label y i ∈ {−1, +1}. Then we write the soft margin classification problem as follows: . . . , t; i = 1, . . . , l; ξ i ≥ 0, i = 1, . . . , l; which somewhat differs from those in [26]. Here ξ i is the set slack variable and we impose the penalty for the sum of set slacks. By using the convex optimization theory, we can write its dual that has the quadratic programming format: α ik ≤ C, i = 1, . . . , l; α ik ≥ 0, k = 1, . . . , t; i = 1, . . . , l; The basic solution of the primal problem is given by the formula: At the same time, we observe that the dual problem falls into format (8) and its feasible set is the corresponding Cartesian product. Hence, our method can be suitable in the high-dimensional case, where the number of sets is also very large.

Network equilibrium problems
Various network equilibrium problems represent one of the main tools for evaluation of flows distribution in traffic and communication networks. We now describe for instance the path flow formulation of the network equilibrium problem with elastic demands; see e.g. [27] and references therein. The model is determined on an oriented graph, each of its arc being associated with some flow and some cost (for instance, time of delay), which depends on the values of arc flows. Usually, the number of nodes and arcs is very large for applied problems.
Let us be given a graph with a finite set of nodes V and a set of oriented arcs A which join the nodes so that any arc a = (i, j) has the origin i and the destination j. Next, among all the pairs of nodes of the graph we extract a subset of origin-destination (O/D) pairs M of the form m = (i → j). Besides, each pair m ∈ M is associated with a variable flow demand v m and with the set of paths P m which connect the origin and destination for this pair. We suppose that each v m is non-negative with some upper bound γ m ≤ +∞ for m ∈ M. Denote by τ m the minimal path cost for the pair m and suppose that it depends on the flow demand, i.e. τ m = τ m (v m ). Also, denote by u p the path flow for the path p. Then the feasible set of flows/demands W can be defined as follows: We say that a feasible flow / demand pair (u * , v * ) ∈ W is an equilibrium point if it satisfies the following conditions: and However, conditions (25)-(26) determine equivalently the following VI: Find a pair (u * , v * ) ∈ W such that m∈M p∈Pm Furthermore, due to the separability of the functions c a and τ m , their continuity implies integrability, i.e., then there exist functions It follows that VI (27) also gives an optimality condition of the following optimization problem: Hence, each solution of (28) is a solution to VI (27), the inverse assertion is true if the functions η a and −σ m are convex, this seems rather natural. However, this problem falls into the basic format (8) and the suggested PL method can be applied to this problem.
The basic auxiliary problem consists in finding an element (ū s ,v s ) = y s (x k ) ∈ Y s (x k ) with x k = (u k , v k ), which is now corresponds to a solution of the problem min (us,vs)∈Ws for some selected pair s ∈ M. This solution can be found with the simple procedure below, which is based on optimality conditions (25)- (26). First we calculate a shortest path t ∈ P s for the pair s with the minimal cost λ = g t (u k ).
We supposed above that each function τ m is continuous, i.e. that each function σ m is smooth. However, the described procedure for problem (29) is extended easily to the case where −σ m is convex and continuous, then τ m can be set-valued. At the same time, we note that the network equilibrium problem with fixed demands differs only in somewhat simplified formulation of problem (28). Clearly, the described method remains convergent in these cases and seems in general simpler and more flexible in comparison with the usual conditional gradient and projection type methods.

Penalty method for decomposable optimization problems
A great number of optimization problems related to large scale systems are written as follows: for instance, it can be attributed to the total income maximization in a system containing n subsystems (producers), who utilize common and particular factors. That is, producer i chooses an output vector x i ∈ R l i , his/her consumption rates are described by an m 0 × l i matrix A i of common factors and by an m i × l i matrix B i of particular factors, whereas the vector c i denotes prices of his/her outputs, the vector b i ∈ R m i (respectively, b 0 ∈ R m 0 ) denotes inventories of particular (respectively, common) factors; see e.g. [28,2]. Due to its very large dimensionality, a suitable decomposition approach can be utilized to reduce the computer memory and calculation expenses. For instance, the price (Dantzig-Wolfe) decomposition principle replaces problem (30)-(32) with its dual defined with the help of the Lagrangian including only the term associated with the common constraints in (31). However, we can also utilize the penalty approach and replace problem (30)-(32) with the sequence of auxiliary problems of the form subject to x i ∈ X i , i = 1, . . . , n; where τ > 0 is a penalty parameter. Clearly, problem (33)-(34) also falls into the basic format (8) and application of the suggested PL (conditional gradient) method leads to some other decomposition method for the initial problem (30)-(32). In fact, the partial gradient of the cost function at x is written as follows , and we can make shifts only in the selected component d k s at each iteration. Besides, in order to find y k s = y s (x k ) ∈ Y s (x k ), we have to solve the separate problem min ys∈Xs → g s (x k ), y s .
Combining this method with proper regulation of τ , we obtain a sequence convergent to a solution of (30)-(32).

Computational experiments
In order to compare the performance of the presented method with the usual nondecomposable version we carried out preliminary series of computational experiments. For simplicity, we took only the smooth problems, i.e. set h ≡ 0. Hence, we compared the usual conditional gradient method (CGM) from [1] and our method which is treated as its adaptive version (ACGM). We took the even partition of R N , i.e., set N i = t = N/n for i = 1, . . . , n. Next, each set X i was chosen to be the standard simplex in R t , i.e., We took ∆ k = ϕ(x k ) as accuracy measure and chose the accuracy 0.1. We chose the same starting point (1/t)e, where e denote the vector of units in R N , and the rule δ l+1 = νδ l with ν = 0.5 for (ACGM). The methods were implemented in Delphi with double precision arithmetic. We report the number of iterations (it) and the total number of calculations (cl) of the partial gradients g i for attaining the desired accuracy.
In the first series, we took the convex quadratic cost function. We chose µ(x) = f 1 (x) where f 1 (x) = 0.5 P x, x − q, x , the elements of the matrix P are defined by and elements of the vector q are defined by q j = sin(j)/j for all i, j. The results are given in Table 1. In the second series, we took the composite convex cost function where f 1 was defined as above and f 2 (x) = 1/( c, x + τ ), where c i = 2 + sin(i) for i = 1, . . . , N and τ = 5. The results are given in Table 2. In almost all the cases, (ACGM) showed some preference over (CGM) in the number of partial gradients calculations. At the same time, tuning parameters of (ACGM) needs further investigations.

Conclusions
We described a new adaptive component-wise method for decomposable composite optimization problems involving non-smooth functions, where the feasible set is the Cartesian product. The method consists in selective component-wise steps together with a special control of tolerance sequences. We showed that this keeps the convergence properties of the usual PL one together with reduction of the computational expenses. We describe several classes of significant applications for the new method. The preliminary results of computational tests showed rather satisfactory convergence.