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 other ...

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 variab ...

problems, matrix optimization, dual quadratic bounds in multi-extremal programming problems. Shor became a full member of the National Academy of Science of Ukraine 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 subgradients (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 convex optimization, minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algor ...

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

complexity analysis In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that re ...

of its

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

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 pro ...

with real data. However, it was

Leonid Khachiyan Leonid Genrikhovich Khachiyan (; russian: Леони́д Ге́нрихович Хачия́н; May 3, 1952April 29, 2005) was a Soviet and American mathematician and computer scientist. He was most famous for his ellipsoid algorithm (1979) for ...

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 the ...

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

, 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 function#As a polynomial function, li ...

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