# American Institute of Mathematical Sciences

• Previous Article
Partially symmetric nonnegative rectangular tensors and copositive rectangular tensors
• JIMO Home
• This Issue
• Next Article
Selection of DRX scheme for voice traffic in LTE-A networks: Markov modeling and performance analysis
April  2019, 15(2): 757-774. doi: 10.3934/jimo.2018069

## A proximal-projection partial bundle method for convex constrained minimax problems

 1 College of Mathematics and Information Science, Guangxi University, Nanning 530004, China 2 College of Science, Guangxi University of Nationalities, Nanning 530007, China 3 School of Mathematics and Statistics, Yulin Normal University, Yulin 537000, China 4 Department of Applied Mathematics, University of New South Wales, Kensington, 2052, Sydney, Australia

* Corresponding author: Jinbao Jian

Received  September 2016 Revised  January 2018 Published  June 2018

Fund Project: Project supported by the National Natural Science Foundation (11761013, 11771383) and Guangxi Natural Science Foundation (2013GXNSFAA019013, 2014GXNSFFA118001, 2016GXNSFDA380019) of China. This work was essentially done while the first author was visiting The University of New South Wales, Australia.

In this paper, we propose a partial bundle method for a convex constrained minimax problem where the objective function is expressed as maximum of finitely many convex (not necessarily differentiable) functions. To avoid complete evaluation of all component functions of the objective, a partial cutting-planes model is adopted instead of the traditional one. Based on the proximal-projection idea, at each iteration, an unconstrained proximal subproblem is solved first to generate an aggregate linear model of the objective function, and then another subproblem based on this model is solved to obtain a trial point. Moreover, a new descent test criterion is proposed, which can not only simplify the presentation of the algorithm, but also improve the numerical performance significantly. An explicit upper bound for the number of bundle resets is also derived. Global convergence of the algorithm is established, and some preliminary numerical results show that our method is very encouraging.

Citation: 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
##### References:
 [1] A. Baums, Minimax method in optimizing energy consumption in real-time embedded systems, Automatic Control and Computer Sciences, 43 (2009), 57-62.  doi: 10.3103/S0146411609020011.  Google Scholar [2] J. F. Bonnans, J. C. Gilbert, C. Lemaréchal and C. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects, Second ed. Springer-Verlag, Berlin Heidelberg New York, 2006.  Google Scholar [3] J. V. Burke, A. S. Lewis and M. L. Overton, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM Journal on Optimization, 15 (2005), 751-779.  doi: 10.1137/030601296.  Google Scholar [4] F. L. Chernousko, Minimax control for a class of linear systems subject to disturbances, Journal of Optimization Theory and Applications, 127 (2005), 535-548.  doi: 10.1007/s10957-005-7501-1.  Google Scholar [5] J. Dattorro, Convex Optimization † Euclidean Distance Geometry, second edn, $\mathcal{M}\varepsilonβ oo$, 2015. Google Scholar [6] G. Di Pillo, L. Grippo and S. Lucidi, A smooth method for the finite minimax problem, Mathematical Programming, 60 (1993), 187-214.  doi: 10.1007/BF01580609.  Google Scholar [7] A. Fuduli, M. Gaudioso, G. Giallombardo and G. Miglionico, A partially inexact bundle method for convex semi-infinite minmax problems, Communications in Nonlinear Science and Numerical Simulation, 21 (2015), 172-180.  doi: 10.1016/j.cnsns.2014.07.033.  Google Scholar [8] M. Gaudioso, G. Giallombardo and G. Miglionico, An incremental method for solving convex finite min-max problems, Mathematics of Operations Research, 31 (2006), 173-187.  doi: 10.1287/moor.1050.0175.  Google Scholar [9] M. Gaudioso, G. Giallombardo and G. Miglionico, On solving the Lagrangian dual of integer programs via an incremental approach, Computational Optimization and Applications, 44 (2009), 117-138.  doi: 10.1007/s10589-007-9149-2.  Google Scholar [10] W. Hare and J. Nutini, A derivative-free approximate gradient sampling algorithm for finite minimax problems, Computational Optimization and Applications, 56 (2013), 1-38.  doi: 10.1007/s10589-013-9547-6.  Google Scholar [11] W. Hare and M. Macklem, Derivative-free optimization methods for finite minimax problems, Optimization Methods and Software, 28 (2013), 300-312.  doi: 10.1080/10556788.2011.638923.  Google Scholar [12] S. X. He and Y. Y. Nie, A class of nonlinear Lagrangian algorithms for minimax problems, Journal of Industrial and Management Optimization, 9 (2013), 75-97.  doi: 10.3934/jimo.2013.9.75.  Google Scholar [13] M. Huang, X. J. Liang, Y. Lu and L. P. Pang, The bundle scheme for solving arbitrary eigenvalue optimizations, Journal of Industrial and Management Optimization, 13 (2017), 659-680.  doi: 10.3934/jimo.2016039.  Google Scholar [14] J. B. Jian, X. L. Zhang, R. Quan and Q. Ma, Generalized monotone line search SQP algorithm for constrained minimax problems, Optimization, 58 (2009), 101-131.  doi: 10.1080/02331930801951140.  Google Scholar [15] J. B. Jian, X. D. Mo, L. J. Qiu, S. M. Yang and F. S. Wang, Simple sequential quadratically constrained quadratic programming feasible algorithm with active identification sets for constrained minimax problems, Journal of Optimization Theory and Applications, 160 (2014), 158-188.  doi: 10.1007/s10957-013-0339-z.  Google Scholar [16] J. B. Jian, C. M. Tang and F. Tang, A feasible descent bundle method for inequality constrained minimax problems (in Chinese), Science China: Mathematics, 45 (2015), 2001-2024.   Google Scholar [17] E. Karas, A. Ribeiro, C. Sagastizábal and M. Solodov, A bundle-filter method for nonsmooth convex constrained optimization, Mathematical Programming, 116 (2009), 297-320.  doi: 10.1007/s10107-007-0123-7.  Google Scholar [18] N. Karmitsa, Test Problems for Large-Scale Nonsmooth Minimization, Tech. Rep. No. B. 4/2007, Department of Mathematical Information Technology, University of Jyväskylä, Finland, 2007. Google Scholar [19] K. C. Kiwiel, A projection-proximal bundle method for convex nondifferentiable minimization, In: M. Théra, R. Tichatschke (eds.) Ill-posed Variational Problems and Regularization Techniques, Lecture Notes in Econom. Math. Systems, Springer-Verlag, Berlin, 477 (1999), 137–150. doi: 10.1007/978-3-642-45780-7_9.  Google Scholar [20] K. C. Kiwiel, A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming, SIAM Journal on Optimization, 17 (2006), 1015-1034.  doi: 10.1137/050639284.  Google Scholar [21] K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, 1133. Springer-Verlag, 1985. doi: 10.1007/BFb0074500.  Google Scholar [22] C. Lemaréchal, An extension of Davidon methods to nondifferentiable problems, Mathematical Programming Study, 3 (1975), 95-109.   Google Scholar [23] X. S. Li and S. C. Fang, On the entropic regularization method for solving min-max problems with applications, Mathematical Methods of Operations Research, 46 (1997), 119-130.  doi: 10.1007/BF01199466.  Google Scholar [24] Y. P. Li and G. H. Huang, Inexact minimax regret integer programming for long-term planning of municipal solid waste management -- part a: Methodology development, Environmental Engineering Science, 26 (2009), 209-218.  doi: 10.1089/ees.2007.0241.ptA.  Google Scholar [25] G. Liuzzi, S. Lucidi and M. Sciandrone, A derivative-free algorithm for linearly constrained finite minimax problems, SIAM Journal on Optimization, 16 (2006), 1054-1075.  doi: 10.1137/040615821.  Google Scholar [26] L. Lukšan and J. Vlček, Test Problems for Nonsmooth Unconstrained and Linearly Constrained Optimization, Tech. Rep. No. 798, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2000. Google Scholar [27] K. Madsen and H. Schjær-Jacobsen, Linearly constrained minimax optimization, Mathematical Programming, 14 (1978), 208-223.  doi: 10.1007/BF01588966.  Google Scholar [28] C. Michelot and F. Plastria, An extended multifacility minimax location problemrevisited, Annals of Operations Research, 111 (2002), 167-179.  doi: 10.1023/A:1020953703533.  Google Scholar [29] A. Nedić and D. P. Bertsekas, Incremental subgradient methods for nondifferentiable optimization, SIAM Journal on Optimization, 12 (2001), 109-138.  doi: 10.1137/S1052623499362111.  Google Scholar [30] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N. J., 1970.  Google Scholar [31] B. Rustem and Q. Nguyen, An algorithm for the inequality-constrained discrete min-max problem, SIAM Journal on Optimization, 8 (1998), 265-283.  doi: 10.1137/S1056263493260386.  Google Scholar [32] C. Sagastizábal and M. Solodov, An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter, SIAM Journal on Optimization, 16 (2005), 146-169.  doi: 10.1137/040603875.  Google Scholar [33] N. Z. Shor, Minimization Methods for Non-differentiable Functions, Springer-Verlag, Berlin, 1985. doi: 10.1007/978-3-642-82118-9.  Google Scholar [34] C. M. Tang, H. Y. Chen and J. B. Jian, An improved partial bundle method for linearly constrained minimax problems, Statistics, Optimization and Information Computing, 4 (2016), 84-98.  doi: 10.19139/soic.v4i1.205.  Google Scholar [35] C. M. Tang and J. B. Jian, Strongly sub-feasible direction method for constrained optimization problems with nonsmooth objective functions, European Journal of Operational Research, 218 (2012), 28-37.  doi: 10.1016/j.ejor.2011.10.055.  Google Scholar [36] C. M. Tang, S. Liu, J. B. Jian and J. L. Li, A feasible SQP-GS algorithm for nonconvex, nonsmooth constrained optimization, Numerical Algorithms, 65 (2014), 1-22.  doi: 10.1007/s11075-012-9692-5.  Google Scholar [37] A. Vardi, New minimax algorithm, Journal of Optimization Theory and Applications, 75 (1992), 613-634.  doi: 10.1007/BF00940496.  Google Scholar [38] F. S. Wang and K. C. Zhang, A hybrid algorithm for nonlinear minimax problems, Annals of Operations Research, 164 (2008), 167-191.  doi: 10.1007/s10479-008-0401-7.  Google Scholar [39] F. S. Wang and K. C. Zhang, A hybrid algorithm for linearly constrained minimax problems, Annals of Operations Research, 206 (2013), 501-525.  doi: 10.1007/s10479-012-1274-3.  Google Scholar [40] S. Y. Wang, Y. Yamamoto and M. Yu, A minimax rule for portfolio selection in frictional markets, Mathematical Methods of Operations Research, 57 (2003), 141-155.  doi: 10.1007/s001860200241.  Google Scholar [41] S. Xu, Smoothing method for minimax problems, Computational Optimization and Applications, 20 (2001), 267-279.  doi: 10.1023/A:1011211101714.  Google Scholar [42] MOSEK: The MOSEK optimization toolbox for MATLAB manual, Version 7.1 (2016). MOSEK ApS, Denmark, http://www.mosek.com. Google Scholar

show all references

##### References:
 [1] A. Baums, Minimax method in optimizing energy consumption in real-time embedded systems, Automatic Control and Computer Sciences, 43 (2009), 57-62.  doi: 10.3103/S0146411609020011.  Google Scholar [2] J. F. Bonnans, J. C. Gilbert, C. Lemaréchal and C. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects, Second ed. Springer-Verlag, Berlin Heidelberg New York, 2006.  Google Scholar [3] J. V. Burke, A. S. Lewis and M. L. Overton, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM Journal on Optimization, 15 (2005), 751-779.  doi: 10.1137/030601296.  Google Scholar [4] F. L. Chernousko, Minimax control for a class of linear systems subject to disturbances, Journal of Optimization Theory and Applications, 127 (2005), 535-548.  doi: 10.1007/s10957-005-7501-1.  Google Scholar [5] J. Dattorro, Convex Optimization † Euclidean Distance Geometry, second edn, $\mathcal{M}\varepsilonβ oo$, 2015. Google Scholar [6] G. Di Pillo, L. Grippo and S. Lucidi, A smooth method for the finite minimax problem, Mathematical Programming, 60 (1993), 187-214.  doi: 10.1007/BF01580609.  Google Scholar [7] A. Fuduli, M. Gaudioso, G. Giallombardo and G. Miglionico, A partially inexact bundle method for convex semi-infinite minmax problems, Communications in Nonlinear Science and Numerical Simulation, 21 (2015), 172-180.  doi: 10.1016/j.cnsns.2014.07.033.  Google Scholar [8] M. Gaudioso, G. Giallombardo and G. Miglionico, An incremental method for solving convex finite min-max problems, Mathematics of Operations Research, 31 (2006), 173-187.  doi: 10.1287/moor.1050.0175.  Google Scholar [9] M. Gaudioso, G. Giallombardo and G. Miglionico, On solving the Lagrangian dual of integer programs via an incremental approach, Computational Optimization and Applications, 44 (2009), 117-138.  doi: 10.1007/s10589-007-9149-2.  Google Scholar [10] W. Hare and J. Nutini, A derivative-free approximate gradient sampling algorithm for finite minimax problems, Computational Optimization and Applications, 56 (2013), 1-38.  doi: 10.1007/s10589-013-9547-6.  Google Scholar [11] W. Hare and M. Macklem, Derivative-free optimization methods for finite minimax problems, Optimization Methods and Software, 28 (2013), 300-312.  doi: 10.1080/10556788.2011.638923.  Google Scholar [12] S. X. He and Y. Y. Nie, A class of nonlinear Lagrangian algorithms for minimax problems, Journal of Industrial and Management Optimization, 9 (2013), 75-97.  doi: 10.3934/jimo.2013.9.75.  Google Scholar [13] M. Huang, X. J. Liang, Y. Lu and L. P. Pang, The bundle scheme for solving arbitrary eigenvalue optimizations, Journal of Industrial and Management Optimization, 13 (2017), 659-680.  doi: 10.3934/jimo.2016039.  Google Scholar [14] J. B. Jian, X. L. Zhang, R. Quan and Q. Ma, Generalized monotone line search SQP algorithm for constrained minimax problems, Optimization, 58 (2009), 101-131.  doi: 10.1080/02331930801951140.  Google Scholar [15] J. B. Jian, X. D. Mo, L. J. Qiu, S. M. Yang and F. S. Wang, Simple sequential quadratically constrained quadratic programming feasible algorithm with active identification sets for constrained minimax problems, Journal of Optimization Theory and Applications, 160 (2014), 158-188.  doi: 10.1007/s10957-013-0339-z.  Google Scholar [16] J. B. Jian, C. M. Tang and F. Tang, A feasible descent bundle method for inequality constrained minimax problems (in Chinese), Science China: Mathematics, 45 (2015), 2001-2024.   Google Scholar [17] E. Karas, A. Ribeiro, C. Sagastizábal and M. Solodov, A bundle-filter method for nonsmooth convex constrained optimization, Mathematical Programming, 116 (2009), 297-320.  doi: 10.1007/s10107-007-0123-7.  Google Scholar [18] N. Karmitsa, Test Problems for Large-Scale Nonsmooth Minimization, Tech. Rep. No. B. 4/2007, Department of Mathematical Information Technology, University of Jyväskylä, Finland, 2007. Google Scholar [19] K. C. Kiwiel, A projection-proximal bundle method for convex nondifferentiable minimization, In: M. Théra, R. Tichatschke (eds.) Ill-posed Variational Problems and Regularization Techniques, Lecture Notes in Econom. Math. Systems, Springer-Verlag, Berlin, 477 (1999), 137–150. doi: 10.1007/978-3-642-45780-7_9.  Google Scholar [20] K. C. Kiwiel, A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming, SIAM Journal on Optimization, 17 (2006), 1015-1034.  doi: 10.1137/050639284.  Google Scholar [21] K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, 1133. Springer-Verlag, 1985. doi: 10.1007/BFb0074500.  Google Scholar [22] C. Lemaréchal, An extension of Davidon methods to nondifferentiable problems, Mathematical Programming Study, 3 (1975), 95-109.   Google Scholar [23] X. S. Li and S. C. Fang, On the entropic regularization method for solving min-max problems with applications, Mathematical Methods of Operations Research, 46 (1997), 119-130.  doi: 10.1007/BF01199466.  Google Scholar [24] Y. P. Li and G. H. Huang, Inexact minimax regret integer programming for long-term planning of municipal solid waste management -- part a: Methodology development, Environmental Engineering Science, 26 (2009), 209-218.  doi: 10.1089/ees.2007.0241.ptA.  Google Scholar [25] G. Liuzzi, S. Lucidi and M. Sciandrone, A derivative-free algorithm for linearly constrained finite minimax problems, SIAM Journal on Optimization, 16 (2006), 1054-1075.  doi: 10.1137/040615821.  Google Scholar [26] L. Lukšan and J. Vlček, Test Problems for Nonsmooth Unconstrained and Linearly Constrained Optimization, Tech. Rep. No. 798, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2000. Google Scholar [27] K. Madsen and H. Schjær-Jacobsen, Linearly constrained minimax optimization, Mathematical Programming, 14 (1978), 208-223.  doi: 10.1007/BF01588966.  Google Scholar [28] C. Michelot and F. Plastria, An extended multifacility minimax location problemrevisited, Annals of Operations Research, 111 (2002), 167-179.  doi: 10.1023/A:1020953703533.  Google Scholar [29] A. Nedić and D. P. Bertsekas, Incremental subgradient methods for nondifferentiable optimization, SIAM Journal on Optimization, 12 (2001), 109-138.  doi: 10.1137/S1052623499362111.  Google Scholar [30] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N. J., 1970.  Google Scholar [31] B. Rustem and Q. Nguyen, An algorithm for the inequality-constrained discrete min-max problem, SIAM Journal on Optimization, 8 (1998), 265-283.  doi: 10.1137/S1056263493260386.  Google Scholar [32] C. Sagastizábal and M. Solodov, An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter, SIAM Journal on Optimization, 16 (2005), 146-169.  doi: 10.1137/040603875.  Google Scholar [33] N. Z. Shor, Minimization Methods for Non-differentiable Functions, Springer-Verlag, Berlin, 1985. doi: 10.1007/978-3-642-82118-9.  Google Scholar [34] C. M. Tang, H. Y. Chen and J. B. Jian, An improved partial bundle method for linearly constrained minimax problems, Statistics, Optimization and Information Computing, 4 (2016), 84-98.  doi: 10.19139/soic.v4i1.205.  Google Scholar [35] C. M. Tang and J. B. Jian, Strongly sub-feasible direction method for constrained optimization problems with nonsmooth objective functions, European Journal of Operational Research, 218 (2012), 28-37.  doi: 10.1016/j.ejor.2011.10.055.  Google Scholar [36] C. M. Tang, S. Liu, J. B. Jian and J. L. Li, A feasible SQP-GS algorithm for nonconvex, nonsmooth constrained optimization, Numerical Algorithms, 65 (2014), 1-22.  doi: 10.1007/s11075-012-9692-5.  Google Scholar [37] A. Vardi, New minimax algorithm, Journal of Optimization Theory and Applications, 75 (1992), 613-634.  doi: 10.1007/BF00940496.  Google Scholar [38] F. S. Wang and K. C. Zhang, A hybrid algorithm for nonlinear minimax problems, Annals of Operations Research, 164 (2008), 167-191.  doi: 10.1007/s10479-008-0401-7.  Google Scholar [39] F. S. Wang and K. C. Zhang, A hybrid algorithm for linearly constrained minimax problems, Annals of Operations Research, 206 (2013), 501-525.  doi: 10.1007/s10479-012-1274-3.  Google Scholar [40] S. Y. Wang, Y. Yamamoto and M. Yu, A minimax rule for portfolio selection in frictional markets, Mathematical Methods of Operations Research, 57 (2003), 141-155.  doi: 10.1007/s001860200241.  Google Scholar [41] S. Xu, Smoothing method for minimax problems, Computational Optimization and Applications, 20 (2001), 267-279.  doi: 10.1023/A:1011211101714.  Google Scholar [42] MOSEK: The MOSEK optimization toolbox for MATLAB manual, Version 7.1 (2016). MOSEK ApS, Denmark, http://www.mosek.com. Google Scholar
Numerical results for $C = \{x:\ l\leq x\leq u\}$.
 Problem $n, m$ Algorithm NI ND N$f_i$ $f^*$ N$_f^{eq}$ CB2$^\Box$ $2,3$ $\verb"PPPBM"^+$ 3 2 6 20.000000 2 $\verb"PPPBM"^-$ 11 3 17 20.000000 6 $\verb"PPBM"$ 6 5 18 20.000000 6 CB3$^\Box$ $2,3$ $\verb"PPPBM"^+$ 3 2 6 16.000000 2 $\verb"PPPBM"^-$ 38 7 51 16.000000 17 $\verb"PPBM"$ 9 7 27 16.000000 9 DEM$^\Box$ $2,3$ $\verb"PPPBM"^+$ 2 2 6 -2.500000 2 $\verb"PPPBM"^-$ 2 2 6 -2.500000 2 $\verb"PPBM"$ 2 1 6 -2.500000 2 QL$^\Box$ $2,3$ $\verb"PPPBM"^+$ 2 2 6 7.940000 2 $\verb"PPPBM"^-$ 4 2 8 7.940000 3 $\verb"PPBM"$ 2 1 6 7.940000 2 LQ$^\Box$ $2,2$ $\verb"PPPBM"^+$ 2 2 4 -1.311371 2 $\verb"PPPBM"^-$ 4 2 6 -1.311371 3 $\verb"PPBM"$ 2 1 4 -1.311371 2 Mifflin1$^\Box$ $2,2$ $\verb"PPPBM"^+$ 3 2 4 3.300000 2 $\verb"PPPBM"^-$ 10 2 12 3.300000 6 $\verb"PPBM"$ 3 2 6 3.300000 3 Rosen-Suzuki$^\Box$ $4,4$ $\verb"PPPBM"^+$ 46 14 101 -43.853572 25 $\verb"PPPBM"^-$ 177 10 247 -43.853353 62 $\verb"PPBM"$ 87 14 348 -43.853158 87 Shor$^\Box$ $5,10$ $\verb"PPPBM"^+$ 43 16 241 23.418920 24 $\verb"PPPBM"^-$ 197 7 343 23.418952 34 $\verb"PPBM"$ 46 16 460 23.418938 46 Maxquad$^\Box$ $10,5$ $\verb"PPPBM"^+$ 38 15 145 -0.841407 29 $\verb"PPPBM"^-$ 149 30 416 -0.841408 83 $\verb"PPBM"$ 69 31 345 -0.841408 69 Maxq$^\Box$ $20,20$ $\verb"PPPBM"^+$ 49 13 512 0.010000 26 $\verb"PPPBM"^-$ 663 16 2967 0.010000 148 $\verb"PPBM"$ 45 9 900 0.010000 45 Maxl$^\Box$ $20,20$ $\verb"PPPBM"^+$ 19 11 269 0.100000 13 $\verb"PPPBM"^-$ 61 24 623 0.100000 31 $\verb"PPBM"$ 46 18 920 0.100000 46 Goffin$^\Box$ $50,50$ $\verb"PPPBM"^+$ 27 3 1074 25.000000 21 $\verb"PPPBM"^-$ 28 4 1124 25.000000 22 $\verb"PPBM"$ 29 4 1450 25.000000 29 MXHILB$^\Box$ $50,50$ $\verb"PPPBM"^+$ 41 16 830 0.000038 17 $\verb"PPPBM"^-$ 148 8 858 0.000037 17 $\verb"PPBM"$ 36 12 1800 0.000043 36
 Problem $n, m$ Algorithm NI ND N$f_i$ $f^*$ N$_f^{eq}$ CB2$^\Box$ $2,3$ $\verb"PPPBM"^+$ 3 2 6 20.000000 2 $\verb"PPPBM"^-$ 11 3 17 20.000000 6 $\verb"PPBM"$ 6 5 18 20.000000 6 CB3$^\Box$ $2,3$ $\verb"PPPBM"^+$ 3 2 6 16.000000 2 $\verb"PPPBM"^-$ 38 7 51 16.000000 17 $\verb"PPBM"$ 9 7 27 16.000000 9 DEM$^\Box$ $2,3$ $\verb"PPPBM"^+$ 2 2 6 -2.500000 2 $\verb"PPPBM"^-$ 2 2 6 -2.500000 2 $\verb"PPBM"$ 2 1 6 -2.500000 2 QL$^\Box$ $2,3$ $\verb"PPPBM"^+$ 2 2 6 7.940000 2 $\verb"PPPBM"^-$ 4 2 8 7.940000 3 $\verb"PPBM"$ 2 1 6 7.940000 2 LQ$^\Box$ $2,2$ $\verb"PPPBM"^+$ 2 2 4 -1.311371 2 $\verb"PPPBM"^-$ 4 2 6 -1.311371 3 $\verb"PPBM"$ 2 1 4 -1.311371 2 Mifflin1$^\Box$ $2,2$ $\verb"PPPBM"^+$ 3 2 4 3.300000 2 $\verb"PPPBM"^-$ 10 2 12 3.300000 6 $\verb"PPBM"$ 3 2 6 3.300000 3 Rosen-Suzuki$^\Box$ $4,4$ $\verb"PPPBM"^+$ 46 14 101 -43.853572 25 $\verb"PPPBM"^-$ 177 10 247 -43.853353 62 $\verb"PPBM"$ 87 14 348 -43.853158 87 Shor$^\Box$ $5,10$ $\verb"PPPBM"^+$ 43 16 241 23.418920 24 $\verb"PPPBM"^-$ 197 7 343 23.418952 34 $\verb"PPBM"$ 46 16 460 23.418938 46 Maxquad$^\Box$ $10,5$ $\verb"PPPBM"^+$ 38 15 145 -0.841407 29 $\verb"PPPBM"^-$ 149 30 416 -0.841408 83 $\verb"PPBM"$ 69 31 345 -0.841408 69 Maxq$^\Box$ $20,20$ $\verb"PPPBM"^+$ 49 13 512 0.010000 26 $\verb"PPPBM"^-$ 663 16 2967 0.010000 148 $\verb"PPBM"$ 45 9 900 0.010000 45 Maxl$^\Box$ $20,20$ $\verb"PPPBM"^+$ 19 11 269 0.100000 13 $\verb"PPPBM"^-$ 61 24 623 0.100000 31 $\verb"PPBM"$ 46 18 920 0.100000 46 Goffin$^\Box$ $50,50$ $\verb"PPPBM"^+$ 27 3 1074 25.000000 21 $\verb"PPPBM"^-$ 28 4 1124 25.000000 22 $\verb"PPBM"$ 29 4 1450 25.000000 29 MXHILB$^\Box$ $50,50$ $\verb"PPPBM"^+$ 41 16 830 0.000038 17 $\verb"PPPBM"^-$ 148 8 858 0.000037 17 $\verb"PPBM"$ 36 12 1800 0.000043 36
Numerical results for $C = \{x:\ \|x-a\|\leq b\}$.
 Problem $n, m$ Algorithm NI ND N$f_i$ $f^*$ N$_f^{eq}$ CB2° $2,3$ $\verb"PPPBM"^+$ 2 2 6 3.343146 2 $\verb"PPPBM"^-$ 4 2 8 3.343146 3 $\verb"PPBM"$ 2 1 6 3.343146 2 CB3° $2,3$ $\verb"PPPBM"^+$ 8 4 14 24.479797 5 $\verb"PPPBM"^-$ 16 7 30 24.479796 10 $\verb"PPBM"$ 11 8 33 24.479795 11 DEM° $2,3$ $\verb"PPPBM"^+$ 22 11 45 -1.499974 15 $\verb"PPPBM"^-$ 36 2 41 -1.499956 14 $\verb"PPBM"$ 19 13 57 -1.499950 19 QL° $2,3$ $\verb"PPPBM"^+$ 5 5 15 25.820215 5 $\verb"PPPBM"^-$ 12 5 24 25.820216 8 $\verb"PPBM"$ 12 9 36 25.820215 12 LQ° $2,2$ $\verb"PPPBM"^+$ 21 7 27 -0.999989 14 $\verb"PPPBM"^-$ 41 4 46 -0.999999 23 $\verb"PPBM"$ 18 17 36 -0.999996 18 Mifflin1° $2,2$ $\verb"PPPBM"^+$ 3 2 4 48.153612 2 $\verb"PPPBM"^-$ 4 2 6 48.153612 3 $\verb"PPBM"$ 2 1 4 48.153612 2 Rosen-Suzuki° $4,4$ $\verb"PPPBM"^+$ 10 6 25 39.715617 6 $\verb"PPPBM"^-$ 12 4 24 39.715617 6 $\verb"PPBM"$ 9 8 36 39.715617 9 Shor° $5,10$ $\verb"PPPBM"^+$ 3 2 20 50.250278 2 $\verb"PPPBM"^-$ 6 2 24 50.250278 2 $\verb"PPBM"$ 4 1 40 50.250278 4 Maxquad° $10,5$ $\verb"PPPBM"^+$ 35 16 146 -0.841408 29 $\verb"PPPBM"^-$ 146 30 413 -0.841406 83 $\verb"PPBM"$ 84 20 420 -0.841408 84 Maxq° $20,20$ $\verb"PPPBM"^+$ 78 8 780 0.011183 39 $\verb"PPPBM"^-$ 612 18 4777 0.011193 239 $\verb"PPBM"$ 84 18 1680 0.011197 84 Maxl° $20,20$ $\verb"PPPBM"^+$ 22 3 269 0.552786 13 $\verb"PPPBM"^-$ 24 5 309 0.552786 15 $\verb"PPBM"$ 22 2 440 0.552786 22 Goffin° $50,50$ $\verb"PPPBM"^+$ 27 3 1074 28.786797 21 $\verb"PPPBM"^-$ 28 4 1124 28.786797 22 $\verb"PPBM"$ 28 3 1400 28.786797 28 MXHILB° $50,50$ $\verb"PPPBM"^+$ 61 16 847 0.613446 17 $\verb"PPPBM"^-$ 250 14 937 0.613479 19 $\verb"PPBM"$ 41 21 2050 0.613444 41
 Problem $n, m$ Algorithm NI ND N$f_i$ $f^*$ N$_f^{eq}$ CB2° $2,3$ $\verb"PPPBM"^+$ 2 2 6 3.343146 2 $\verb"PPPBM"^-$ 4 2 8 3.343146 3 $\verb"PPBM"$ 2 1 6 3.343146 2 CB3° $2,3$ $\verb"PPPBM"^+$ 8 4 14 24.479797 5 $\verb"PPPBM"^-$ 16 7 30 24.479796 10 $\verb"PPBM"$ 11 8 33 24.479795 11 DEM° $2,3$ $\verb"PPPBM"^+$ 22 11 45 -1.499974 15 $\verb"PPPBM"^-$ 36 2 41 -1.499956 14 $\verb"PPBM"$ 19 13 57 -1.499950 19 QL° $2,3$ $\verb"PPPBM"^+$ 5 5 15 25.820215 5 $\verb"PPPBM"^-$ 12 5 24 25.820216 8 $\verb"PPBM"$ 12 9 36 25.820215 12 LQ° $2,2$ $\verb"PPPBM"^+$ 21 7 27 -0.999989 14 $\verb"PPPBM"^-$ 41 4 46 -0.999999 23 $\verb"PPBM"$ 18 17 36 -0.999996 18 Mifflin1° $2,2$ $\verb"PPPBM"^+$ 3 2 4 48.153612 2 $\verb"PPPBM"^-$ 4 2 6 48.153612 3 $\verb"PPBM"$ 2 1 4 48.153612 2 Rosen-Suzuki° $4,4$ $\verb"PPPBM"^+$ 10 6 25 39.715617 6 $\verb"PPPBM"^-$ 12 4 24 39.715617 6 $\verb"PPBM"$ 9 8 36 39.715617 9 Shor° $5,10$ $\verb"PPPBM"^+$ 3 2 20 50.250278 2 $\verb"PPPBM"^-$ 6 2 24 50.250278 2 $\verb"PPBM"$ 4 1 40 50.250278 4 Maxquad° $10,5$ $\verb"PPPBM"^+$ 35 16 146 -0.841408 29 $\verb"PPPBM"^-$ 146 30 413 -0.841406 83 $\verb"PPBM"$ 84 20 420 -0.841408 84 Maxq° $20,20$ $\verb"PPPBM"^+$ 78 8 780 0.011183 39 $\verb"PPPBM"^-$ 612 18 4777 0.011193 239 $\verb"PPBM"$ 84 18 1680 0.011197 84 Maxl° $20,20$ $\verb"PPPBM"^+$ 22 3 269 0.552786 13 $\verb"PPPBM"^-$ 24 5 309 0.552786 15 $\verb"PPBM"$ 22 2 440 0.552786 22 Goffin° $50,50$ $\verb"PPPBM"^+$ 27 3 1074 28.786797 21 $\verb"PPPBM"^-$ 28 4 1124 28.786797 22 $\verb"PPBM"$ 28 3 1400 28.786797 28 MXHILB° $50,50$ $\verb"PPPBM"^+$ 61 16 847 0.613446 17 $\verb"PPPBM"^-$ 250 14 937 0.613479 19 $\verb"PPBM"$ 41 21 2050 0.613444 41
Numerical results for Madsen-Schjær-Jacobsen's problem [27].
 $n, m$ Algorithm NI ND N$f_i$ $f^*$ N$_f^{eq}$ $30, 58$ $\verb"PPPBM"^+$ 99 15 3842 -19.336156 66 $\verb"PPBM"$ 99 18 5742 -19.336155 99 $50, 98$ $\verb"PPPBM"^+$ 138 22 10502 -62.867219 107 $\verb"PPBM"$ 161 25 15778 -62.867219 161 $100,198$ $\verb"PPPBM"^+$ 346 27 42247 -281.077609 213 $\verb"PPBM"$ 358 25 70884 -281.077569 358 $150,298$ $\verb"PPPBM"^+$ 388 31 81950 -655.540257 275 $\verb"PPBM"$ 510 31 151980 -655.540202 510
 $n, m$ Algorithm NI ND N$f_i$ $f^*$ N$_f^{eq}$ $30, 58$ $\verb"PPPBM"^+$ 99 15 3842 -19.336156 66 $\verb"PPBM"$ 99 18 5742 -19.336155 99 $50, 98$ $\verb"PPPBM"^+$ 138 22 10502 -62.867219 107 $\verb"PPBM"$ 161 25 15778 -62.867219 161 $100,198$ $\verb"PPPBM"^+$ 346 27 42247 -281.077609 213 $\verb"PPBM"$ 358 25 70884 -281.077569 358 $150,298$ $\verb"PPPBM"^+$ 388 31 81950 -655.540257 275 $\verb"PPBM"$ 510 31 151980 -655.540202 510
 [1] Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 [2] Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018 [3] Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 [4] 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 [5] Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185 [6] Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080 [7] Alvaro Sandroni, Eran Shmaya. A prequential test for exchangeable theories. Journal of Dynamics & Games, 2014, 1 (3) : 497-505. doi: 10.3934/jdg.2014.1.497 [8] Yaonan Ma, Li-Zhi Liao. The Glowinski–Le Tallec splitting method revisited: A general convergence and convergence rate analysis. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1681-1711. doi: 10.3934/jimo.2020040 [9] Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068 [10] Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050 [11] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 [12] Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 [13] 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 [14] Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $O(n)$ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082 [15] Tengteng Yu, Xin-Wei Liu, Yu-Hong Dai, Jie Sun. Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021084 [16] Leon Mons. Partial regularity for parabolic systems with VMO-coefficients. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021041 [17] Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045 [18] Tomasz Kosmala, Markus Riedle. Variational solutions of stochastic partial differential equations with cylindrical Lévy noise. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 2879-2898. doi: 10.3934/dcdsb.2020209 [19] Qi Lü, Xu Zhang. A concise introduction to control theory for stochastic partial differential equations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021020 [20] 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

2019 Impact Factor: 1.366