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 and 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. 

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10]

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

[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.

[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.

[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.

[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.

[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.

[16]

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

[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.

[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.

[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.

[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.

[21]

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

[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.

[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.

[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/

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[37]

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

[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.

[39]

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

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. 

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10]

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

[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.

[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.

[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.

[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.

[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.

[16]

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

[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.

[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.

[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.

[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.

[21]

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

[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.

[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.

[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/

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[37]

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

[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.

[39]

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

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 and 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 and 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 and 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 and 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 and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064

[6]

Ling Zhang, Xiaoqi Sun. Stability analysis of time-varying delay neural network for convex quadratic programming with equality constraints and inequality constraints. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022035

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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 and Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125

[12]

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

[13]

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

[14]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[15]

Yue Qi, Tongyang Liu, Su Zhang, Yu Zhang. Robust Markowitz: Comprehensively maximizing Sharpe ratio by parametric-quadratic programming. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021235

[16]

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 and Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

[17]

Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83

[18]

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

[19]

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

[20]

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 and Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

 Impact Factor: 

Metrics

  • PDF downloads (136)
  • HTML views (118)
  • Cited by (0)

Other articles
by authors

[Back to Top]