The goal of this paper is to study the effect of inexact first-order information on the first-order methods designed for smooth strongly convex optimization problems. It can be seen as a generalization to the strongly convex case of our previous paper [1]. We introduce the notion of...

In this paper we introduce a new primal-dual technique for convergence analysis of gradient schemes for non-smooth convex optimization. As an example of its application, we derive a primal-dual gradient method for a special class of structured non-smooth optimization problems, which ensures a...

In this paper we develop a new theory of static equilibrium in congested transportation networks. Our considerations are based on a physical meaning of the flows rather than on an artificially chosen model of travel time functions. We introduce a concept of the stable equilibrium and prove the...

In this paper we prove that the semidefinite relaxation of boolean quadratic maximization problem with indefinite matrix provides us with a fixed absolute accuracy estimate for the exact solution.

In this paper we consider the semidefinite relaxation of some global optimization problems. We prove that in some cases this relaxation provides us with a constant relative accuracy estimate for the exact solution.

In the first part of this paper we prove that the global quadratic optimization problem over a simplex can be solved with a constant relative accuracy. In the second part we consider some natural extensions of the result.

In this paper we develop new primal-dual interior-point methods for linear programming, which are based on the concept of parabolic target space. We show that such schemes work in the infinity-neighborhood of the primal-dual central path. Nevertheless these methods possess the best known...

In this paper we suggest a cubic regularization for a Newton method as applied to unconstrained minimization problem. For this scheme we prove general convergence results. We analyze the behavior of this scheme on different problem classes, for which we get global and local worst-case complexity...

This paper considers the theory of market versus optimal product diversity in the light of two recent advances in oligopoly theory. The first is the development of discrete choice models to describe heterogeneous consumer tastes, and the application of such models to oligopolistic competition....

In this paper we extend the smoothing technique [7], [9] onto the problems of Semidefinite Optimization. For that, we develop a simple framework for estimating a Lipschitz constant for the gradient of some symmetric functions of eigenvalues of symmetric matrices. Using this technique, we can...