Electronic Issue "Scientific Research"

A minimization problem with strictly convex separable objective function subject to a convex separable inequality constraint of the form "less than or equal to" and bounds on the variables is considered. Necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. An iterative algorithm of polynomial complexity for solving such problems is suggested and its convergence is proved. Modifications of this algorithm are proposed in connection with some extensions of the considered problem as well as in order to avoid some computational difficulties. Examples of important convex functions for the problem under consideration and computational results are presented.

[1] P. Berman, N. Kovoor, and P.M. Pardalos, Algorithms for the least distance problem, in: Complexity in Numerical Optimization, P.M. Pardalos (Ed.), World Scientific, New Jersey, 1993, pp. 33-56. [2] D.P. Bertsekas, Projected Newton methods for optimization problems with simple constraints, SIAM J. Control Optim. 20 (1982) 221-246. [3] G.R. Bitran, A.C. Hax, Disaggregation and resource allocation using convex knapsack problems with bounded variables, Management Sci. 27 (1981), No. 4, 431-441. [4] J.R. Brown, Bounded knapsack sharing, Math. Program. 67 (1994), No. 3, 343 - 382. [5] P. Brucker, An O(n) algorithm for quadratic knapsack problems, Oper. Res. Lett. 3 (1984), No. 3, 163-166. 18 [6] P.H. Calamai, J.J. Morґe, Quasi-Newton updates with bounds, SIAM J. Numer. Anal. 24 (1987), No. 6, 1434-1441. [7] A. Charnes, W.W. Cooper, The theory of search: optimum distribution of search effort, Management Sci. 5 (1958), 44-50. [8] R.W. Cottle, S.G. Duval, K. Zikan, A Lagrangean relaxation algorithm for the constrained matrix problem, Naval Res. Logist. Quart. 33 (1986), No. 1, 55-76. [9] R.S. Dembo, U. Tulowitzki, On the minimization of quadratic functions subject to box constraints, Working Paper Series B 71, School of Organization and Management, Yale University, New Haven, 1983. [10] J.-P. Dussault, J.A. Ferland, B. Lemaire, Convex quadratic programming with one constraint and bounded variables, Math. Program. 36 (1986), No. 1, 90-104. [11] J.A. Ferland, B. Lemaire, P. Robert, Analytic solutions for nonlinear programs with one or two equality constraints, Publication 285, Departement d'informatique et de recherche operationnelle, Universitґe de Montrґeal, Montrґeal, 1978. [12] S.M. Grzegorski, Orthogonal projections on convex sets for Newton-like methods, SIAM J. Numer. Anal. 22 (1985), 1208-1219. [13] M. Held, P. Wolfe, H.P. Crowder, Validation of subgradient optimization, Math. Program. 6 (1974), 62-88. [14] R. Helgason, J. Kennington, H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program, Math. Program. 18 (1980), No. 3, 338-343. [15] G.T.Herman, A.Lent, A family of iterative quadratic optimization algorithms for pairs of inequalities, with application in diagnostic radiology, Math. Program. Study 9 (1978), 15-29. [16] N. Katoh, T. Ibaraki, H. Mine, A polynomial time algorithm for the resource allocation problem with a convex objective function, J. Oper. Res. Soc. 30 (1979), No. 5, 449-455. [17] H. Luss, S.K. Gupta, Allocation of effort resources among competing activities, Oper. Res. 23 (1975), No. 2, 360-366. [18] R.K. McCord, Minimization with one linear equality constraint and bounds on the variables, Technical Report SOL 79-20, System Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, 1979. [19] C. Michelot, A finite algorithm for finding the projection of a point onto the canonical simplex of IRn, J. Optim. Theory Appl. 50 (1986), No. 1, 195-200. [20] J.J. Morґe, G. Toraldo, Algorithms for bound constrained quadratic programming problems, Numer. Math. 55 (1989), No. 4, 377-400. [21] J.J. Morґe, S.A. Vavasis, On the solution of concave knapsack problems, Math. Program. 49 (1991), No. 3, 397-411. [22] P.M. Pardalos, N. Kovoor, An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds, Math. Program. 46 (1990), No. 3, 321-328. 19 [23] P.M.Pardalos, Y. Ye, C.-G. Han, Algorithms for the solution of quadratic knapsack problems, Linear Algebra Appl. 152 (1991), 69-91. [24] A.G. Robinson, N. Jiang, C.S. Lerme, On the continuous quadratic knapsack problem, Math. Program. 55 (1992), No. 1, 99-108. [25] R.T. Rockafellar, R.J.-B. Wets, A note about projections in the implementation of stochastic quasigradient methods, in: Numerical Techniques for Stochastic Optimization, Yu. Ermoliev, R.J.- B. Wets (Eds.), Springer Verlag, Berlin, 1988, pp. 385-392. [26] S.M. Stefanov, On the implementation of stochastic quasigradient methods to some facility location problems, Yugosl. J. Oper. Res., 10 (2000), No. 2, 235-256. [27] S.M. Stefanov, Convex separable minimization subject to bounded variables, Comput. Optim. Appl. 18 (2001), No. 1, 27-48. [28] S.M. Stefanov, Convex quadratic minimization subject to a linear constraint and box constraints, Appl. Math. Res. Express 2004 (2004), No. 1, 17-42. [29] S.M. Stefanov, Polynomial algorithms for projecting a point onto a region defined by a linear constraint and box constraints in IRn, J. Appl. Math. 2004 (2004), No. 5, 409-431. [30] S.M. Stefanov, Convex separable minimization problems with a linear constraint and bounded variables, Int. J. Math. Math. Sci. 2005 (2005), No. 9, 1339-1363. [31] S.M. Stefanov, An efficient method for minimizing a convex separable logarithmic function subject to a convex inequality constraint or linear equality constraint, J. Appl. Math. Decis. Sci. 2006 (2006), No. 1, Article ID 89307, 1-19. [32] S.M. Stefanov, Minimizing a convex separable exponential function subject to linear equality constraint and bounded variables, J. Interdiscip. Math. 9 (2006), No. 1, 207-226. [33] S.M. Stefanov, Minimization of a convex linear-fractional separable function subject to a convex inequality constraint or linear inequality constraint and bounds on the variables, Appl. Math. Res. Express 2006 (2006), No. 2, Article ID 36581, 1-24. [34] S.M. Stefanov, Minimization of a strictly convex separable function subject to a convex inequality constraint or linear equality constraints and bounds on the variables, Sci. Res. 5 (2007) 1-10. [35] S.A. Vavasis, Local minima for indefinite quadratic knapsack problems, Math. Program. 54 (1992), No. 2, 127-153. [36] P. Wolfe, Algorithm for a least-distance programming problem, Math. Program. Study 1 (1974), 190-205. [37] P.H. Zipkin, Simple ranking methods for allocation of one resource, Management Sci. 26 (1980), No. 1, 34-43.