Naum Zuselevich Shor (russian: Наум Зуселевич Шор) (1 January 1937 – 26 February 2006) was a

Soviet The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a List of former transcontinental countries#Since 1700, transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, ...

and

Ukrainian Ukrainian may refer to: * Something of, from, or related to Ukraine * Something relating to Ukrainians, an East Slavic people from Eastern Europe * Something relating to demographics of Ukraine in terms of demography and population of Ukraine * So ...

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

specializing in

optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

. He made significant contributions to

nonlinear In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many oth ...

and

stochastic programming In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, ...

, numerical techniques for non-smooth optimization,

discrete optimization Discrete optimization is a branch of optimization in applied mathematics and computer science. Scope As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete varia ...

problems, matrix optimization, dual quadratic bounds in multi-extremal programming problems. Shor became a full member of the

National Academy of Science of Ukraine The National Academy of Sciences of Ukraine (NASU; uk, Національна академія наук України, ''Natsional’na akademiya nauk Ukrayiny'', abbr: NAN Ukraine) is a self-governing state-funded organization in Ukraine t ...

in 1998.

Subgradient methods

N. Z. Shor is well known for his

method Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to: *Scien ...

of generalized

gradient descent In mathematics, gradient descent (also often called steepest descent) is a first-order iterative optimization algorithm for finding a local minimum of a differentiable function. The idea is to take repeated steps in the opposite direction of the ...

with space dilation in the direction of the difference of two successive

subgradient In mathematics, the subderivative, subgradient, and subdifferential generalize the derivative to convex functions which are not necessarily differentiable. Subderivatives arise in convex analysis, the study of convex functions, often in connecti ...

s (the so-called r-algorithm), that was created in collaboration with Nikolay G. Zhurbenko. The

ellipsoid method In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds ...

was re-invigorated by A.S. Nemirovsky and D.B. Yudin, who developed a careful complexity analysis of its

approximation An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...

properties for problems of

convex minimization Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization probl ...

with real data. However, it was Leonid Khachiyan who provided the rational-arithmetic complexity analysis, using an

ellipsoid An ellipsoid is a surface that may be obtained from a sphere by deforming it by means of directional scalings, or more generally, of an affine transformation. An ellipsoid is a quadric surface; that is, a surface that may be defined as th ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

, that established that

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

problems can be solved in polynomial time. It has long been known that the ellipsoidal methods are special cases of these subgradient-type methods.

R-algorithm

Shor's r-algorithm is for unconstrained minimization of (possibly) non-smooth functions, which has been somewhat popular despite an unknown convergence rate."The Speed of Shor's R-Algorithm", available at http://www.optimization-online.org/DB_HTML/2007/05/1656.html It can be viewed as a

Quasi-Newton method Quasi-Newton methods are methods used to either find zeroes or local maxima and minima of functions, as an alternative to Newton's method. They can be used if the Jacobian or Hessian is unavailable or is too expensive to compute at every iteration. ...

, although it does not satisfy the secant equation. Although the method involves subgradients, it is distinct from his so-called ''subgradient method'' described above.

References

Notes

Bibliography

* .

External links

ORB Newsletter Issue 5
contains an article with a short biography * {{DEFAULTSORT:Shor, Naum Z. Numerical analysts Theoretical computer scientists Mathematical analysts Ukrainian mathematicians Soviet computer scientists Taras Shevchenko National University of Kyiv alumni Academic staff of the Moscow Institute of Physics and Technology Members of the National Academy of Sciences of Ukraine Recipients of the USSR State Prize 1937 births 2006 deaths Ukrainian Jews Laureates of the State Prize of Ukraine in Science and Technology