This paper addresses the problems of fractional programming which data is given by d.c. functions. Such problems are, in general, nonconvex (with numerous local extrema). We develop an efficient global search method for fractional program based on two different approaches. The first approach develops the Dinkelbach's idea and uses a solution of an equation with the optimal value of an auxiliary d.c. optimization problem with a vector parameter. The second one deals with another auxiliary problem with nonconvex inequality constraints. Both auxiliary problems are d.c. optimization problems, which allows us to apply the Global Optimization Theory and develop two corresponding global search algorithms. The algorithms have been substantiated and tested on an extended set of sum-of-ratios problems with up to 200 variables and 200 terms in the sum. Also we propose an algorithm for solving problems of fractional programming, which combines the two approaches.
During the recent decades the problems with the functions representable as a difference of two convex functions (i.e. d.c. functions) can be considered as one of most attractive in nonconvex optimization [Hiriart-Urruty, 1985, Horst&Pardalos, 1995, Horst&Tuy, 1996, Evtushenko& Posypkin, 2013, Khamisov, 1999, Strekalovsky, 2003, Strongin&Sergeyev, 2000, Tuy, 1998]. Actually, any continuous optimization problem can be approximated by a d.c. problem with any prescribed accuracy [Hiriart-Urruty, 1985, Horst&Tuy, 1996, Tuy, 1998]. In addition, the space of d.c. functions is a linear space, any polynomial and moreover any twice differentiable function belong to the space of d.c. functions [Hiriart-Urruty, 1985, Horst&Pardalos, 1995, Horst&Tuy, 1996, Strekalovsky, 2003, Strongin&Sergeyev, 2000, Tuy, 1998]. Besides, this space is closed with respect to all standard operations used in Analysis and Optimization. On account of this situation the general problem of mathematical optimization (Pdc) {
f0(x) := g0(x) − h0(x) ↓ mxin, x ∈ S, fj (x) := gj (x) − hj (x) ≤ 0, j = 1, . . . , m, where the functions gj (·), hj (·), j = 1, . . . , m,, are convex on IRn, S is a convex set, S ⊂ IRn, can be considered as a rather attractive object from theoretical and practical points of view.
Recently, we have succeeded in developing the Global Optimality Conditions for Problem (Pdc), which perfectly fits optimization theory and proved to be rather efficient in terms of computations [Strekalovsky, 2003, Strekalovsky, 2014]. Now we apply this theory to solving the following problem of the fractional optimization [Bugarin et al., 2016, Schaible&Shi, 2003] (Pf )
m f (x) := ∑i=1 φψii((xx)) ↓ min, x ∈ S, x where S ⊂ IRn is a convex set and ψi : IRn → IR, φi : IRn → IR, (H0)
ψi(x) > 0, φi(x) > 0 ∀x ∈ S, i = 1, . . . , m.
It is well-known that the fractional programming problem is NP-complete [Freund&Jarre, 2001]. Surveys on methods for solving this problem can be found in [Bugarin et al., 2016, Schaible&Shi, 2003], but the development of new efficient methods for a fractional program still remains an important field of research in mathematical optimization, because the sum-of-ratios programs arise in various economic applications and real-life problems [Schaible&Shi, 2003].
Here we develop efficient global search method for fractional program, which is based on two following approaches. Generalizing the Dinkelbach’s idea, we propose to reduce the fractional program with d.c. functions to solving an equation with the vector parameter that satisfies the nonnegativity assumption. In this case, we need to solve the auxiliary d.c. minimization problems, i.e. Problem (Pdc) with fi(x) ≡ 0, i ∈ I. We also propose reduction of the sum-of-ratios problem to a minimization of a linear function on the nonconvex feasible set given by d.c. inequality constraints, i.e. Problem (Pdc) where f0(x) is a linear function. Thus, based on the solution of these two particular cases of general d.c. optimization problem (Pdc) we develop two-method technology for solving a general fractional program, based on the Global Search Theory for d.c. optimization [Strekalovsky, 2003, Strekalovsky, 2014].
This paper is an extension of our research [Gruzdeva&Strekalovsky, 2017], where the theoretical framework and some computational simulations were presented. The outline of the paper is as follows. In Sect. 2, we describe two approaches to solving Problem (Pf ) using auxiliary d.c. optimization problems. In Sect. 3, we show some comparative computational testing of two approaches on fractional program instances with up to 200 variables and 200 terms in the sum generated randomly and elaborate an algorithm for solving sum-of-ratios problem combining the two proposed methods. 2
Instead of considering a fractional program directly, we develop efficient global search methods, which are based on two approaches. The first method adopts a reduction of the fractional minimization problem to the solution of an equation with an optimal value of the d.c. optimization problem with a vector parameter. The second method is based on the reduction of the sum-of-ratios problem to the optimization problem with nonconvex constraints. 2.1
To solve fractional program using d.c. minimization we consider the following auxiliary optimization problem (P ) Φ(x, α) := m ∑[ψi(x) − αiφi(x)] ↓ min, x ∈ S, i=1 x where α = (α1, . . . , αm)⊤ ∈ IRm is the vector parameter.
In this subsection we recall some results [Gruzdeva&Strekalovskiy, 2016] concerning the relations between Problems (Pf ) and (P ). Note, that the data of Problem (Pf ) must satisfy “the nonnegativity condition”, i.e. the following inequalities hold (H(α))
ψi(x) − αiφi(x) ≥ 0 ∀x ∈ S, i = 1, . . . , m.
Let us introduce the function V(α) of the optimal value to Problem (P ): In addition, suppose that the following assumptions are fulfilled: Further, suppose that in Problem (P 0 ) the following equality takes place:
V(α) := inxf{Φ(x, α) | x ∈ S} = inf x { m } ∑[ψi(x) − αiφi(x)] : x ∈ S .
i=1 (H1) (a) V(α) > −∞ ∀α ∈ K, where K is a convex set from IRm; (b) ∀α ∈ K ⊂ IRm there exists a solution z = z(α) to Problem (P )
V(α0) : = inf x { m ∑[ψi(x) − α0iφi(x)] : x ∈ S i=1 } = 0.
(1)
In [Gruzdeva&Strekalovskiy, 2016] we proved that any solution z = z(α0) to Problem (P 0 ) is a solution to Problem (Pf ), so that z ∈ Sol(P 0 ) ⊂ Sol(Pf ).
Therefore in order to verify the equality (1), we should be able to find a global solution to Problem (P ) for every α ∈ IR+m. Since ψi(·), φi(·), i = 1, . . . , m, are simply convex or generally d.c. functions it can be readily seen that Problem (P ) belongs to the class of d.c. minimization. As a consequence, in order to solve Problem (P ), we can apply the Global Search Theory [Strekalovsky, 2003, Strekalovsky, 2014].
Due to the theoretical foundation developed in [Gruzdeva&Strekalovskiy, 2016], we are able to avoid the consideration of Problem (Pf ), and address the parametrized problem (P ) with α ∈ IR+m. Hence, instead of solving Problem (Pf ), we propose to combine solving of Problem (P ) with a search with respect to the parameter α ∈ IR+m in order to find the vector α0 ∈ IR+m such that V(α0) = 0.
Denote Φi(x) := ψi(x) − αikφi(x), i = 1, . . . , m. Let [vk, uk] be a k-segment for varying α. Let a solution z(αk) to Problem (P k ) be given and we computed Vk := V(αk).
αk-bisection algorithm Step 1. If Vk > 0, then set vk+1 = αk, αk+1 = 21 (uk + αk).
Step 2. If Vk < 0, then set uk+1 = αk, αk+1 = 12 (vk + αk). ψi(z(αk)) Step 3. If Vk = 0 and miin Φi(z(αk)) < 0, then set αik+1 = φi(z(αk)) ∀i : Φi(z(αk)) < 0, αk+1 = αik ∀i : Φi(z(αk)) ≥ 0.
i In addition, set vk+1 = 0, uk+1 = tk+1αk+1, where tk+1 = α+ max αi i .
Stop: we computed the values αk+1, vk+1 and uk+1.
Further, let [0, α+] be an initial segment for varying α. To choose α+ we should take into account that due to (H(α)) and (H0), we have ∀i = 1, . . . , m : αi ≤ fi(x) , ψi(x) ϕi(x) ≤ i=1 ϕi(x) m ∑ ψi(x) = f (x) ∀x ∈ S, so, for example, α+ can be chosen as αi+ = fi(x0), i = 1, . . . , m.
Step 0. (Initialization) k = 0, vk = 0, uk = α+, αk = 2+ ∈ [vk, uk].
Step 1. Find a solution z(αk) to Problem (P k ) using the global search strategy for d.c. [Strekalovsky, 2003, Strekalovsky, 2014].
Let us emphasize the fact that the algorithm for solving Problem (Pf ) of fractional optimization consists of 3 basic stages: the (a) local and (b) global searches in Problem (P ) with a fixed vector parameter α (Step 1) and (c) the method for finding the vector parameter α (Step 3) at which the optimal value of Problem (P ) is zero, i.e. V(α) = 0. In this subsection we reduce the fractional program to the following optimization problem with a nonconvex feasible set (P) m f0 := ∑αi ↓ (mx;in), x ∈ S,
i=1 fi := ψi(x) − αiφi(x) ≤ 0, i = 1, . . . , m.
In [Gruzdeva&Strekalovsky, 2016] it was proved that for any solution (x∗, α∗) ∈ IRn × IRm to the problem (P), the point x∗ will be a solution to Problem (Pf ).
Further we solved problem (P) using the exact penalization approach for d.c. optimization developed in [Strekalovsky, 2016, Strekalovsky, 2017]. Therefore, we introduce the penalized problem as follows (P )
θ (x) = f0(x) + σ max{0, fi(x), i ∈ I} ↓ min, x ∈ S.
It can be readily seen that the penalized function θ (·) is a d.c. function, because the functions fi(·) = gi(·) − hi(·), i ∈ I ∪ { }
0 , are the same, and we can apply the global search theory to solving this class of nonconvex problems [Strekalovsky, 2003, Strekalovsky, 2014].
Actually, since σ > 0, θ (x) = G (x) − H (x), H (x) := h0(x) + σ ∑hi(x), i∈I G (x) := θ (x)+H (x) = g0(x)+σ max { m ∑hi(x); max[gi(x) + i=1 i∈I
} ∑ hj(x)] , j∈I; j̸=i it is clear that G (·) and H (·) are convex functions.
Let the Lagrange multipliers, associated with the constraints and corresponding to the point zk, k ∈ {1, 2, ...}, be denoted by λ := (λ1, . . . , λm) ∈ IRm.
Step 1. Using the local search method from [Strekalovsky&Gruzdeva, 2007, Strekalovsky, 2015], find a critical point zk in (P).
m Step 2. Set σk := ∑λi. Choose a number β : inf(G , S) ≤ β ≤ sup(G , S).
i=1
Choose an initial β0 = G (zk), ζk = θ (zk).
Step 3. Construct a finite approximation Rk(β) = {v1, . . . , vNk | H (vi) = β + ζk, i = 1, . . . , Nk, Nk = Nk(β)} of the level surface {H (x) = β + ζk} of the function H (·).
Step 4. Find a δk-solution u¯i of the following Linearized Problem: (P Li)
G (x) − ⟨∇H (vi), x⟩ ↓ mxin, x ∈ S. so that G (u¯i) − ⟨∇H (vi), u¯i⟩ − δk ≤ inxf{G (x) − ⟨∇H (vi), x⟩}. by the local search method from Step 5. Starting from the point u¯i, find a KKT-point ui
[Strekalovsky&Gruzdeva, 2007, Strekalovsky, 2015].
Step 6. Choose the point uj : f (uj) ≤ min{f0(ui), i = 1, ..., N }.
Step 7. If f0(uj) < f0(zk), then set zk+1 = uj, k = k + 1 and go to Step 2.
Step 8. Otherwise, choose a new value of β and go to Step 3.
The point z∗ resulting from the global search strategy will be a solution to the original fraction program [Gruzdeva&Strekalovsky, 2016]. It should be noted that, in contrast to the approach from Subsect. 2.1, αi will be found simultaneously with the solution vector x, because they are variables, although auxiliary ones, of the optimization problem. 3
Two approaches from above for solving the fractional programs (Pf ) via d.c. optimization problems were verified. The algorithm based on the method for solving fractional problem from Subsect. 2.1 (F1-algorithm) and the global search scheme from Subsect. 2.2 (F2-algorithm) were coded in C++ language and applied to an extended set of test examples generated randomly with up to 200 variables and 200 terms in the sum. All computational experiments were performed on the Intel Core i7-4790K CPU 4.0 GHz. All convex auxiliary problems (linearized problems) on the steps of F1-, F2-algorithms were solved by the software package IBM ILOG CPLEX 12.6.2.
Some of the computational experiments of testing the proposed algorithms on fractional problems with quadratic functions in the numerators of ratios is presented here.
We generated the problems of the type proposed by [Jong, 2013] as follows: f (x) := ∑m⟨x, Aix⟩ + ⟨bi, x⟩ ↓ mxin, Qx ≤ q, x ∈ [1, 5]n, i=1 ⟨ci, x⟩ (2) where Ai = UiD0iUiT , Ui = V1V2V3, i = 1, . . . , n; Vj = I − 2 ∥wwjwj∥jT2 , j = 1, 2, 3; w1 = −i + rand(n, 1), w2 = −2i+rand(n, 1), w3 = −3i+rand(n, 1); ci = i−i·rand(n, 1), bi = i+i·rand(n, 1), Q = −1+2·rand(5, n), q = 2 + 3 · rand(5, 1)[Jong, 2013]. (We denote by rand(k1, k2) the random matrix with k1 rows, k2 columns and the elements generated randomly on [0, 1].)
Note that Problems (P ) corresponding to the problems (2) happened to be convex, because the constructed functions ψi = ⟨x, Aix⟩ + ⟨bi, x⟩, i = 1, . . . , m, are convex. That is why the F1-algorithm’s run-time turned out to be much less than the run-time of F2-algorithm, in which it is necessary to solve nonconvex problems with m d.c. constraints.
The shortcoming of the F2-algorithm is the run-time which is spent on solving problems with d.c. constraints, but F1-algorithm wastes a lot of run-time for finding the vector parameter α at which the optimal value of Problem (P ) is zero.
The results of computational experiments suggest that the solving of the fraction programs need a combination of the two approaches. For example, we can use the solution to Problem (P) to search for the parameter α that reduces the optimal value function of Problem (P ) to zero. This idea could be implemented by the following algorithm.
Step 0. (Initialization) k = 0, vk = 0, uk = α+.
Step 1. Starting from feasible point xk, implement the local search method from [Strekalovsky&Gruzdeva, 2007,
Strekalovsky, 2015] to find a critical point zk = (zˆ(αk), αk) in d.c. constraints problem (P).
Step 2. (Stopping criterion) If Vk := V(αk) = 0 and min Φi(zˆ(αk)) ≥ 0, then STOP: zˆ(αk) ∈ Sol(Pf ).
i Step 3. Find a solution z(αk) to Problem (P k ) using the global search strategy for d.c. [Strekalovsky, 2003, Strekalovsky, 2014]. minimization Step 4. (Stopping criterion) If Vk := V(αk) = 0 and min Φi(z(αk)) ≥ 0, then STOP: z(αk) ∈ Sol(Pf ).
i Step 5. Implement αk-bisection algorithm to find new parameters αk+1, vk+1 and uk+1.
Set xk+1 = (z(αk), αk+1), k = k + 1 and go to Step 1.
The two-component algorithm was tested on a lots of test examples and its run-time turned out to be less than the run-time of F1-algorithm. 4
In this paper, we showed how fractional programs can be solved by applying the Global Search Theory of d.c. optimization. The methods developed were substantiated and tested on an extended set of test examples generated randomly. In addition, we proposed a two-component technology based on both the global search algorithm for d.c. minimization problem and algorithm for solving d.c. constraints problem. This work is carried out under financial support of Russian Science Foundation (project no. 15-11-20015). [Bugarin et al., 2016] Bugarin, F., Henrion, D. & Lasserre J.-B. Minimizing the sum of many rational functions.
Mathematical Programming Computation, 8, 83-111. doi: 10.1007/s12532-015-0089-z [Evtushenko& Posypkin, 2013] Evtushenko, Y. & Posypkin, M. A deterministic approach to global boxconstrained optimization. Optimization Letters, 7(4), 819-829. doi: 10.1007/s11590-012-0452-1 [Freund&Jarre, 2001] Freund, R.W. & Jarre, F. Solving the sum-of-ratios problem by an interior-point method.
Journal of Global Optimization, 19(1), 83-102. [Gruzdeva&Strekalovskiy, 2016] Gruzdeva, T.V. & Strekalovskiy, A.S. An approach to fractional programming via D.C. optimization. AIP Conference Proceedings, 1776, 090010. doi: 10.1063/1.4965374 [Gruzdeva&Strekalovsky, 2017] Gruzdeva, T.V. & Strekalovsky, A.S. A D.C. Programming Approach to Fractional Problems. In: R. Battiti, D. Kvasov, Y. Sergeyev (eds.) ”Learning and Intelligent Optimization Conference LION11, Nizhny Novgorod, Russia”. Lecture Notes in Computer Science, 10556 Springer. To appear. [Tuy, 1998] Tuy, H. Convex Analysis and Global Optimization. Dordrecht: Kluwer Academic Publishers.