Vaidya’s Method for Convex Stochastic Optimization Problems in Small Dimension

Mathematical Notes - The paper deals with a general problem of convex stochastic optimization in a space of small dimension (for example, 100 variables). It is known that for deterministic problems...     

Reachability of Optimal Convergence Rate Estimates for High-Order Numerical Convex Optimization Methods

Doklady Mathematics - The Monteiro–Svaiter accelerated hybrid proximal extragradient method (2013) with one step of Newton’s method used at every iteration for the approximate solution...     

Parallel Algorithms and Probability of Large Deviation for Stochastic Convex Optimization Problems

We consider convex stochastic optimization problems under different assumptions on the properties of available stochastic subgradient. It is known that, if the value of the objective function is available, one can obtain, in parallel, several independent approximate solutions in terms of the objective residual expectation. Then, choosing the solution with the minimum function value, one can control the probability of large deviation of the objective residual. On the contrary, in this short paper, we address the situation, when the value of the objective function is unavailable or is too expensive to calculate. Under "‘light-tail"’ assumption for stochastic subgradient and in general case with moderate large deviation probability, we show that parallelization combined with averaging gives bounds for probability of large deviation similar to a serial method. Thus, in these cases, one can benefit from parallel computations and reduce the computational time without loss in the solution quality.     

On the velocity of separation between two successive traveling waves in the asymptotics of the solution to the Cauchy problem for a Burgers-type equation

An upper bound on the distance between the centers of two successive traveling waves occurring in the asymptotics of the solution to the Cauchy problem for a Burgers-type equation is established under generic conditions. Taking into account a previously established lower bound, an asymptotically sharper estimate is derived.     

On the Upper Bound for the Expectation of the Norm of a Vector Uniformly Distributed on the Sphere and the Phenomenon of Concentration of Uniform Measure on the Sphere

Mathematical Notes - We consider the problem of constructing upper bounds for the expectation of the norm of a vector uniformly distributed on the Euclidean unit sphere.     

Stochastic intermediate gradient method for convex optimization problems

New first-order methods are introduced for solving convex optimization problems from a fairly broad class. For composite optimization problems with an inexact stochastic oracle, a stochastic intermediate gradient method is proposed that allows using an arbitrary norm in the space of variables and a prox-function. The mean rate of convergence of this method and the probability of large deviations from this rate are estimated. For problems with a strongly convex objective function, a modification of this method is proposed and its rate of convergence is estimated. The resulting estimates coincide, up to a multiplicative constant, with lower complexity bounds for the class of composite optimization problems with an inexact stochastic oracle and for all usually considered subclasses of this class.     

Generalized Mirror Prox Algorithm for Monotone Variational Inequalities: Universality and Inexact Oracle

Journal of Optimization Theory and Applications - We introduce an inexact oracle model for variational inequalities with monotone operators, propose a numerical method that solves such variational...     

An Adaptive Proximal Method for Variational Inequalities

Computational Mathematics and Mathematical Physics - A novel analog of Nemirovski’s proximal mirror method with an adaptive choice of constants in the minimized prox-mappings at each...     

Local Algorithms for Minimizing the Force Field for 3D Representation of Macromolecules

Computational Mathematics and Mathematical Physics - The majority of problems in structural computational biology require minimization of the energy function (force field) defined on the molecule...