Recently, it has been shown how, on the basis of the usual accelerated gradient method for solving problems of smooth convex optimization, accelerated methods for more complex problems (with a structure) and problems that are solved using various local information about the behavior of a function (stochastic gradient, Hessian, etc.) can be obtained. The term “accelerated methods” here means, on the one hand, the presence of some unified and fairly general way of acceleration. On the other hand, this also means the optimality of the methods, which can often be proved rigorously. In the present work, an attempt is made to construct in the same way a theory of accelerated methods for solving smooth convex-concave saddle-point problems with a structure. The main result of this article is the obtainment of in some sense necessary and sufficient conditions under which the complexity of solving nonlinear convex-concave saddle-point problems with a structure in the number of calculations of the gradients of composites in direct variables is equal in order of magnitude to the complexity of solving bilinear problems with a structure
A novel analog of Nemirovski’s proximal mirror method with an adaptive choice of constants in the minimized prox-mappings at each iteration for variational inequalities with a Lipschitz continuous field is proposed. Estimates of the number of iterations needed to attain the desired quality of solution of the variational inequality are obtained. It is shown how the proposed approach can be extended for the case of Hölder continuous field. A modification of the proposed algorithm for the case of an inexact oracle for the field operator is also considered.
The asymptotic behavior of a stochastic process satisfying a linear stochastic differential equation is analyzed. More specifically, the problem is solved of finding a normalizing function such that the normalized process tends to zero with probabilty 1. The explicit expression found for the function involves the parameters of the perturbing process, and the function itself has a simple interpretation. The solution of the indicated probles makes it possible to considerably improve almost sure optimality results for a stochastic linear regulator on an infinite time interval.
Explicit two-level in time and symmetric in space finite-difference schemes constructed by approximating the 1D barotropic quasi-gas-/quasi-hydrodynamic systems of equations are studied. The schemes are linearized about a constant solution with a nonzero velocity, and, for them, necessary and sufficient conditions for the L2-dissipativity of solutions to the Cauchy problem are derived depending on the Mach number. These conditions differ from one another by at most twice. The results substantially develop the ones known for the linearized Lax–Wendroff scheme. Numerical experiments are performed to analyze the applicability of the found conditions in the nonlinear formulation to several schemes for different Mach numbers.
A strongly convex function of simple structure (for example, separable) is minimized under affine constraints. A dual problem is constructed and solved by applying a fast gradient method. The necessary properties of this method are established relying on which, under rather general conditions, the solution of the primal problem can be recovered with the same accuracy as the dual solution from the sequence generated by this method in the dual space of the problem. Although this approach seems natural, some previously unpublished rather subtle results necessary for its rigorous and complete theoretical substantiation in the required generality are presented.
The problem of equilibrium distribution of flows in a transportation network in which a part of edges are characterized by cost functions and the other edges are characterized by their capacity and constant cost for passing through them if there is no congestion is studied. Such models (called mixed models) arise, e.g., in the description of railway cargo transportation. A special case of the mixed model is the family of equilibrium distribution of flows over routes—BMW (Beckmann) model and stable dynamics model. The search for equilibrium in the mixed model is reduced to solving a convex optimization problem. In this paper, the dual problem is constructed that is solved using the mirror descent (dual averaging) algorithm. Two different methods for recovering the solution of the original (primal) problem are described. It is shown that the proposed approaches admit efficient parallelization. The results on the convergence rate of the proposed numerical methods are in agreement with the known lower oracle bounds for this class of problems (up to multiplicative constants).
Previous and new results are used to compare two mathematical insurance models with identical insurance company strategies in a financial market, namely, when the entire current surplus or its constant fraction is invested in risky assets (stocks), while the rest of the surplus is invested in a risk-free asset (bank account). Model I is the classical Cramér–Lundberg risk model with an exponential claim size distribution. Model II is a modification of the classical risk model (risk process with stochastic premiums) with exponential distributions of claim and premium sizes. For the survival probability of an insurance company over infinite time (as a function of its initial surplus), there arise singular problems for second-order linear integrodifferential equations (IDEs) defined on a semiinfinite interval and having nonintegrable singularities at zero: model I leads to a singular constrained initial value problem for an IDE with a Volterra integral operator, while II model leads to a more complicated nonlocal constrained problem for an IDE with a non-Volterra integral operator. A brief overview of previous results for these two problems depending on several positive parameters is given, and new results are presented. Additional results are concerned with the formulation, analysis, and numerical study of “degenerate” problems for both models, i.e., problems in which some of the IDE parameters vanish; moreover, passages to the limit with respect to the parameters through which we proceed from the original problems to the degenerate ones are singular for small and/or large argument values. Such problems are of mathematical and practical interest in themselves. Along with insurance models without investment, they describe the case of surplus completely invested in risk-free assets, as well as some noninsurance models of surplus dynamics, for example, charity-type models.
The multidimensional quasi-gasdynamic system written in the form of mass, momentum, and total energy balance equations for a perfect polytropic gas with allowance for a body force and a heat source is considered. A new conservative symmetric spatial discretization of these equations on a nonuniform rectangular grid is constructed (with the basic unknown functions—density, velocity, and temperature—defined on a common grid and with fluxes and viscous stresses defined on staggered grids). Primary attention is given to the analysis of entropy behavior: the discretization is specially constructed so that the total entropy does not decrease. This is achieved by substantially revision of the standard discretization and applying numerous original features. A simplification of the constructed discretization serves as a conservative discretization with nondecreasing total entropy for the simpler quasi-hydrodynamic system of equations. In the absence of regularizing terms, the results also hold for the Navier–Stokes equations forf a viscous compressible heat-conducting gas.
For the regular Sturm–Liouville boundary value problem with general nonseparated selfadjoint boundary conditions, conditions for the existence of zero and negative eigenvalues and expressions for their number are obtained. The conditions are expresses in a closed form, and the coefficient functions of the original equation appear in these conditions indirectly through a single numerical characteristic.
We present direct logarithmically optimal in theory and fast in practice algorithms to implement the tensor products finite element method (FEM) based on the tensor products of the 1D high-order FEM spaces on multi-dimensional rectangular parallelepipeds for solving the $N$-dimensional Poisson type equation $-\Delta u+\alpha u=f$ ($N\geq 2$) with the Dirichlet boundary conditions. They are based on the well-known Fourier approaches. The key new points are a detailed description for the eigenpairs of the 1D eigenvalue problems for the high order FEM as well as the fast direct and inverse algorithms for expansion in the respective eigenvectors utilizing simultaneously several versions of the FFT (fast Fourier transform). Results of numerical experiments in 2D and 3D cases are presented. The algorithms can serve for numerous applications, in particular, to implement the tensor product high order finite element methods for various time-dependent partial differential equations (PDEs) including the multidimensional heat, wave and Schrödinger ones. %
A new concept of (δ ,L)-model of a function that is a generalization of the Devolder–Glineur–Nesterov (δ ,L)-oracle is proposed. Within this concept, the gradient descent and fast gradient descent methods are constructed and it is shown that constructs of many known methods (composite methods, level methods, conditional gradient and proximal methods) are particular cases of the methods proposed in this paper.
The importance of functional differential equations of pointwise type is determined by the fact that their solutions are used to construct traveling-wave solutions for induced infinite-dimensional ordinary differential equations, and vice versa. Solutions of such equations exhibit bifurcation. A theorem on branching bifurcation is obtained for the solution to a linear homogeneous functional differential equation of pointwise type.
Multicriteria choice methods are developed by applying methods of criteria importance theory with uncertain information on criteria importance and with preferences varying along their scale. Formulas are given for computing importance coefficients and importance scale estimates that are “characteristic” representatives of the feasible set of these parameters. In the discrete case, an alternative with the highest probability of being optimal (for a uniform distribution of parameter value probabilities) can be used as the best one. It is shown how such alternatives can be found using the Monte Carlo method.
A multidimensional barotropic quasi-gasdynamic system of equations in the form of mass and momentum conservation laws with a general gas equation of state with $p=p(\rho)$ and $p'(\rho)>0$ potential body force is considered. For this system, two new symmetric spatial discretizations on nonuniform rectangular grids are constructed (in which the density and velocity are defined on the basic grid, while the components of the regularized mass flux and the viscous stress tensor are defined on staggered grids). These discretizations involve nonstandard approximations to $\nabla p(\rho)$, $\dv(\rho\bu)$ and $\rho$. As a result, a discrete total mass conservation law and a discrete energy inequality guaranteeing that the total energy does not grow with time can be derived. Importantly, these discretizations have the additional property of being well balanced for equilibrium solutions. Another conservative discretization is discussed in which all mass flux components and viscous stresses are defined on the same grid. For the simpler barotropic quasi-hydrodynamic system of equations, the corresponding simplifications of the constructed discretizations have similar properties.
The one-dimensional quasi-gasdynamic system of equations in the form of mass, momentum, and total energy conservation laws with general gas equations of state is considered. A family of three-point symmetric spatial discretizations of this system is studied for which the internal energy equation has a suitable form (without imbalance terms). An entropy balance equation is derived, and the influence exerted by the choice of discretizations of various terms on the form of difference imbalance terms in this equation is determined. Special discretizations are presented for which the corresponding nondivergence imbalance terms are zero. The Euler system of equations is solved numerically in the cases of a perfect polytropic gas, stiffened gas, and the van der Waals equations of state.
Behavior of the dispersion curves of waveguides with anisotropic filling is considered. The existence of backward and complex waves at certain values of the anisotropy coefficients is established. The region of localization of the singular points of the dispersion curves in which the generation of backward waves takes place is found.