SpringerLink
Log in

Fast algorithm for singly linearly constrained quadratic programs with box-like constraints

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

This paper focuses on a singly linearly constrained class of convex quadratic programs with box-like constraints. We propose a new fast algorithm based on parametric approach and secant approximation method to solve this class of quadratic problems. We design efficient implementations for our proposed algorithm and compare its performance with two state-of-the-art standard solvers called Gurobi and Mosek. Numerical results on a variety of test problems demonstrate that our algorithm is able to efficiently solve the large-scale problems with the dimension up to fifty million and it substantially outperforms Gurobi and Mosek in terms of the running time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

References

  1. Boyd, S., Diaconis, P., **ao, L.: Fastest mixing Markov chain on a graph. SIAM Rev. 46, 667–689 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Boyd, S., Diaconis, P., Parrilo, P.A., **ao, L.: Fastest mixing Markov chain on graphs with symmetries. SIAM J. Optim. 20, 792–819 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bitran, G.R., Hax, A.C.: Disaggregation and resource allocation using convex knapsack problems with bounded variables. Manag. Sci. 27, 431–441 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  4. Brucker, P.: An \(O(n)\) algorithm for quadratic knapsack problems. Oper. Res. Lett. 3, 163–166 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  5. Calamai, P.H., Moré, J.J.: Quasi-Newton updates with bounds. SIAM J. Numer. Anal. 24, 1434–1441 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  6. Cominetti, R., Mascarenhas, W.F., Silva, P.J.S.: A Newtons method for the continuous quadratic knapsack problem. Math. Progr. Comput. 6, 151–169 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cosares, S., Hochbaum, D.S.: Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources. Math. Oper. Res. 19, 94–111 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  8. Dai, Y.-H., Fletcher, R.: New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math. Progr. 106, 403–421 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Davis, T.A., Hager, W.W., Hungerford, J.T.: An efficient hybrid algorithm for the separable convex quadratic knapsack problem. ACM Trans. Math. Softw. 30(3), 377–380 (2004)

    Article  MathSciNet  Google Scholar 

  10. Ding, C., Sun, D.F., Toh, K.-C.: An introduction to a class of matrix cone programming. Math. Progr. 144, 141–179 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, http://www.gurobi.com (2015)

  12. Helgason, R., Kennington, J., Lall, H.: A polynomially bounded algorithm for a singly constrained quadratic program. Math. Progr. 18, 338–343 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hochbaum, D.S., Hong, S.-P.: About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Progr. 69, 269–309 (1995)

    MathSciNet  MATH  Google Scholar 

  14. Kiwiel, K.C.: On linear-time algorithms for the continuous quadratic knapsack problem. J. Optim. Theory Appl. 134, 549–554 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kiwiel, K.C.: Breakpoint searching algorithms for the continuous quadratic knapsack problem. Math. Progr. 112, 473–491 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kiwiel, K.C.: Variable fixing algorithms for the continuous quadratic knapsack problem. J. Optim. Theory Appl. 136, 445–458 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  17. Liu, Y.-J., Wang, S.Y., Sun, J.H.: Finding the projection onto the intersection of a closed half-space and a variable box. Oper. Res. Lett. 41, 259–264 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  18. Maculan, N., Santiago, C.P., Macambira, E.M., Jardim, M.H.C.: 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, 553–574 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  19. Moreau, J.J.: Décomposition orthogonale d’un espace hibertien selon deux cones mutuellement polaires. C. R. Acad. Sci. 255, 238–240 (1962)

    MATH  Google Scholar 

  20. MOSEK ApS, The MOSEK Optimization Toolbox for MATLAB Manual. Version 7.1 (Revision 28), http://docs.mosek.com/7.1/toolbox/index.html (2015)

  21. Pardalos, P.M., Kovoor, N.: An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds. Math. Progr. 46, 321–328 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  22. Robinson, A.G., Jiang, N., Lerme, C.S.: On the continuous quadratic knapsack problem. Math. Progr. 55, 99–108 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Wu, B., Ding, C., Sun, D.F., Toh, K.-C.: On the Moreau–Yoshida regularization of the vector \(k\)-norm related functions. SIAM J. Optim. 24, 766–794 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  24. Zarantonello, E.H.: Projections on convex sets in Hilbert space and spectral theory I and II. In: Zarantonello, E.H. (ed.) Contributions to Nonlinear Functional Analysis, pp. 237–424. Academic Press, New York (1971)

    Chapter  Google Scholar 

Download references

Acknowledgments

We are grateful to the reviewers for constructive comments, which greatly improved the quality of this paper. We also thank Zaiwen Wen at Peking University for suggesting us to compare our algorithm with Gurobi and Mosek solvers. M. Liu: The author’s research is supported by the National Natural Science Foundation of China under Grant 11371255. Y. -J. Liu: The author’s research is supported by the National Natural Science Foundation of China under Grants 11001180 and 11371255, the Program for Liaoning Excellent Talents in University under Grant LR2015047, and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.

Author information

Authors and Affiliations

  1. School of Science, Shenyang Aerospace University, Shenyang, 110136, People’s Republic of China

    Meijiao Liu & Yong-** Liu

Authors
  1. Meijiao Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yong-** Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yong-** Liu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, M., Liu, YJ. Fast algorithm for singly linearly constrained quadratic programs with box-like constraints. Comput Optim Appl 66, 309–326 (2017). https://doi.org/10.1007/s10589-016-9863-8

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-016-9863-8

Keywords

Mathematics Subject Classification

Search

Navigation