March  2022, 12(1): 15-29. doi: 10.3934/naco.2021048

Variable fixing method by weighted average for the continuous quadratic knapsack problem

1. 

Department of Applied Mathematics, National University of Tainan, Tainan 70005, Taiwan

2. 

Department of Physics, National Cheng Kung University, Tainan 70101, Taiwan

* Corresponding author: Hsin-Min Sun

Received  March 2020 Revised  October 2020 Published  March 2022 Early access  November 2021

We analyze the method of solving the separable convex continuous quadratic knapsack problem by weighted average from the viewpoint of variable fixing. It is shown that this method, considered as a variant of the variable fixing algorithms, and Kiwiel's variable fixing method generate the same iterates. We further improve the algorithm based on the analysis regarding the semismooth Newton method. Computational results are given and comparisons are made among the state-of-the-art algorithms. Experiments show that our algorithm has significantly good performance; it behaves very much like an $ O(n) $ algorithm with a very small constant.

Citation: Hsin-Min Sun, Yu-Juan Sun. Variable fixing method by weighted average for the continuous quadratic knapsack problem. Numerical Algebra, Control & Optimization, 2022, 12 (1) : 15-29. doi: 10.3934/naco.2021048
References:
[1]

E. G. BirginJ. M. Martínez and M. Raydan, Algorithm 813: SPG—software for convex-constrained optimization, ACM Trans. Math. Softw., 27 (2001), 340-349.   Google Scholar

[2]

G. R. Bitran and A. C. Hax, Disaggregation and resource allocation using convex knapsack problems with bounded variables, Manag. Sci., 27 (1981), 431-441.  doi: 10.1287/mnsc.27.4.431.  Google Scholar

[3]

B. E. Boser, I. M. Guyon and V. N. Vapnik, A training algorithm for optimal margin classifiers, in Proc. 5th Annu. Wkshp. Comput. Learning Theory (COLT'92) (ed. D. Haussler), ACM Press, (1992), 144–152. Google Scholar

[4]

K. M. Bretthauer and B. Shetty, Quadratic resource allocation with generalized upper bounds, Oper. Res. Lett., 20 (1997), 51-57.  doi: 10.1016/S0167-6377(96)00039-9.  Google Scholar

[5]

K. M. BretthauerB. Shetty and S. Syam, A branch-and-bound algorithm for integer quadratic knapsack problems, ORSA J. Comput., 7 (1995), 109-116.  doi: 10.1287/ijoc.7.1.109.  Google Scholar

[6]

K. M. BretthauerB. Shetty and S. Syam, A projection method for the integer quadratic knapsack problem, J. Oper. Res. Soc., 47 (1996), 457-462.  doi: 10.1057/jors.1996.44.  Google Scholar

[7]

P. Brucker, An O($n$) algorithm for quadratic knapsack problems, Oper. Res. Lett., 3 (1984), 163-166.  doi: 10.1016/0167-6377(84)90010-5.  Google Scholar

[8]

P. H. Calamai and J. J. Moré, Quasi-Newton updates with bounds, SIAM J. Numer. Anal., 24 (1987), 1434-1441.  doi: 10.1137/0724092.  Google Scholar

[9]

R. CominettiW. F. Mascarenhas and P. J. S. Silva, A Newton's method for the continuous quadratic knapsack problem, Math. Prog. Comp., 6 (2014), 151-169.  doi: 10.1007/s12532-014-0066-y.  Google Scholar

[10]

C. Cortes and V. Vapnik, Support-vector networks, Machine Learning, 20 (1995), 273-297.   Google Scholar

[11]

S. Cosares and D. S. Hochbaum, Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources, Math. Oper. Res., 19 (1994), 94-111.  doi: 10.1287/moor.19.1.94.  Google Scholar

[12]

R. W. CottleS. G. Duvall and K. Zikan, A Lagrangian relaxation algorithm for the constrained matrix problem, Nav. Res. Logist. Q., 33 (1986), 55-76.  doi: 10.1002/nav.3800330106.  Google Scholar

[13]

Y.-H. Dai and R. Fletcher, New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds, Math. Program., 106 (2006), 403-421.  doi: 10.1007/s10107-005-0595-2.  Google Scholar

[14]

T. A. Davis, W. W. Hager and J. T. Hungerford, An efficient hybrid algorithm for the separable convex quadratic knapsack problem, ACM Trans. Math. Softw., 42 Article 22 (2016), 25 pages. doi: 10.1145/2828635.  Google Scholar

[15]

J.-P. DussaultJ. A. Ferland and B. Lemaire, Convex quadratic programming with one constraint and bounded variables, Math. Program., 36 (1986), 90-104.  doi: 10.1007/BF02591992.  Google Scholar

[16]

B. C. Eaves, On quadratic programming, Manag. Sci., 17 (1971), 698-711.  doi: 10.1287/mnsc.17.11.698.  Google Scholar

[17]

C. Edirisinghe and J. Jeong, Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time, Math. Program., 164 (2017), 193-227.  doi: 10.1007/s10107-016-1082-7.  Google Scholar

[18]

A. Frangioni and E. Gorgone, A library for continuous convex separable quadratic knapsack problems, Eur. J. Oper. Res., 229 (2013), 37-40.  doi: 10.1016/j.ejor.2013.02.038.  Google Scholar

[19]

W. W. Hager and J. T. Hungerford, Continuous quadratic programming formulations of optimization problems on graphs, Eur. J. Oper. Res., 240 (2015), 328-337.  doi: 10.1016/j.ejor.2014.05.042.  Google Scholar

[20]

W. W. Hager and Y. Krylyuk, Graph partitioning and continuous quadratic programming, SIAM J. Disc. Math., 12 (1999), 500-523.  doi: 10.1137/S0895480199335829.  Google Scholar

[21]

M. HeldP. Wolfe and H. P. Crowder, Validation of subgradient optimization, Math. Program., 6 (1974), 62-88.  doi: 10.1007/BF01580223.  Google Scholar

[22]

R. HelgasonJ. Kennington and H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program, Math. Program., 18 (1980), 338-343.  doi: 10.1007/BF01588328.  Google Scholar

[23]

D. S. Hochbaum and S. P. Hong, About strongly polynomial time algorithms for quadratic optimization over submodular constraints, Math. Program., 69 (1995), 269-309.  doi: 10.1007/BF01585561.  Google Scholar

[24]

J. Jeong, Indefinite Knapsack Separable Quadratic Programming: Methods and Applications, Ph.D. Dissertation, University of Tennessee, Knoxville, 2014. Available from: https://trace.tennessee.edu/utk_graddiss/2704/ Google Scholar

[25]

N. Katoh, A. Shioura and T. Ibaraki, Resource allocation problems, in Handbook of Combinatorial Optimization (eds. P.M. Pardalos, DZ Du and R.L. Graham), Springer, (2013), 2897–2988. doi: 10.1007/978-1-4419-7997-1.  Google Scholar

[26]

K. C. Kiwiel, On linear-time algorithms for the continuous quadratic knapsack problem, J. Optim. Theory Appl., 134 (2007), 549-554.  doi: 10.1007/s10957-007-9259-0.  Google Scholar

[27]

K. C. Kiwiel, Breakpoint searching algorithms for the continuous quadratic knapsack problem, Math. Program., 112 (2008), 473-491.  doi: 10.1007/s10107-006-0050-z.  Google Scholar

[28]

K. C. Kiwiel, Variable fixing algorithms for the continuous quadratic knapsack problem, J. Optim. Theory Appl., 136 (2008), 445-458.  doi: 10.1007/s10957-007-9317-7.  Google Scholar

[29]

N. MaculanC. P. SantiagoE. M. Macambira and M. H. C. Jardim, An $O(n)$ algorithm for projecting a vector on the intersection of a hyperplane and a box in $\mathbb{R}^n$, J. Optim. Theory Appl., 117 (2003), 553-574.  doi: 10.1023/A:1023997605430.  Google Scholar

[30]

N. Megiddo and A. Tamir, Linear time algorithms for some separable quadratic programming problems, Oper. Res. Lett., 13 (1993), 203-211.  doi: 10.1016/0167-6377(93)90041-E.  Google Scholar

[31]

S. S. Nielsen and S. A. Zenios, Massively parallel algorithms for singly constrained convex programs, ORSA J. Comput., 4 (1992), 166-181.  doi: 10.1287/ijoc.4.2.166.  Google Scholar

[32]

P. M. Pardalos and N. Kovoor, An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds, Math. Program., 46 (1990), 321-328.  doi: 10.1007/BF01585748.  Google Scholar

[33]

P. M. PardalosY. Ye and C.-G. Han, Algorithms for the solution of quadratic knapsack problems, Linear Algebra Appl., 152 (1991), 69-91.  doi: 10.1016/0024-3795(91)90267-Z.  Google Scholar

[34]

M. Patriksson, A survey on the continuous nonlinear resource allocation problem, Eur. J. Oper. Res., 185 (2008), 1-46.  doi: 10.1016/j.ejor.2006.12.006.  Google Scholar

[35]

M. Patriksson and C. Strömberg, Algorithms for the continuous nonlinear resource allocation problem–-New implementations and numerical studies, Eur. J. Oper. Res., 243 (2015), 703-722.  doi: 10.1016/j.ejor.2015.01.029.  Google Scholar

[36]

A. G. RobinsonN. Jiang and C. S. Lerme, On the continuous quadratic knapsack problem, Math. Program., 55 (1992), 99-108.  doi: 10.1007/BF01581193.  Google Scholar

[37]

B. Shetty and R. Muthukrishnan, A parallel projection for the multicommodity network model, J. Oper. Res. Soc., 41 (1990), 837-842.   Google Scholar

[38]

H.-M. Sun and R.-L. Sheu, Minimum variance allocation among constrained intervals, J. Glob. Optim., 74 (2019), 21-44.  doi: 10.1007/s10898-019-00748-3.  Google Scholar

[39]

J. A. Ventura, Computational development of a Lagrangian dual approach for quadratic networks, Networks, 21 (1991), 469-485.  doi: 10.1002/net.3230210407.  Google Scholar

show all references

References:
[1]

E. G. BirginJ. M. Martínez and M. Raydan, Algorithm 813: SPG—software for convex-constrained optimization, ACM Trans. Math. Softw., 27 (2001), 340-349.   Google Scholar

[2]

G. R. Bitran and A. C. Hax, Disaggregation and resource allocation using convex knapsack problems with bounded variables, Manag. Sci., 27 (1981), 431-441.  doi: 10.1287/mnsc.27.4.431.  Google Scholar

[3]

B. E. Boser, I. M. Guyon and V. N. Vapnik, A training algorithm for optimal margin classifiers, in Proc. 5th Annu. Wkshp. Comput. Learning Theory (COLT'92) (ed. D. Haussler), ACM Press, (1992), 144–152. Google Scholar

[4]

K. M. Bretthauer and B. Shetty, Quadratic resource allocation with generalized upper bounds, Oper. Res. Lett., 20 (1997), 51-57.  doi: 10.1016/S0167-6377(96)00039-9.  Google Scholar

[5]

K. M. BretthauerB. Shetty and S. Syam, A branch-and-bound algorithm for integer quadratic knapsack problems, ORSA J. Comput., 7 (1995), 109-116.  doi: 10.1287/ijoc.7.1.109.  Google Scholar

[6]

K. M. BretthauerB. Shetty and S. Syam, A projection method for the integer quadratic knapsack problem, J. Oper. Res. Soc., 47 (1996), 457-462.  doi: 10.1057/jors.1996.44.  Google Scholar

[7]

P. Brucker, An O($n$) algorithm for quadratic knapsack problems, Oper. Res. Lett., 3 (1984), 163-166.  doi: 10.1016/0167-6377(84)90010-5.  Google Scholar

[8]

P. H. Calamai and J. J. Moré, Quasi-Newton updates with bounds, SIAM J. Numer. Anal., 24 (1987), 1434-1441.  doi: 10.1137/0724092.  Google Scholar

[9]

R. CominettiW. F. Mascarenhas and P. J. S. Silva, A Newton's method for the continuous quadratic knapsack problem, Math. Prog. Comp., 6 (2014), 151-169.  doi: 10.1007/s12532-014-0066-y.  Google Scholar

[10]

C. Cortes and V. Vapnik, Support-vector networks, Machine Learning, 20 (1995), 273-297.   Google Scholar

[11]

S. Cosares and D. S. Hochbaum, Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources, Math. Oper. Res., 19 (1994), 94-111.  doi: 10.1287/moor.19.1.94.  Google Scholar

[12]

R. W. CottleS. G. Duvall and K. Zikan, A Lagrangian relaxation algorithm for the constrained matrix problem, Nav. Res. Logist. Q., 33 (1986), 55-76.  doi: 10.1002/nav.3800330106.  Google Scholar

[13]

Y.-H. Dai and R. Fletcher, New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds, Math. Program., 106 (2006), 403-421.  doi: 10.1007/s10107-005-0595-2.  Google Scholar

[14]

T. A. Davis, W. W. Hager and J. T. Hungerford, An efficient hybrid algorithm for the separable convex quadratic knapsack problem, ACM Trans. Math. Softw., 42 Article 22 (2016), 25 pages. doi: 10.1145/2828635.  Google Scholar

[15]

J.-P. DussaultJ. A. Ferland and B. Lemaire, Convex quadratic programming with one constraint and bounded variables, Math. Program., 36 (1986), 90-104.  doi: 10.1007/BF02591992.  Google Scholar

[16]

B. C. Eaves, On quadratic programming, Manag. Sci., 17 (1971), 698-711.  doi: 10.1287/mnsc.17.11.698.  Google Scholar

[17]

C. Edirisinghe and J. Jeong, Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time, Math. Program., 164 (2017), 193-227.  doi: 10.1007/s10107-016-1082-7.  Google Scholar

[18]

A. Frangioni and E. Gorgone, A library for continuous convex separable quadratic knapsack problems, Eur. J. Oper. Res., 229 (2013), 37-40.  doi: 10.1016/j.ejor.2013.02.038.  Google Scholar

[19]

W. W. Hager and J. T. Hungerford, Continuous quadratic programming formulations of optimization problems on graphs, Eur. J. Oper. Res., 240 (2015), 328-337.  doi: 10.1016/j.ejor.2014.05.042.  Google Scholar

[20]

W. W. Hager and Y. Krylyuk, Graph partitioning and continuous quadratic programming, SIAM J. Disc. Math., 12 (1999), 500-523.  doi: 10.1137/S0895480199335829.  Google Scholar

[21]

M. HeldP. Wolfe and H. P. Crowder, Validation of subgradient optimization, Math. Program., 6 (1974), 62-88.  doi: 10.1007/BF01580223.  Google Scholar

[22]

R. HelgasonJ. Kennington and H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program, Math. Program., 18 (1980), 338-343.  doi: 10.1007/BF01588328.  Google Scholar

[23]

D. S. Hochbaum and S. P. Hong, About strongly polynomial time algorithms for quadratic optimization over submodular constraints, Math. Program., 69 (1995), 269-309.  doi: 10.1007/BF01585561.  Google Scholar

[24]

J. Jeong, Indefinite Knapsack Separable Quadratic Programming: Methods and Applications, Ph.D. Dissertation, University of Tennessee, Knoxville, 2014. Available from: https://trace.tennessee.edu/utk_graddiss/2704/ Google Scholar

[25]

N. Katoh, A. Shioura and T. Ibaraki, Resource allocation problems, in Handbook of Combinatorial Optimization (eds. P.M. Pardalos, DZ Du and R.L. Graham), Springer, (2013), 2897–2988. doi: 10.1007/978-1-4419-7997-1.  Google Scholar

[26]

K. C. Kiwiel, On linear-time algorithms for the continuous quadratic knapsack problem, J. Optim. Theory Appl., 134 (2007), 549-554.  doi: 10.1007/s10957-007-9259-0.  Google Scholar

[27]

K. C. Kiwiel, Breakpoint searching algorithms for the continuous quadratic knapsack problem, Math. Program., 112 (2008), 473-491.  doi: 10.1007/s10107-006-0050-z.  Google Scholar

[28]

K. C. Kiwiel, Variable fixing algorithms for the continuous quadratic knapsack problem, J. Optim. Theory Appl., 136 (2008), 445-458.  doi: 10.1007/s10957-007-9317-7.  Google Scholar

[29]

N. MaculanC. P. SantiagoE. M. Macambira and M. H. C. Jardim, An $O(n)$ algorithm for projecting a vector on the intersection of a hyperplane and a box in $\mathbb{R}^n$, J. Optim. Theory Appl., 117 (2003), 553-574.  doi: 10.1023/A:1023997605430.  Google Scholar

[30]

N. Megiddo and A. Tamir, Linear time algorithms for some separable quadratic programming problems, Oper. Res. Lett., 13 (1993), 203-211.  doi: 10.1016/0167-6377(93)90041-E.  Google Scholar

[31]

S. S. Nielsen and S. A. Zenios, Massively parallel algorithms for singly constrained convex programs, ORSA J. Comput., 4 (1992), 166-181.  doi: 10.1287/ijoc.4.2.166.  Google Scholar

[32]

P. M. Pardalos and N. Kovoor, An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds, Math. Program., 46 (1990), 321-328.  doi: 10.1007/BF01585748.  Google Scholar

[33]

P. M. PardalosY. Ye and C.-G. Han, Algorithms for the solution of quadratic knapsack problems, Linear Algebra Appl., 152 (1991), 69-91.  doi: 10.1016/0024-3795(91)90267-Z.  Google Scholar

[34]

M. Patriksson, A survey on the continuous nonlinear resource allocation problem, Eur. J. Oper. Res., 185 (2008), 1-46.  doi: 10.1016/j.ejor.2006.12.006.  Google Scholar

[35]

M. Patriksson and C. Strömberg, Algorithms for the continuous nonlinear resource allocation problem–-New implementations and numerical studies, Eur. J. Oper. Res., 243 (2015), 703-722.  doi: 10.1016/j.ejor.2015.01.029.  Google Scholar

[36]

A. G. RobinsonN. Jiang and C. S. Lerme, On the continuous quadratic knapsack problem, Math. Program., 55 (1992), 99-108.  doi: 10.1007/BF01581193.  Google Scholar

[37]

B. Shetty and R. Muthukrishnan, A parallel projection for the multicommodity network model, J. Oper. Res. Soc., 41 (1990), 837-842.   Google Scholar

[38]

H.-M. Sun and R.-L. Sheu, Minimum variance allocation among constrained intervals, J. Glob. Optim., 74 (2019), 21-44.  doi: 10.1007/s10898-019-00748-3.  Google Scholar

[39]

J. A. Ventura, Computational development of a Lagrangian dual approach for quadratic networks, Networks, 21 (1991), 469-485.  doi: 10.1002/net.3230210407.  Google Scholar

Table 1.  uncorrelated test
Dimension Iterations Time (msec) Iterations Time (msec)
$ n $ avg max min avg max min avg max min avg max min
QWMVA2 QWMVA
50000 4.9 9 3 1.5 1.8 1.2 7.8 11 6 1.6 1.9 1.4
100000 5.7 12 3 3.0 4.3 2.6 8.2 11 7 3.3 3.7 2.5
500000 5.7 13 4 16.0 23.0 13.5 8.7 12 7 17.5 20.0 14.0
1000000 5.7 14 3 38.5 71.0 30.0 8.8 12 7 46.6 55.0 33.0
1500000 5.7 13 4 62.1 116.7 46.7 8.9 12 7 76.7 91.7 56.7
2000000 6.0 14 4 86.7 164.0 64.0 8.9 12 7 104.3 122.0 68.0
Newton Secant
50000 4.7 8 3 2.3 2.7 1.8 8.2 12 6 3.0 4.0 2.2
100000 5.2 9 3 4.7 5.5 3.8 8.7 14 6 6.1 8.2 4.1
500000 5.3 9 4 25.8 30.5 20.5 8.6 14 6 31.2 43.0 21.5
1000000 5.2 10 3 52.0 63.0 42.0 8.4 13 6 60.9 82.0 44.0
1500000 5.1 9 3 77.0 93.3 58.3 8.4 14 6 93.2 130.0 63.3
2000000 5.2 11 4 102.1 124.0 84.0 8.5 15 7 126.5 170.0 94.0
Variable fixing Median search
50000 7.8 11 6 2.5 2.8 2.2 16.7 17 16 4.3 4.5 3.6
100000 8.2 11 7 5.0 5.4 4.4 17.7 18 17 8.4 9.0 7.3
500000 8.7 12 7 30.6 34.5 26.5 19.9 20 19 45.2 50.5 39.0
1000000 8.8 12 7 65.1 73.0 55.0 20.9 21 20 92.8 99.0 80.0
1500000 8.9 12 7 98.1 108.3 85.0 21.6 22 21 144.4 151.7 125.0
2000000 8.9 12 7 129.4 144.0 108.0 22.0 22 21 192.4 202.0 166.0
Dimension Iterations Time (msec) Iterations Time (msec)
$ n $ avg max min avg max min avg max min avg max min
QWMVA2 QWMVA
50000 4.9 9 3 1.5 1.8 1.2 7.8 11 6 1.6 1.9 1.4
100000 5.7 12 3 3.0 4.3 2.6 8.2 11 7 3.3 3.7 2.5
500000 5.7 13 4 16.0 23.0 13.5 8.7 12 7 17.5 20.0 14.0
1000000 5.7 14 3 38.5 71.0 30.0 8.8 12 7 46.6 55.0 33.0
1500000 5.7 13 4 62.1 116.7 46.7 8.9 12 7 76.7 91.7 56.7
2000000 6.0 14 4 86.7 164.0 64.0 8.9 12 7 104.3 122.0 68.0
Newton Secant
50000 4.7 8 3 2.3 2.7 1.8 8.2 12 6 3.0 4.0 2.2
100000 5.2 9 3 4.7 5.5 3.8 8.7 14 6 6.1 8.2 4.1
500000 5.3 9 4 25.8 30.5 20.5 8.6 14 6 31.2 43.0 21.5
1000000 5.2 10 3 52.0 63.0 42.0 8.4 13 6 60.9 82.0 44.0
1500000 5.1 9 3 77.0 93.3 58.3 8.4 14 6 93.2 130.0 63.3
2000000 5.2 11 4 102.1 124.0 84.0 8.5 15 7 126.5 170.0 94.0
Variable fixing Median search
50000 7.8 11 6 2.5 2.8 2.2 16.7 17 16 4.3 4.5 3.6
100000 8.2 11 7 5.0 5.4 4.4 17.7 18 17 8.4 9.0 7.3
500000 8.7 12 7 30.6 34.5 26.5 19.9 20 19 45.2 50.5 39.0
1000000 8.8 12 7 65.1 73.0 55.0 20.9 21 20 92.8 99.0 80.0
1500000 8.9 12 7 98.1 108.3 85.0 21.6 22 21 144.4 151.7 125.0
2000000 8.9 12 7 129.4 144.0 108.0 22.0 22 21 192.4 202.0 166.0
Table 2.  weakly correlated test
Dimension Iterations Time (msec) Iterations Time (msec)
$ n $ avg max min avg max min avg max min avg max min
QWMVA2 QWMVA
50000 5.0 11 3 1.4 2.0 1.2 7.7 10 6 1.6 1.7 1.3
100000 5.5 11 3 2.9 3.9 2.4 7.9 11 7 3.1 3.5 2.4
500000 5.7 13 3 15.5 22.0 13.5 8.2 11 7 16.8 18.0 14.5
1000000 5.5 13 3 37.4 62.0 27.0 8.4 11 7 44.6 50.0 31.0
1500000 5.4 13 4 60.3 108.3 48.3 8.6 10 7 74.2 83.3 56.7
2000000 5.9 13 4 84.4 146.0 66.0 8.6 12 7 100.4 110.0 64.0
Newton Secant
50000 4.6 8 3 2.2 2.4 1.8 8.0 12 6 2.9 4.2 1.9
100000 5.0 9 3 4.4 4.8 3.5 8.4 14 6 5.8 8.8 3.7
500000 5.1 8 3 24.3 28.0 19.5 8.5 13 6 29.6 45.0 19.5
1000000 5.0 9 3 49.4 59.0 37.0 8.2 13 6 57.3 91.0 39.0
1500000 5.0 8 3 74.2 90.0 60.0 8.3 13 6 88.3 130.0 56.7
2000000 5.1 10 3 98.9 118.0 78.0 8.3 14 6 120.8 182.0 76.0
Variable fixing Median search
50000 7.7 10 6 2.4 2.6 2.2 16.7 17 16 4.2 4.4 3.6
100000 7.9 11 7 4.8 5.3 4.4 17.7 18 17 8.3 8.7 7.2
500000 8.2 11 7 29.1 31.5 26.0 19.9 20 19 44.8 47.5 39.0
1000000 8.4 11 7 61.9 67.0 55.0 21.0 21 20 91.7 97.0 80.0
1500000 8.6 10 7 93.4 100.0 83.3 21.6 22 21 141.9 150.0 123.3
2000000 8.6 12 7 125.3 138.0 102.0 21.9 22 21 189.7 198.0 162.0
Dimension Iterations Time (msec) Iterations Time (msec)
$ n $ avg max min avg max min avg max min avg max min
QWMVA2 QWMVA
50000 5.0 11 3 1.4 2.0 1.2 7.7 10 6 1.6 1.7 1.3
100000 5.5 11 3 2.9 3.9 2.4 7.9 11 7 3.1 3.5 2.4
500000 5.7 13 3 15.5 22.0 13.5 8.2 11 7 16.8 18.0 14.5
1000000 5.5 13 3 37.4 62.0 27.0 8.4 11 7 44.6 50.0 31.0
1500000 5.4 13 4 60.3 108.3 48.3 8.6 10 7 74.2 83.3 56.7
2000000 5.9 13 4 84.4 146.0 66.0 8.6 12 7 100.4 110.0 64.0
Newton Secant
50000 4.6 8 3 2.2 2.4 1.8 8.0 12 6 2.9 4.2 1.9
100000 5.0 9 3 4.4 4.8 3.5 8.4 14 6 5.8 8.8 3.7
500000 5.1 8 3 24.3 28.0 19.5 8.5 13 6 29.6 45.0 19.5
1000000 5.0 9 3 49.4 59.0 37.0 8.2 13 6 57.3 91.0 39.0
1500000 5.0 8 3 74.2 90.0 60.0 8.3 13 6 88.3 130.0 56.7
2000000 5.1 10 3 98.9 118.0 78.0 8.3 14 6 120.8 182.0 76.0
Variable fixing Median search
50000 7.7 10 6 2.4 2.6 2.2 16.7 17 16 4.2 4.4 3.6
100000 7.9 11 7 4.8 5.3 4.4 17.7 18 17 8.3 8.7 7.2
500000 8.2 11 7 29.1 31.5 26.0 19.9 20 19 44.8 47.5 39.0
1000000 8.4 11 7 61.9 67.0 55.0 21.0 21 20 91.7 97.0 80.0
1500000 8.6 10 7 93.4 100.0 83.3 21.6 22 21 141.9 150.0 123.3
2000000 8.6 12 7 125.3 138.0 102.0 21.9 22 21 189.7 198.0 162.0
Table 3.  correlated test
Dimension Iterations Time (msec) Iterations Time (msec)
$ n $ avg max min avg max min avg max min avg max min
QWMVA2 QWMVA
50000 5.1 12 3 1.4 1.8 1.2 7.6 9 7 1.6 1.7 1.4
100000 5.1 11 3 2.9 3.7 2.5 7.8 10 6 3.1 3.4 2.5
500000 5.5 12 3 15.5 21.0 13.0 8.1 10 7 16.7 18.0 14.5
1000000 5.6 12 3 37.2 58.0 27.0 8.3 10 7 44.0 49.0 36.0
1500000 5.5 14 3 60.4 96.7 46.7 8.4 11 7 72.0 80.0 53.3
2000000 5.5 13 3 82.1 128.0 62.0 8.3 10 7 97.9 106.0 88.0
Newton Secant
50000 4.8 7 3 2.1 2.4 1.7 8.1 12 6 2.8 4.3 1.6
100000 4.7 9 3 4.3 4.8 3.4 8.0 11 6 5.8 8.7 3.8
500000 5.0 8 3 23.8 28.5 18.0 8.3 12 6 29.0 44.5 19.0
1000000 4.9 8 3 48.9 60.0 37.0 8.2 12 6 57.2 88.0 38.0
1500000 5.0 9 3 73.1 93.3 56.7 8.3 12 6 91.1 131.7 58.3
2000000 4.9 7 3 96.1 116.0 72.0 8.1 11 6 114.3 176.0 80.0
Variable fixing Median search
50000 7.6 9 7 2.4 2.6 2.2 16.7 17 16 4.2 4.4 3.8
100000 7.8 10 6 4.8 5.5 4.4 17.7 18 17 8.3 8.7 7.3
500000 8.1 10 7 28.8 31.0 26.0 19.9 20 19 44.8 47.5 39.5
1000000 8.3 10 7 61.1 68.0 55.0 20.9 21 20 91.2 97.0 81.0
1500000 8.4 11 7 92.2 103.3 83.3 21.6 22 21 142.2 150.0 123.3
2000000 8.3 10 7 122.0 136.0 110.0 21.9 22 21 188.6 198.0 172.0
Dimension Iterations Time (msec) Iterations Time (msec)
$ n $ avg max min avg max min avg max min avg max min
QWMVA2 QWMVA
50000 5.1 12 3 1.4 1.8 1.2 7.6 9 7 1.6 1.7 1.4
100000 5.1 11 3 2.9 3.7 2.5 7.8 10 6 3.1 3.4 2.5
500000 5.5 12 3 15.5 21.0 13.0 8.1 10 7 16.7 18.0 14.5
1000000 5.6 12 3 37.2 58.0 27.0 8.3 10 7 44.0 49.0 36.0
1500000 5.5 14 3 60.4 96.7 46.7 8.4 11 7 72.0 80.0 53.3
2000000 5.5 13 3 82.1 128.0 62.0 8.3 10 7 97.9 106.0 88.0
Newton Secant
50000 4.8 7 3 2.1 2.4 1.7 8.1 12 6 2.8 4.3 1.6
100000 4.7 9 3 4.3 4.8 3.4 8.0 11 6 5.8 8.7 3.8
500000 5.0 8 3 23.8 28.5 18.0 8.3 12 6 29.0 44.5 19.0
1000000 4.9 8 3 48.9 60.0 37.0 8.2 12 6 57.2 88.0 38.0
1500000 5.0 9 3 73.1 93.3 56.7 8.3 12 6 91.1 131.7 58.3
2000000 4.9 7 3 96.1 116.0 72.0 8.1 11 6 114.3 176.0 80.0
Variable fixing Median search
50000 7.6 9 7 2.4 2.6 2.2 16.7 17 16 4.2 4.4 3.8
100000 7.8 10 6 4.8 5.5 4.4 17.7 18 17 8.3 8.7 7.3
500000 8.1 10 7 28.8 31.0 26.0 19.9 20 19 44.8 47.5 39.5
1000000 8.3 10 7 61.1 68.0 55.0 20.9 21 20 91.2 97.0 81.0
1500000 8.4 11 7 92.2 103.3 83.3 21.6 22 21 142.2 150.0 123.3
2000000 8.3 10 7 122.0 136.0 110.0 21.9 22 21 188.6 198.0 172.0
Table 4.  Multicommodity network flow test
Dimension Iterations Time (msec) Iterations Time (msec)
$ n $ avg max min avg max min avg max min avg max min
QWMVA2 QWMVA
50000 5.9 8 4 1.1 1.3 0.9 5.9 8 4 1.1 1.2 0.8
100000 5.8 9 4 2.2 2.6 1.8 5.8 9 4 2.1 2.5 1.7
500000 6.1 9 4 12.2 14.0 10.0 6.1 9 4 11.5 13.5 9.0
1000000 6.2 9 4 27.1 32.0 21.0 6.2 9 4 25.5 30.0 19.0
1500000 6.1 11 4 44.1 51.7 35.0 6.1 11 4 42.0 50.0 33.3
2000000 6.2 8 4 59.5 68.0 48.0 6.2 8 4 56.8 66.0 44.0
Newton Secant
50000 5.9 8 4 1.9 2.4 1.2 14.2 18 9 3.0 3.9 1.9
100000 5.8 9 4 3.8 4.9 2.6 14.0 19 9 6.0 8.2 4.2
500000 6.1 9 4 22.7 30.5 14.5 14.2 19 9 32.4 43.5 23.5
1000000 6.2 9 4 46.9 64.0 29.0 14.2 19 9 64.5 87.0 40.0
1500000 6.1 11 4 69.1 95.0 43.3 14.0 21 10 95.6 145.0 66.7
2000000 6.1 8 4 92.7 124.0 58.0 14.2 16 11 128.1 148.0 98.0
Variable fixing Median search
50000 5.9 8 4 1.9 2.4 1.2 16.6 17 16 3.3 3.6 3.1
100000 5.8 9 4 3.7 4.7 2.5 17.7 18 17 6.5 6.9 6.1
500000 6.1 9 4 22.0 28.5 14.0 19.9 20 19 35.8 38.0 33.0
1000000 6.2 9 4 45.6 61.0 27.0 20.9 21 20 73.3 77.0 69.0
1500000 6.1 11 4 66.5 91.7 41.7 21.6 22 21 112.9 118.3 108.3
2000000 6.2 8 4 90.9 118.0 56.0 21.9 22 21 151.0 162.0 144.0
Dimension Iterations Time (msec) Iterations Time (msec)
$ n $ avg max min avg max min avg max min avg max min
QWMVA2 QWMVA
50000 5.9 8 4 1.1 1.3 0.9 5.9 8 4 1.1 1.2 0.8
100000 5.8 9 4 2.2 2.6 1.8 5.8 9 4 2.1 2.5 1.7
500000 6.1 9 4 12.2 14.0 10.0 6.1 9 4 11.5 13.5 9.0
1000000 6.2 9 4 27.1 32.0 21.0 6.2 9 4 25.5 30.0 19.0
1500000 6.1 11 4 44.1 51.7 35.0 6.1 11 4 42.0 50.0 33.3
2000000 6.2 8 4 59.5 68.0 48.0 6.2 8 4 56.8 66.0 44.0
Newton Secant
50000 5.9 8 4 1.9 2.4 1.2 14.2 18 9 3.0 3.9 1.9
100000 5.8 9 4 3.8 4.9 2.6 14.0 19 9 6.0 8.2 4.2
500000 6.1 9 4 22.7 30.5 14.5 14.2 19 9 32.4 43.5 23.5
1000000 6.2 9 4 46.9 64.0 29.0 14.2 19 9 64.5 87.0 40.0
1500000 6.1 11 4 69.1 95.0 43.3 14.0 21 10 95.6 145.0 66.7
2000000 6.1 8 4 92.7 124.0 58.0 14.2 16 11 128.1 148.0 98.0
Variable fixing Median search
50000 5.9 8 4 1.9 2.4 1.2 16.6 17 16 3.3 3.6 3.1
100000 5.8 9 4 3.7 4.7 2.5 17.7 18 17 6.5 6.9 6.1
500000 6.1 9 4 22.0 28.5 14.0 19.9 20 19 35.8 38.0 33.0
1000000 6.2 9 4 45.6 61.0 27.0 20.9 21 20 73.3 77.0 69.0
1500000 6.1 11 4 66.5 91.7 41.7 21.6 22 21 112.9 118.3 108.3
2000000 6.2 8 4 90.9 118.0 56.0 21.9 22 21 151.0 162.0 144.0
Table 5.  Results for the projection in SVM training. The values reported are the average number of iterations and the average computing time in milliseconds. For $ \textsf{BLGnapsack} $ only the time is reported
Set $ n $ QWMVA2 QWMVA Newton Secant BLG Var. Fixing
Iter. Time Iter. Time Iter. Time Iter. Time Time Iter. Time
UCI 1065 5.02 0.023 7.84 0.021 4.98 0.022 8.20 0.031 0.025 7.84 0.017
UCI 2265 5.28 0.061 8.55 0.061 5.28 0.081 9.03 0.109 0.093 8.55 0.066
UCI 3185 5.37 0.102 8.23 0.097 5.31 0.133 9.06 0.176 0.165 8.23 0.127
UCI 6370 5.51 0.249 8.67 0.248 5.44 0.316 9.46 0.445 0.402 8.67 0.363
UCI 12740 5.87 0.540 9.37 0.555 5.80 0.665 9.98 1.036 0.843 9.37 0.776
MNIST 800 3.32 0.018 5.72 0.022 3.14 0.015 6.77 0.016 0.012 5.72 0.017
MNIST 1600 3.56 0.038 5.94 0.045 3.31 0.029 7.01 0.033 0.029 5.94 0.035
MNIST 3200 3.65 0.092 6.37 0.111 3.45 0.068 7.11 0.074 0.103 6.37 0.098
MNIST 6400 3.56 0.189 6.73 0.231 3.47 0.161 7.25 0.170 0.222 6.73 0.260
MNIST 11702 3.74 0.357 7.39 0.438 3.59 0.322 7.32 0.344 0.398 7.39 0.525
Set $ n $ QWMVA2 QWMVA Newton Secant BLG Var. Fixing
Iter. Time Iter. Time Iter. Time Iter. Time Time Iter. Time
UCI 1065 5.02 0.023 7.84 0.021 4.98 0.022 8.20 0.031 0.025 7.84 0.017
UCI 2265 5.28 0.061 8.55 0.061 5.28 0.081 9.03 0.109 0.093 8.55 0.066
UCI 3185 5.37 0.102 8.23 0.097 5.31 0.133 9.06 0.176 0.165 8.23 0.127
UCI 6370 5.51 0.249 8.67 0.248 5.44 0.316 9.46 0.445 0.402 8.67 0.363
UCI 12740 5.87 0.540 9.37 0.555 5.80 0.665 9.98 1.036 0.843 9.37 0.776
MNIST 800 3.32 0.018 5.72 0.022 3.14 0.015 6.77 0.016 0.012 5.72 0.017
MNIST 1600 3.56 0.038 5.94 0.045 3.31 0.029 7.01 0.033 0.029 5.94 0.035
MNIST 3200 3.65 0.092 6.37 0.111 3.45 0.068 7.11 0.074 0.103 6.37 0.098
MNIST 6400 3.56 0.189 6.73 0.231 3.47 0.161 7.25 0.170 0.222 6.73 0.260
MNIST 11702 3.74 0.357 7.39 0.438 3.59 0.322 7.32 0.344 0.398 7.39 0.525
[1]

Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2331-2343. doi: 10.3934/jimo.2020071

[2]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075

[3]

Xin Zhao, Jinyan Fan. On subspace properties of the quadratically constrained quadratic program. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1625-1640. doi: 10.3934/jimo.2017010

[4]

Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871

[5]

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

[6]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[7]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[8]

Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052

[9]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653

[10]

Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125

[11]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[12]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

[13]

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

[14]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

[15]

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

[16]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

[17]

Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061

[18]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[19]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

[20]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]