Browse Prior Art Database

Optimization Algorithm for Nondifferentiable Functions

IP.com Disclosure Number: IPCOM000082922D
Original Publication Date: 1975-Feb-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 2 page(s) / 29K

Publishing Venue

IBM

Related People

Wolfe, PS: AUTHOR

Abstract

Herein described is a computationally feasible algorithm with guaranteed convergence for the minimization of a convex, but not necessarily differentiable, function of several variables.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 78% of the total text.

Page 1 of 2

Optimization Algorithm for Nondifferentiable Functions

Herein described is a computationally feasible algorithm with guaranteed convergence for the minimization of a convex, but not necessarily differentiable, function of several variables.

Let f be a convex function of several variables, defined and finite valued for all values of those variables. Suppose that for any point x it is computationally feasible to calculate at least one subgradient of f at x (see the References (1) or (2) for relevant definitions). The starting point x(o), the subgradient g(o) Epsilon Zeta f(x(o)), and positive scalars Delta , Epsilon , m(2) < m(1) < 1/2 are given. (Reasonable values are Delta = Epsilon = 10/-6/f(x(o)), m(2) = 0.1, m(1) = 0.4. The point x(o) should be a best estimate of the solution.). Set G(o) = {g(o)}, a(o) = 0. Execute the steps below for k=0, 1,.. .;

(Image Omitted)

Note 1: "Nr G" denotes the point of smallest Euclidean norm in the

convex hull of the set G. It is to be calculated by the

procedure "Algorithm for finding nearest points in convex

hulls", IBM Technical Disclosure Bulletin, Vol.17, No.9,

February, 1975, pages 2823 - 2824.

Note 2: The choice of t in Step 4(a) is to be made according to a rule established in the art: Choose t = 1 when k = 0 and whenever x(k-1) = x(k); otherwise, choose t =

2[f(x(k-1)-f(x(k)]/Fg(k),d(k)J.

Note 3: The choice of H in Step 5 has not been specified. The convergence results do not depend on that choice, but the

speed of conve...