We suggest an approach to solve special classes of multi-extremal problems to optimize the monotone combination (e.g., sum, product) of several functions, under the assumption that the effective algorithms to optimize each of this item are known (e.g., each of these functions has some properties of generalized concavity: linear fractional, etc.) The algorithm proposed is iterative. It realizes one of the idea of the branchand-bound method and consists in successive correcting of the low and the upper bounds of optimal value of objective functions. Moreover, we use the methodology of multi-objective optimization, studying the image of Pareto boundary in the image space. In each iteration, the total area of the region, guaranteed to contain the image optimal point, decreases at least twice.
Note that to solve problem (1) the effective algorithms (taking into account the special structure of the problem) are known only for the case when the set X is polyhedral and the functions Fi have a special form (for example, they are linear fractional). Let us mention briefly some works: [Choo et al., 1982], [Warburton, 1985], [Benson, 2002], [Kuno, 2002], [Gruzdeva & Strekalovsky, 2016]. A feature of the described algorithms in mentioned works is that they take into account a special kind of problem, therefore they cannot be transferred directly to the case when the functions Fi have a more general form.
The main goal of our paper is to construct an effective algorithm for solving a problem of the form (1). The proposed algorithm realizes the idea of the branch-and-bound method and consists in successively refinement of the boundaries of the optimal value of the objective function. The very preliminary variant of this approach can be found in [Bykadorov, 2016]. 2
Consider the problem
(P ) : f (x) = f1(x) + f2(x) → xm∈iXn; where X ⊂ Rn is a set while fi are real-valued functions defined on X. We assume that effective algorithms are known for solving each of the following problems:
fi(x) → xm∈iXn; i = 1; 2: i0 = xm∈iXn fi(x); i = 1; 2: Let us associate with each i ∈ R the sets Xi ( i) = {x ∈ X : fi(x) ≤ i} ; i = 1; 2; and consider the problems (P1 ( 2)) : f1(x) → x∈X2( 2) min ; (P2 ( 1)) : f2(x) → x∈X1( 1) min : (P1 ( 0))and (P2 ( 10))are solvable and, moreover, f1 (xP2( 10)
2
Let us denote Let xP1( 2) and xP2( 1) be the solutions of the problems (P1 ( 2)) and (P2 ( 1)), respectively. For arbitrary choice of 1 and 2, it is possible that problems (P1 ( 2)) and (P2 ( 1)) have no solutions. But due to (3), problems ) ) = 20.
= 10 and f2 (xP1( 20) De nition. A pair ( 1; 2) is said to be attainable if a point x ∈ X exists such that f1(x) = 1; f2(x) = 2. Remark. By construction, pairs ( 10; 200) and ( 100; 20) are attainable.
Let x∗ be the solution of Problem (P ) and fi (x∗) = i∗; i = 1; 2. Due to (3) and (4), i∗ ∈ [ i0; i00] ; i = 1; 2. Consider right isosceles triangle ABC with vertices Let us denote Ti = [ i0; i00] ; i = 1; 2. In what follows, we assume that the following condition is fulfilled. Condition (A). For any pair ( 1; 2) ∈ T1 × T2, the points x′ ∈ X and x′′ ∈ X exist such that f1 (x′) = 1; f2 (x′) = f2 (xP2( 1)); f1 (x′′) = f1 (xP1( 2)); f2 (x′′) = 2: Remark. Let ( 1; 2) ∈ T1 × T2. Then the pairs ( 1; f2 (xP2( 1)))and (f1 (xP1( 2)); 2) are attainable. Lemma 1. The following statements are true.
Note. The proofs of this and subsequent statements are rather technical. We plan to bring these formal proofs in the extended version of this paper.
Consider the function G : T1 → R defined as follows:
G ( 1) = min {f2(x) : x ∈ X1 ( 1) ; 1 ∈ T1} :
Corollary 1.1. The function G is decreasing.
Consider the set
Y = {( 1; G ( 1)) : 1 ∈ T1} (6) (see figure 2). We associate with each pair ( 1; 2) ∈ Y the line H ( 1; 2) passing through it and parallel to the hypotenuse of triangle ABC. Then the pair ( 1∗; 2∗) of interest to us (the values of the functions f1 and f2 in the optimum) is characterized as follows (see figure 2): for each pair ( 1; 2) ∈ Y , the line H ( 1; 2) lies \above" the straight line H ( 1∗; 2∗).
The remainder of this section we devote to describing a situation when Condition (A) holds. Lemma 2. The following statements are true. • Let 1 ∈ T1. If f1 (xP2( 1)) < 1 then xP2( 1) ̸∈ arg minx∈X f2(x). • Let 2 ∈ T2. If f2 (xP1( 2)) < 2 then xP1( 2) ̸∈ arg minx∈X f1(x).
Lemma 3. The following statements are true. • Let 1 ∈ T1 and function f2 be quasi-convex on set X. If f1 (xP2( 1)) < f1 (x′) = 1; f2 (x′) = f2 (xP2( 1) .
) • Let 2 ∈ T2 and function f1 be quasi-convex on set X. If f2 (xP1( 2)) <
f1 (x′′) = f1 (xP1( 2)); f2 (x′′) = 2.
Corollary 3.1. The following statements are true. 1 then x′ ∈ X exists such that 2 then x′′ ∈ X exists such that • Let function f2 be quasi-convex on set X. For each 1 ∈ T1, point x′ exists such that f1 (x′) = 1; f2 (x′) = f2 (xP2( 1) .
) • Let function f1 be quasi-convex on set X. For each 2 ∈ T2, point x′′ ∈ X exists such that f1 (x′′) = f1 (xP1( 2)); f2 (x′′) = 2.
Corollary 3.2. Let functions f1 and f2 be quasi-convex on X. Then Condition (A) holds. 3
The algorithm is iterative, realizes one of the ideas of the branch-and-bound method, and consists in the sequential refinement of the estimates of the values 1∗; 2∗ and 1∗ + 2∗, as well as the reduction the total area of the region containing the point ( 1∗; 2∗).
Let 1 ∈ [ 10; 10 + 10;2]. (For the definition of 10 see (3), while the definition of 10;2 see in (5)). We set 2 = G ( 1). Note that ( 1; 2) ∈ Y by the definition of set Y , see (6).
The following cases are possible: • 1 + 2 < • 1 + 2 = • 1 + 2 > • 1 + 2 > 0 ≡ 10 + 20 + 10;2, see figure 3; 0, see figure 4; 0; 2 < 20 + 10;2, see figure 5; 0; 2 ≥ 20 + 10;2, see figure 6.
In each of these cases we can exclude from further consideration the regions that (due to Corollary 2) does not contain the point of our interest ( 1∗; 2∗). These areas correspond to the shaded parts of the triangle ABC. As a result, the estimates for the value 1∗ + 2∗ are refined, and the area of the region, which is guaranteed not containing the point ( 1∗; 2∗), is also increased.
In the next steps, the described procedure is applied to each of the obtained unshaded triangles, or to one of them (for example, the largest, “the most perspective”). 4
Some Remarks 1. As initial lower bounds for 1∗; 2∗ and 1∗ + 2∗, we can take, for example, the following: and as the upper bounds, the values where
1 = 1 +2 1 ; 2 = f2 (xP2( 1)); then due to Corollary 1.1, we can delete from the triangle ABC the region whose area is not less than half the area of the triangle ABC, see all the cases shown in figures 3 – 6. Therefore, in each iteration, the total area of the region, guaranteed to contain the image optimal point, decreases at least twice. This allows us to tell about the effectiveness of the algorithm.
3. The disadvantage of the proposed approach is to recognize the possible increase in the number of resulting triangles, this leads to an increase in the volume of stored information. However, in the case of an excessive increase in the number of these triangles, one can be chosen (for example, the largest one, i.e., “promising”) and temporarily “forget” about the others, see figure 7, thus obtaining new estimates of the quantities 1∗; 2∗ and 1∗ + 2∗ for this selected triangle. These new estimates may allow us to exclude some of the “forgotten” triangles from further consideration, since we remove all parts of the triangles lying “above” the corresponding hypotenuse (this part may coincide with the whole triangle, see figure 8). Then we can consider all the “updated” triangles, choose one of them as the most “promising” for the next step. Thus, the number of considered triangles does not necessarily increase, and, moreover, may even decrease. 5
Step 0. Define the values 1; 2; ; 1; 2; such that 1 ≤ 1∗ ≤ 1; 2 ≤ 2∗ ≤ 2; ≤ 1∗ + 2∗ ≤ : Choose ", the required accuracy of calculations.
Set l = 1 as the total number of triangles under consideration, s = 1 as the number of the considered triangle. 1 + 1 )
. Solve the problemP2 ( 1). Set 2 = f2 (xP2( 1) .
2 Step 1. Choose 1 ∈ [ 1; 1]. For example, set 1 = Step 2.
(2a) Let the case shown in figure 3 is realized, i.e., 1 + 2 < ≡ 1 + 2 + 1;2, where min { 1 − 1; 2 − 2} (cf. (5)). Calculate for the considered triangle the values x; y; z (see figure 9): 1;2 = x[s] = 1; y[s] = 1 + 2 − 2; z[s] = 2: Calculate x; y; z for the new triangle: x[l + 1] = 1; y[l + 1] = 1; z[l + 1] = 2. Set l = l + 1. Go to Step 3.
(2b) Let one of the cases shown in figure 4 and 5 is realized, i.e., 1 + 2 = , or 1 + 2 > but 2 < 2 + 1;2. Set x[s] = 1; y[s] = 2; z[s] = 2; x[l + 1] = 1; y[l + 1] = 1 + 2 − 2; z[l + 1] = 2; l = l + 1. Go to Step 4.
(2c) Let the case shown in figure 6 is realized, i.e., 1 + 2 > but 2 ≥ 2 + 1;2. Set x[s] = 1; y[s] = 2; z[s] = 2. Go to Step 4.
Step 3. Compare the coordinates of the vertices of all the triangles obtained. If the situation shown in figure 8, are realized, then delete the triangles (or parts thereof) located “between” the two hypotenuses. Renumber the remaining triangles. Recalculate for each of the triangles the value y (since in the triangles the trapezium part was removed, with bases parallel to the hypotenuse).
Step 4. Among all triangles, choose the largest (i.e., such that the value y − x is maximal). We assign the number s to this triangle.
Step 5. For triangle with the number s, calculate the values x[s]; y[s]; z[s], see figure 9. Set 1 = x[s];
≡ y[s] − x[s] ≤ " then STOP. Otherwise, go to Step 1.
The application of the proposed approach to the general form of the problem (1) requires that effective algorithms
for solving each of the problems (2) be known. In addition, Condition (A) is required. In particular, we can
assume that the functions Fi have some properties of generalized convexity
Possible modifications of the proposed approach deal with different ways of constructing the curve Y (see (6)) using already known achievable points (for example, by interpolations, approximations).
Besides, the described approach is also applicable to the optimization of “monotonic” combinations (for example, products) of functions. In this case, for the product of two functions, in image space, the level lines of the function f1 · f2 are hyperbolas. Hence, instead of the right isosceles triangles, we deal with the “curvilinear” right triangles by replacing the hypotenuse with a piece of the corresponding hyperbola. It seems that the generality of the proposed approach is its advantage over other methods that take into account the structure of the problem.
Of course, the practical value of the proposed approach is questionable since no experimental results are presented. It is necessary to add practical experiments demonstrating the superiority of the proposed approach over other global optimization methods. We plan to do it in the future, in the extended versions of the paper.
Finally, the approach can be applied to the problems that arise in marketing: optimization of communication expenditure [Bykadorov et al., 2002] and the effectiveness of advertising [Bykadorov et al., 2009a], pricing [Bykadorov et al., 2009b]; to monopolistic competition models: retailing [Bykadorov et al., 2014], investments in R&D [Antoshchenkova & Bykadorov, 2017], market distortion [Bykadorov et al., 2016], and international trade [Bykadorov et al., 2015].
The author considers it his pleasant duty to express deep gratitude to the anonymous reviewers for very valuable comments. It is hoped that their excellent comments have allowed to improve the content of the paper and the presentation of the material.