[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Convex programming with single separable constraint and bounded variables

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

Abstract

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. G.R. Bitran and A.C. Hax, “Disaggregation and resource allocation using convex knapsack problems with bounded variables,” Management Science, vol. 27, pp. 431–441, 1981.

    MathSciNet  MATH  Google Scholar 

  2. O.P. Burdakov, J.M. Martínez, and E.A. Pilotta, “A limited-memory multipoint symmetric secant method for bound constrained optimization,” Ann. Oper. Res., vol. 117, pp. 51–70, 2002.

    Article  MathSciNet  MATH  Google Scholar 

  3. P.L. De Angelis, I.M. Bomze, and G. Toraldo, “Ellipsoidal approach to box-constrained quadratic problems,” J Global Optim., vol. 28, pp. 1–15, 2004.

    Article  MathSciNet  MATH  Google Scholar 

  4. P.L. De Angelis, P.M. Pardalos, and G. Toraldo, “Quadratic programming with box constraints,” in Developments in Global Optimization I.M. Bomze, T. Csendes, R. Horst, and P.M. Pardalos (eds.), Kluwer Academic Publishers, pp. 73–93 1997.

  5. G. Di Pillo, S. Lucidi, L. Palagi, “A shifted-barrier primal-dual algorithm model for linearly constrained optimization problems,” Comput. Optim. Applic., vol. 12, pp. 157–188, 1999.

    Article  MathSciNet  MATH  Google Scholar 

  6. J.P. Dussault, J. Ferland, and B. Lemaire, “ Convex quadratic programming with one constraint and bounded variables,” Math. Program., vol. 36, pp. 90–104, 1986.

    MathSciNet  MATH  Google Scholar 

  7. F. Facchinei, J. Júdice, and J. Soares, “An active set Newton algorithm for large-scale non-linear programs with box constraints,” SIAM J. Optim., vol. 8, no. 1, pp. 158-186, 1998.

    Article  MathSciNet  MATH  Google Scholar 

  8. L. Fernandes, A. Fischer, J. Júdice, C. Requejo, and J. Soares, “A block active set algorithm for large-scale quadratic programming with box constraints,” Ann Oper. Res., vol. 81, pp.75-95, 1998.

    Article  MathSciNet  MATH  Google Scholar 

  9. R. Helgason, J. Kennington, and H. Lall, “A polynomially bounded algorithm for a singly constrained quadratic program,” Math. Program., vol. 18, no.3, pp. 338–343, 1980.

    Article  MathSciNet  MATH  Google Scholar 

  10. H. Luss and S.K. Gupta, “Allocation of effort resources among competing activities,” Oper. Res., vol.23, pp. 360–366, 1975.

    Article  MathSciNet  MATH  Google Scholar 

  11. K.G. Murty, Linear and Combinatorial Programming, John Wiley & Sons, INC: New York-London-Sydney-Toronto, 1976.

    MATH  Google Scholar 

  12. P.M. Pardalos and N. Kovoor,“An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds,” Math. Program., vol. 46, pp. 321–328, 1990.

    Article  MathSciNet  MATH  Google Scholar 

  13. R.T. Rockafellar and R.J.-B. Wets, “A note about projections in the implementations of stochastic quasigradient methods,” in Numerical Techniques for Stochastic Optimization Yu. Ermoliev and R.J.-B. Wets (eds.), Springer Verlag: Berlin, 1988, pp. 385-392.

    Google Scholar 

  14. Song Xu, “A non-interior path following method for convex quadratic programming problems with bound constraints,” Comput. Optim. Applic., vol. 27, pp. 285–303, 2004.

    Article  MATH  Google Scholar 

  15. S.M. Stefanov, “On the implementation of stochastic quasigradient methods to some facility location problems,” Yugoslav J. Oper. Res., vol.10, no. 2, pp. 235–256, 2000.

    MathSciNet  MATH  Google Scholar 

  16. S.M. Stefanov, “Convex separable minimization subject to bounded variables,” Comput. Optim. Applic., vol. 18, no.1, pp. 27–48, 2001a.

    Article  MathSciNet  MATH  Google Scholar 

  17. S.M. Stefanov, Separable Programming. Theory and Methods. Kluwer Academic Publishers: Dordrecht-Boston-London, 2001b.

    MATH  Google Scholar 

  18. S.M. Stefanov, “Convex quadratic minimization subject to a linear constraint and box constraints,” Appli. Math. Res. eXpress, no.1, pp. 17–42, 2004.

  19. D. Vandenbussche and G.L. Nemhauser, “A branch-and-cut algorithm for nonconvex quadratic programs with box constraints,” Math. Program. Ser. A, vol. 102, no. 3, pp. 559–575, 2005.

    Article  MathSciNet  MATH  Google Scholar 

  20. J.L. Wang, M.W. Zhang, and T.S. Du, “A primal-dual infeasible interior point algorithm for separable convex quadratic programming with box constraints,” J. Hebei Normal University, Natural Science Edition, vol. 26, no. 6, pp. 568–572, 587, 2002.

  21. Zi-L. Wei, “Subspace search method for quadratic programming with box constraints,” J. Comput. Math., vol. 17, no. 3, pp. 307–314, 1999.

    MathSciNet  MATH  Google Scholar 

  22. P.H. Zipkin, “Simple ranking methods for allocation of one resource,” Manag. Sci., vol. 26, pp. 34–43, 1980.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Panjab University, Chandigarh, 160014, India

    Kalpana Dahiya & Vanita Verma

  2. Department of Mathematics, Miranda House, University of Delhi, Delhi, 110007, India

    Surjeet Kaur Suneja

Authors
  1. Kalpana Dahiya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Surjeet Kaur Suneja
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vanita Verma
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kalpana Dahiya.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dahiya, K., Suneja, S.K. & Verma, V. Convex programming with single separable constraint and bounded variables. Comput Optim Applic 36, 67–82 (2007). https://doi.org/10.1007/s10589-006-0396-4

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-006-0396-4

Keywords

Search

Navigation