• PDF
• Cite
• Share
Article Contents  Article Contents

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

• * Corresponding author: Jinbao Jian
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.

Mathematics Subject Classification: Primary: 90C47, 49K35.

 Citation: • • Table 1.  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

Table 2.  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

Table 3.  Numerical results for Madsen-Schjær-Jacobsen's problem .

 $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
• Tables(3)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint