×

Convex programming with single separable constraint and bounded variables. (English) Zbl 1278.90308

Summary: A minimization problem with convex objective function subject to a separable convex inequality constraint ”\(\leq\)” 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 \(\geq\) constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.

MSC:

90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

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. · Zbl 0454.90059 · doi:10.1287/mnsc.27.4.431
[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. · Zbl 1025.90038 · doi:10.1023/A:1021561204463
[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. · Zbl 1134.90459 · doi:10.1023/B:JOGO.0000006654.34226.fe
[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. · Zbl 0886.90130
[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. · Zbl 1040.90565 · doi:10.1023/A:1008675917367
[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. · Zbl 0633.90057 · doi:10.1007/BF02591992
[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. · Zbl 0911.90301 · doi:10.1137/S1052623493253991
[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. · Zbl 0906.90138 · doi:10.1023/A:1018990014974
[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. · Zbl 0452.90054 · doi:10.1007/BF01588328
[10] H. Luss and S.K. Gupta, ”Allocation of effort resources among competing activities,” Oper. Res., vol.23, pp. 360–366, 1975. · Zbl 0298.90015 · doi:10.1287/opre.23.2.360
[11] K.G. Murty, Linear and Combinatorial Programming, John Wiley & Sons, INC: New York-London-Sydney-Toronto, 1976. · Zbl 0334.90032
[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. · Zbl 0711.90061 · doi:10.1007/BF01585748
[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. · Zbl 0664.90067
[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. · Zbl 1061.90090 · doi:10.1023/B:COAP.0000013060.16224.31
[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. · Zbl 1029.90517
[16] S.M. Stefanov, ”Convex separable minimization subject to bounded variables,” Comput. Optim. Applic., vol. 18, no.1, pp. 27–48, 2001a. · Zbl 0963.90048 · doi:10.1023/A:1008739510750
[17] S.M. Stefanov, Separable Programming. Theory and Methods. Kluwer Academic Publishers: Dordrecht-Boston-London, 2001b.
[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. · Zbl 1141.90497
[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. · Zbl 1137.90010 · doi:10.1007/s10107-004-0550-7
[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. · Zbl 1127.90413
[21] Zi-L. Wei, ”Subspace search method for quadratic programming with box constraints,” J. Comput. Math., vol. 17, no. 3, pp. 307–314, 1999. · Zbl 0937.65067
[22] P.H. Zipkin, ”Simple ranking methods for allocation of one resource,” Manag. Sci., vol. 26, pp. 34–43, 1980. · Zbl 0448.90049 · doi:10.1287/mnsc.26.1.34
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.