In this paper, we develop new subgradient methods for solving nonsmooth convex optimization problems. These methods are the first ones, for which the whole sequence of test points is endowed with the worst-case performance guarantees. The new methods are derived from a relaxed estimating...

We provide Frank-Wolfe (= Conditional Gradients) method with a convergence analysis allowing to approach a primal-dual solution of convex optimization problem with composite objective function. Additional properties of complementary part of the objective (strong convexity) significantly...

In this paper we suggest a new framework for constructing mathematical models of market activity. Contrary to the majority of the classical economical models (e.g. Arrow- Debreu, Walras, etc.), we get a characterization of general equilibrium of the market as a saddle point in a convex-concave...

Problems dealing with the design and the operations of gas transmission networks are challenging. The difficulty mainly arises from the simultaneous modeling of gas transmission laws and of the investment costs. The combination of the two yields a non- linear non-convex optimization problem. To...

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...

In this paper we study the Riemannian length of the primal central path computed with respect to the local metric defined by a self-concordant function. We show that despite to some examples, in many important situations the length of this path is quite close to the length of geodesic curves. We...

In this paper we suggest new dual methods for solving variational inequalities with monotone operators. We show that with an appropriate step-size strategy, our method is optimal both for Lipschitz continuous operators (O(1/e)iterations), and for the operators with bounded variations(0 (1/e2))....

In this paper we analyze several new methods for solving optimization problems with the objective function formed as a sum of two convex terms: one is smooth and given by a black-box oracle, and another is general but simple and its structure is known. Despite to the bad properties of the sum,...

In this paper we propose a new approach for constructing efficient schemes for nonsmooth convex optimization. It is based on a special smoothing technique, which can be applied to the functions with explicit max-structure. Our approach can be considered as an alternative to black-box...

Optimization problems over several cones of non-negative polynomials are described; we focus on linear constraints on the coefficients that represent interpolation constraints. For these problems, the complexity of solving the dual formulation is shown to be almost independent of the number of...