# American Institute of Mathematical Sciences

October  2019, 15(4): 1897-1920. doi: 10.3934/jimo.2018128

## Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs

 Laboratoire MISI, Faculté des Sciences et Techniques, Univ. Hassan 1, Settat, 26000, Morocco

* Corresponding author: Ahmed Roubi

The authors would like to thank a referee for his valuable comments

Received  January 2018 Revised  March 2018 Published  August 2018

In this work, we propose an approximating scheme based on the proximal point algorithm, for solving generalized fractional programs (GFP) by their continuous reformulation, also known to as partial dual counterparts of GFP. Bundle dual algorithms are then derived from this scheme. We prove the convergence and the rate of convergence of these algorithms. As for dual algorithms, the proposed methods generate a sequence of values that converges from below to the minimal value of $(P)$, and a sequence of approximate solutions that converges to a solution of the dual problem. For certain classes of problems, the convergence is at least linear.

Citation: Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1897-1920. doi: 10.3934/jimo.2018128
##### References:

show all references

##### References:
Results for Algorithm 5 and Algorithm [43] with $n = 10$, $m = 10$ and $p = 5$.
 $\bf{n=10}$ $\bf{m=10}$ $\bf{p=5}$ Algo 5 Algo [43] $\bf{ \pmb{\mathsf{ β}}_k}$ $c$ 0.01 0.05 0.1 0.5 0.9 0.01 0.05 0.1 0.5 0.9 0.01 Av. IT 13.1 11.2 10.6 9.7 6.8 8.1 8.8 7.8 5.8 4.6 Av. QP 137.7 102 95.8 89.8 73.6 81.3 88.3 78.7 62.6 48.8 Av. T(s) 21.6 14.6 13.7 13.5 11.7 12 12.7 11.6 10.4 8.2 0.5 Av. IT 13.1 12.9 12.2 9.9 7.2 8.7 8.8 7.4 6 4.5 Av. QP 81.6 84.5 75.7 66.2 56.4 67.4 69.6 55 47.9 40 Av. T(s) 8.8 9.6 8.8 8.4 7.3 8.8 9.1 7.7 7.3 6.3 1 Av. IT 13.8 13 10.7 10.3 7.1 8.6 7.6 7.4 5.3 4.7 Av. QP 76.2 66.5 53.1 60.6 47.1 53.9 50.1 51.4 38.4 37.1 Av. T(s) 8.3 7.1 5.5 7.7 5.7 6.8 6.6 6.8 5.5 5.6 5 Av. IT 12.8 11.3 10.8 12.1 10.5 9.4 8.3 8.4 9 8.3 Av. QP 43.6 37.6 34.8 45.5 48.1 39.7 35.7 36.2 46 47.7 Av. T(s) 4.5 3.9 3.6 4.6 4.9 4.5 4.2 4.3 5.4 5.7 10 Av. IT 12.5 11.8 11.5 12 13.3 12.8 12.3 11.9 13.4 13.4 Av. QP 34.7 30 27.7 34.1 49.8 45.1 42.7 41.7 57.2 61.3 Av. T(s) 3.9 3.3 3.1 3.7 5 4.4 4.2 4.2 5.5 6.2
 $\bf{n=10}$ $\bf{m=10}$ $\bf{p=5}$ Algo 5 Algo [43] $\bf{ \pmb{\mathsf{ β}}_k}$ $c$ 0.01 0.05 0.1 0.5 0.9 0.01 0.05 0.1 0.5 0.9 0.01 Av. IT 13.1 11.2 10.6 9.7 6.8 8.1 8.8 7.8 5.8 4.6 Av. QP 137.7 102 95.8 89.8 73.6 81.3 88.3 78.7 62.6 48.8 Av. T(s) 21.6 14.6 13.7 13.5 11.7 12 12.7 11.6 10.4 8.2 0.5 Av. IT 13.1 12.9 12.2 9.9 7.2 8.7 8.8 7.4 6 4.5 Av. QP 81.6 84.5 75.7 66.2 56.4 67.4 69.6 55 47.9 40 Av. T(s) 8.8 9.6 8.8 8.4 7.3 8.8 9.1 7.7 7.3 6.3 1 Av. IT 13.8 13 10.7 10.3 7.1 8.6 7.6 7.4 5.3 4.7 Av. QP 76.2 66.5 53.1 60.6 47.1 53.9 50.1 51.4 38.4 37.1 Av. T(s) 8.3 7.1 5.5 7.7 5.7 6.8 6.6 6.8 5.5 5.6 5 Av. IT 12.8 11.3 10.8 12.1 10.5 9.4 8.3 8.4 9 8.3 Av. QP 43.6 37.6 34.8 45.5 48.1 39.7 35.7 36.2 46 47.7 Av. T(s) 4.5 3.9 3.6 4.6 4.9 4.5 4.2 4.3 5.4 5.7 10 Av. IT 12.5 11.8 11.5 12 13.3 12.8 12.3 11.9 13.4 13.4 Av. QP 34.7 30 27.7 34.1 49.8 45.1 42.7 41.7 57.2 61.3 Av. T(s) 3.9 3.3 3.1 3.7 5 4.4 4.2 4.2 5.5 6.2
Results for Algorithm 5 and Algorithm [43] with $n = 20$, $m = 10$ and $p = 10$.
 $\bf{n=20}$ $\bf{m=10}$ $\bf{p=10}$ Algo 5 Algo [43] $\bf{ \pmb{\mathsf{ β}}_k}$ $c$ 0.01 0.05 0.1 0.5 0.9 0.01 0.05 0.1 0.5 0.9 0.01 Av. IT 13.3 12.9 11.5 10.8 8.8 7.9 8.4 7.5 5.2 4.4 Av. QP 119.7 117.4 90.9 95.3 87.9 97.8 104.2 93.9 64.6 59.4 Av. T(s) 34.2 33.9 25.7 27.5 25.2 16.5 17.7 16.3 12 11.4 0.5 Av. IT 12.6 12.4 11.2 12.3 9.5 8 8.8 8.1 5.3 4.5 Av. QP 71.3 65.5 59.6 71.8 64.1 78.1 93.5 81.6 56.4 47.2 Av. T(s) 17.2 16.7 15 19.5 17.5 12.4 14.6 13.1 10 8.9 1 Av. IT 13.4 13.1 13.1 12.3 10.4 9.6 8.8 8.2 5.2 4.9 Av. QP 64.2 63.6 59.3 59.4 58.5 83.2 75 72.7 50.9 43 Av. T(s) 16.6 16.5 15.5 16.6 16 13.1 11.8 11.5 9 7.8 5 Av. IT 19.5 17.3 16.7 17.2 20.3 9.5 9.3 9.5 7.7 8.1 Av. QP 57.1 45.1 41 47.2 64 45.3 45.7 49.8 42.1 54.3 Av. T(s) 14.1 11.1 10.6 11.9 17.2 6.8 6.9 7.3 6.7 8.6 10 Av. IT 30.1 30 30.2 30.7 33.4 12.7 12.7 11.7 13.5 12.2 Av. QP 59.7 57.7 56.7 59.9 73.1 52.2 52.7 48.1 64.8 71.4 Av. T(s) 15.4 15.2 14.8 15.7 20.5 6.9 6.9 6.4 8.2 9.4
 $\bf{n=20}$ $\bf{m=10}$ $\bf{p=10}$ Algo 5 Algo [43] $\bf{ \pmb{\mathsf{ β}}_k}$ $c$ 0.01 0.05 0.1 0.5 0.9 0.01 0.05 0.1 0.5 0.9 0.01 Av. IT 13.3 12.9 11.5 10.8 8.8 7.9 8.4 7.5 5.2 4.4 Av. QP 119.7 117.4 90.9 95.3 87.9 97.8 104.2 93.9 64.6 59.4 Av. T(s) 34.2 33.9 25.7 27.5 25.2 16.5 17.7 16.3 12 11.4 0.5 Av. IT 12.6 12.4 11.2 12.3 9.5 8 8.8 8.1 5.3 4.5 Av. QP 71.3 65.5 59.6 71.8 64.1 78.1 93.5 81.6 56.4 47.2 Av. T(s) 17.2 16.7 15 19.5 17.5 12.4 14.6 13.1 10 8.9 1 Av. IT 13.4 13.1 13.1 12.3 10.4 9.6 8.8 8.2 5.2 4.9 Av. QP 64.2 63.6 59.3 59.4 58.5 83.2 75 72.7 50.9 43 Av. T(s) 16.6 16.5 15.5 16.6 16 13.1 11.8 11.5 9 7.8 5 Av. IT 19.5 17.3 16.7 17.2 20.3 9.5 9.3 9.5 7.7 8.1 Av. QP 57.1 45.1 41 47.2 64 45.3 45.7 49.8 42.1 54.3 Av. T(s) 14.1 11.1 10.6 11.9 17.2 6.8 6.9 7.3 6.7 8.6 10 Av. IT 30.1 30 30.2 30.7 33.4 12.7 12.7 11.7 13.5 12.2 Av. QP 59.7 57.7 56.7 59.9 73.1 52.2 52.7 48.1 64.8 71.4 Av. T(s) 15.4 15.2 14.8 15.7 20.5 6.9 6.9 6.4 8.2 9.4
 [1] Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565 [2] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [3] María J. Garrido-Atienza, Bohdan Maslowski, Jana  Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088 [4] Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 [5] Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881 [6] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [7] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [8] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [9] Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 [10] Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213 [11] Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$\alpha$ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113

2019 Impact Factor: 1.366