Solving the Sum-of-Ratios Problem by an Interior-Point Method.
We consider the problem of minimizing the sum of a convex function and of p1 fractions subject to convex constraints. The numerators of the fractions are positive convex functions, and the denominators are positive concave functions. Thus, each fraction is quasi-convex. We give a brief discussion of the problem and prove that in spite of its special structure, the problem is \cN\cP-complete even when only p=1 fraction is involved. We then show how the problem can be reduced to the minimization of a function of p variables where the function values are given by the solution of certain convex subproblems. Based on this reduction, we propose an algorithm for computing the global minimum of the problem by means of an interior-point method for convex programs.
Introduction
Nonlinear programming problems often involve objective functions that
can be expressed in terms of one or several ratios. Exploiting the special
structure of such fractional programs has been the subject of extensive
studies in the last few decades. For an overview of fractional program-
ming, we refer the reader to (Schaible, 1995) and the references given
therein.
Fractional programs with only a single ratio or a maximum of finitely
many ratios are fairly well understood. Under suitable conditions, these
problems still satisfy some form of generalized convexity, which can be
exploited in algorithms for the numerical solution of such problems. For
example, there are polynomial-time interior-point methods for classes of
such problems; see (Freund and Jarre, 1994, 1995; Nemirovskii, 1996).
y Numerical Analysis Manuscript No. 99-3-13, Bell Laboratories, Murray Hill,
New Jersey, June 1999.
Available on WWW at http://cm.bell-labs.com/cs/doc/99.
Roland W. Freund and Florian Jarre
On the other hand, fractional programs with sums of ratios are much
more difficult and not as well understood; see (Schaible, 1995, 1996).
Such problems possess some form of generalized convexity only in special
cases, such as the ones discussed in (Schaible, 1984; Hirche, 1985),
and in general, they have multiple maxima and minima. Algorithms
for classes of sum-of-ratios problems are described in (Cambini et al.,
1989; Chen et al., 1998; Falk and Palocsay, 1992; Konno and Kuno,
1990; Konno and Yamashita, 1998; Ritter, 1967) and in the review
article (Schaible, 1996). However, most of these algorithms are for the
optimization of linear ratios subject to linear constraints. The purpose
of this paper is to present a suitable interior-point approach for the
solution of much more general problems with convex-concave ratios
and convex constraints. Our approach is based on approximating the
sum-of-ratios problem by a sequence of convex minimization problems.
For such convex problems, interior-point methods have become the
methods of choice, both from the point of view of theoretical complexity
and of practical efficiency. By using a simple warm-start strategy, the
cost for solving the individual convex subproblems can be reduced to
very few iterations. Finally, the interior-point method provides certain
dual information needed for the overall approach.
More precisely, we consider the problem of minimizing or maximizing
the sum of a single function and of p - 1 ratios subject to convex
constraints, and we explore the use of interior-point methods for the
solution of such problems. More precisely, we study problems of the
subject to x 2
and
subject to x 2 S: (2)
Here and in the sequel, we make the following assumptions.
ASSUMPTION 1. S ae IR n is a compact convex set such that f j (x) - 0
and S. For the minimization
problem (1), the functions h and f 1 are convex and
the functions are concave. For the maximization problem
(2), the functions h and f 1 are concave and the functions
are convex.
For simplicity, from now on we restrict ourselves to minimization
problems (1). The results and algorithms for (1) in this paper can easily
Solving the Sum-of-Ratios Problem 3
be converted to maximization problems (2) by simply exchanging "min"
and "max", "convex" and "concave", and "-" and "-".
In Section 2, we first discuss the simplest case, namely the sum of
a convex function and only We show that this problem is
NP-complete and propose a method for finding the global minimizer.
In Section 3, the method is generalized to the case p - 2. In Section 4,
we report results of numerical experiments. In Section 5, we make some
concluding remarks.
2. Sum of one fraction and a convex function
Throughout this section, we assume that 1. In this case, problem
(1) reduces to the form
subject to x 2 S: (3)
Here, f; are functions that satisfy the conditions specified
in Assumption 1, i.e., f and h are convex, g is concave, and f(x) - 0
S. For any fixed r ? 0, let
ae
r
oe
and
r
g, the feasible set in (4) is empty, and in
this case, we set q(r) := 1. Note that x(r) is not necessarily unique,
but, of course, q(r) is. From the definition of q, it is obvious that x(r   )
solves (3) if, and only if, r   minimizes q. Thus, problem (3) is reduced
to the one-dimensional problem of minimizing the function q.
Determining x(r) for a given value r ? 0 is a convex optimization
problem, which can be solved by several methods.
If a separation oracle for S (ae IR n ) is given, the evaluation of q
for a given value of r can be done (up to a given precision) by the
ellipsoid method. Here, by "separation oracle", we mean a subprogram
that accepts as input any vector x 2 IR n and produces as output either
the information "x 2 S", or a vector h 2 IR n , h 6= 0, with h T y - h T x
for all y 2 S. In the second case, the vector h defines a hyperplane that
"separates" x from S.
If self-concordant barrier functions for the sets
ae
r
- and g(x) - r
oe
4 Roland W. Freund and Florian Jarre
for real numbers - are known, then q(r) can also be evaluated by an
interior-point method. Here, a barrier function for a convex set C is
a function that is convex and finite in the interior of C, and goes
to infinity as x approaches the boundary of C. The notion of self-
concordance was first introduced in (Nesterov and Nemirovskii, 1994).
Roughly speaking, self-concordance is defined as a local Lipschitz condition
of the Hessian of the barrier function. As shown in (Nesterov and
Nemirovskii, 1994), many convex sets possess easily computable self-
concordant barrier functions, and the concept of interior-point methods
based on self-concordance is a very general approach.
We remark that for the special case of a constant function h and
problem (1) can be reduced to a problem of the form (3),
i.e., with only one ratio, by means of the Charnes-Cooper transformation
(Charnes and Cooper, 1962); see, e.g., (Cambini et al., 1989). A
self-concordant barrier function for the conic hull introduced by this
transformation is discussed in (Freund et al., 1996). In general, when
is constant, the Charnes-Cooper transformation can be
used to reduce problem (1) to a sum-of-ratios problem with
This simple reduction may be crucial for algorithms whose computational
costs grow rapidly with the number of ratios. For example, given
a sum-of-ratios problem with will be more efficient
to first employ the Charnes-Cooper transformation and then apply the
algorithm of the present paper to the reformulation with
than using the same algorithm for the solution of the original problem
with 2.
2.1. Properties of the function q
Next, we recall some well-known properties of the function q given
by (4) and (5).
oet, and by the convexity of f , we have
s
ae f(x(r))
r
oe
Similarly, the convexity of h implies that
By the concavity of g, it also follows that g(x) - s. Hence, x is feasible
for (4), and
s
Solving the Sum-of-Ratios Problem 5
In spite of (6), (7), and (8), the function q is not quasi-convex, i.e., in
general it may happen that
Note that if q were quasi-convex, problem (3) could be solved in polynomial
time by using a golden-mean search for q.
In view of the above derivation, we may still ask ourselves whether
the function q may "smooth out" some of the local minimizers of (3),
and whether minimizing q might be easier than solving problem (3)
directly (assuming that we can evaluate q and its derivatives). The
observation that the function q is not necessarily simpler than (3) is
illustrated in Figure 1 below, which depicts the function q for a special
case where S is just a real interval. This plot shows that q may exhibit
a very "irregular" behavior.
2.2. NP-completeness
Next, we prove that problem (3) is "essentially" NP-complete. To
this end, we show that a well-known NP-complete problem, namely
the following knapsack problem, can be recast as a special instance of
problem (3).
Knapsack problem:
Let an integer d ? 1, weights
and costs c g. The problem
is to find a subset I 0 ae I such that
maximized subject
to the constraint
For a discussion of the knapsack problem and a proof of its NP-
completeness, we refer the reader to (Garey and Johnson, 1979).
Our result on the NP-completeness of problem (3) can now be
stated as follows.
THEOREM 2. Problem (3) is NP-complete in the following sense. Let
the data of a knapsack problem with d 2 IN weights be given. There exists
a convex, piecewise linear function f , a linear function g, and a linear
function h defined on the interval such that f , g, h, and
their respective derivatives can be evaluated in polynomial time, f , g,
and h take values of polynomial size, and solving problem (3) is equivalent
to solving the given knapsack problem.
REMARK 3. The right endpoint 2 d of the interval S in Theorem 2 is
not polynomial. At first sight, this might lead to the impression that the
reduction of a knapsack problem to problem (3) is exponential. This,
6 Roland W. Freund and Florian Jarre
of course, is not the case. Indeed, just as in the case of linear pro-
grams, which may also involve non-polynomial upper or lower bounds,
one only needs polynomiality in the coding length of the problem. The
coding length of problem (3) is at least d, and hence the coding length
of the endpoint 2 d is in fact polynomial in the coding length of the
problem. Finally, note that if the function f=g were convex, then an
ffl-approximation to problem (3) could be computed in polynomial time.
The NP-completeness in Theorem 2 does not result from the size of
the endpoint 2 d of S, but from the lack of convexity.
Proof of Theorem 2. Let d 2 IN , weights w
be the given data of a knapsack
problem. From this data, we now construct a special problem of the
form (3) that is "equivalent" to the knapsack problem.
To this end, we first enumerate the 2 d subsets of I
by simply counting from 1 to 2 d in the binary system. Then, for each
subset I 0 of I, there exists an index 1 - k - 2 d such that I
is the k-th subset of the enumeration. We can determine I k just by
knowing its index k, and without looking at any other subset. We can
also determine the weight
w i of the k-th subset just by knowing
the index k. For
where c :=
. Solving the knapsack problem is then equivalent
to finding
min
1-k-2 d
For later use, we note that
Next, we set S := [1; 2 d ] and define functions f;
The functions g and h are the linear functions given by
The function f is defined as the piecewise linear interpolant through the
points . Hence, on each interval k - x
Solving the Sum-of-Ratios Problem 7
Using (10), one readily verifies that the function f is convex on S.
Clearly, given any x 2 S, it is possible to evaluate f(x) in O(d)
arithmetic operations, and the number of digits needed to represent
the function values are at most 2d plus the number of digits
needed to evaluate
Finally, we show that for the set S and the functions f , g, and h
just defined, the minimizer of (3) is the index k of a k-th subset I k ae I
that solves the knapsack problem. Let 1 and consider the
objective function of (3) for By (10)-(12), the second
derivative of the objective function satisfies
for all x 2 This shows that the objective function of (3) is
concave on [k; k + 1], and thus its minimum over [k; k + 1] is attained
at 1. By (11) and (12), the corresponding function
values are
2 d for
2 d for
Therefore, problem (3) is equivalent to (9), which in turn is equivalent
to solving the knapsack problem.
For the special instance of problem (3) constructed in the proof
of Theorem 2, the evaluation of the associated function (5), q(r), is
particularly simple. Indeed, let x - r and x 2
d
dx
r
r
r
r
r
0:
This shows that the objective function in (4) is monotonically increasing
Therefore, the minimum in (4) is
attained for and the function q(r) in (5) is identical to the
objective function of (3). In Figure 1, we plot the function q for the
case of the knapsack problem with

Figure

1 displays an example where minimizing q is identical to
solving problem (3). In general, however, we may anticipate that the
8 Roland W. Freund and Florian Jarre
Value of r
Value
of

Figure

1. The objective function with random w i 's and c i 's.
structure of the higher-dimensional problem (3) is far more complicated
than the scalar function q. We propose an approach for solving problem
(3) by evaluating q for various values of r and exploiting Lipschitz
properties of q.
We emphasize that in the case where the function q has very many
local minimizers of approximately the same magnitude (as in the class
of problems constructed in the proof of Theorem 2), any approach for
solving problem (1) will necessarily be very slow (unless
2.3. A global minimization method
If f; g, and h are smooth, due to the structure of S, the function q is
generally a piecewise smooth function. To compute a global minimizer
r   of q, we construct a lower-bound function q(r) - q(r) and then
minimize q.
The function q depends on a partition,
where we assume that r (1) - r   and r (k) - r   . Note that
Solving the Sum-of-Ratios Problem 9
so that a value for r (1) can be obtained from a given lower bound of g
on S, and a value for r (k) by solving the concave maximization problem
in (13).
Let some i and be given. Define a lower-bound
number
ae
r (i+1)
oe
so that q i - q(r) for r 2 [r (i) ; r (i+1) ]. Note that evaluating the right-hand
side of (14) amounts to solving a convex optimization problem.
Let x i be a solution of the minimization problem in (14). It follows that
Using these two inequalities, for all r 2 [r (i) ; r (i+1) ], we get
r
r
r (i+1)
r
r (i)
r
r
r (i)
r (i)
r
r (i)
where
r (i)
Note that the inequality (15) follows from r (i) =r - 1 and q i \Gammaq(r (i)
The bound (16) proves left-sided Lipschitz continuity of q. Indeed,
near the above bound is close to the value q(r (i) ). However,
for , the bound reduces to q i , which is lower than the value
q(r (i+1) ).
Roland W. Freund and Florian Jarre
Note that a bound of the form (15) with q(r (i+1) ) in place of q(r (i) )
is not possible. It may occur that q(r (i+1) ) AE q(r (i) ). Intuitively, this
will happen when no longer contains points
for which f or h are reasonably small but does.
In this case, the Lipschitz constant for q from the right may be much
larger than the one from the left. To determine a suitable Lipschitz
property from the right, we define the function
~
ae
r (i+1)
oe
Observe that ~
q i is convex (in r). Moreover, ~ q i satisfies ~
for r - r (i+1) , and ~
We remark that when evaluating
q(r (i+1) ), the problem (17) with is solved, and the
Lagrange multiplier-denoted by - g in the sequel-corresponding to
the constraint g(x) - r (i+1) can also be computed. Indeed, interior-point
methods can be implemented so that such a multiplier is obtained
at no extra cost. The Lagrange multiplier leads to the bound
for r - r (i+1) ; see, e.g., Theorem VII.3.3.2 in (Hiriart-Urruty and
Lemarechal, 1993). The lower-bound function q(r) is then defined for
as the maximum of the bounds (16) and (18),
A simple method for solving problem (3) then proceeds as follows.
Given k points
a new point -
r from the interval (r (i) ; r (i+1) ) that contains a minimizer
of minf is chosen. Then, -
r is inserted into the
list (19) (thus k is increased by one), and the process is repeated.
Note that the update of q(r) only involves the interval between r (i)
and r (i+1) neighboring -
r. This interval is split into two subintervals
r] and [-r; r (i+1) ], and the minimum of q(r) is evaluated over both
intervals. In particular, the effort for minimizing q merely consists of
bookkeeping. Figure 2 gives an example of the bounds leading to q(r).
Note that the slopes of q(r) and q(r) may be of opposite sign, so
that in the interior of [r (i) ; r (i+1) ] the function q(r) may not be a good
approximation to q(r). Hence, -
may
be a poor choice. A more reliable choice used in our numerical examples
below is - r := 1
Solving the Sum-of-Ratios Problem 11
slope q 0
arg min q(r)
ffl .

Figure

2. The functions q and q.
To keep the evaluation of q at moderate costs, it suffices to compute
only approximations to q(-r) and ~
along with some error esti-
mates. Interior-point methods are particularly suitable for computing
an approximate solution -
x(r) of the convex problem (4), along with a
certified error bound of the form jq(r) ffl. The
computation of - x(r) takes at most O(log(1=ffl)) iterations provided that
a self-concordant barrier function for S and for the level sets of the
functions f , g, and h is known. This observation is the key point for
our proposed algorithm. Next, we present a statement of the algorithm.
ALGORITHM 4. (Conceptual overall algorithm for
INPUT. Functions f , g, h and a compact convex set S defining the
single-ratio problem (3).
A stopping tolerance ffl ? 0.
Step 0. Determine r (1) and r (2) with
Roland W. Freund and Florian Jarre
If no such value r (1) exists: STOP, the problem violates Assumption
1.
Otherwise, compute q(r (1) ), q(r (2) ), and the Lagrange multipliers
for g.
(number of "support points" r (\Delta) ).
Step 1. Set -
Step 2. Compute q(-r) along with the Lagrange multiplier - g for g.
Step 3. Based on (18), evaluate
arg min
r2[r (i) ;-r]
q(r) and arg min
Step 4. Increase k by one, and insert -
r into the list of r (\Delta) 's.
Step 5. Find
Step 6. If q(~r) - min 1-k q(r (')
~
r is an approximate minimizer.
Otherwise, return to Step 1.
We remark that, in Step 3 of Algorithm 4, the bound q(r) may either
be obtained by setting q i
\Gamma1, or by solving an additional problem
of the form (14). The latter case is more expensive and results in a
better bound for q(r) since both (16) and (18) are used. In most cases
in (18) is "overly large"), it is more efficient to rely on (18)
only, and not to solve (14).
Note that the minimizers of the lower-bound function q(r) computed
in Step 3 of Algorithm 4 can be stored in a heap, so that Step 5 merely
consists of selecting the first element from this heap.
Finally, we remark that, in practice, the feasible set S will usually
be of the form
ae
oe
are given convex functions.
Solving the Sum-of-Ratios Problem 13
3. Minimizing the sum of several fractions
In this section, we return to the general problem (1) of minimizing
the sum of a convex function and p ratios. The basic idea for solving
problem (1) is similar to the special case treated in Section 2.
Assumption 1 be satisfied. In this case,
is a vector of p parameters. In analogy
to the definitions (4) and (5) of x(r) and q(r) in the case
where S(r) :=
ae
oe
and
Initially, we assume that vectors r (1) and r (2) are computed such that
there is a minimizer r   of q satisfying r (1) - r   - r (2) . (As usual, the
-sign is understood component wise.) Each component of r (1) and r (2)
can be computed separately as in the case
Now let r, r (i) , r (i+1) , and some direction \Deltar 2 IR p be given such
that the relations
are satisfied. The bounds (16) and (18) can be generalized to provide
bounds for q(r \Deltar). We split \Deltar
be the Lagrange multipliers for the
constraints (20). By Theorem VII.3.3.2 in (Hiriart-Urruty
and Lemarechal, 1993), a lower bound for q is given by
To obtain a lower bound for q in direction \Deltar + , we define the value
r (i+1)
r (i)
It then follows that
14 Roland W. Freund and Florian Jarre
r (i)
r (i+1)
r (i+1)
r (i)
r (i+1)
r (i+1)
r (i+1)
r (i)
r (i)
r (i+1)
where
r (i+1)
r (i+1)
r (i+1)
r (i)
r (i+1)
Combining the above relations, we get
r (i+1)
This bound is analogous to the one for
In (22), we may replace r (i) by r
and r by (r to obtain the new bound
with
r (i+1)
\Deltar
r (i+1)
r (i+1)
\Deltar
r (i+1)
Solving the Sum-of-Ratios Problem 15
Based on this bound, we can define an anisotropic trust region about
each point r, as long as some lower and some upper limits (like r (i)
and r (i+1) in the previous derivation) are given. The union of the trust
regions about all support points r (i) forms a Voronoi diagram in IR p ,
the vertices of which contain the candidates for the minimizer of the
lower-bound function q(r). For a definition of Voronoi diagrams, their
properties, and algorithms for their numerical computation, we refer
the reader to (Aurenhammer, 1991; Fortune, 1997). As in the case
these candidates for the minimizer of q(r) may not result in the
best choice for inserting a new value -
r somewhere between the known
points r (i) . In addition, the computation of the vertices of the Voronoi
diagram is complicated and expensive. We propose a simpler scheme
based on bounds analogous to (18) where the lower-bound function q(r)
is defined in the box
ae
oe
with given vectors r (i)
j . For r 2 B (i) , we obtain from (21) that
Next, we summarize the resulting overall algorithm.
ALGORITHM 5. (Conceptual overall algorithm for p - 2.)
INPUT. h, and a compact convex
set S defining the multi-ratio problem (1).
A stopping tolerance ffl ? 0.
Step 0. For all
If r (1)
j does not exist for some 1 - j - p: STOP, the problem
violates Assumption 1.
Otherwise, compute q(r (1) ), q(r (2) ), and the Lagrange multipliers
j for the g j 's.
(number of "support points" r (\Delta) ).
containing
arg min q(r)).
Roland W. Freund and Florian Jarre
Step 1. Set
(the index where a split
pays most) and define - r by
r (i)
Step 2. Compute q(-r) along with the Lagrange multiplier - j for each
function g j .
Step 3. Based on (21), evaluate
arg min
l
q(r) and arg min
l
Step 4. Increase k by one, insert - r into the list of r (\Delta) 's splitting B (i)
along the hyperplane r
r l into two boxes (one for - r and
one for r (i) ).
Step 5. Find i - k such that ~ r := arg min r q(r) 2 B (i) .
Step 6. If q(~r) - min 1-k q(r (')
~
r is an approximate minimizer.
Otherwise, return to Step 1.
4. Numerical experiments
Algorithm 4 for minimizing the sum of a convex function and of
convex-concave fraction has been implemented in Matlab. For the solution
of the convex subproblems, we use the interior-point method
described in (Jarre and Saunders, 1995). As we have seen in Figure 1,
the resulting problem (3) may be very complicated, and may have very
many local minimizers. Nevertheless, we anticipate that the parameterization
with respect to r will smooth out many of the local minimizers
of (3) and thus result in a function q that is easier to minimize than
the objective function of the original problem (3).
In this section, we report numerical results of Algorithm 4 applied
to certain examples with random data. In this case, the expectation
that the function q is easier to minimize than the original problem (3)
was fully met. In fact, the function q appeared to be unimodal with
respect to r for these examples.
Solving the Sum-of-Ratios Problem 17
Our test examples are minimization problems of the form (3), where
ae
oe
Here, the matrices H;F;G and are constructed to be
positive semidefinite. Therefore, in (23), the functions h and f are
convex, the function g is concave, and the feasible set S is convex.
The data for (23) is chosen randomly as follows. For each matrix D i , we
first generated a random lower bidiagonal matrix L i the nonzero entries
of which are uniformly distributed in [\Gamma1; 1], and then we computed
i . This guarantees that each D i is a positive semidefinite
tridiagonal matrix. Similarly, H, F , and G are constructed as random
positive semidefinite tridiagonal matrices. In (23), h, f , g, and
are vectors that were also generated randomly. Further-
more, the scalars -, ', fl, and were chosen such that the
interior of the feasible domain S is guaranteed to be nonempty, and
such that the functions f and g are guaranteed not to have a zero
in S. Finally, we have run experiments for problems (23) with values
of n ranging from and values of m ranging from
Note that the constraints in (23) are nonlinear, and
therefore, adaptations of the simplex method for solving problem (3)
with data (23) would be rather complicated.
In

Figure

3, we plot the function q for a typical example (23) with
marks a point r at which the method
has evaluated the function q in order to be able to guarantee that the
final iterate is indeed an approximate global minimizer. Thus, each
stands for the application of an interior-point method to solve a
convex problem of the form (4). Since for each " " the interior-point
method can be "warm-started" using as starting points some convex
combination of almost final iterates of two neighboring problems, the
overall number of interior-point iterations for each " " was less than
eight in the average. The curve q(r) is of course not known, in general.
(Here, it is plotted merely for illustration; its values were determined
by solving a convex problem of the form (4) for some 200 evenly spaced
values of r.)
In

Figure

4, we show a detailed enlargement of the points generated
by Algorithm 4 near the global minimizer of a problem with
20. The plot shows that the distance between support points r
on the right of the minimizer is much smaller than to the left, indicating
that in this particular case, the Lipschitz bound (16) provides a much
Roland W. Freund and Florian Jarre
-5
Value of r
Value
of
Exact function
Points generated by algorithm

Figure

3. The function q(r) for a random example,
more accurate approximation to q(r) than (18). Thus, the algorithm
did not evaluate a further refinement for the points on the left of the
minimizer.
In

Table

I, we report the number of iterations taken by our Matlab
implementation to solve problem (23) with
constraints and different dimensions n. The stopping criterion for these
examples was chosen such that
q(r final
is guaranteed. Here, q(r opt ) is the unknown global optimum of (23). The
numerical results are intended to provide a first rough estimate on the
dependence of our algorithm on the dimension n of the space. We stress
that the numbers of Newton steps and Hessian evaluations in Table I
could be further reduced by a more sophisticated implementation. The
number of Newton steps given in Table I refers to the sum of exact and
inexact Newton steps. For inexact Newton steps, the Hessian matrix of
a previous Newton step has been used in place of the current Hessian
matrix. The overall computational effort is dominated by the number of
Hessian evaluations. The number of r's refers to the number of support
points r at which q(r) was evaluated.
Solving the Sum-of-Ratios Problem 19
Value of r
Value
of
Exact function
Points generated by algorithm

Figure

4. The function q(r) near the global minimum for a random example,

Table

I. Iteration numbers.
# of r's 20 17 14 14
# of IP iterations 407 384 299 326
# of Hessians 644 584 478 548
# of Newton steps 1277 1134 980 1135
The random examples presented above exhibited only one local
minimizer of the function q, as in Figure 3. We therefore constructed
some small problems in three dimensions in such a way that there were
several local minimizers at integer values of r. If two or more of the
local minimizers have nearly the same value q(r), the method refines
about both minimizers until the global minimizer has been identified.
The plot in Figure 5 shows such a "worst-case" behavior where the
method takes a large number of steps before identifying a point near
as an ffl-global minimizer. If the stopping tolerance ffl is decreased
further, then only the bounds near are refined to increase the
accuracy of the global minimizer.
Roland W. Freund and Florian Jarre
50.20.40.60.8Value of r
Value
of
Exact function
Points generated by algorithm

Figure

5. The function q(r) for a case with several local minimia.
It is needless to say that Algorithm 4 does not lend itself to solving
the knapsack problem of Section 2.2. The structure of the knapsack
problem is not exploited by Algorithm 4, and the Lipschitz bounds (16)
and (18) are too weak to provide a sufficiently sharp lower estimate
for the function q for an interval of length more than one. Hence Algorithm
4 is at least as expensive as enumerating all possible integer
solutions. While the knapsack problem represents an example for which
Algorithm 4 is not suitable, we believe that most applications have a
structure more similar to the random problems above for which Algorithm
4 provides a reliable and reasonably fast method for identifying
the global minimum.
5. Conclusions
We considered the sum-of-ratios problem in IR n where the sum of a
convex function and p convex-concave fractions is minimized subject
to convex constraints. We proposed an approach to transform this
problem to the problem of minimizing a suitably defined function q of
variables. The function q can be evaluated by using an interior-point
method for convex minimization. We established Lipschitz bounds for
Solving the Sum-of-Ratios Problem 21
q that can also be evaluated numerically by using an interior-point
method. Based on these bounds, a method was derived to find an
ffl-approximation to the global minimizer of the sum-of-ratios problem.
We presented numerical experiments with the proposed algorithm
for the case of minimizing the sum of a convex function and of
convex-concave fraction. An implementation of the algorithm for the
case will be described elsewhere.

Acknowledgements

We would like to thank Siegfried Schaible for bringing the sum-of-
ratio problem to our attention and for providing us with a copy of
the technical report (Schaible, 1996). The authors are grateful to the
referees and the editor for their constructive comments that helped us
to improve the presentation of the paper.



--R

Voronoi diagrams-a survey of a fundamental geometric data structure
On maximizing a sum of ratios
Information and Optimization Sciences 10:
Programming with linear fractional function- als
Efficient algorithms and implementations for optimizing the sum of linear fractional func- tions
Optimizing the sum of linear fractional func- tions
Voronoi diagrams and Delaunay triangulations
An interior-point method for fractional programs with convex constraints
An interior-point method for multifractional programs with convex constraints
On self-concordant barrier functions for conic hulls and fractional programming
Computers and Intractability: A Guide to the Theory of NP-Completeness

Convex Analysis and Minimization Algorithms I
A practical interior-point method for convex programming
Generalized linear multiplicative and fractional programming
Minimization of the sum and the product of several linear fractional functions over a polytope
On polynomiality of the method of analytic centers for fractional problems

A parametric method for solving certain nonconcave maximization problems
Simultaneous optimization of absolute and relative terms
Fractional programming
Fractional programming with sums of ratios
--TR

--CTR
Takahito Kuno, A Revision of the Trapezoidal Branch-and-Bound Algorithm for Linear Sum-of-Ratios Problems, Journal of Global Optimization, v.33 n.2, p.215-234, October   2005
Yang Dai , Jianming Shi , Shouyang Wang, Conical Partition Algorithm for Maximizing the Sum of dc Ratios, Journal of Global Optimization, v.31 n.2, p.253-270, February  2005
Harold P. Benson, Using concave envelopes to globally solve the nonlinear sum of ratios problem, Journal of Global Optimization, v.22 n.1-4, p.343-364, January 2002
H. P. Benson, Global optimization algorithm for the nonlinearsum of ratios problem, Journal of Optimization Theory and Applications, v.112 n.1, p.1-29, January 2002
convex subproblem;interior-point method;sum of ratios;knapsack problem;cNcP-completeness;fractional programming;global optimum