User:Kateditor/sandbox

Galina Mikhailovna Korpelevich (russian: Галина Михайловна Корпелевич; 14 July 1937 – 30 November 1985) was a soviet mathematician, known for her invention of extragradient method for solving variational inequalities.

Galina's grave in Vostryakovski cemetry in Moscow

Galina Mikhailovna Korpelevich
Born	(1937-07-14)July 14, 1937 Moscow
Died	November 30, 1985(1985-11-30) (aged 48)
Alma mater	Moscow State University
Known for	Extragradient method
Scientific career
Fields	Mathematical logic Optimization Mathematical Programming
Institutions	Cental Economic and Mathematical Institute of Russian Academy of Sciences
Thesis	On the relationship of the concepts of solvability and countability for finite automata[cite]
Academic advisors	V.A.Uspensky

Early life and education

Karpelevich was born in Moscow on 14 July 1937. She was the oldest of two daughters. Galina had jewish origin from her father's side Mikhail Karpelevich (russian Карпелевич Михаил Иосифович) who was an engineer. Mikhail was killed in 1942 during WW2 leaving his daughters exclusively in his wife's hands. Galina always loved mathematics. In 1956 her passion finally led her to enter mechanical and mathematical department of Moscow State University. She continued her education with master studies around mathematical logic. Her master thesis written under the supervision of Professor V.A.Uspensky is entitled "On the relationship of the concepts of solvability and countability for finite automata"[cite], the results of which were recommended for publication by Academician A.N.Kolmogorov. Later, Galina worked as a mathematical programmer in the Cental Economic and Mathematical Institute of Russian Academy of Sciences having the position of junior researcher. Galina had also played a significant role in organizing some special events like one in Estonia, where mathematicians (including Yuri Manin, Alexandre Kirillov, Roland Dobrushin, Robert Minlos) met economists in the attempt to collaborate. Galina died just at the age of 48 due to brain tumor. Her husband Boris Polyak (russian: Борис Теодорович Поляк) is until now a mahematician in Moscow^[1] and their son Mikhael Polyak continues family's professional tradition as professor of mathematics in Technion, Haifa^[2].

Extragradient method[3]

Operator ${\displaystyle T\colon H\to H}$ is monotone in a Hilbert space H if ${\displaystyle (T(x)-T(y),x-y)\geq 0,\forall x,y\in H}$

Suppose variational inequality ${\displaystyle (T(x),y-x)\geq 0,\forall y\in Q\subset H}$ has a solution ${\displaystyle x^{*}\in Q}$, ${\displaystyle Q}$ being a closed convex set. The extragradient method for solving the variational inequality has the form:

${\displaystyle {\begin{aligned}\qquad {\bar {x}}_{k}=P_{Q}(x_{k}-aT(x_{k})),\qquad x_{k+1}=P_{Q}(x_{k}-aT({\bar {x}}_{k}))\end{aligned}}}$

where ${\displaystyle P_{Q}}$ is the projection on ${\displaystyle Q}$. If ${\displaystyle T(x)}$ is the gradient of a smooth convex function ${\displaystyle f(x)}$, then the variational inequality is optimality condition for minimization of ${\displaystyle f(x)}$ on ${\displaystyle Q}$ and ${\displaystyle T({\bar {x}}_{k})}$ is the extrapolated gradient of ${\displaystyle f(x_{k})}$. This explains the name of the method.

Theorem

If T satisfies Lipschitz condition on ${\displaystyle Q}$ with constant ${\displaystyle L}$ and ${\displaystyle 0<a<1/L}$, then ${\displaystyle x_{k}\rightarrow x^{*}}$ for ${\displaystyle k\rightarrow \infty }$.

The method can be applied for finding saddle points and for solving matrix games (here the method converges linearly provided the solution is unique).

Her reputation

Galina's life is not known among the scientific community even if her homonym algorithm plays an essential role in optimization field.

References

1. "Boris Polyak (Борис Поляк)". scholar.google.ru. Retrieved 2022-09-14.
2. Polyak, Mikhael. "Mikhael Polyak's website".
3. G. M. Korpelevich. "Extragradient method" (PDF).