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

Normal conical algorithm for concave minimization over polytopes

Published: 01 July 1991 Publication History

Abstract

A new conical algorithm is developed for finding the global minimum of a concave function over a polytope. To ensure faster convergence and overcome some major drawbacks of previous conical algorithms, a normal (rather than exhaustive) subdivision process is used.

References

[1]
S. Bali, "Minimization of a concave function on a bounded convex polyhedron," Ph.D. Dissertation, University of California (Los Angeles, A, 1973).
[2]
V.P. Bulatov, <i>Metody Pogrujeniia v Zadatehak Optimizatsii</i> (Nauka, Sibirskoe Otdelenie, Novosibirsk, 1977).
[3]
M. Hamami and S.E. Jacobsen, "Exhaustive nondegenerate conical processes for concave minimization on convex polytopes," <i>Mathematics of Operations Research</i> 13 (1988) 479-487.
[4]
R. Horst, "An algorithm for nonconvex programming problems," <i>Mathematical Programming</i> 10 (1976) 312-321.
[5]
R. Horst, "On the global minimization of concave functions: Introduction and survey," <i>Operations Research Spektrum</i> 6 (1984) 195-205.
[6]
R. Horst and Ng.V. Thoai, "Implementation, modification and comparison of some algorithms for concave minimization problems," Preprint, Department of Mathematics, University of Trier (1988), to appear in: <i>Computing.</i>
[7]
S.E. Jacobsen, "Convergence of a Tuy-type algorithm for concave minimization subject to linear constraints," <i>Applied Mathematics and Optimization</i> 7 (1981) 1-9.
[8]
P.M. Pardalos and J.B. Rosen, "Methods for global concave minimization: a bibliographic survey," <i>SIAM Review</i> 26 (1986) 367-379.
[9]
Ng.V. Thoai and H. Tuy, "Convergent algorithm for minimizing a concave function," <i>Mathematics of Operations Research</i> 5 (1980) 556-566.
[10]
Ng.V. Thoai and J. de Vries, "Numerical experiments on concave minimization algorithms," to appear in: <i>Methods of Operations Research.</i>
[11]
H. Tuy, "Vognutoe programmirovaniie pri Iineinyk ogranitchenyakh," <i>Doklady AN SSSR</i> 158 (1964) 32-35. [Translated as: "Concave programming under linear constraints," <i>Soviet Mathematics</i> 5 (1964) 1437-1440.]
[12]
H. Tuy, T.V. Thieu and Ng.Q. Thai, "A conical algorithm for globally minimizing a concave function over a closed convex set," <i>Mathematics of Operations Research</i> 10 (1985) 498-514.
[13]
H. Tuy, V. Khachaturov and S. Utkin, "A class of exhaustive cone splitting procedures in conical algorithms for concave minimization," <i>Optimization</i> 18 (1987) 791-808.
[14]
H. Tuy, "A general deterministic approach to global optimization via D.C. programming," in: J.B. Hiriari-Urruty, ed., <i>Fermat Days 1985: Mathematics for Optimization. Mathematics Studies Series</i> (North-Holland, Amsterdam, 1986).
[15]
H. Tuy, "On polyhedral annexation method for concave minimization," submitted for publication.
[16]
H. Tuy and R. Horst, "Convergence and restart in branch and bound algorithms for global optimization algorithms," <i>Mathematical Programming</i> 41 (1988) 161-184.
[17]
P.B. Zwart, "Nonlinear Programming: counterexamples to two global optimization algorithms," <i>Operations Research</i> 21 (1973) 1260-1266.
[18]
P.B. Zwart, "Global maximization of a convex function with linear inequality constraints," <i>Operations Research</i> 22 (1974) 602-609.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B
Mathematical Programming: Series A and B  Volume 51, Issue 1-3
July 1991
408 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 1991

Author Tags

  1. Concave minimization
  2. bisection
  3. conical algorithm
  4. convergence condition
  5. normal subdivision process

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2016)A generalization of ω-subdivision ensuring convergence of the simplicial algorithmComputational Optimization and Applications10.1007/s10589-015-9817-664:2(535-555)Online publication date: 1-Jun-2016
  • (2015)A convergent conical algorithm with ω-bisection for concave minimizationJournal of Global Optimization10.1007/s10898-014-0197-861:2(203-220)Online publication date: 1-Feb-2015
  • (2014)On the exhaustivity of simplicial partitioningJournal of Global Optimization10.1007/s10898-013-0040-758:1(189-203)Online publication date: 1-Jan-2014
  • (2010)Outer approximation algorithms for canonical DC problemsJournal of Global Optimization10.1007/s10898-009-9415-146:2(163-189)Online publication date: 1-Feb-2010
  • (2007)Pivot, Cut, and DiveJournal of Heuristics10.1007/s10732-007-9021-713:5(471-503)Online publication date: 1-Oct-2007
  • (2001)On the Convergence of Cone Splitting Algorithms with ω-SubdivisionsJournal of Optimization Theory and Applications10.1023/A:1017595513275110:1(119-144)Online publication date: 1-Jul-2001
  • (2000)On Convergence of the Simplicial Branch-and-Bound Algorithm Based on ź-SubdivisionsJournal of Optimization Theory and Applications10.5555/3222369.3222892107:1(69-79)Online publication date: 1-Oct-2000
  • (2000)Finite Exact Branch-and-Bound Algorithms for Concave Minimization over PolytopesJournal of Global Optimization10.1023/A:100832443047118:2(107-128)Online publication date: 1-Oct-2000
  • (1999)How to Extend the Concept of Convexity Cuts to Derive Deeper Cutting PlanesJournal of Global Optimization10.1023/A:100831522975015:4(371-404)Online publication date: 1-Dec-1999
  • (1998)A Simplified Convergence Proof for the Cone Partitioning AlgorithmJournal of Global Optimization10.1023/A:100832550794913:4(407-416)Online publication date: 1-Dec-1998

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media