Dinkelbach Type Approximation Algorithms for Nonlinear Fractional Optimization Problems

1 year ago

(original), ISI/JCR, Nonlinear analysis, optimization, paper

Abstract

In this paper we establish some approximation versions of the classical Dinkelbach algorithm for nonlinear fractional optimization problems in Banach spaces. We start by examining what occurs if at any step of the algorithm, the generated point desired to be a minimizer can only be determined with a given error. Next we assume that the step error tends to zero as the algorithm advances. The last version of the algorithm we present is making use of Ekeland’s variational principle for generating the sequence of minimizer-like points. In the final part of the article we deliver some results in order to achieve a Palais-Smale type compactness condition that guarantees the convergence of our Dinkelbach-Ekeland algorithm.

Authors

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

Radu Precup
Faculty of Mathematics and Computer Science and Institute of Advanced Studies in Science and Technology, Babes–Bolyai University, Cluj-Napoca, Romania;
Tiberiu Popoviciu Institute ofNumerical Analysis, Romanian Academy, Cluj-Napoca, Romania

Keywords

Dinkelbach algorithm; Ekeland principle; fractional optimization; Palais-Smale condition.

Paper coordinates

A. Orzan, R. Precup, Dinkelbach type approximation algorithms for nonlinear fractional optimization problems, Numerical Functional Analysis and Optimization, 44 (2023) no. 9, pp. 954–969. https://doi.org/10.1080/01630563.2023.2217893

PDF

https://www.tandfonline.com/doi/pdf/10.1080/01630563.2023.2217893

About this paper

Journal

Numerical Functional Analysis and Optimization

Publisher Name

Taylor and Francis Ltd.

DOI

https://doi.org/10.1080/01630563.2023.2217893

Print ISSN

Online ISSN

google scholar link

Paper (preprint) in HTML form

Dinkelbach type approximation algorithms for nonlinear fractional optimization problems

Alexandru Orzan, Radu Precup A. Orzan, Faculty of Mathematics and Computer Science, Babeş–Bolyai University, 400084 Cluj-Napoca, Romania & Technical University of Cluj-Napoca
Department of Mathematics, Cluj-Napoca 400027, Romania alexandru.orzan@ubbcluj.ro, alexandru.orzan@math.utcluj.ro R. Precup, Faculty of Mathematics and Computer Science and Institute of Advanced Studies in Science and Technology, Babeş–Bolyai University, 400084 Cluj-Napoca, Romania & Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, P.O. Box 68-1, 400110 Cluj-Napoca, Romania r.precup@math.ubbcluj.ro

Abstract.

Key words and phrases:

Fractional optimization, Dinkelbach algorithm, Ekeland principle, Palais-Smale condition

1991 Mathematics Subject Classification:

65K10, 49M37, 90C30

1. Introduction

Fractional optimization problems arise in the modeling of many real-world processes, while the objective is to optimize a certain indicator expressed as a ratio. Examples can be given from financial and corporate planning, production planning, health care and hospital planning, social project development etc. (see, e.g., [1, 4, 9, 19] and the references therein). Examples of fractional optimization problems can also be identified in mathematics. For instance, the problem of eigenvalues and eigenvectors of a positive-definite auto-adjoint operator $L$ returns to the minimization of the ratio

\frac{\left(Lx,x\right)}{\left|x\right|^{2}},\ \ \ x\neq 0.

The minimal value is the first eigenvalue and the minimum point is a corresponding eigenvector (see, e.g., [12, Section 3.11]). Other examples come from graph theory and game theory (see [19]). On more research papers on this subjects, we refer the reader to the following titles [5, 10, 15, 16] and also to some of more recent work in this field [2, 3, 6, 14, 17, 18, 21].

The general form of a fractional problem reads as follows

\frac{A\left(x\right)}{B\left(x\right)}\ \longrightarrow\ \min_{x\in D}\text{,}

where $A$ and $B$ a two given functionals defined on a set $D$ and $B\left(x\right)\neq 0$ for all $x\in D.$ Solving the problem means to obtain a pair $\left(\lambda^{\ast},x^{\ast}\right),$ where $\lambda^{\ast}$ is the minimal value of $A/B$ and $x^{\ast}$ is a minimum point, i.e.,

\lambda^{\ast}=\frac{A\left(x^{\ast}\right)}{B\left(x^{\ast}\right)}=\min_{D}% \frac{A}{B}.

Beside the direct minimization methods, there are known some specific techniques which reduce the problem to an optimization one concerning a non-ratio functional. Such a technique was introduced by Dinkelbach [7] and is based on the parametric optimization problem

A\left(x\right)-\lambda B\left(x\right)\ \longrightarrow\ \min_{x\in D}.

It consists in generating a sequence $\left(\lambda_{k}\right)$ of values of the parameter which ultimately gives the minimum of ratio $A/B,$ and an accompanying sequence $\left(x_{k}\right)$ which at limit gives a desired minimum point. At each step $k,$ $\lambda_{k-1}$ being found, it is assume that the functional $A-\lambda_{k-1}B$ reaches its infimum at some point $x_{k}.$ This is the aspect that limits the applicability of the method, otherwise useful under general conditions on the nonlinear functionals $A$ and $\ B.$

This paper focuses exactly on this issue. Our first aim is to adapt Dinkelbach’s algorithm to the case where at each step, we only consider an $\varepsilon$ -approximation of the minimum point. It is proved that the modified algorithm converges to an approximation solution $\left(\widetilde{\lambda},\widetilde{x}\right)$ with $\varepsilon$ -dependent accuracy. Under some topological assumptions on $D,$ $A,$ $B$ and a compactness condition, it is shown that the functional $A/B$ achieves the value $\widetilde{\lambda}.$ Next we prove that if the error $\varepsilon_{k}$ accepted at any step decreases to zero, then the algorithm converges to $\left(\lambda^{\ast},\widetilde{x}\right),$ where $\lambda^{\ast}$ is the infimum of $A/B$ which is reached under the compactness assumption. Our third aim is to give sufficient conditions for the compactness assumption. Here Ekeland’s variational principle proves to be useful for a more special choice of the $x_{k}$ -point which would make it possible to involve a Palais-Smale (PS) type compactness condition. Achieving the (PS) condition is also discussed.

2. Preliminaries

For informing the reader and for comparison with the results that will be presented in the next section, we recall Dinkelbach’s algorithm and the main stages of the proof of its convergence.

Let $D$ be a nonempty arbitrary set, $A:D\rightarrow\mathbb{R}$ bounded from bellow and $B:D\rightarrow\mathbb{R}$ with

0<c\leq B\left(x\right)\leq C\ \ \ \text{for all\ \ }x\in D.

The problem is to find $\lambda^{\ast},$ the minimum on $D$ of the ration $A/B,$ and $x^{\ast},$ a point in $D$ at which $\lambda^{\ast}$ is reached.

Algorithm 2.1 (Dinkelbach’s algorithm).

Step $0$ (initialization):

Take any point $x_{0}\in D,$ calculate $\lambda_{0}=\frac{A\left(x_{0}\right)}{B\left(x_{0}\right)}$ and set $k=1.$

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

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

A\left(x_{k}\right)-\lambda_{k-1}B\left(x_{k}\right)=m_{k}:=\min_{D}\left(A-% \lambda_{k-1}B\right),

calculate

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

and perform Step $k+1.$

Theorem 2.2.

Dinkelbach’s algorithm is convergent and if $\lambda^{\ast}=\lim\lambda_{k}$ and $x^{\ast}\in D$ is such that

A\left(x^{\ast}\right)-\lambda^{\ast}B\left(x^{\ast}\right)=\min_{D}\left(A-% \lambda^{\ast}B\right),

then

(2.1)

\lambda^{\ast}=\frac{A\left(x^{\ast}\right)}{B\left(x^{\ast}\right)}=\min_{D}% \frac{A}{B}.

Proof.

(a) The sequence $\left(\lambda_{k}\right)$ is decreasing. Indeed the inequality $\lambda_{k}\leq\lambda_{k-1}$ is equivalent with $A\left(x_{k}\right)-\lambda_{k-1}B\left(x_{k}\right)\leq 0$ which is true since

A\left(x_{k}\right)-\lambda_{k-1}B\left(x_{k}\right)=m_{k}\leq A\left(x_{k-1}% \right)-\lambda_{k-1}B\left(x_{k-1}\right)=0.

In addition the boundedness conditions on $A$ and $B$ guarantee that $\left(\lambda_{k}\right)$ is bounded. Hence it has a finite limit $\lambda^{\ast}.$

(b) Since $\left(\lambda_{k}\right)$ is decreasing and $B$ is positive it follows that the sequence $\left(m_{k}\right)$ is increasing. In addition, it is bounded from above by $0$ as follows from

m_{k}=\min_{D}\left(A-\lambda_{k-1}B\right)\leq A\left(x_{k-1}\right)-\lambda_% {k-1}B\left(x_{k-1}\right)=0.

Hence $\left(m_{k}\right)$ has a limit. Next from

	$\displaystyle 0$	$\displaystyle=$	$\displaystyle A\left(x_{k}\right)-\lambda_{k}B\left(x_{k}\right)=A\left(x_{k}% \right)-\lambda_{k-1}B\left(x_{k}\right)+\left(\lambda_{k-1}-\lambda_{k}\right% )B\left(x_{k}\right)$
		$\displaystyle=$	$\displaystyle m_{k}+\left(\lambda_{k-1}-\lambda_{k}\right)B\left(x_{k}\right)$

passing to limit gives $\ m_{k}\rightarrow 0.$

$\displaystyle A\left(x^{\ast}\right)-\lambda^{\ast}B\left(x^{\ast}\right)$	$\displaystyle\leq$	$\displaystyle A\left(x_{k}\right)-\lambda^{\ast}B\left(x_{k}\right)$
	$\displaystyle=$	$\displaystyle A\left(x_{k}\right)-\lambda_{k}B\left(x_{k}\right)+\left(\lambda% _{k}-\lambda^{\ast}\right)B\left(x_{k}\right)$
	$\displaystyle=$	$\displaystyle\left(\lambda_{k}-\lambda^{\ast}\right)B\left(x_{k}\right)% \rightarrow 0.$

(d) Next it is shown that $\lambda^{\ast}=\inf_{D}\frac{A}{B}.$ From (c), one has $\lambda^{\ast}\geq\inf_{D}\frac{A}{B}.$ Assume however that the strict inequality holds. Then for some $\varepsilon>0,$ $\lambda^{\ast}-\varepsilon>\inf_{D}\frac{A}{B}$ and consequently there exists an $\overline{x}\in D$ with $\lambda^{\ast}-\varepsilon\geq\frac{A\left(\overline{x}\right)}{B\left(% \overline{x}\right)}.$ One has

$\displaystyle 0$	$\displaystyle\geq$	$\displaystyle A\left(\overline{x}\right)-\left(\lambda^{\ast}-\varepsilon% \right)B\left(\overline{x}\right)$
	$\displaystyle=$	$\displaystyle A\left(\overline{x}\right)-\lambda_{k-1}B\left(\overline{x}% \right)+\left(\lambda_{k-1}-\lambda^{\ast}\right)B\left(\overline{x}\right)+% \varepsilon B\left(\overline{x}\right)$
	$\displaystyle\geq$	$\displaystyle m_{k}+\left(\lambda_{k-1}-\lambda^{\ast}\right)B\left(\overline{% x}\right)+\varepsilon B\left(\overline{x}\right),$

whence passing to limit, using the conclusion in (b), gives the false result $0\geq\varepsilon B\left(\overline{x}\right).$ Therefore the equality holds.

(e) Now (c) and (d) lead to (2.1).

Notice that the above algorithm and theorem do not involve any structuring of the set $D .$ However, the general version of Dinkelbach’s algorithm is based on the assumption that the minimization problem for $A-\lambda B$ has a solution for every $\lambda\in\left[\lambda_{-1},\lambda_{0}\right],$ where $\lambda_{-1}=\inf_{D}\left(A/B\right).$ In this way the minimization problem is transferred from $A/B$ to the $A-\lambda B,$ for which it is assumed that there are simpler methods of solving, as is the case where $A$ and $B$ are affine or convex/concave functions.

We conclude this Preliminaries section by recalling the Ekeland variational principle and some of its consequences (see, e.g., [8, 11]), which, as stated in the Introduction, will prove to be of great importance for our work. We also recall the Palais-Smale (compactness) condition, denoted for simplicity by (PS).

Theorem 2.3 (Ekeland).

Let $(X,d)$ be a complete metric space and let $E:X\rightarrow\mathbb{R}$ be a lower semicontinuous function bounded from below. Then given $\varepsilon>0$ and $u_{0}\in X$ , there exists a point $u\in X$ such that

E(u)\leq E(v)+\varepsilon d(u,v)\;\;\;\ \text{for\ all}\;v\in X

and

E(u)\leq E(u_{0})-\varepsilon d(u,u_{0}).

Corollary 2.4.

Let $(X,|\cdot|)$ be a Banach space and $E:X\rightarrow\mathbb{R}$ a $C^{1}$ functional bounded from below. Then for every $\varepsilon>0,$ there exists an element $u\in X$ such that

E(u)\leq\inf_{X}E+\varepsilon,\ \ \ \left|E^{\prime}\left(u\right)\right|\leq\varepsilon

A $C^{1}$ functional $E$ defined on a Banach space is said to satisfy the (PS) condition if any sequence $(x_{k})$ with

E(x_{k})\rightarrow c\ \ \left(c\in\mathbb{R}\right)\;\;\;\text{and}\;\;\;E^{% \prime}(x_{k})\rightarrow 0

has a convergent subsequence.

Theorem 2.5.

Let $(X,|\cdot|)$ be a Banach space and $E:X\rightarrow\mathbb{R}$ be a $C^{1}$ functional bounded from below that satisfies the (PS) condition. Then there exists a point $x^{\ast}\in X$ with

E(x^{\ast})=\inf_{X}E\;\;\;\text{and}\;\;\;E^{\prime}\left(x^{\ast}\right)=0.

3. Approximation Dinkelbach algorithms

Dinkelbach’s algorithm requires that at each step $k,$ an exact minimum point can be obtained. However this requirement is almost impossible to fulfill. In what follows we investigate the impact of approximation errors over the iterative algorithm which follows similar steps to those from Dinkelbach’s procedure.

3.1. Dinkelbach algorithm with a fixed error

Let the conditions of Dinkelbach’s algorithm hold and let $\varepsilon>0$ be fixed. Assuming that at any step of the algorithm, the point $x_{k}$ desired to be a point of minimum can only be determined with an error of at most $\varepsilon.$ Thus Dinkelbach’s algorithm is modified as follows:

Algorithm 3.1 (Dinkelbach algorithm with a fixed error).

Step $0$ (initialization):

Take any point $x_{0}\in D,$ calculate $\lambda_{0}=\frac{A\left(x_{0}\right)}{B\left(x_{0}\right)}$ and set $k=1.$

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

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

(3.1)

A\left(x_{k}\right)-\lambda_{k-1}B\left(x_{k}\right)\leq\inf_{D}\left(A-% \lambda_{k-1}B\right)+\varepsilon,

calculate

\lambda_{k}=\min\left\{\frac{A\left(x_{k}\right)}{B\left(x_{k}\right)},\ % \lambda_{k-1}\right\}

and perform Step $k+1.$

Theorem 3.2.

If $\ \widetilde{\lambda}=\lim\lambda_{k}$ and $\ \widetilde{x}\in D$ is such that

A\left(\widetilde{x}\right)-\widetilde{\lambda}B\left(\widetilde{x}\right)\leq% \inf_{D}\left(A-\widetilde{\lambda}B\right)+\varepsilon,

then

(3.2)

\inf_{D}\frac{A}{B}\leq\widetilde{\lambda}\leq\inf_{D}\frac{A}{B}+\frac{% \varepsilon}{c}

and

(3.3)

\widetilde{\lambda}-\frac{\varepsilon}{c}\leq\frac{A\left(\widetilde{x}\right)% }{B\left(\widetilde{x}\right)}\leq\widetilde{\lambda}+\frac{\varepsilon}{c}.

Proof.

From definition, the sequence $\left(\lambda_{k}\right)$ is decreasing and since $A/B$ is bounded from below, it is also bounded. Hence it has a finite limit $\widetilde{\lambda}.$ Since any $\lambda_{k}$ is a value at some point of $A/B,$ one has $\lambda_{k}\geq\inf A/B$ and then

(3.4)

\widetilde{\lambda}\geq\inf_{D}\frac{A}{B}.

Now we prove that

(3.5)

\widetilde{\lambda}\leq\inf_{D}\frac{A}{B}+\frac{\varepsilon}{c}.

Assuming the contrary we can find $\delta>0$ and $\overline{x}\in D$ with

\widetilde{\lambda}-\delta\geq\frac{A\left(\overline{x}\right)}{B\left(% \overline{x}\right)}+\frac{\varepsilon}{c}.

Hence

$\displaystyle 0$	$\displaystyle\geq$	$\displaystyle A\left(\overline{x}\right)-\left(\widetilde{\lambda}-\delta-% \frac{\varepsilon}{c}\right)B\left(\overline{x}\right)$
	$\displaystyle=$	$\displaystyle A\left(\overline{x}\right)-\lambda_{k-1}B\left(\overline{x}% \right)+\left(\lambda_{k-1}-\widetilde{\lambda}\right)B\left(\overline{x}% \right)+\left(\delta+\frac{\varepsilon}{c}\right)B\left(\overline{x}\right)$
	$\displaystyle\geq$	$\displaystyle\inf_{D}\left(A-\lambda_{k-1}B\right)+\left(\lambda_{k-1}-% \widetilde{\lambda}\right)B\left(\overline{x}\right)+\left(\delta+\frac{% \varepsilon}{c}\right)B\left(\overline{x}\right)$
	$\displaystyle\geq$	$\displaystyle A\left(x_{k}\right)-\lambda_{k-1}B\left(x_{k}\right)-\varepsilon% +\left(\lambda_{k-1}-\widetilde{\lambda}\right)B\left(\overline{x}\right)+% \left(\delta+\frac{\varepsilon}{c}\right)B\left(\overline{x}\right).$

Here

A\left(x_{k}\right)-\lambda_{k-1}B\left(x_{k}\right)=\left(\frac{A\left(x_{k}% \right)}{B\left(x_{k}\right)}-\lambda_{k-1}\right)B\left(x_{k}\right)\geq\left% (\lambda_{k}-\lambda_{k-1}\right)C.

Consequently

0\geq\left(\lambda_{k}-\lambda_{k-1}\right)C-\varepsilon+\left(\lambda_{k-1}-% \widetilde{\lambda}\right)B\left(\overline{x}\right)+\left(\delta+\frac{% \varepsilon}{c}\right)B\left(\overline{x}\right).

Letting $k$ go to infinity gives

0\geq-\varepsilon+\left(\delta+\frac{\varepsilon}{c}\right)B\left(\overline{x}% \right),

whence since $B\left(\overline{x}\right)/c\geq 1,$ leads to the false result $0\geq\delta B\left(\overline{x}\right).$ Thus (3.5) holds.

Therefore (3.4) and (3.5) show that

\inf_{D}\frac{A}{B}\leq\widetilde{\lambda}\leq\inf_{D}\frac{A}{B}+\frac{% \varepsilon}{c}.

Clearly the second inequality implies the first inequality in (3.3). To prove the second inequality of (3.3), we first show that $A\left(\widetilde{x}\right)-\widetilde{\lambda}B\left(\widetilde{x}\right)\leq\varepsilon.$

Two cases are possible:

Case 1: There is an index $j\geq 1$ such that for every $k\geq j,$ one has $\lambda_{k}=\lambda_{k-1}.$ Let $j_{0}$ be the smalest index having this property and denote $k_{0}=j_{0}-1$ . Clearly one has

\lambda_{k_{0}}=\lambda_{k_{0}+1}=\lambda_{k_{0}+2}=\ ...\ ,

whence $\widetilde{\lambda}=\lambda_{k_{0}}.$ There are two subcases:

(a) $k_{0}=0.$ Then

\lambda_{k_{0}}=\frac{A\left(x_{0}\right)}{B\left(x_{0}\right)};

(b) $k_{0}\geq 1.$ Then since $j_{0}$ is the smalest index with the above property, we have $\lambda_{k_{0}}<\lambda_{k_{0}-1},$ whence

\lambda_{k_{0}}=\min\left\{\frac{A\left(x_{k_{0}}\right)}{B\left(x_{k_{0}}% \right)},\ \lambda_{k_{0}-1}\right\}=\frac{A\left(x_{k_{0}}\right)}{B\left(x_{% k_{0}}\right)}.

Hence in both subcases (a) and (b), we have $\lambda_{k_{0}}=$ $A\left(x_{k_{0}}\right)/B\left(x_{k_{0}}\right).$ Then

	$\displaystyle A\left(\widetilde{x}\right)-\widetilde{\lambda}B\left(\widetilde% {x}\right)$	$\displaystyle=$	$\displaystyle A\left(\widetilde{x}\right)-\lambda_{k_{0}}B\left(\widetilde{x}% \right)\leq\inf_{D}\left(A-\lambda_{k_{0}}B\right)+\varepsilon$
		$\displaystyle\leq$	$\displaystyle A\left(x_{k_{0}}\right)-\lambda_{k_{0}}B\left(x_{k_{0}}\right)+% \varepsilon=\varepsilon.$

Hence

(3.6)

\frac{A\left(\widetilde{x}\right)}{B\left(\widetilde{x}\right)}\leq\widetilde{% \lambda}+\frac{\varepsilon}{c},

as wished.

Case 2, contrary to Case 1: For every index $j\geq 1,$ there exists $k_{j}\geq j$ with $\lambda_{k_{j}}<\lambda_{k_{j}-1}.$ Thus, in this case, we have a subsequence $\left(x_{k_{j}}\right)$ of $\left(x_{k}\right)$ with

(3.7)

\lambda_{k_{j}}=\frac{{A}\left(x_{k_{j}}\right)}{B\left(x_{k_{j}}\right)}

for all $j .$ Then

$\displaystyle A\left(\widetilde{x}\right)-\widetilde{\lambda}B\left(\widetilde% {x}\right)$	$\displaystyle\leq$	$\displaystyle\inf_{D}\left(A-\widetilde{\lambda}B\right)+\varepsilon$
	$\displaystyle\leq$	$\displaystyle A\left(x_{k_{j}}\right)-\lambda_{k_{j}}B\left(x_{k_{j}}\right)+% \left(\lambda_{k_{j}}-\widetilde{\lambda}\right)B\left(x_{k_{j}}\right)+\varepsilon$
	$\displaystyle=$	$\displaystyle\left(\lambda_{k_{j}}-\widetilde{\lambda}\right)B\left(x_{k_{j}}% \right)+\varepsilon$

and letting $j\rightarrow\infty$ again gives $A\left(\widetilde{x}\right)-\widetilde{\lambda}B\left(\widetilde{x}\right)\leq\varepsilon,$ whence (3.6).

Remark 3.1.

Theorem 3.2 reduces to Theorem 2.2 for $\varepsilon=0,$ when at every step, $A\left(x_{k}\right)/B\left(x_{k}\right)\leq A\left(x_{k-1}\right)/B\left(x_{k-% 1}\right)$ and so $\lambda_{k}=A\left(x_{k}\right)/B\left(x_{k}\right).$

According to Theorem 3.2, $\widetilde{\lambda}$ differs from $\ \inf_{D}A/B$ with at most $\varepsilon/c$ and $\ \widetilde{x}$ is a $2\varepsilon/c$ approximation minimum point of $\ \inf_{D}A/B.$

Next we try to see how the functional $A/B$ reaches the value $\widetilde{\lambda}.$ To this aim we need a topological structure of $D,$ the continuity of $A$ and $B,$ and a compactness condition.

Theorem 3.3.

Assume in addition that $D$ is a metric space, $A$ and $B$ are continuous on $D$ and that the following compactness condition holds:

(C):: any sequence $\ \left(y_{k}\right)$ of elements of $\ D$ for which the sequence $\ \left(A\left(y_{k}\right)/B\left(y_{k}\right)\right)$ is convergent has a subsequence convergent in $D .$

Then there exists a point $\widetilde{x}\in\overline{\left\{x_{k}\right\}}$ (either a term or an accumulation point of the sequence $\left(x_{k}\right)$ generated by the approximation Dinkerbach’s algorithm) such that $\widetilde{\lambda}=A\left(\widetilde{x}\right)/B\left(\widetilde{x}\right).$

Proof.

Refer to the cases mentioned in the proof of the previous theorem.

In Case 1, the statement is obvious since

\widetilde{\lambda}=\lambda_{k_{0}}=\frac{A\left(x_{k_{0}}\right)}{B\left(x_{k% _{0}}\right)}.

In Case 2, since $\lambda_{k_{j}}\rightarrow\widetilde{\lambda},$ according to our compactness assumption (C), the sequence $\left(x_{k_{j}}\right)$ has a subsequence that converges to a certain element $\widetilde{x}\in D.$ Going to the limit with the corresponding subsequence in (3.7) we find that

\widetilde{\lambda}=\frac{A\left(\widetilde{x}\right)}{B\left(\widetilde{x}% \right)}.

Remark 3.2.

It is clear that condition (C) is satisfied if $D$ is a compact metric space.

3.2. Dinkelbach algorithm with errors decreasing to zero

Let $\left(\varepsilon_{k}\right)$ be a decreasing to zero sequence of numbers, where for each $k,$ $\varepsilon_{k}$ is the admissible error at step $k$ of the approximation Dinkelbach type algorithm from above. Hence instead of (3.1) we now consider

A\left(x_{k}\right)-\lambda_{k-1}B\left(x_{k}\right)\leq\inf_{D}\left(A-% \lambda_{k-1}B\right)+\varepsilon_{k}.

In this case, $\widetilde{\lambda}$ equals the infimum of $A/B,$ as shown by the next result.

Theorem 3.4.

If $\widetilde{\lambda}=\lim\lambda_{k}$ and $\widetilde{x}\in D$ is such that

A\left(\widetilde{x}\right)-\widetilde{\lambda}B\left(\widetilde{x}\right)\leq% \inf_{D}\left(A-\widetilde{\lambda}B\right)+\varepsilon,

then

(3.8)

\widetilde{\lambda}=\lambda^{\ast}=\inf_{D}\frac{A}{B}

and

\frac{A\left(\widetilde{x}\right)}{B\left(\widetilde{x}\right)}\leq\inf_{D}% \frac{A}{B}+\frac{\varepsilon}{c}.

Proof.

For the proof we only need to show instead of (3.5) the following inequality

(3.9)

\widetilde{\lambda}\leq\inf_{D}\frac{A}{B}.

Assuming by contradiction that the strict opposite inequality holds, we can find $\delta>0$ and $\overline{x}\in D$ such that

\widetilde{\lambda}-\delta\geq\frac{A\left(\overline{x}\right)}{B\left(% \overline{x}\right)}.

Then

$\displaystyle 0$	$\displaystyle\geq$	$\displaystyle A\left(\overline{x}\right)-\left(\widetilde{\lambda}-\delta% \right)B\left(\overline{x}\right)$
	$\displaystyle=$	$\displaystyle A\left(\overline{x}\right)-\lambda_{k-1}B\left(\overline{x}% \right)+\left(\lambda_{k-1}-\widetilde{\lambda}\right)B\left(\overline{x}% \right)+\delta B\left(\overline{x}\right)$
	$\displaystyle\geq$	$\displaystyle\inf_{D}\left(A-\lambda_{k-1}B\right)+\left(\lambda_{k-1}-% \widetilde{\lambda}\right)B\left(\overline{x}\right)+\delta B\left(\overline{x% }\right)$
	$\displaystyle\geq$	$\displaystyle A\left(x_{k}\right)-\lambda_{k-1}B\left(x_{k}\right)-\varepsilon% _{k}+\left(\lambda_{k-1}-\widetilde{\lambda}\right)B\left(\overline{x}\right)+% \delta B\left(\overline{x}\right)$
	$\displaystyle\geq$	$\displaystyle\left(\lambda_{k}-\lambda_{k-1}\right)C-\varepsilon_{k}+\left(% \lambda_{k-1}-\widetilde{\lambda}\right)B\left(\overline{x}\right)+\delta B% \left(\overline{x}\right).$

Letting $k$ go to infinity gives the false result $0\geq\delta B\left(\overline{x}\right).$ Thus (3.9) holds and yields (3.8).

We note that the result in Theorem 3.3 remains valid in this context as well. More exactly we have

Theorem 3.5.

Under the assumptions of Theorem 3.3, if $\left(\lambda_{k}\right)$ and $\left(x_{k}\right)$ are sequences given by the Dinkelbach algorithm with error decreasing to zero and $\lambda^{\ast}=\lim\lambda_{k},$ then there exists a point $x^{\ast}\in\overline{\left\{x_{k}\right\}}$ (either a term or an accumulation point of the sequence $\left(x_{k}\right)$ ) such that

\lambda^{\ast}=\frac{A\left(x^{\ast}\right)}{B\left(x^{\ast}\right)}=\min_{D}% \frac{A}{B}.

In addition

(3.10)

\inf_{D}\left(A-\lambda_{k}B\right)\rightarrow\inf_{D}\left(A-\lambda^{\ast}B% \right)=0\ \ \ \text{as\ }k\rightarrow\infty.

Proof.

The first part follows from Theorems 3.3 and 3.4. To prove (3.10), denote

l_{k}={\inf_{D}}\left({A-\lambda_{k}B}\right)\;\;\;\text{and}\;\;\;l^{\ast}={% \inf_{D}}\left({A-\lambda^{\ast}B}\right).

Since the sequence $\left(\lambda_{k}\right)$ is decreasing, one has that $\left(l_{k}\right)$ is increasing. In addition from $\lambda^{\ast}\leq\lambda_{k},$ we have $A-\lambda^{\ast}B\geq A-\lambda_{k}B,$ hence $l^{\ast}\geq l_{k}.$ Consequently, the sequence $\left(l_{k}\right)$ is convergent. Let $\tilde{l}={\lim_{k\rightarrow\infty}l_{k}}.$ Obviously $\tilde{l}\leq l^{\ast}.$ Suppose that $\tilde{l}<l^{\ast}.$ Then there exists $\delta>0$ such that $\tilde{l}+\delta\leq l^{\ast}.$ Let $\epsilon\in(0,{\frac{\delta}{2}}).$ Since $B$ is bounded and positive and $\left(\lambda_{k}\right)$ is convergent to $\lambda_{\ast},$ it follows there exists $k_{\epsilon}$ such that for any $k\geq k_{\epsilon}$ we have

(3.11)

(\lambda_{k}-\lambda^{\ast})B\leq\epsilon.

Let $k$ be an arbitrarly number with $k\geq k_{\epsilon}$ . Since $l_{k}={\inf_{D}}\left({A-\lambda_{k}B}\right),$ we get the existence of a point $x_{\epsilon}\in D$ with

A(x_{\epsilon})-\lambda_{k}B(x_{\epsilon})\leq l_{k}+\epsilon.

The last relation can be written as

A(x_{\epsilon})-\lambda^{\ast}B(x_{\epsilon})-(\lambda_{k}-\lambda^{\ast})B(x_% {\epsilon})\leq l_{k}+\epsilon,

or equivalently as

A(x_{\epsilon})-\lambda^{\ast}B(x_{\epsilon})\leq l_{k}+\epsilon+(\lambda_{k}-% \lambda^{\ast})B(x_{\epsilon}).

Now taking into account relation (3.11), we obtain

l^{\ast}\leq A(x_{\epsilon})-\lambda^{\ast}B(x_{\epsilon})\leq l_{k}+2\epsilon,

which implies

l_{k}+2\epsilon\geq l^{\ast}\geq\tilde{l}+\delta\geq l_{k}+\delta,

whence $\delta\leq 2\epsilon,$ a contradiction with the choice of $\epsilon.$ Thus $\tilde{l}=l^{\ast}$ and the conclusion follows.

Our next goal is to fulfil assumption (C) for noncompact sets $D .$ We get closer to this desire if we can have additional properties on the sequence $\left(x_{k}\right).$ Such a property is guaranteed by Ekeland’s principle, and under the differentiability condition on $A$ and $B,$ makes it possible to invoke the Palais-Smale condition.

4. Dinkelbach-Ekeland approximation algorithm

4.1. Dinkelbach-Ekeland algorithm

We are now going to present a modified version of Dinkelbach’s algorithm. More precisely, while we are generally operating the same way as above, we are also making use of Ekeland’s variational principle to generate the points of the sequence $(x_{k})$ . To this aim, let $(X,|\cdot|)$ be a Banach space and $A,B:X\rightarrow\mathbb{R}$ two $C^{1}$ functionals such that $A$ is bounded from below and

0<c\leq B\left(x\right)\leq C\ \ \ \text{for all\ \ }x\in X.

As above, we are interested in finding $\lambda^{\ast},$ the minimum value on $X$ of the ratio $A/B,$ and $x^{\ast},$ a point in $X$ at which $\lambda^{\ast}$ is attained.

Let $(\varepsilon_{k})$ be a decreasing sequence of positive real numbers. The Dinkelbach-Ekeland algorithm is described below:

Algorithm 4.1 (Dinkelbach-Ekeland algorithm).

Step $0$ (initialization):

Take any point $x_{0}\in X,$ calculate $\lambda_{0}=\displaystyle{\frac{A\left(x_{0}\right)}{B\left(x_{0}\right)}}$ and set $k=1.$

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

By using Ekeland’s principle, more exactly Corollary 2.4, we find a point $x_{k}\in X$ such that

(4.1)

A(x_{k})-\lambda_{k-1}B(x_{k})\leq\inf_{X}(A-\lambda_{k-1}B)+\varepsilon_{k},

\left|A^{\prime}(x_{k})-\lambda_{k-1}B^{\prime}(x_{k})\right|\leq\varepsilon_{k}

then calculate

\lambda_{k}=\min\left\{\frac{A\left(x_{k}\right)}{B\left(x_{k}\right)},\ % \lambda_{k-1}\right\}

and perform Step $k+1.$

Theorem 4.2.

Under the above assumptions, if $\left(\lambda_{k}\right)$ and $\left(x_{k}\right)$ are the sequences given by the algorithm and $\widetilde{\lambda}=\lim\lambda_{k}$ , then

(4.2)

A(x_{k})-\widetilde{\lambda}B(x_{k})\rightarrow\inf_{X}\left(A-\widetilde{% \lambda}B\right)\;\;\text{\mbox{and}}\;\;A^{\prime}(x_{k})-\widetilde{\lambda}% B^{\prime}(x_{k})\rightarrow 0.

If in addition the functional $A-\widetilde{\lambda}B$ satisfies the (PS) condition, then there exists a point $x^{\ast}\in\overline{\left\{x_{k}\right\}}$ (either a term or an accumulation point of the sequence $\left(x_{k}\right)$ ) such that

\widetilde{\lambda}=\lambda^{\ast}=\frac{A\left(x^{\ast}\right)}{B\left(x^{% \ast}\right)}=\min_{X}\frac{A}{B}.

Proof.

By using the notations from Theorem 3.5, relation (4.1) implies

l_{k}\leq A(x_{k+1})-\lambda_{k}B(x_{k+1})\leq l_{k}+\varepsilon_{k+1}

which since $\varepsilon_{k}\to 0$ , leads to

\lim\{A(x_{k+1})-\lambda_{k}B(x_{k+1})\}=\lim l_{k},

and by (3.10) we obtain

\lim\{A(x_{k+1})-\lambda_{k}B(x_{k+1})\}=\inf\{A-\widetilde{\lambda}B\}=0.

Furthurmore we have

\lim\{A(x_{k+1})-\widetilde{\lambda}B(x_{k+1})\}=\lim\{A(x_{k+1})-\lambda_{k}B% (x_{k+1})+(\widetilde{\lambda}-\lambda_{k})B(x_{k+1})\},

and since $B$ is bunded and $\widetilde{\lambda}\to\lambda_{k}$ , we obtain $(\widetilde{\lambda}-\lambda_{k})B\to 0$ , consqeuently

\lim\{A(x_{k+1})-\widetilde{\lambda}B(x_{k+1})\}=\inf\{A-\widetilde{\lambda}B\}.

Because

|A^{\prime}(x_{k})-\lambda_{k-1}B^{\prime}(x_{k})|=|A^{\prime}(x_{k})-% \widetilde{\lambda}B^{\prime}(x_{k})+(\widetilde{\lambda}-\lambda_{k-1})B^{% \prime}(x_{k})|\leq\epsilon_{k}

we obtain similarly that

\lim A^{\prime}(x_{k})-\widetilde{\lambda}B^{\prime}(x_{k})=0.

Hence the sequence $(x_{k})$ has the properties from (4.2).

Next, assume that the (PS) condition holds for the functional $A-\widetilde{\lambda}B$ .

Case 1: $(\lambda_{k})$ has a subsequence $(\lambda_{k_{j}})$ such that $\lambda_{k_{j}}=\displaystyle{\frac{A\left(x_{k_{j}}\right)}{B\left(x_{k_{j}}% \right)}}$ . Then $(x_{k_{j}})$ satisfies relations (4.2) and since the functional $A-\widetilde{\lambda}B$ satisfies the (PS) condition, via Theorem 2.5, it follows there exists $(x_{v})$ a subsequence of $(x_{k_{j}})$ convergent to a point $x^{\ast}\in X$ with

A(x^{\ast})-\widetilde{\lambda}B(x^{\ast})=\inf\{A-\widetilde{\lambda}B\}\;\;% \mbox{and}\;\;A^{\prime}(x^{*})-\widetilde{\lambda}B^{\prime}(x^{*})=0,

and by using Theorem 3.2, and letting $\varepsilon:=\varepsilon_{k}$ in relation (3.2), we have

\inf_{X}\frac{A}{B}\leq\widetilde{\lambda}\leq\inf_{X}\frac{A}{B}+\frac{% \varepsilon_{k}}{c},

which since $\varepsilon_{k}\rightarrow 0$ leads to

\widetilde{\lambda}=\lambda^{\ast}=\frac{A\left(x^{\ast}\right)}{B\left(x^{% \ast}\right)}=\min_{X}\frac{A}{B}.

Case 2: There exists an index $k_{0}$ such that $\lambda_{k}=\lambda_{k_{0}}$ for all $k\geq k_{0}$ and $\lambda_{k_{0}-1}>\lambda_{k_{0}}.$ Then $\widetilde{\lambda}=$ $\lambda_{k_{0}}=A\left(x_{k_{0}}\right)/B\left(x_{k_{0}}\right),$ and by Theorem 3.2 we have the same conclusion.

4.2. Sufficient conditions for the (PS) requirement

Here we provide some sufficient conditions for a functional $F$ to satisfy the (PS) condition. They require some topological properties on $F^{\prime}$ that are well-known in nonlinear analysis.

Lemma 4.3.

Let $(X,|\cdot|)$ be a Hilbert space and $F:X\rightarrow\mathbb{R}$ a $C^{1}$ functional having the following two properties:

(i):: any sequence $\left(x_{k}\right)$ for which $\left(F\left(x_{k}\right)\right)$ converges is bounded;
(ii):: the operator $N:=I-F^{\prime}$ is completely continuous.

Then $F$ satisfies the (PS) condition.

Proof.

Let $(x_{k})$ be any sequence of points from $X$ such that

(4.3)

F(x_{k})\rightarrow c\;\;\;\text{and}\;\;\;F^{\prime}(x_{k})\rightarrow 0,

where $c\in\mathbb{R}$ . We shall prove that $(x_{k})$ has a convergent subsequence. From (4.3) and assumption (i), it follows that the sequence $(x_{k})$ is bounded. Also from (4.3), we deduce that the set $\{F^{\prime}(x_{k})\}$ is relatively compact. Next from (ii), the set $\left\{N(x_{k})\right\}$ is relatively compact and from the equality $x_{k}=N(x_{k})+F^{\prime}(x_{k})$ it follows that the set $\{x_{k}\},$ as a sum of two relatively compact sets, is relatively compact too. Then the sequence $\left(x_{k}\right)$ has a convergent sequence.

A stronger topological condition on $F^{\prime}$ guarantees that any sequence $\left(x_{k}\right)$ satisfying $F^{\prime}\left(x_{k}\right)\rightarrow 0$ is entirely convergent ( $F$ satisfies strongly the (PS) condition).

Lemma 4.4.

Let $(X,|\cdot|)$ be a Hilbert space and $F:X\rightarrow\mathbb{R}$ a $C^{1}$ functional such that

(ii*):: the operator $N=I-F^{\prime}$ is a contraction on $X .$

Then $F$ satisfies strongly the (PS) condition.

Proof.

Let $(x_{k})$ be any sequence of points from $X$ satisfying (4.3). Since $x_{k}=N(x_{k})+F^{\prime}(x_{k})$ it follows that for any integer $p\geq 1$ we have

\left|x_{k+p}-x_{k}\right|\leq\left|N(x_{k+p})-N(x_{k})\right|+\left|F^{\prime% }(x_{k+p})-F^{\prime}(x_{k})\right|.

Let $L$ be the Lipschitz constant $\left(L<1\right)$ of the operator $N .$ Then

\left|N(x_{k+p})-N(x_{k})\right|\leq L\left|x_{k+p}-x_{k}\right|

which leads to

(4.4)

\left|x_{k+p}-x_{k}\right|\leq\frac{1}{1-L}\left|F^{\prime}(x_{k+p})-F^{\prime% }(x_{k})\right|.

From (4.3) and (4.4) we conclude that $(x_{k})$ is a Cauchy sequence, consequently the statement is proved.

Coming back to functionals of the form $A-\lambda B$ as in our Dinkelbach-Ekeland algorithm, we have the following result.

Proposition 4.5.

Let $(X,|\cdot|)$ be a Hilbert space, $A,B:X\rightarrow\mathbb{R}$ be $C^{1}$ functionals such there exist constants $c, C$ with $0<c\leq B\leq C$ . The following statements hold:

(a):: If $A$ is coercive and the operators $I-A^{\prime}$ and $B^{\prime}$ are completely continuous, then for each $\lambda\in\mathbb{R},$ the functional $A-\lambda B$ satisfies the (PS) condition.
(b):: If the operators $I-A^{\prime}$ and $B^{\prime}$ are $L_{A}$ - respectively $L_{B}$ -Lipschitz continuous with $L_{A}<1,$ then the functional $A-\lambda B$ satisfies strongly the (PS) condition for every $\lambda$ with $\left|\lambda\right|<\left(1-L_{A}\right)/L_{B}.$

Proof.

Let $F=A-\lambda B$ and let $\left(x_{k}\right)$ be any sequence satisfying (4.3).

(a) The coercivity of $A$ and boundedness of $B$ guarantee that $F$ is coercive. Then since the limit of $F\left(x_{k}\right)$ is finite, one has that $\left(x_{k}\right)$ is bounded. Thus $F$ satisfies condition (i) from Lemma 4.3. In addition, the operator $I-F^{\prime}=I-A^{\prime}+\lambda B^{\prime}$ is completely continuous as a sum of the completely continuous operators $I-A^{\prime}$ and $\lambda B^{\prime}.$ Thus $F$ also satisfies condition (ii) of Lemma 4.3. The conclusion now follows from Lemma 4.3.

(b) It is easily seen that the operator $I-A^{\prime}+\lambda B^{\prime}$ is a contraction if $L_{A}+\left|\lambda\right|L_{B}<1.$ Then Lemma 4.4 gives the result.

As regards the Dinkelbach-Ekeland algorithm we have the following final result on its convergence.

Theorem 4.6.

Let $(X,|\cdot|)$ be a Hilbert space, the conditions of Theorem 4.2 hold, $\left(\lambda_{k}\right)$ and $\left(x_{k}\right)$ be the sequences given by the Algorithm 4.1 and $\widetilde{\lambda}=\lim\lambda_{k}.$

(a):

If $A$ is coercive and the operators $I-A^{\prime}$ and $B^{\prime}$ are completely continuous, then there exists a point $x^{\ast}\in\overline{\left\{x_{k}\right\}}$ (either a term or an accumulation point of the sequence $\left(x_{k}\right)$ ) such that

(4.5)

\widetilde{\lambda}=\lambda^{\ast}=\frac{A\left(x^{\ast}\right)}{B\left(x^{% \ast}\right)}=\min_{X}\frac{A}{B}.

(b):

If the operators $I-A^{\prime}$ and $B^{\prime}$ are $L_{A}$ - respectively $L_{B}$ -Lipschitz continuous with $L_{A}<1$ and

(4.6)

\max\left\{\lambda_{0},-\lambda_{-1}\right\}<\frac{1-L_{A}}{L_{B}},

where $\lambda_{-1}=\inf_{X}A/B,$ then the sequence $\left(x_{k}\right)$ converges to some $x^{\ast}$ and (4.5) holds.

Proof.

(a) The result immediately follows from Theorem 4.2 and Proposition 4.5 (a).

(b) Clearly one has $\lambda_{-1}\leq\lambda_{k}\leq\lambda_{0}$ for all $k .$ It follows that $\lambda_{-1}\leq\widetilde{\lambda}\leq\lambda_{0}$ and so $-\widetilde{\lambda}\leq-\lambda_{-1}.$ Then $\left|\widetilde{\lambda}\right|\leq\max\left\{\lambda_{0},-\lambda_{-1}\right% \}.~{}$ This in view of (4.6) gives $\left|\widetilde{\lambda}\right|<\left(1-L_{A}\right)/L_{B}.$ Thus Proposition 4.5 (b) applies to $\lambda=\widetilde{\lambda}.$ Notice that the entire sequence $\left(x_{k}\right)$ converges since $A^{\prime}\left(x_{k}\right)-\widetilde{\lambda}B^{\prime}\left(x_{k}\right)% \rightarrow 0.$

Acknowledgement. The authors would like to especially thank the reviewer for the suggestion of a possible continuation of the research and the related bibliographic indications.

References

[1] Avriel, M., Diewert, W.E., Schaible, S., Zang, I. (1988). Generalized Concavity. New York, NY: Plenum Press.
[2] Boţ, R.I., Csetnek, E.R. (2017). Proximal-gradient algorithms for fractional programming. Optimization 66:1383-1396.
[3] Boţ, R.I., Dao, M.N., Li, G. (2022). Extrapolated proximal subgradient algorithms for nonconvex and nonsmooth fractional programs. Math. Oper. Res. 47:2415-2443.
[4] Cambini, A., Martein, L. (2009). Generalized Convexity and Optimization: Theory and Applications. Berlin: Springer.
[5] Crouzeix, J.P., Ferland, J.A. (1991). Algorithms for generalized fractional programming. Math. Program. 52: 191-207.
[6] Crouzeix, J.P., Ferland, J.A., Nguyen, V.H. (2008). Revisiting Dinkelbach-type algorithms for generalized fractional programs. Operational Research Society of India 45: 96-110.
[7] Dinkelbach, W. (1967). On nonlinear fractional programming. Management Sci. 13:492-498.
[8] Ekeland, I. (1947). On the variational principle. J. Math. Anal. Appl. 47:324-353.
[9] Elbenani, B., Ferland, J.A. (2012). Cell formation problem solved exactly with the Dinkelbach algorithm. CIRRELT-2012-07, University of Montreal.
[10] Frenk, J.B.G., Schaibe, S. (2005). Fractional programming. In: Hadjisavvas, N., Komlósi, S., Schaible, S.S., Eds. Handbook of Generalized Convexity and Generalized Monotonicity, Vol. 76, Berlin: Springer, pp. 335-386.
[11] Frigon, M. (2011). On some generalizations of Ekeland’s principle and inward contractions in gauge spaces. J. Fixed Point Theory Appl. 10:279-298.
[12] Precup, R. (2013). Linear and Semilinear Partial Differential Equations. Berlin: De Gruyter.
[13] Precup, R. (2014). Nash-type equilibria and periodic solutions to nonvariational systems. Adv. Nonlinear Anal. 3:197-207. (2014)
[14] Ródenas, R.G., López M.L., Verastegui, D. (1999). Extensions of Dinkelbach’s algorithm for solving non-linear fractional programming problems. Top 7:33-70.
[15] Schaible, S. (1981). A survey of fractional programming. In: Schaible, S., Ziemba, W.T., Eds. Generalized Concavity in Optimization and Economics. New-York: Academic Press, pp. 417-440.
[16] Schaible, S. (1982). Bibliography in fractional programming. Math. Methods Oper. Res. 26:211-241.
[17] Schaible, S., Shi, J. (2003). Fractional programming: the sum-of-ratios case. Optim. Methods Softw. 18:219-229.
[18] Shi, J. (2001). A Combined algorithm for fractional programming. Ann. Oper. Res. 103:135-147.
[19] Stancu-Minasian, I.M. (1997). Fractional Programming. Dordrecht: Kluwer.
[20] Stancu-Minasian I.M., Tigan, S. (2000). Continuous time linear-fractional programming. The minimum-risk approach. RAIRO Oper. Res. 34:397-409.
[21] Tammer, K., Tammer, Chr., Ohlendorf, E. (2005). Multicriterial Fractional Optimization, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik, preprint.

[1] Avriel, M., Diewert, W. E., Schaible, S., Zang, I. (1988). Generalized Concavity. New York, NY: Plenum Press.
[2] Cambini, A., Martein, L. (2009). Generalized Convexity and Optimization: Theory and Applications. Berlin: Springer.
[3] Elbenani, B., Ferland, J.A. (2012). Cell formation problem solved exactly with the Dinkelbach algorithm. CIRRELT-2012-07, University of Montreal, Montreal. Quebec., p.1–14.
[4] Stancu-Minasian, I. M. (1997). Fractional Programming. Dordrecht: Kluwer.
[5] Precup, R. (2013). Linear and Semilinear Partial Differential Equations. Berlin: De Gruyter.
[6] Crouzeix, J. P., Ferland, J. A. (1991). Algorithms for generalized fractional programming. Math. Program. 52(1-3):191–207. DOI: 10.1007/BF01582887.
[7] Frenk, J. B. G., Schaibe, S. (2005). Fractional programming. In: Hadjisavvas, N., Komlosi, S., Schaible, S.S., eds. Handbook of Generalized Convexity and Generalized Monotonicity, Vol. 76, Berlin: Springer, p. 335–386.
[8] Schaible, S. (1981). A survey of fractional programming. In: Schaible, S., Ziemba, W.T., eds. Generalized Concavity in Optimization and Economics. New York: Academic Press, pp. 417–440.
[9] Schaible, S. (1982). Bibliography in fractional programming. Math. Methods Oper. Res. 26(1):211–241. DOI: 10.1007/BF01917115.
[10] Bot¸, R. I., Csetnek, E. R. (2017). Proximal-gradient algorithms for fractional programming. Optimization. 66(8):1383–1396. DOI: 10.1080/02331934.2017.1294592.
[11] Bot¸, R. I., Dao, M. N., Li, G. (2022). Extrapolated proximal subgradient algorithms for nonconvex and nonsmooth fractional programs. Mathematics of OR. 47(3):2415–2443. DOI: 10.1287/moor.2021.1214.
[12] Crouzeix, J. P., Ferland, J. A., Nguyen, V. H. (2008). Revisiting Dinkelbach-type algorithms for generalized fractional programs. Operational Res. Soc. India. 45:96-110.
[13] Rodenas, R. G., Lopez, M. L., Verastegui, D. (1999). Extensions of Dinkelbach ’s algorithm for solving non-linear fractional programming problems. Top. 7(1):33–70. DOI: 10.1007/BF02564711.
[14] Schaible, S., Shi, J. (2003). Fractional programming: The sum-of-ratios case. Optim. Methods Softw. 18(2):219–229. DOI: 10.1080/1055678031000105242.
[15] Shi, J. (2001). A Combined algorithm for fractional programming. Ann. Oper. Res. 103(1/4):135–147. DOI: 10.1023/A:1012998904482.
[16] Tammer, K., Tammer, C., Ohlendorf, E. (2005). Multicriterial Fractional Optimization. Humboldt-Universitat zu Berlin, Mathematisch-Naturwissenschaftliche Fakultat II, Institut fur Mathematik, Berlin, preprint.
[17] Dinkelbach, W. (1967). On nonlinear fractional programming. Manage. Sci. 13(7): 492–498. DOI: 10.1287/mnsc.13.7.492.
[18] Ekeland, I. (1974). On the variational principle. J. Math. Anal. Appl. 47(2):324–353. DOI: 10.1016/0022-247X(74)90025-0.
[19] Frigon, M. (2011). On some generalizations of Ekeland’s principle and inward contractions in gauge spaces. J. Fixed Point Theory Appl. 10(2):279–298. DOI:10.1007/s11784-011-0068-6.
[20] Precup, R. (2014). Nash-type equilibria and periodic solutions to nonvariational systems. Adv. Nonlinear Anal. 3(4):197–207. DOI: 10.1515/anona-2014-0006.

2023

Space-time upscaling of reactive transport in porous media

January 17, 2022

NANMAT Workshop for young PhD students November 2023

November 13, 2023

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

August 2, 2023

Dinkelbach Type Approximation Algorithms 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

Dinkelbach type approximation algorithms for nonlinear fractional optimization problems

Abstract.

Key words and phrases:

1991 Mathematics Subject Classification:

1. Introduction

2. Preliminaries

Algorithm 2.1 (Dinkelbach’s algorithm).

Theorem 2.2.

Proof.

Theorem 2.3 (Ekeland).

Corollary 2.4.

Theorem 2.5.

3. Approximation Dinkelbach algorithms

3.1. Dinkelbach algorithm with a fixed error

Algorithm 3.1 (Dinkelbach algorithm with a fixed error).

Theorem 3.2.

Proof.

Remark 3.1.

Theorem 3.3.

Proof.

Remark 3.2.

3.2. Dinkelbach algorithm with errors decreasing to zero

Theorem 3.4.

Proof.

Theorem 3.5.

Proof.

4. Dinkelbach-Ekeland approximation algorithm

4.1. Dinkelbach-Ekeland algorithm

Algorithm 4.1 (Dinkelbach-Ekeland algorithm).

Theorem 4.2.

Proof.

4.2. Sufficient conditions for the (PS) requirement

Lemma 4.3.

Proof.

Lemma 4.4.

Proof.

Proposition 4.5.

Proof.

Theorem 4.6.

Proof.

References

References

Related Posts