# 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] Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069 [2] Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027 [3] Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381 [4] Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361 [5] Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089 [6] Mostafa El Haffari, Ahmed Roubi. Prox-dual regularization algorithm for generalized fractional programs. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1991-2013. doi: 10.3934/jimo.2017028 [7] Anurag Jayswal, Ashish Kumar Prasad, Izhar Ahmad. On minimax fractional programming problems involving generalized $(H_p,r)$-invex functions. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1001-1018. doi: 10.3934/jimo.2014.10.1001 [8] Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064 [9] Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653 [10] Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 [11] Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153 [12] Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791 [13] Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83 [14] Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011 [15] Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 [16] Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283 [17] 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 [18] Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153 [19] Mingfang Ding, Yanqun Liu, John Anthony Gear. An improved targeted climbing algorithm for linear programs. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 399-405. doi: 10.3934/naco.2011.1.399 [20] Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020

2018 Impact Factor: 1.025

## Tools

Article outline

Figures and Tables