Componentwise Dinkelbach algorithm for nonlinear fractional optimization problems

1 year ago

Abstract

The paper deals with fractional optimization problems where the objective function (ratio of two functions) is defined on a Cartesian product of two real normed spaces X and Y. Within this framework, we are interested to determine the so-called partial minimizers, i.e. points in $X\times Y$ with the property that any of its variables minimizes the objective function, restricted to this variable, with respect to the other one. While any global minimizer is obviously a partial minimizer, the reverse implication holds true only under additional assumptions (e.g. separability properties of the involved functions). By exploiting the particularities of the objective function, we deliver a Dinkelbach type algorithm for computing partial minimizers of fractional optimization problems. Further assumptions on the involved spaces and functions, such as Lipschitz-type continuity, partial Fr\'{e}chet differentiability, and coercivity, enable us to establish the convergence of our algorithm to a partial minimizer.

Authors

Christian Günther
Institut für Angewandte Mathematik, Leibniz University Hannover, Hannover, Germany

Alexandru Orzan
Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Cluj-Napoca, Romania; Department of Mathematics, Technical University of Cluj-Napoca, Cluj-Napoca, Romania

Radu Precup
Babes-Bolyai University, Cluj-Napoca, Romania &
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy

Keywords

Fractional optimization; Dinkelbach type algorithm; coercive function; partial minimizer

Paper coordinates

C. Günther, Al. Orzan and R. Precup, Componentwise Dinkelbach algorithm for nonlinear fractional optimization problems, Optimization, 73 (2024) no 11, pp. 3323-3337. https://doi.org/10.1080/02331934.2023.2256750

PDF

About this paper

Journal

Optimization
A Journal of Mathematical Programming and Operations Research

Publisher Name

Taylor and Francis

DOI

https://doi.org/10.1080/02331934.2023.2256750

Print ISSN

Online ISSN

google scholar link

Paper (preprint) in HTML form

Componentwise Dinkelbach algorithm for nonlinear fractional optimization problems

Christian Günther^a, Alexandru Orzan^b and Radu Precup^c CONTACT A. Orzan Email: alexandru.orzan@ubbcluj.ro, alexandru.orzan@math.utcluj.ro ^aLeibniz University Hannover, Institut für Angewandte Mathematik, Welfengarten 1, 30167 Hannover, Germany; ^bBabeş-Bolyai University, Faculty of Mathematics and Computer Science, 400084 Cluj-Napoca & Technical University of Cluj-Napoca, Department of Mathematics, 400027 Cluj-Napoca, Romania; ^cBabeş-Bolyai University, Faculty of Mathematics and Computer Science, 400084 Cluj-Napoca & Institute of Advanced Studies In Science and Technology, 400048 Cluj-Napoca & Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, 400110 Cluj-Napoca, Romania.

Abstract

The paper deals with fractional optimization problems where the objective function (ratio of two functions) is defined on a Cartesian product of two real normed spaces $X$ and $Y$ . Within this framework, we are interested to determine the so-called partial minimizers, i.e., points in $X\times Y$ with the property that any of its variables minimizes the objective function, restricted to this variable, with respect to the other one. While any global minimizer is obviously a partial minimizer, the reverse implication holds true only under additional assumptions (e.g. separability properties of the involved functions). By exploiting the particularities of the objective function, we deliver a Dinkelbach type algorithm for computing partial minimizers of fractional optimization problems. Further assumptions on the involved spaces and functions, such as Lipschitz-type continuity, partial Fréchet differentiability, and coercivity, enable us to establish the convergence of our algorithm to a partial minimizer.

Keywords: Fractional optimization; Dinkelbach type algorithm; coercive function; partial minimizer

Mathematics Subject Classification: 90C32; 49M37; 46N10

Dedicated to Professor Wolfgang W. Breckner on the occasion of his 80th anniversary.

1 Introduction and Preliminaries

Fractional optimization problems occur in numerous practical applications where the goal is to optimize a ratio-based performance metric (see, e.g., Shen and Yu [1, 2], Elbenani and Ferland [3] and the references therein). Thus they are important in many fields such as economy, industrial planning, medical planning, social politics and other related domains. Moreover, fractional optimization problems have a wide range of mathematical applications (see, e.g., Frenk and Schaible [4], Göpfert et al. [5], Schaible [6, 8, 7]). Within operator theory, for instance, the problem of eigenvalues and eigenvectors reduces to a fractional minimization problem (see, e.g., Precup [9]). Problems of this type also occur in other domains of mathematics, for example in graph theory and game theory (see Stancu-Minasian [10], Stancu-Minasian and Tigan [11]).

Throughout the entire article, let us consider that $(X,|\cdot|_{X})$ and $(Y,|\cdot|_{Y})$ are two real normed spaces, $D_{1}\subseteq X$ , $D_{2}\subseteq Y$ are nonempty sets and $A,B:D_{1}\times D_{2}\rightarrow\mathbb{R}$ are functions such that $A$ is bounded from below and

0<c\leq B\left(x,y\right)\leq C\ \ \ \text{for all\ \ }\left(x,y\right)\in D_{% 1}\times D_{2}.

The general fractional optimization problem we are interested in is given by

\frac{A\left(x,y\right)}{B\left(x,y\right)}\ \longrightarrow\ \min_{(x,y)\in D% _{1}\times D_{2}}.

(

P

)

In problem $(P)$ , one is usually searching for points $(x^{\ast},y^{\ast})\in D_{1}\times D_{2}$ such that

\frac{A\left(x^{*},y^{*}\right)}{B\left(x^{*},y^{*}\right)}\ =\min_{(x,y)\in D% _{1}\times D_{2}}\frac{A\left(x,y\right)}{B\left(x,y\right)},

which means that $(x^{*},y^{*})$ is a global minimizer. Within this paper, we switch our focus on the problem of finding points $(x^{*},y^{*})\in D_{1}\times D_{2}$ with the property that

	$\displaystyle\frac{A(x^{\ast},y^{\ast})}{B(x^{\ast},y^{\ast})}$	$\displaystyle=\min_{x\in D_{1}}\frac{A(\cdot,y^{\ast})}{B(\cdot,y^{\ast})},$		(1)
	$\displaystyle\frac{A(x^{\ast},y^{\ast})}{B(x^{\ast},y^{\ast})}$	$\displaystyle=\min_{y\in D_{2}}\frac{A(x^{\ast},\cdot\;)\;}{B(x^{\ast},\cdot\;% )}.$		(2)

Points satisfying (1) and (2) are called partial minimizers for problem ( $P$ ).

Remark 1.1.

Obviously, any global minimizer of the functional $\frac{A}{B}$ is also a partial minimizer. However, the converse implication does not generally hold true, as shown by the following example:

A\left(x,y\right)=x^{2}+y^{2}-3xy,\ \ \ B\left(x,y\right)=x^{2}+y^{2}+1\ \text% {\ with}\ \ D_{1}=D_{2}=\left[0,1\right].

It is easy to check that $\left(0,0\right)$ is a partial minimizer but not a global one, since $A\left(1,1\right)/B\left(1,1\right)=-1/3<0=A\left(0,0\right)/B\left(0,0\right)$ .

When dealing with fractional optimization problems, one famous method for computing global minimizers is the Dinkelbach algorithm (see Dinkelbach [12] and the references [13], [14], [15], [16], [17], [18]).

In order to obtain partial minimizers, we use a modified version of the Dinkelbach algorithm, which relies on solving at each iteration step two parametric problems of the following type

	$\displaystyle A(x,y)-\lambda B(x,y)$	$\displaystyle\to\min_{x\in D_{1}},$		( $P_{y}(\lambda)$ )
	$\displaystyle A(x,y)-\lambda B(x,y)$	$\displaystyle\to\min_{y\in D_{2}},$		( $P_{x}(\lambda)$ )

where $\lambda\in\mathbb{R}$ is a parameter. Our algorithmic procedure generates three sequences $(\lambda_{k}),(x_{k})$ and $(y_{k})$ , where $x_{k}$ is a solution of the problem $(P_{y_{k-1}}(\lambda_{k-1}))$ , $y_{k}$ is a solution of $(P_{x_{k}}(\lambda_{k-1}))$ and

\lambda_{k}=\displaystyle{\frac{A(x_{k},y_{k})}{B(x_{k},y_{k})}}.

Under some appropriate conditions on the fractional optimization problem, the convergence of the sequences is ensured and we obtain that the point $(x^{*},y^{*})$ , where $x^{*}$ and $y^{*}$ are the limits of $(x_{k})$ and $(y_{k})$ , is a partial minimizer of $\frac{A}{B}$ , while the limit of $(\lambda_{k})$ equals the value $\displaystyle{\frac{A(x^{*},y^{*})}{B(x^{*},y^{*})}}$ .

The paper is structured as follows: in Section 2 we show some relationships between global minimizers and partial minimizers (Proposition 2.1) and we emphasize the particular case when $A(x,y)$ and $B(x,y)$ have separate variables, showing that in this framework the partial minimum coincides with the global minimum (Proposition 2.2). In Section 3 we first present for comparison the original Dinkelbach algorithm (Algorithm 3.1). Next we give our componentwise version of the algorithm (Algorithm 3.2). The last Section 4 is devoted to the convergence of Algorithm 3.2. The monotony and convergence of the sequence $(\lambda_{k})$ are established by Theorem 4.1, while the convergence of the sequences $(x_{k})$ and $(y_{k})$ is proved by Theorem 4.4. We conclude the paper by an illustrative example.

2 Relationships between global minimizers and partial minimizers

In what follows, we outline the connections between global minimizers, partial minimizers, and critical points.

Proposition 2.1.

Let $X$ and $Y$ be two real normed spaces and $f:X\times Y\to\mathbb{R}$ a function. Then:

$1^{\circ}$

Any global minimizer of $f$ is a partial minimizer, but the converse implication is not generally true, even in the case when the function is convex.
$2^{\circ}$

If $f$ is a $C^{1}$ Fréchet differentiable function, then any partial minimizer is a critical point.
$3^{\circ}$

If $f$ is convex, then $\left(x,y\right)$ is a global minimizer if and only if the origin belongs to the subdifferential of $f$ at $\left(x,y\right),$ i.e., $0\in\partial f\left(x,y\right).$ In particular, if $f$ is convex and $C^{1}$ Fréchet differentiable, then any partial minimizer is a global minimizer.

Proof.

The first part of assertion $1^{\circ}$ is straightforward. In order to show the second part, one can simply take the function $f:\mathbb{R}^{2}\rightarrow\mathbb{R}$ , $f(x,y)=2|x-y|-y$ . By some quick computations using the definition, it can be deduced that $f$ is convex. Additionally, one can easily check that the point $(0,0)$ is a partial minimizer. However, $f$ does not have a global minimum, since it is not bounded from below ( $f(x,x)=-x\rightarrow-\infty$ as $x\rightarrow+\infty$ ).

For assertion $2^{\circ}$ , recall that for the product space $X\times Y$ , the Fréchet derivative of $f$ at the point $(x,y)$ is in fact the couple of partial derivatives $(f_{x}(x,y),f_{y}(x,y))$ . Assume now that $(x^{\ast},y^{\ast})$ is a partial minimizer for $f$ . Then we have that

	$\displaystyle f(x^{\ast},y^{\ast})$	$\displaystyle\leq$	$\displaystyle f(x,y^{\ast}),\;\mbox{for all $x\in X$}$
	$\displaystyle f(x^{\ast},y^{\ast})$	$\displaystyle\leq$	$\displaystyle f(x^{\ast},y),\;\mbox{for all $y\in Y$.}$

Thus $x^{\ast}$ is a minimum point for the function $f(\cdot,y^{\ast})$ , whereas $y^{\ast}$ is a minimum point for the function $f(x^{\ast},\cdot)$ . Hence, from the infinite dimensional version of Fermat’s theorem and taking into account that $f$ is Fréchet differentiable, one has that $f_{x}(x^{\ast},y^{\ast})=0,\ f_{y}(x^{\ast},y^{\ast})=0$ . Therefore $(x^{\ast},y^{\ast})$ is indeed a critical point of $f$ .

The first part of assertion $3^{\circ}$ is very popular in convex optimization (see, e.g., [19, p. 91] for infinite dimensional spaces and [20, Theorem 3.2.10] for the finite dimensional case). The last assertion is now a simple consequence of $2^{\circ}.$ ∎

The next result comes as a sufficient condition under which the partial minimizer points are global minimizers, for a fractional function $\displaystyle{\frac{A}{B}}$ .

Proposition 2.2.

If $A,B:D_{1}\times D_{2}\to\mathbb{R}$ have separate variables in the sense that

A\left(x,y\right)=A_{1}\left(x\right)+A_{2}\left(y\right),\ \ \ B\left(x,y% \right)=B_{1}\left(x\right)+B_{2}\left(y\right)

then any partial minimizer is a global minimizer of the ratio $A\left(x,y\right)/B\left(x,y\right)$ .

Proof.

Indeed, if $(x^{*},y^{*})$ is a partial minimizer, we have that

\frac{A_{1}(x^{*})+A_{2}(y^{*})}{B_{1}(x^{*})+B_{2}(y^{*})}\leq\frac{A_{1}(x)+% A_{2}(y^{*})}{B_{1}(x)+B_{2}(y^{*})}\ \ \ \text{for all\ \ }x\in D_{1}

(3)

and

\frac{A_{1}(x^{*})+A_{2}(y^{*})}{B_{1}(x^{*})+B_{2}(y^{*})}\leq\frac{A_{1}(x^{% *})+A_{2}(y)}{B_{1}(x^{*})+B_{2}(y)}\ \ \ \text{for all\ \ }y\in D_{2}.

(4)

After a few computations we have that relation (3) is equivalent to

		$\displaystyle A_{1}(x^{})B_{1}(x)+A_{1}(x^{})B_{2}(y^{})+A_{2}(y^{})B_{1}(x)$
	$\displaystyle\leq\;$	$\displaystyle A_{1}(x)B_{1}(x^{})+A_{1}(x)B_{2}(y^{})+A_{2}(y^{})B_{1}(x^{% }).$

In a similar way, we arrive to the fact that relation (4) is equivalent to

		$\displaystyle A_{1}(x^{})B_{2}(y)+A_{2}(y^{})B_{1}(x^{})+A_{2}(y^{})B_{2}(% y^{*})$
	$\displaystyle\leq\;$	$\displaystyle A_{1}(x^{})B_{2}(y^{})+A_{2}(y)B_{1}(x^{})+A_{2}(y)B_{2}(y^{% }).$

By adding the last two relations and removing the similar terms, we obtain that

		$\displaystyle A_{1}(x^{})B_{1}(x)+A_{2}(y^{})B_{1}(x)+A_{1}(x^{})B_{2}(y)+A% _{2}(y^{})B_{2}(y^{*})$
	$\displaystyle\leq\;$	$\displaystyle A_{1}(x)B_{1}(x^{})+A_{1}(x)B_{2}(y^{})+A_{2}(y)B_{1}(x^{})+A% _{2}(y)B_{2}(y^{})$

which leads to

\frac{A_{1}(x^{*})+A_{2}(y^{*})}{B_{1}(x^{*})+B_{2}(y^{*})}\leq\frac{A_{1}(x)+% A_{2}(y)}{B_{1}(x)+B_{2}(y)}\ \ \ \text{for all\ \ }(x,y)\in D_{1}\times D_{2}.

∎

3 Dinkelbach type algorithms

In this section we are going to state the componentwise Dinkelbach algorithm for calculating partial minimizers of fractional optimization problems. We start by recalling the original Dinkelbach algorithm applied to objective functions $\displaystyle{\frac{A}{B}}$ , depending of two variables, with the aim to have a better understanding of our componentwise algorithm that follows.

Algorithm 3.1 (Dinkelbach’s algorithm).

Step $0$ (initialization)

Take any point $(x_{0},y_{0})\in D_{1}\times D_{2},$ calculate

\lambda_{0}:={\frac{A\left(x_{0},y_{0}\right)}{B\left(x_{0},y_{0}\right)}\ }

and set $k=1.$

Step $k$ (cycle step for $k\geq 1)$

Find a point $(x_{k},y_{k})\in D_{1}\times D_{2}$ such that

A\left(x_{k},y_{k}\right)-\lambda_{k-1}B\left(x_{k},y_{k}\right)=\min_{D_{1}% \times D_{2}}\left(A-\lambda_{k-1}B\right),

calculate

\lambda_{k}=\frac{A\left(x_{k},y_{k}\right)}{B\left(x_{k},y_{k}\right)}

and perform Step $k+1.$

Remark 3.1.

It is known that, under certain assumptions on the objective function, both sequences $(x_{k})$ and $(y_{k})$ generated by the Dinkelbach algorithm are convergent to $x^{*}$ and $y^{*}$ , and the point $(x^{*},y^{*})$ is a global minimizer of $A/B$ on $D_{1}\times D_{2}$ (see Dinkelbach [12]).

We are going to give now our modified version of the Dinkelbach algorithm for computing partial minimizers of fractional optimization problems.

Algorithm 3.2 (Componentwise Dinkelbach algorithm).

Step $0$ (initialization)

Take any point $(x_{0},y_{0})\in D_{1}\times D_{2},$ calculate

\lambda_{0}:={\frac{A\left(x_{0},y_{0}\right)}{B\left(x_{0},y_{0}\right)}\ }

and set $k=1.$

Step $k$ (cycle step)

Find a point $x_{k}\in D_{1}$ such that

\min_{x\in D_{1}}\left[A(\cdot,y_{k-1})-\lambda_{k-1}B(\cdot,y_{k-1})\right]=A% (x_{k},y_{k-1})-\lambda_{k-1}B(x_{k},y_{k-1}),

(5)

then find $\ y_{k}\in D_{2}$ such that

\min_{y\in D_{2}}\left[A(x_{k},\cdot)-\lambda_{k-1}B(x_{k},\cdot)\right]=A(x_{% k},y_{k})-\lambda_{k-1}B(x_{k},y_{k}),

(6)

next calculate

\lambda_{k}:=\frac{A(x_{k},y_{k})}{B(x_{k},y_{k})}

(7)

and perform Step $\ k+1.$

Remark 3.2.

Our componentwise algorithm (Algorithm 3.2) for computing partial minimizers of fractional optimization problems combines ideas of the original Dinkelbach method (Algorithm 3.1) and the so-called alternating direction method (see, e.g., Boţ and Csetnek [21], Boţ, Dao and Li [22], Boyd et al. [23], Geissler et al. [24], Goldstein et al. [25], Kleinert and Schmidt [26]). However, one has to notice that compared to the alternating direction method, in our approach the objective function $A-\lambda_{k-1}B$ keeps on changing at every iteration due to the sequence $(\lambda_{k})$ .

In the particular case when partial minimizers coincide with global minimizers (see Section 2), the componentwise algorithm will give an alternative to the original Dinkelbach procedure (Algorithm 3.1) for computing global minimizers.

In view of Proposition 2.2, for the case when the functions $A$ and $B$ have separate variables, our componentwise algorithm requires at each step $k$ to separately solve the minimization problems

	$\displaystyle A_{1}\left(.\right)-\lambda_{k-1}B_{1}\left(.\right)\$	$\displaystyle\rightarrow$	$\displaystyle\ \min_{D_{1}}\ \ \ \ \text{for obtaining \ }x_{k}$
	$\displaystyle A_{2}\left(.\right)-\lambda_{k-1}B_{2}\left(.\right)\$	$\displaystyle\rightarrow$	$\displaystyle\ \min_{D_{2}}\ \ \ \ \text{for obtaining \ }y_{k}$

instead of the global minimization problem

A-\lambda_{k-1}B\ \rightarrow\ \min_{D_{1}\times D_{2}}\ \ \text{for obtaining \ }\left(x_{k},y_{k}\right)

required by the original Dinkelbach algorithm.

Remark 3.3.

We prescribe the implementation of Algorithm 3.2 along with other well-known fractional programming techniques. Notably, Boţ and Csetnek [21] introduced modifications of the Dinkelbach algorithm for certain classes of fractional programming problems. Instead of completely solving the scalarized problems in each iteration, these modifications take only one iterative step of a numerical method. This approach has been further developed in [22]. Furthermore, Algorithm 3.2 could also be adapted following the approach presented in the paper Orzan and Precup [15]. This adaptation would involve replacing the exact solutions of the minimization problems at each iterative step with approximate solutions, introducing a predefined error tolerance in the process.

Remark 3.4.

It is worth noticing that the most problematic step when applying the algorithm is solving the minimization problems given by (5) and (6). Certainly, from an efficiency perspective, these problems should be easier to solve than the original fractional problem. In many cases this can be guaranteed if we consider the following frameworks:

•

Convex-Concave Fractional Programs: Assume that $D_{1}$ , $D_{2}$ are convex sets, $A$ is nonnegative and convex with respect to (w.r.t.) each variable and $B$ is concave w.r.t. each variable. Then the minimization problems at hand turn into classical convex problems.
•

Convex-Convex Fractional Programs: Consider that $D_{1}$ , $D_{2}$ are convex sets, $A$ is nonnegative and convex w.r.t. each variable and $B$ is also convex w.r.t. each variable. Then the objective functions involved in the minimization problems mentioned above are differences of convex functions. Such problems are known in the literature as DC optimization problems and can be solved by using specific techniques (see, e.g., Hiriart-Urruty [27], Le Thi and Pham [28, 29], de Oliveira [30], Singer [31, Chapter 8], Toland [32]).

Our last Remark provides some conditions under which the structure of the minimization problems involved in the algorithm is more simple to deal with. The following Proposition states existence results for the solutions of problems (5) and (6). Some other conditions of generalized convexity type (see, e.g., Breckner and Kassay [33]) might also be considered.

Proposition 3.1.

The minimization problems given by (5) and (6) have solutions if any of the following conditions is fulfilled:

(a)

$D_{1}$ , $D_{2}$ are compact sets, $A$ is is lower semicontinuous (l.s.c.) in each variable and $B$ is continuous in each variable.
(b)

$D_{1}=X$ and $D_{2}=Y$ are finite-dimensional normed spaces, $A$ is l.s.c. in each variable, coercive in $x$ (i.e., $\lim_{|x|_{X}\to\infty}A(x,y)=\infty$ for every $y\in Y$ ), coercive in $y$ (i.e., $\lim_{|y|_{Y}\to\infty}A(x,y)=\infty$ for every $x\in X$ ) and $B$ is continuous in each variable.
(c)

$D_{1}=X$ , $D_{2}=Y$ are reflexive Banach spaces, $A$ is both l.s.c. and convex in each variable, coercive in $x$ , coercive in $y$ and nonnegative, whereas $B$ is both upper semicontinuous and concave in each variable.

Proof.

For $(a)$ the result follows by the classical Weierstrass theorem. $(b)$ follows easily by our assumptions, taking into account the compactness of the unit ball and the Weierstrass theorem. $(c)$ follows by Zălinescu [34, Theorem 2.5.1]. ∎

4 Convergence of the componentwise Dinkelbach algorithm

In this section, we present the results concerning the convergence of the sequences $(\lambda_{k}),(x_{k}),(y_{k})$ given by our Algorithm 3.2.

Theorem 4.1.

The sequence $\left(\lambda_{k}\right)$ given by Algorithm 3.2 is nonincreasing and convergent to a real number $\lambda^{*}$ .

Proof.

Let $k\geq 1$ . The inequality $\lambda_{k}\leq\lambda_{k-1}$ is equivalent to $\displaystyle{\frac{A(x_{k},y_{k})}{B(x_{k},y_{k})}}\leq\lambda_{k-1}$ and since $B$ is positive, to the inequality

A(x_{k},y_{k})-\lambda_{k-1}B(x_{k},y_{k})\leq 0

that we have to prove. Using the definition of the point $y_{k}$ , we have

A(x_{k},y_{k})-\lambda_{k-1}B(x_{k},y_{k})\leq A(x_{k},y_{k-1})-\lambda_{k-1}B% (x_{k},y_{k-1}).

By doing the same thing for $x_{k}$ we obtain

A(x_{k},y_{k-1})-\lambda_{k-1}B(x_{k},y_{k-1})\leq A(x_{k-1},y_{k-1})-\lambda_% {k-1}B(x_{k-1},y_{k-1})=0.

These two inequalities imply the desired result. Thus $\left(\lambda_{k}\right)$ is nonincreasing and since it is also bounded from below, it converges to some $\lambda^{\ast}.$ ∎

Theorem 4.2.

Assume that $D_{1},D_{2}$ are closed subsets of the normed spaces $X$ and $Y,$ respectively, the operators $A$ and $B$ are continuous, and

x_{k}\rightarrow x^{\ast},\ \ \ \ \ y_{k}\rightarrow y^{\ast}.

(8)

Then the following assertions hold true:

(a)

One has

$\lambda^{\ast}={\frac{A(x^{\ast},y^{\ast})}{B(x^{\ast},y^{\ast})}.}$
(b)

Denoting

$m_{k,1}:=A(x_{k},y_{k-1})-\lambda_{k-1}B(x_{k},y_{k-1}),\ \ \ m_{k,2}:=A(x_{k}% ,y_{k})-\lambda_{k-1}B(x_{k},y_{k}),$

one has

$\lim_{k\rightarrow\infty}m_{k,1}=\lim_{k\rightarrow\infty}m_{k,2}=0.$
(c)

$(x^{\ast},y^{\ast})$ is a partial minimizer on $D_{1}\times D_{2}$ of $A\left(x,y\right)/B\left(x,y\right).$

Proof.

Conclusions (a) and (b) follow from (7). To prove (c) we start from

m_{k,1}\leq A(x,y_{k-1})-\lambda_{k-1}B(x,y_{k-1})

for every $x\in D_{1}.$ By letting $k$ go to infinity, we obtain that

0\leq A(x,y^{\ast})-\lambda^{\ast}B(x,y^{\ast})

which is equivalent to $\ \lambda^{\ast}\leq{\frac{A(x,y^{*})}{B(x,y^{*})}}$ ( $x\in D_{1}$ ). Similarly, for any $y\in D_{2}$ one has

m_{k,2}\leq A(x_{k},y)-\lambda_{k-1}B(x_{k},y),

whence since $\ m_{k,2}\rightarrow 0$ we get

0\leq A(x^{\ast},y)-\lambda^{\ast}B(x^{\ast},y),

that is $\ \lambda^{\ast}\leq{\frac{A(x^{\ast},y)}{B(x^{\ast},y)}}$ ( $y\in D_{2}$ ). Hence we conclude that $(x^{\ast},y^{\ast})$ is a partial minimizer. ∎

In our way to ensure that condition (8) takes place, we first proceed to guarantee the boundedness of one of the sequences $(x_{k})$ and $(y_{k})$ . To this aim, we are going to assume that $D_{1}=X$ , $D_{2}=Y$ are entire normed spaces and the following hypothesis holds true:

(H1): The functional $A(x,y)$ is coercive in $x$ uniformly w.r.t. $y,$ i.e., for any $M>0$ , there is $l_{M}>0$ such that $A(x,y)\geq M$ for $\left|x\right|_{X}\geq l_{M}$ and all $y\in Y.$

Remark 4.1.

One can easily prove that if functional $A$ is coercive in $x$ uniformly w.r.t. $y$ , then it is also coercive in $x$ (as defined by $(b)$ in Proposition 3.1). The converse, however, is not generally true (take $A(x,y)=x^{2}-y^{2}$ and consider the points from the first bisector to reach the contradiction).

Proposition 4.3.

Under assumption (H1), the sequence $\left(x_{k}\right)$ is bounded.

Proof.

Since $(\lambda_{k})$ and the operator $B$ are bounded, there exists $M>0$ such that

A(x_{k},y_{k})\leq M\text{ \ for all }k.

(9)

Consequently, if we suppose that the sequence $(x_{k})$ is unbounded, then by the coercivity condition (H1), we can find some unbounded subsequence $(x_{k_{p}})$ of $(x_{k})$ and arrive to a contradiction with (9). ∎

In the following part of the section we proceed with the essential step of ensuring the convergence of the sequences $(x_{k}),(y_{k})$ , which will conclude the convergence of our Algorithm 3.2. In order to achieve this, we consider that $X$ and $Y$ are Hilbert spaces, $D_{1}=X$ , $D_{2}=Y$ and $A$ , $B$ are $C^{1}$ functionals with their partial (Fréchet) derivatives (see, e.g., Precup [35]) satisfying some Lipschitz continuity or monotonicity conditions related to their derivatives.

We denote by $A_{x}^{\prime},A_{y}^{\prime},B_{x}^{\prime}$ and $B_{y}^{\prime}$ the partial Fréchet derivatives of $A$ and $B$ , and we assume that

(H2): The derivatives $B_{x}^{\prime}$ and $B_{y}^{\prime}$ are bounded on $X\times Y.$

Now we define the operators

	$\displaystyle N_{11}(x,y)$	$\displaystyle:=c_{1}x-A_{x}^{\prime}(x,y),$	$\displaystyle N_{12}(x,y)$	$\displaystyle:=c_{1}y-A_{y}^{\prime}(x,y),$
	$\displaystyle N_{21}(x,y)$	$\displaystyle:=c_{2}x-B_{x}^{\prime}(x,y),$	$\displaystyle N_{22}(x,y)$	$\displaystyle:=c_{2}y-B_{y}^{\prime}(x,y),$

where

c_{1}\geq\max\{1,\lambda_{0}\}+\lambda_{0}c_{2}\quad\mbox{and}\quad c_{2}>0.

(10)

Furthermore we also assume that

(H3) There exist some positive constants $a_{ij},b_{ij}\in\mathbb{R}$ , $i,j\in\{1,2\}$ , such that

$\displaystyle\left\|N_{11}(x,y)-N_{11}(\bar{x},\bar{y})\right\|_{X}$	$\displaystyle\leq$	$\displaystyle a_{11}\|x-\bar{x}\|_{X}+a_{12}\|y-\bar{y}\|_{Y},$
$\displaystyle\left\|N_{12}(x,y)-N_{12}(\bar{x},\bar{y})\right\|_{Y}$	$\displaystyle\leq$	$\displaystyle a_{21}\|x-\bar{x}\|_{X}+a_{22}\|y-\bar{y}\|_{Y},$
$\displaystyle\left\|N_{21}(x,y)-N_{21}(\bar{x},\bar{y})\right\|_{X}$	$\displaystyle\leq$	$\displaystyle b_{11}\|x-\bar{x}\|_{X}+b_{12}\|y-\bar{y}\|_{Y},$
$\displaystyle\left\|N_{22}(x,y)-N_{22}(\bar{x},\bar{y})\right\|_{Y}$	$\displaystyle\leq$	$\displaystyle b_{21}\|x-\bar{x}\|_{X}+b_{22}\|y-\bar{y}\|_{Y}$

for all $x,\bar{x}\in X$ and $y,\bar{y}\in Y.$

We denote

	$\displaystyle c_{11}$	$\displaystyle:=a_{11}+b_{11},\;c_{12}:=a_{12}+b_{12},\;c_{21}:=a_{21}+b_{21},% \;c_{22}:=a_{22}+b_{22},$
	$\displaystyle a$	$\displaystyle:={\frac{c_{12}c_{21}}{(1-c_{11})(1-c_{22})}}$

and we assume that

(H4) $c_{11}<1,\ c_{22}<1$ and $a<1.$

We now present a sufficient condition for the convergence of the sequences $(x_{k})$ and $(y_{k})$ , reminiscent of Banach’s fixed point theorem.

Theorem 4.4.

Under the assumptions (H1)-(H4), the sequences $\left(x_{k}\right)$ and $\left(y_{k}\right)$ are convergent.

Proof.

By the definition of $x_{k}$ and Fermat’s theorem we have that

A_{x}^{\prime}(x_{k},y_{k-1})-\lambda_{k-1}B_{x}^{\prime}(x_{k},y_{k-1})=0

hence

A_{x}^{\prime}(x_{k},y_{k-1})-\lambda^{\ast}B_{x}^{\prime}(x_{k},y_{k-1})+% \alpha_{k}=0

(11)

where $\ \alpha_{k}=(\lambda^{\ast}-\lambda_{k-1})B_{x}^{\prime}(x_{k},y_{k-1})$ . In a similar manner we obtain for $y_{k}$ that

A_{y}^{\prime}(x_{k},y_{k})-\lambda^{\ast}B_{y}^{\prime}(x_{k},y_{k})+\beta_{k% }=0

(12)

where $\ \beta_{k}=(\lambda^{\ast}-\lambda_{k-1})B_{y}^{\prime}(x_{k},y_{k})$ . We note that in virtue of (H2), the sequences $(\alpha_{k})$ and $(\beta_{k})$ are convergent to zero. From relation (11) we obtain that

c_{1}x_{k}-N_{11}(x_{k},y_{k-1})-\lambda^{\ast}c_{2}x_{k}+\lambda^{\ast}N_{21}% (x_{k},y_{k-1})+\alpha_{k}=0

which is equivalent to

(c_{1}-\lambda^{\ast}c_{2})x_{k}=N_{11}(x_{k},y_{k-1})-\lambda^{\ast}N_{21}(x_% {k},y_{k-1})-\alpha_{k}.

(13)

Taking $k+p$ in the role of $k$ in formula (13) we infer that

(c_{1}-\lambda^{\ast}c_{2})x_{k+p}=N_{11}(x_{k+p},y_{k+p-1})-\lambda^{\ast}N_{% 21}(x_{k+p},y_{k+p-1})-\alpha_{k+p}.

(14)

From the hypothesis (H3) and by combining relations (13) and (14), we have that

	$\displaystyle\|c_{1}-\lambda^{\ast}c_{2}\|\left\|x_{k+p}-x_{k}\right\|_{X}$	$\displaystyle\leq a_{11}\|x_{k+p}-x_{k}\|_{X}+a_{12}\|y_{k+p-1}-y_{k-1}\|_{Y}$
		$\displaystyle+\;\lambda^{\ast}b_{11}\|x_{k+p}-x_{k}\|_{X}+\lambda^{\ast}b_{12}\|y% _{k+p-1}-y_{k-1}\|_{Y}$
		$\displaystyle+\|\alpha_{k+p}-\alpha_{k}\|_{X}.$

Since $c_{1}>\lambda_{0}c_{2},$ $\lambda_{0}\geq\lambda^{\ast}$ and $c_{2}>0,$ one has $c_{1}>\lambda^{\ast}c_{2}$ and so

	$\displaystyle\|x_{k+p}-x_{k}\|_{X}$	$\displaystyle\leq\frac{a_{11}}{c_{1}-\lambda^{\ast}c_{2}}\|x_{k+p}-x_{k}\|_{X}+% \frac{a_{12}}{c_{1}-\lambda^{\ast}c_{2}}\|y_{k+p-1}-y_{k-1}\|_{Y}\;$
		$\displaystyle+\;\frac{\lambda^{\ast}b_{11}}{c_{1}-\lambda^{\ast}c_{2}}\|x_{k+p}% -x_{k}\|_{X}+\frac{\lambda^{\ast}b_{12}}{c_{1}-\lambda^{\ast}c_{2}}\|y_{k+p-1}-y% _{k-1}\|_{Y}$
		$\displaystyle+\frac{1}{c_{1}-\lambda^{\ast}c_{2}}\|\alpha_{k+p}-\alpha_{k}\|_{X}.$

Taking into account the assumptions imposed on $c_{1}$ and $c_{2}$ in (10), we obtain that $c_{1}\geq\max\left\{1,\lambda_{0}\right\}+\lambda_{0}c_{2}\geq\left(1+c_{2}% \right)\lambda_{0},$ which leads to $\ \ {\frac{\lambda^{\ast}}{c_{1}-\lambda^{\ast}c_{2}}}\leq\frac{\lambda_{0}}{c% _{1}-\lambda_{0}c_{2}},$ and consequently we infer that $\ {\frac{\lambda^{\ast}}{c_{1}-\lambda^{\ast}c_{2}}}\leq 1$ . In addition, since $c_{1}\geq 1+\lambda_{0}c_{2}\geq 1+\lambda^{\ast}c_{2}$ , it follows that ${\frac{1}{c_{1}-\lambda^{\ast}c_{2}}}\leq 1.$ Hence

|x_{k+p}-x_{k}|_{X}\leq(a_{11}+b_{11})|x_{k+p}-x_{k}|_{X}+(a_{12}+b_{12})|y_{k% +p-1}-y_{k-1}|_{Y}+|\alpha_{k+p}-\alpha_{k}|_{X}.

(15)

By making use of relation (12), it can be deduced in a similar manner that

	$\displaystyle\|c_{1}-\lambda^{\ast}c_{2}\|\left\|y_{k+p}-y_{k}\right\|_{Y}$	$\displaystyle\leq a_{21}\|x_{k+p}-x_{k}\|_{X}+a_{22}\|y_{k+p}-y_{k}\|_{Y}$
		$\displaystyle+\;\lambda^{\ast}b_{21}\|x_{k+p}-x_{k}\|_{X}+\lambda^{\ast}b_{22}\|y% _{k+p}-y_{k}\|_{Y}$
		$\displaystyle+\|\beta_{k+p}-\beta_{k}\|_{Y},$

and based on (10), we obtain that

\left|y_{k+p}-y_{k}\right|_{Y}\leq(a_{21}+b_{21})|x_{k+p}-x_{k}|_{X}+(a_{22}+b% _{22})|y_{k+p}-y_{k}|_{Y}+|\beta_{k+p}-\beta_{k}|_{Y}.

(16)

Consequently, relations (15) and (16) become

	$\displaystyle(1-c_{11})\left\|x_{k+p}-x_{k}\right\|_{X}$	$\displaystyle\leq$	$\displaystyle c_{12}\|y_{k+p-1}-y_{k-1}\|_{Y}+\|\alpha_{k+p}-\alpha_{k}\|_{X},$
	$\displaystyle(1-c_{22})\left\|y_{k+p}-y_{k}\right\|_{Y}$	$\displaystyle\leq$	$\displaystyle c_{21}\|x_{k+p}-x_{k}\|_{X}+\|\beta_{k+p}-\beta_{k}\|_{Y}.$

Hence, due to (H4), we arrive to

\left|x_{k+p}-x_{k}\right|_{X}\leq\frac{c_{12}}{1-c_{11}}|y_{k+p-1}-y_{k-1}|_{% Y}+\frac{1}{1-c_{11}}|\alpha_{k+p}-\alpha_{k}|_{X}

(17)

and

\left|y_{k+p}-y_{k}\right|_{Y}\leq\frac{c_{21}}{1-c_{22}}|x_{k+p}-x_{k}|_{X}+% \frac{1}{1-c_{22}}|\beta_{k+p}-\beta_{k}|_{Y}.

(18)

Using relation (18) with $k-1$ in the role of $k$ , we obtain that

\left|y_{k+p-1}-y_{k-1}\right|_{Y}\leq\frac{c_{21}}{1-c_{22}}|x_{k+p-1}-x_{k-1% }|_{X}+\frac{1}{1-c_{22}}|\beta_{k+p-1}-\beta_{k-1}|_{Y}.

(19)

By combining relations (17) and (19) we are led to

	$\displaystyle\left\|x_{k+p}-x_{k}\right\|_{X}$	$\displaystyle\leq\frac{c_{12}c_{21}}{(1-c_{11})(1-c_{22})}\|x_{k+p-1}-x_{k-1}\|_% {X}$
		$\displaystyle+\frac{c_{12}}{(1-c_{11})(1-c_{22})}\|\beta_{k+p-1}-\beta_{k-1}\|_{% Y}+\frac{1}{1-c_{11}}\|\alpha_{k+p}-\alpha_{k}\|_{X}.$

Consequently, denoting

\gamma_{k,p}:=|x_{k+p}-x_{k}|_{X},\;\ b_{k,p}:=\frac{c_{12}}{(1-c_{11})(1-c_{2% 2})}|\beta_{k+p-1}-\beta_{k-1}|_{Y}+\frac{1}{1-c_{11}}|\alpha_{k+p}-\alpha_{k}% |_{X},

one can rewrite the last inequality as

\gamma_{k,p}\leq a\gamma_{k-1,p}+b_{k,p}.

By making use of [36, Lemma 3.2] and assumption (H4), we obtain that $\gamma_{k,p}\rightarrow 0$ as $k\rightarrow\infty$ uniformly in $p$ , hence $(x_{k})$ is a Cauchy sequence, therefore convergent. Taking into account relation (18), we obtain that $(y_{k})$ is also convergent and the conclusion follows. ∎

Remark 4.2.

Taking into account Theorem 4.2, under the assumptions of Theorem 4.4, if $x^{*}$ and $y^{*}$ are the limits of the sequences $(x_{k})$ and $(y_{k})$ given by the componentwise Dinkelbach algorithm, then $(x^{*},y^{*})$ is a partial minimizer for $A(x,y)/B(x,y)$ .

We are now going to put our results to the test by providing a simple example.

Example 4.5.

Let $X=Y=\mathbb{R}$ , $\theta_{1},\theta_{2}>0$ and $A,B:\mathbb{R}^{2}\rightarrow\mathbb{R}$ given by

A(x,y)=(x+1)^{2}+y^{2}-1\quad\mbox{and}\quad B(x,y)=1+\theta_{1}\frac{x^{2}}{1% +x^{2}}+\theta_{2}\frac{y^{2}}{1+y^{2}}.

One can easily check that $A$ and $B$ satisfy condition (b) from Proposition 3.1, hence the existence of the sequences $(x_{k})$ and $(y_{k})$ is ensured. We start with $\lambda_{0}=\frac{A(0,0)}{B(0,0)}=0.$ Assumptions $(H1),(H2)$ can be verified real quick. After some simple computations, we have that

	$\displaystyle N_{11}(x,y)$	$\displaystyle=(c_{1}-2)x-2,$	$\displaystyle N_{12}(x,y)$	$\displaystyle=(c_{1}-2)y,$
	$\displaystyle N_{21}(x,y)$	$\displaystyle=c_{2}x-\theta_{1}\frac{2x}{(1+x^{2})^{2}},$	$\displaystyle N_{22}(x,y)$	$\displaystyle=c_{2}y-\theta_{2}\frac{2y}{(1+y^{2})^{2}},$

where the constants $c_{1},c_{2}$ must satisfy $\ c_{1}\geq 1$ and $\ c_{2}>0.$ Thus we have

$\displaystyle\left\|N_{11}(x,y)-N_{11}(\bar{x},\bar{y})\right\|$	$\displaystyle\leq$	$\displaystyle\|c_{1}-2\|\|x-\bar{x}\|,$
$\displaystyle\left\|N_{12}(x,y)-N_{12}(\bar{x},\bar{y})\right\|$	$\displaystyle\leq$	$\displaystyle\|c_{1}-2\|\|y-\bar{y}\|,$
$\displaystyle\left\|N_{21}(x,y)-N_{21}(\bar{x},\bar{y})\right\|$	$\displaystyle\leq$	$\displaystyle(c_{2}+2\theta_{1})\|x-\bar{x}\|,$
$\displaystyle\left\|N_{22}(x,y)-N_{22}(\bar{x},\bar{y})\right\|$	$\displaystyle\leq$	$\displaystyle(c_{2}+2\theta_{2})\|y-\bar{y}\|$

for all $x,\bar{x},y,\bar{y}\in\mathbb{R}$ , hence assumption $(H3)$ is also valid. Consequently we have that

\displaystyle c_{11}

\displaystyle=|c_{1}-2|+c_{2}+2\theta_{1},

\displaystyle c_{12}

\displaystyle=0,

\displaystyle c_{21}

\displaystyle=0,

\displaystyle c_{22}

\displaystyle=|c_{1}-2|+c_{2}+2\theta_{2},

\displaystyle a

\displaystyle=0.

If we choose $\ c_{1}=2$ , $c_{2}=\theta_{1}=\theta_{2}=\frac{1}{4}$ , then $(H4)$ is also satisfied and according to Remark 4.2 there exists $(x^{*},y^{*})$ which is a partial minimizer for $A(x,y)/B(x,y)$ . Notice that the functions $A$ and $B$ mentioned above have separate variables and, as a consequence, we obtain, via Proposition 2.2, that the point $(x^{*},y^{*})$ is also a global minimizer.

Acknowledgement

The authors are very grateful to the anonymous referees for their valuable comments that helped us improve the manuscript.

References

[1] Shen K, Yu W. Fractional programming for communication systems–Part I: Power control and beamforming. IEEE Transactions on Signal Processing 2018;66(10):2616–2630.
[2] Shen K, Yu W. Fractional programming for communication systems–Part II: Uplink scheduling via matching. IEEE Transactions on Signal Processing 2018;66(10):2631–2644.
[3] Elbenani B, Ferland JA. Cell formation problem solved exactly with the Dinkelbach algorithm. Report CIRRELT-2012-07, University of Montreal. 2012.
[4] Frenk JBG, Schaible S. Fractional programming. In: Hadjisavvas N, Komlósi S, Schaible S, editors. Handbook of generalized convexity and generalized monotonicity. New York (NY): Springer; 2005. p. 335–386.
[5] Göpfert A, Riahi H, Tammer C, et al. Variational methods in partially ordered spaces. New York (NY): Springer; 2006.
[6] Schaible S. A survey of fractional programming. In: Schaible S, Ziemba WT, editors. Generalized concavity in optimization and economics. New York (NY): Academic Press; 1981. p. 417-440.
[7] Schaible S. Bibliography in fractional programming. Math. Methods Oper. Res. 1982;26:211–241.
[8] Schaible S, Shi J. Fractional programming: The sum-of-ratios case. Optim. Methods Softw. 2003;18:219–229.
[9] Precup R. Linear and semilinear partial differential equations. Berlin (BE): De Gruyter; 2013.
[10] Stancu-Minasian IM. Fractional programming. Theory, methods and applications. Dordrecht (NL): Kluwer; 1997.
[11] Stancu-Minasian IM, Tigan S. Continuous time linear-fractional programming. The minimum-risk approach. RAIRO Oper. Res. 2000;34:397–409.
[12] Dinkelbach W. On nonlinear fractional programming. Manage. Sci. 1967;13:492–498.
[13] Crouzeix JP, Ferland JA. Algorithms for generalized fractional programming. Math. Program. 1991;52:191–207.
[14] Crouzeix JP, Ferland JA, Nguyen VH. Revisiting Dinkelbach-type algorithms for generalized fractional programs. OPSEARCH. 2008;45:97–110.
[15] Orzan A, Precup R. Dinkelbach type approximation algorithms for nonlinear fractional optimization problems. Numerical Functional Analysis and Optimization. 2023; 44(9):954–969. DOI: 10.1080/01630563.2023.2217893
[16] Ródenas RG, López ML, Verastegui D. Extensions of Dinkelbach’s algorithm for solving non-linear fractional programming problems. Top 1999;7:33–70.
[17] Shi J. A combined algorithm for fractional programming. Ann. Oper. Res. 2001;103:135–147.
[18] Tammer K, Tammer C, Ohlendorf E. Multicriterial fractional optimization, Berlin (BE): Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik; 2005.
[19] Barbu V, Precupanu T. Convexity and optimization in Banach spaces. Alphen aan de Rijn (NL): Sijthoff and Noordhoff; 1978.
[20] Cambini A, Martein L. Generalized convexity and optimization: Theory and applications. Berlin (DE): Springer-Verlag; 2009.
[21] Boţ RI, Csetnek ER. Proximal-gradient algorithms for fractional programming. Optimization. 2017;66(8):1383–1396.
[22] Boţ RI, Dao MN, Li G. Extrapolated proximal subgradient algorithms for nonconvex and nonsmooth fractional programs. Mathematics of Operations Research. 2021;47(3):2415–2443.
[23] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 2011; 3(1):1–122.
[24] Geissler B, Morsi A, Schewe L, et al. Penalty alternating direction methods for mixed-integer optimization: A new view on feasibility pumps. SIAM J. Optim. 2017;27(3):1611–1636.
[25] Goldstein T, O’Donoghue B, Setzer S, Baraniuk R. Fast alternating direction optimization methods. SIAM J. Imaging Sci. 2014;7(3):1588–1623.
[26] Kleinert T, Schmidt M. Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS J. Comput. 2021;33(1):198–215.
[27] Hiriart-Urruty JB. Generalized differentiability / duality and optimization for problems dealing with differences of convex functions. In: Ponstein J, editors. Convexity and duality in optimization. Lecture notes in economics and mathematical systems, vol 256. Berlin, Heidelberg (DE): Springer; 1985. p. 37–70.
[28] Le Thi HA, Pham DT. The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Annals of Operations Research. 2005;133:23–46.
[29] Le Thi HA, Pham DT. Open issues and recent advances in DC programming and DCA. Journal of Global Optimization. 2023. https://doi.org/10.1007/s10898-023-01272-1.
[30] de Oliveira W. The ABC of DC programming. Set-Valued and Variational Analysis. 2020;28:679–706.
[31] Singer I. Duality for nonconvex approximation and optimization. New York (NY): Springer; 2006.
[32] Toland JF. A duality principle for non-convex optimisation and the calculus of variations. Arch. Rational Mech. Anal. 1979;71:41–61.
[33] Breckner WW, Kassay G. A systematization of convexity concepts for sets and functions. J. Convex Anal. 1997;4:109–127.
[34] Zălinescu C. Convex analysis in general vector spaces. Singapore (SG): World Scientific Publising; 2002.
[35] Precup R. Methods in nonlinear integral equations. Dordrecht (DR): Springer; 2002.
[36] Precup R. Nash-type equilibria and periodic solutions to nonvariational systems. Adv. Nonlinear Anal. 2014;3:197–207.

[1] Shen K, Yu W. Fractional programming for communication systems–part I: power control and beamforming. IEEE Trans Signal Process. 2018;66(10):2616–2630. doi: 10.1109/TSP.2018.2812733 [Crossref] [Web of Science ®], [Google Scholar]
[2] Shen K, Yu W. Fractional programming for communication systems–part II: uplink scheduling via matching. IEEE Trans Signal Process. 2018;66(10):2631–2644. doi: 10.1109/TSP.2018.2812748 [Crossref] [Web of Science ®], [Google Scholar]
[3] Elbenani B, Ferland JA. Cell formation problem solved exactly with the Dinkelbach algorithm. University of Montreal; 2012. (Report CIRRELT-2012-07). [Google Scholar]
[4] Frenk JBG, Schaible S. Fractional programming. In: Hadjisavvas N, Komlósi S, Schaible S, editors. Handbook of generalized convexity and generalized monotonicity. New York (NY): Springer; 2005. p. 335–386. [Crossref], [Google Scholar]
[5] Göpfert A, Riahi H, Tammer C, et al. Variational methods in partially ordered spaces. New York (NY): Springer; 2006. [Google Scholar]
[6] Schaible S. A survey of fractional programming. In: Schaible S, Ziemba WT, editors. Generalized concavity in optimization and economics. New York (NY): Academic Press; 1981. p. 417–440. [Google Scholar]
[7] Schaible S. Bibliography in fractional programming. Math Methods Oper Res. 1982;26(1):211–241. doi: 10.1007/BF01917115 [Crossref], [Google Scholar]
[8] Schaible S, Shi J. Fractional programming: the sum-of-ratios case. Optim Methods Softw. 2003;18(2):219–229. doi: 10.1080/1055678031000105242 [Taylor & Francis Online] [Web of Science ®], [Google Scholar]
[9] Precup R. Linear and semilinear partial differential equations. Berlin (BE): De Gruyter; 2013. [Google Scholar]
[10] Stancu-Minasian IM. Fractional programming: theory, methods and applications. Dordrecht (NL): Kluwer; 1997. [Crossref], [Google Scholar]
[11] Stancu-Minasian IM, Tigan S. Continuous time linear-fractional programming. the minimum-risk approach. RAIRO Oper Res. 2000;34(4):397–409. doi: 10.1051/ro:2000121 [Crossref] [Web of Science ®], [Google Scholar]
[12] Dinkelbach W. On nonlinear fractional programming. Manage Sci. 1967;13(7):492–498. doi: 10.1287/mnsc.13.7.492 [Crossref], [Google Scholar]
[13] Crouzeix JP, Ferland JA. Algorithms for generalized fractional programming. Math Program. 1991;52(1-3):191–207. doi: 10.1007/BF01582887 [Crossref], [Google Scholar]
[14] Crouzeix JP, Ferland JA, Nguyen VH. Revisiting Dinkelbach-type algorithms for generalized fractional programs. OPSEARCH. 2008;45(2):97–110. doi: 10.1007/BF03398807 [Crossref], [Google Scholar]
[15] Orzan A, Precup R. Dinkelbach type approximation algorithms for nonlinear fractional optimization problems. Numer Funct Anal Optim. 2023;44(9):954–969. doi: 10.1080/01630563.2023.2217893 [Taylor & Francis Online] [Web of Science ®], [Google Scholar]
[16] Ródenas RG, López ML, Verastegui D. Extensions of Dinkelbach’s algorithm for solving non-linear fractional programming problems. Top. 1999;7(1):33–70. doi: 10.1007/BF02564711 [Crossref], [Google Scholar]
[17] Shi J. A combined algorithm for fractional programming. Ann Oper Res. 2001;103(1/4):135–147. doi: 10.1023/A:1012998904482 [Crossref], [Google Scholar]
[18] Tammer K, Tammer C, Ohlendorf E. Multicriterial fractional optimization. Berlin (BE): Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik; 2005. [Google Scholar]
[19] Barbu V, Precupanu T. Convexity and optimization in Banach spaces. Alphen aan de Rijn (NL): Sijthoff and Noordhoff; 1978. [Google Scholar]
[20] Cambini A, Martein L. Generalized convexity and optimization: theory and applications. Berlin (DE): Springer-Verlag; 2009. [Google Scholar]
[21] Boţ RI, Csetnek ER. Proximal-gradient algorithms for fractional programming. Optimization. 2017;66(8):1383–1396. doi: 10.1080/02331934.2017.1294592 [Taylor & Francis Online] [PubMed] [Web of Science ®], [Google Scholar]
[22] Boţ RI, Dao MN, Li G. Extrapolated proximal subgradient algorithms for nonconvex and nonsmooth fractional programs. Math Oper Res. 2021;47(3):2415–2443. [Crossref], [Google Scholar]
[23] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn. 2010;3(1):1–122. doi: 10.1561/2200000016 [Crossref], [Google Scholar]
[24] Geissler B, Morsi A, Schewe L, et al. Penalty alternating direction methods for mixed-integer optimization: a new view on feasibility pumps. SIAM J Optim. 2017;27(3):1611–1636. doi: 10.1137/16M1069687 [Crossref] [Web of Science ®], [Google Scholar]
[25] Goldstein T, O’Donoghue B, Setzer S, et al. Fast alternating direction optimization methods. SIAM J Imaging Sci. 2014;7(3):1588–1623. doi: 10.1137/120896219 [Crossref] [Web of Science ®], [Google Scholar]
[26] Kleinert T, Schmidt M. Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS J Comput. 2021;33(1):198–215. doi: 10.1287/ijoc.2019.0945 [Crossref] [Web of Science ®], [Google Scholar]
[27] Hiriart-Urruty JB. Generalized differentiability / duality and optimization for problems dealing with differences of convex functions. In: Ponstein J, editor. Convexity and duality in optimization. Lecture notes in economics and mathematical systems, vol. 256. Berlin, Heidelberg (DE): Springer; 1985. p. 37–70. [Crossref], [Google Scholar]
[28] Le Thi HA, Pham DT. The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann Oper Res. 2005;133(1-4):23–46. doi: 10.1007/s10479-004-5022-1 [Crossref] [Web of Science ®], [Google Scholar]
[29] Le Thi HA, Pham DT. Open issues and recent advances in DC programming and DCA. J Glob Optim. 2023. doi: 10.1007/s10898-023-01272-1 [Crossref] [Web of Science ®], [Google Scholar]
[30] de Oliveira W. The ABC of DC programming. Set-Valued Var Anal. 2020;28(4):679–706. doi: 10.1007/s11228-020-00566-w [Crossref] [Web of Science ®], [Google Scholar]
[31] Singer I. Duality for nonconvex approximation and optimization. New York (NY): Springer; 2006. [Crossref], [Google Scholar]
[32] Toland JF. A duality principle for non-convex optimisation and the calculus of variations. Arch Rational Mech Anal. 1979;71(1):41–61. doi: 10.1007/BF00250669 [Crossref] [Web of Science ®], [Google Scholar]
[33] Breckner WW, Kassay G. A systematization of convexity concepts for sets and functions. J Convex Anal. 1997;4:109–127. [Google Scholar]
[34] Zălinescu C. Convex analysis in general vector spaces. Singapore (SG): World Scientific Publising; 2002. [Crossref], [Google Scholar]
[35] Precup R. Methods in nonlinear integral equations. Dordrecht (DR): Springer; 2002. [Crossref], [Google Scholar]
[36] Precup R. Nash-type equilibria and periodic solutions to nonvariational systems. Adv Nonlinear Anal. 2014;3:197–207. doi: 10.1515/anona-2014-0006 [Crossref] [Web of Science ®], [Google Scholar]

2023

Linking Methods for Componentwise Variational Systems

October 23, 2023

Professor Doctor Ion Păvăloiu has passed away at the age of 84

August 2, 2023

Nonlinear alternatives of hybrid type for nonself vector-valued maps and application

May 23, 2023

$\displaystyle\left\|N_{11}(x,y)-N_{11}(\bar{x},\bar{y})\right\|_{X}$	$\displaystyle\leq$	$\displaystyle a_{11}\|x-\bar{x}\|_{X}+a_{12}\|y-\bar{y}\|_{Y},$
$\displaystyle\left\|N_{12}(x,y)-N_{12}(\bar{x},\bar{y})\right\|_{Y}$	$\displaystyle\leq$	$\displaystyle a_{21}\|x-\bar{x}\|_{X}+a_{22}\|y-\bar{y}\|_{Y},$
$\displaystyle\left\|N_{21}(x,y)-N_{21}(\bar{x},\bar{y})\right\|_{X}$	$\displaystyle\leq$	$\displaystyle b_{11}\|x-\bar{x}\|_{X}+b_{12}\|y-\bar{y}\|_{Y},$
$\displaystyle\left\|N_{22}(x,y)-N_{22}(\bar{x},\bar{y})\right\|_{Y}$	$\displaystyle\leq$	$\displaystyle b_{21}\|x-\bar{x}\|_{X}+b_{22}\|y-\bar{y}\|_{Y}$

	$\displaystyle\|c_{1}-\lambda^{\ast}c_{2}\|\left\|x_{k+p}-x_{k}\right\|_{X}$	$\displaystyle\leq a_{11}\|x_{k+p}-x_{k}\|_{X}+a_{12}\|y_{k+p-1}-y_{k-1}\|_{Y}$
		$\displaystyle+\;\lambda^{\ast}b_{11}\|x_{k+p}-x_{k}\|_{X}+\lambda^{\ast}b_{12}\|y% _{k+p-1}-y_{k-1}\|_{Y}$
		$\displaystyle+\|\alpha_{k+p}-\alpha_{k}\|_{X}.$

	$\displaystyle\|x_{k+p}-x_{k}\|_{X}$	$\displaystyle\leq\frac{a_{11}}{c_{1}-\lambda^{\ast}c_{2}}\|x_{k+p}-x_{k}\|_{X}+% \frac{a_{12}}{c_{1}-\lambda^{\ast}c_{2}}\|y_{k+p-1}-y_{k-1}\|_{Y}\;$
		$\displaystyle+\;\frac{\lambda^{\ast}b_{11}}{c_{1}-\lambda^{\ast}c_{2}}\|x_{k+p}% -x_{k}\|_{X}+\frac{\lambda^{\ast}b_{12}}{c_{1}-\lambda^{\ast}c_{2}}\|y_{k+p-1}-y% _{k-1}\|_{Y}$
		$\displaystyle+\frac{1}{c_{1}-\lambda^{\ast}c_{2}}\|\alpha_{k+p}-\alpha_{k}\|_{X}.$

	$\displaystyle\|c_{1}-\lambda^{\ast}c_{2}\|\left\|y_{k+p}-y_{k}\right\|_{Y}$	$\displaystyle\leq a_{21}\|x_{k+p}-x_{k}\|_{X}+a_{22}\|y_{k+p}-y_{k}\|_{Y}$
		$\displaystyle+\;\lambda^{\ast}b_{21}\|x_{k+p}-x_{k}\|_{X}+\lambda^{\ast}b_{22}\|y% _{k+p}-y_{k}\|_{Y}$
		$\displaystyle+\|\beta_{k+p}-\beta_{k}\|_{Y},$

	$\displaystyle(1-c_{11})\left\|x_{k+p}-x_{k}\right\|_{X}$	$\displaystyle\leq$	$\displaystyle c_{12}\|y_{k+p-1}-y_{k-1}\|_{Y}+\|\alpha_{k+p}-\alpha_{k}\|_{X},$
	$\displaystyle(1-c_{22})\left\|y_{k+p}-y_{k}\right\|_{Y}$	$\displaystyle\leq$	$\displaystyle c_{21}\|x_{k+p}-x_{k}\|_{X}+\|\beta_{k+p}-\beta_{k}\|_{Y}.$

Componentwise Dinkelbach algorithm for nonlinear fractional optimization problems

Abstract

Authors

Keywords

Paper coordinates

PDF

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

Paper (preprint) in HTML form

Componentwise Dinkelbach algorithm for nonlinear fractional optimization problems

Abstract

1 Introduction and Preliminaries

Remark 1.1.

2 Relationships between global minimizers and partial minimizers

Proposition 2.1.

Proof.

Proposition 2.2.

Proof.

3 Dinkelbach type algorithms

Algorithm 3.1 (Dinkelbach’s algorithm).

Remark 3.1.

Algorithm 3.2 (Componentwise Dinkelbach algorithm).

Remark 3.2.

Remark 3.3.

Remark 3.4.

Proposition 3.1.

Proof.

4 Convergence of the componentwise Dinkelbach algorithm

Theorem 4.1.

Proof.

Theorem 4.2.

Proof.

Remark 4.1.

Proposition 4.3.

Proof.

Theorem 4.4.

Proof.

Remark 4.2.

Example 4.5.

Acknowledgement

References

References

Related Posts