ISSN:
1436-4646
Keywords:
Algorithms for optimization
;
Descent methods
;
Minimax
;
Non-differentiable-optimization
;
Optimization
;
Steepest descent
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract This paper contains basic results that are useful for building algorithms for the optimization of Lipschitz continuous functionsf on compact subsets of E n . In this settingf is differentiable a.e. The theory involves a set-valued mappingx→δ ∈ f(x) whose range is the convex hull of existing values of ∇f and limits of ∇f on a closed∈-ball,B(x, ∈). As an application, simple descent algorithms are formulated that generate sequence {x k } whose distance from some stationary set (see Section 2) is 0, and where {f(x k )} decreases monotonously. This is done with the aid of anyone of the following three hypotheses: For∈ arbitrarily small, a point is available that in arbitrarily close to: (1) the minimizer off onB(x, ∈), (2) the closest point inδ ∈ f(x) to the origin, (3) ϕ(h) ∈ δ ∈ f(x), where [ϕ(h), h] = max {[ϕ, h]: ϕ ∈ δ ∈ f(x)}. Observe that these three problems are simplified iff has a tractable local approximation. The minimax problem is taken as an example, and algorithms for it are sketched. For this example, all three hypotheses may be satisfied. A class of functions called uniformly-locally-convex is introduced that is also tractable.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01584320
Permalink
