Naum Z. Shor
Encyclopedia
Naum Zuselevich Shor (1 January 1937 – 26 February 2006) was a Soviet and Ukrainian
Jewish mathematician
specializing in optimization
.
He made significant contributions to nonlinear
and stochastic programming
, numerical techniques for non-smooth optimization
, discrete optimization
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.
of generalized gradient descent
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
was re-invigorated by A.S. Nemirovsky and D.B. Yudin, who developed a careful complexity analysis
of its approximation
properties for problems of convex minimization with real data. However, it was Leonid Khachiyan
who provided the rational-arithmetic complexity analysis, using an ellipsoid
algorithm
, that established that linear programming
problems can be solved in polynomial time.
It has long been known that the ellipsoidal methods are special cases of these subgradient-type methods.
. It can be viewed as a Quasi-Newton method
, although it does not satisfy the secant equation. Although the method involves subgradients
, it is distinct from his so-called subgradient method described above.
Ukrainians
Ukrainians are an East Slavic ethnic group native to Ukraine, which is the sixth-largest nation in Europe. The Constitution of Ukraine applies the term 'Ukrainians' to all its citizens...
Jewish mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
specializing in optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
.
He made significant contributions to nonlinear
Nonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
and stochastic programming
Stochastic programming
Stochastic programming is a framework for modeling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within...
, numerical techniques for non-smooth optimization
Subgradient method
Subgradient methods are iterative methods for solving convex minimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function...
, discrete optimization
Discrete optimization
Discrete optimization is a branch of optimization in applied mathematics and computer science.As opposed to continuous optimization, the variables used in the mathematical program are restricted to assume only discrete values, such as the integers.Two notable branches of discrete optimization...
problems, matrix optimization
Semidefinite programming
Semidefinite programming is a subfield of convex optimization concerned with the optimization of a linear objective functionover the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron....
, dual quadratic bounds in multi-extremal programming
Multiobjective optimization
Multi-objective optimization , also known as multi-criteria or multi-attribute optimization, is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints....
problems.
Shor became a full member of the National Academy of Science of Ukraine
National Academy of Science of Ukraine
The National Academy of Sciences of Ukraine is the highest government research body in Ukraine and one of the six state academies. Its presidium is located at 57 Volodymyr Street, across the street from the Building of Pedagogical Museum where used to preside the Central Rada during the...
in 1998.
Subgradient methods
N. Z. Shor is well known for his methodIterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
of generalized gradient descent
Gradient descent
Gradient descent is a first-order optimization algorithm. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient of the function at the current point...
with space dilation
Quasi-Newton method
In optimization, quasi-Newton methods are algorithms for finding local maxima and minima of functions. Quasi-Newton methods are based on...
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
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 an optimal solution in a finite number of steps.The...
was re-invigorated by A.S. Nemirovsky and D.B. Yudin, who developed a careful complexity analysis
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
of its approximation
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
properties for problems of convex minimization with real data. However, it was Leonid Khachiyan
Leonid Khachiyan
Leonid Genrikhovich Khachiyan was a Soviet mathematician of Armenian descent who taught Computer Science at Rutgers University. He was most famous for his Ellipsoid algorithm for linear programming, which was the first such algorithm known to have a polynomial running time...
who provided the rational-arithmetic complexity analysis, using an ellipsoid
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 an optimal solution in a finite number of steps.The...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
, that established that linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
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
Schor's r-algorithm is for unconstrained minimization of (possibly) non-smooth functions, which has been somewhat popular despite an unknown convergence rateRate of convergence
In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance if we deal with a sequence of...
. It can be viewed as a Quasi-Newton method
Quasi-Newton method
In optimization, quasi-Newton methods are algorithms for finding local maxima and minima of functions. Quasi-Newton methods are based on...
, although it does not satisfy the secant equation. Although the method involves subgradients
Subderivative
In mathematics, the concepts of subderivative, subgradient, and subdifferential arise in convex analysis, that is, in the study of convex functions, often in connection to convex optimization....
, it is distinct from his so-called subgradient method described above.
External links
- ORB Newsletter Issue 5 contains an article with a short biography