This article is cited in 12 papers

Algorithms for approximate calculation of the minimum of a convex function from its values

V. Yu. Protasov

M. V. Lomonosov Moscow State University

Abstract: The paper deals with a numerical minimization problem for a convex function defined on a convex $n$-dimensional domain and continuous (but not necessarily smooth). The values of the function can be calculated at any given point. It is required to find the minimum with desired accuracy. A new algorithm for solving this problem is presented, whose computational complexity as $n\to\infty$ is considerably less than that of similar algorithms known to the author. In fact, the complexity is improved from $Cn^7\ln^2(n+1)$ [4] to $Cn^2\ln(n+1)$.

UDC: 517

Received: 18.04.1994

DOI: 10.4213/mzm1697

 English version: Mathematical Notes, 1996, 59:1, 69–74

Bibliographic databases:

• 
• 
•