Convex separable optimization is not much harder than linear optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Convex separable optimization is not much harder than linear optimization

Full text

Pdf (1.43 MB)

Source

Journal of the ACM (JACM) archive
Volume 37 , Issue 4 (October 1990) table of contents

Pages: 843 - 862

Year of Publication: 1990

ISSN:0004-5411

Authors

D. S. Hochbaum	Univ. of California, Berkeley
J. George Shanthikumar	Univ. of California, Berkeley

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 132, Citation Count: 16

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/96559.96597 What is a DOI?

ABSTRACT

The polynomiality of nonlinear separable convex (concave) optimization problems, on linear constraints with a matrix with “small” subdeterminants, and the polynomiality of such integer problems, provided the inteter linear version of such problems ins polynomial, is proven. This paper presents a general-purpose algorithm for converting procedures that solves linear programming problems. The conversion is polynomial for constraint matrices with polynomially bounded subdeterminants. Among the important corollaries of the algorithm is the extension of the polynomial solvability of integer linear programming problems with totally unimodular constraint matrix, to integer-separable convex programming. An algorithm for finding a &egr;-accurate optimal continuous solution to the nonlinear problem that is polynomial in log(1/&egr;) and the input size and the largest subdeterminant of the constraint matrix is also presented. These developments are based on proximity results between the continuous and integral optimal solutions for problems with any nonlinear separable convex objective function. The practical feature of our algorithm is that is does not demand an explicit representation of the nonlinear function, only a polynomial number of function evaluations on a prespecified grid.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	W Cook , A M H Gerards , A Schrijver , É Tardos, Sensitivity theorems in integer linear programming, Mathematical Programming: Series A and B, v.34 n.3, p.251-264, April 1986 [doi>10.1007/BF01582230]
	2	DANTZIG, G. B. Linear Programming and Extensions. Princeton University Press, Princeton, N.J., 1963.
	3	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	4	A. Frank , Éva Tardos, An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, v.7 n.1, p.49-65, Jan. 1987 [doi>10.1007/BF02579200]
	5	GRANOT, F., AND SKORIN-KAPOV, J. Some proximity and sensitivity results in quadratic integer programming. Working Paper No. 1207. Univ. British Columbia, Vancouver, British Columbia, Canada, 1986.
	6	HELGASON, R., KENINGTON, J., AND LALL, H. A polynomially bounded algorithm for a singly constrained quadratic program. Math. Prog. 18 (1980), 338-343.
	7	HOCHaAUM, D.S. Optimal algorithms for the allocation problem and its extensions. Manuscript, Univ. California, Berkeley, Berkeley, Calif., 1989.
	8	Dorit S. Hochbaum , Ron Shamir , J. George Shanthikumar, A polynomial algorithm for an integer quadratic non-separable transportation problem, Mathematical Programming: Series A and B, v.55 n.3, p.359-371, July 6, 1992 [doi>10.1007/BF01581207]
	9	HOFFMAN, A., AND WOLFE, P. Minimizing a unimodal function of two integer variables. Math. Prog. Studies 25 (1985), 76-87.
	10	JEROSLOW, R. G. There cannot be any algorithm for integer programming with quadratic constraints. Op. Res. 21 (1973), 221-224.
	11	LAUGHHUNN, D. J. Quadratic binary programming with applications to capital budgeting problems. Op. Res. 10 (1970), 454-467.
	12	LENSTRA, JR., H.W. Integer programming with a fixed number of variables. Math. Op. Res. 8, 4 (1983), 508-548.
	13	LUSS, H., AND GUPTA, S. Allocation of effort resources among competing activities. Op. Res. 23 (1975), 360-366.
	14	MCCALLUM, JR., C.J. An algorithm for certain quadratic integer programs. Bell Labs Tech. Rep., Bell Laboratories, Holmdel, N.J. (undated, referred to in {6}).
	15	MINOUX, M. A polynomial algorithm for minimum quadratic cost flow problems. Europ. J. Op. Res. 18 (1984), 377-387.
	16	MINotJx, M. Solving integer minimum cost flows with separable convex cost objective polynomially. Math. Prog. Study 26 (1986), 237-239.
	17	MONTEIRO, R. C., AND ADLER, I. An extension of Karmarkar-type algorithm to a class of convex separable programming problems with global linear rate of convergence. Manuscript, Univ. California, Berkeley, Berkeley, Calif., ESRC 87-4, Oct. 1987.
	18	NEMIROVSKY, A. S., AND YUDIN, D. D. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983.
	19	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	20	SHAKED, M., AND SHANTHIKUMAR, J. G. Parametric stochastic convexity and concavity of stochastic processes. Ann. Inst. Stat. Math., to appear.
	21	Eva Tardos, A strongly polynomial algorithm to solve combinatorial linear programs, Operations Research, v.34 n.2, p.250-256, March-April 1986 [doi>10.1287/opre.34.2.250]
	22	YAO, D. O., AND SHANTHIKUMAR, J.G. The optimal input rates to a system of manufacturing cells. INFOR 25 (1987), 57-65.
	23	ZIPKIN, P. Simple ranking methods for allocation of one resource. Manage. Sci. 26 (1980), 34-43.

CITED BY 16

	Yumin Zhang , Xiaobo Sharon Hu , Danny Z. Chen, Task scheduling and voltage selection for energy minimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Tetsuo Asano , Naoki Katoh , Koji Obokata , Takeshi Tokuyama, Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.896-904, January 06-08, 2002, San Francisco, California
	Dorit S. Hochbaum, An efficient algorithm for image segmentation, Markov random fields and related problems, Journal of the ACM (JACM), v.48 n.4, p.686-701, July 2001
	Alexander V. Karzanov , S. Thomas McCormick, Polynomial methods for separable convex optimization in unimodular spaces, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.78-87, January 22-24, 1995, San Francisco, California, United States
	Satoru Iwata, A capacity scaling algorithm for convex cost submodular flows, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.482-489, January 28-30, 1996, Atlanta, Georgia, United States
	Ravindra K. Ahuja , Dorit S. Hochbaum , James B. Orlin, Solving the Convex Cost Integer Dual Network Flow Problem, Management Science, v.49 n.7, p.950-964, July 2003
	Wuqin Lin , Zhen Liu , Cathy H. Xia , Li Zhang, Cost minimization of multi-tiered e-business infrastructure with end-to-end delay guarantees, ACM SIGMETRICS Performance Evaluation Review, v.32 n.2, September 2004
	Lap-Fai Leung , Chi-Ying Tsui , Wing-Hung Ki, Minimizing energy consumption of multiple-processors-core systems with simultaneous task allocation, scheduling and voltage assignment, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.647-652, January 27-30, 2004, Yokohama, Japan
	Vishal Khandelwal , Ankur Srivastava, Active mode leakage reduction using fine-grained forward body biasing strategy, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA
	Wuqin Lin , Zhen Liu , Cathy H. Xia , Li Zhang, Optimal capacity allocation for web systems with end-to-end delay guarantees, Performance Evaluation, v.62 n.1-4, p.400-416, October 2005
	Randeep Bhatia , Adrian Segall , Gil Zussman, Analysis of bandwidth allocation algorithms for wireless personal area networks, Wireless Networks, v.12 n.5, p.589-603, September 2006
	V. Khandelwal , A. Srivastava, Leakage control through fine-grained placement and sizing of sleep transistors, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.533-536, November 07-11, 2004
	Wei Jiang , Zhiru Zhang , Miodrag Potkonjak , Jason Cong, Scheduling with integer time budgeting for low-power optimization, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Shu Huang , Rudra Dutta, Spare capacity provisioning for quasi-static traffic, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.18, p.5011-5035, December, 2007
	D. Li , X. L. Sun , J. Wang , K. I. Mckinnon, Convergent Lagrangian and domain cut method for nonlinear knapsack problems, Computational Optimization and Applications, v.42 n.1, p.67-104, January 2009
	Vishal Khandelwal , Ankur Srivastava, Active mode leakage reduction using fine-grained forward body biasing strategy, Integration, the VLSI Journal, v.40 n.4, p.561-570, July, 2007