Yurii Nesterov

Improved global performance guarantees of second-order methods in convex minimization

Pavel Dvurechensky, Yurii Nesterov

In this paper, we attempt to compare two distinct branches of research on second-order optimization methods. The first one studies self-concordant functions and barriers, the main…

New Results on Superlinear Convergence of Classical Quasi-Newton Methods

Anton Rodomanov, Yurii Nesterov

We present a new theoretical analysis of local superlinear convergence of classical quasi-Newton methods from the convex Broyden class. As a result, we obtain a significant improve…

Local and Global Convergence of Greedy Parabolic Target-Following Methods for Linear Programming

Yurii Nesterov

In the first part of this paper, we prove that, under some natural non-degeneracy assumptions, the Greedy Parabolic Target-Following Method, based on {\em universal tangent directi…

Optimization Methods for Fully Composite Problems

Nikita Doikov, Yurii Nesterov

In this paper, we propose a new Fully Composite Formulation of convex optimization problems. It includes, as a particular case, the problems with functional constraints, max-type m…

Universal Complexity Bounds for Universal Gradient Methods in Nonlinear Optimization

Yurii Nesterov

In this paper, we provide the universal first-order methods of Composite Optimization with new complexity analysis. It delivers some universal convergence guarantees, which are not…

Smoothness parameter of power of Euclidean norm

Anton Rodomanov, Yurii Nesterov

In this paper, we study derivatives of powers of Euclidean norm. We prove their HÃ¶lder continuity and establish explicit expressions for the corresponding constants. We show that…

Gradient Methods with Memory

Yurii Nesterov, Mihai I. Florea

In this paper, we consider gradient methods for minimizing smooth convex functions, which employ the information obtained at the previous iterations in order to accelerate the conv…

Dynamic pricing under nested logit demand

David MÃ¼ller, Yurii Nesterov, Vladimir Shikhman

Recently, there is growing interest and need for dynamic pricing algorithms, especially, in the field of online marketplaces by offering smart pricing options for big online stores…

Conic-Optimization Based Algorithms for Nonnegative Matrix Factorization

Valentin Leplat, Yurii Nesterov, Nicolas Gillis +1

Nonnegative matrix factorization is the following problem: given a nonnegative input matrix $V$ and a factorization rank $K$ , compute two nonnegative matrices, $W$ with $K$ columns…

Stochastic Subspace Cubic Newton Method

Filip Hanzely, Nikita Doikov, Peter RichtÃ¡rik +1

In this paper, we propose a new randomized second-order optimization algorithm---Stochastic Subspace Cubic Newton (SSCN)---for minimizing a high dimensional convex function $f$ . Ou…

Asymmetric Long-Step Primal-Dual Interior-Point Methods with Dual Centering

Yurii Nesterov

In this paper, we develop a new asymmetric framework for solving primal-dual problems of Conic Optimization by Interior-Point Methods (IPMs). It allows development of efficient met…

On Inexact Solution of Auxiliary Problems in Tensor Methods for Convex Optimization

Geovani Nunes Grapiglia, Yurii Nesterov

In this paper we study the auxiliary problems that appear in $p$ -order tensor methods for unconstrained minimization of convex functions with $I^½$ -HÃ¶lder continuous $p$ th derivati…

Local convergence of tensor methods

Nikita Doikov, Yurii Nesterov

In this paper, we study local convergence of high-order Tensor Methods for solving convex optimization problems with composite objective. We justify local superlinear convergence u…

math.OC2018

Stochastic gradient methods with inexact oracle

Alexander Gasnikov, Pavel Dvurechensky, Yurii Nesterov

In the article we lead a brief survey of contemporary gradient type methods (with inexact oracle) for stochastic optimization problems.

On the Quality of First-Order Approximation of Functions with HÃ¶lder Continuous Gradient

Guillaume O. Berger, P. -A. Absil, RaphaÃ«l M. Jungers +1

We show that HÃ¶lder continuity of the gradient is not only a sufficient condition, but also a necessary condition for the existence of a global upper bound on the error of the fir…

An optimal lower bound for smooth convex functions

Mihai I. Florea, Yurii Nesterov

First order methods endowed with global convergence guarantees operate using global lower bounds on the objective. The tightening of the bounds has been shown to increase both the…

math.OC2017

Universal fast gradient method for stochastic composit optimization problems

Alexander Gasnikov, Yurii Nesterov

We propose a new simple variant of Fast Gradient Method that requires only one projection per iteration. We called this method Triangle Method (TM) because it has a corresponding g…

On the three-stage version of stable dynamic model

Alexander Gasnikov, Yuriy Dorn, Yurii Nesterov +1

An attempt to merge into a single model, which reduces to the solution of non-smooth convex optimization problem: calculation model of OD-matrix (entropy model), the mode split mod…

Rates of superlinear convergence for classical quasi-Newton methods

Anton Rodomanov, Yurii Nesterov

We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods conv…

Universal Reduced-Operator Method and High-Order Global Curvature Bounds

Nikita Doikov, Yurii Nesterov

In this paper, we develop a new concept of Global Curvature Bound (GCB) for an arbitrary nonlinear operator between abstract metric spaces. We use this notion to characterize the g…

Contracting Proximal Methods for Smooth Convex Optimization

Nikita Doikov, Yurii Nesterov

In this paper, we propose new accelerated methods for smooth convex optimization, called contracting proximal methods. At every step of these methods, we need to minimize a contrac…

math.OC2019

Discrete choice prox-functions on the simplex

David MÃ¼ller, Yurii Nesterov, Vladimir Shikhman

We derive new prox-functions on the simplex from additive random utility models of discrete choice. They are convex conjugates of the corresponding surplus functions. In particular…

Universal method with inexact oracle and its applications for searching equillibriums in multistage transport problems

Alexander Gasnikov, Pavel Dvurechensky, Dmitry Kamzolov +5

In this paper we propose a new efficient approach for numerical calculation of equillibriums in multistage transport problems. In the very core of our approach lies the proper comb…

Convex optimization based on global lower second-order models

Nikita Doikov, Yurii Nesterov

In this paper, we present new second-order algorithms for composite convex optimization, called Contracting-domain Newton methods. These algorithms are affine-invariant and based o…

High-order methods beyond the classical complexity bounds, I: inexact high-order proximal-point methods

Masoud Ahookhosh, Yurii Nesterov

In this paper, we introduce a \textit{Bi-level OPTimization} (BiOPT) framework for minimizing the sum of two convex functions, where both can be nonsmooth. The BiOPT framework invo…

Entropy linear programming

Alexander Gasnikov, Evgenia Gasnikova, Yurii Nesterov +1

We propose an efficient dual algorithm for ELP based on Fast Gradient Method. The basic idea - to solve properly regularized dual problem.

Convex quartic problems: homogenized gradient method and preconditioning

Radu-Alexandru Dragomir, Yurii Nesterov

We consider a convex minimization problem for which the objective is the sum of a homogeneous polynomial of degree four and a linear term. Such task arises as a subproblem in algor…

math.OC2008

Generalized power method for sparse principal component analysis

Michel JournÃ©e, Yurii Nesterov, Peter RichtÃ¡rik +1

In this paper we develop a new approach to sparse principal component analysis (sparse PCA). We propose two single-unit and two block optimization formulations of the sparse PCA pr…

Gradient Regularization of Newton Method with Bregman Distances

Nikita Doikov, Yurii Nesterov

In this paper, we propose a first second-order scheme based on arbitrary non-Euclidean norms, incorporated by Bregman distances. They are introduced directly in the Newton iterate…

Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method

Nikita Doikov, Yurii Nesterov

In this paper, we study the iteration complexity of cubic regularization of Newton method for solving composite minimization problems with uniformly convex objective. We introduce…

Greedy Quasi-Newton Methods with Explicit Superlinear Convergence

Anton Rodomanov, Yurii Nesterov

In this paper, we study greedy variants of quasi-Newton methods. They are based on the updating formulas from a certain subclass of the Broyden family. In particular, this subclass…

math.OC2026

Theorem of Alternative for Extended Homogeneous Linear System and its Application in Conic Optimization

Yurii Nesterov

In this paper, we develop a new framework for constructing infeasible-start primal-dual methods for Conic Optimization. Our approach can be seen as a straightforward consequence of…

Primal subgradient methods with predefined stepsizes

Yurii Nesterov

In this paper, we suggest a new framework for analyzing primal subgradient methods for nonsmooth convex optimization problems. We show that the classical step-size rules, based on…

math.OC2015

Learning Supervised PageRank with Gradient-Free Optimization Methods

Lev Bogolubsky, Pavel Dvurechensky, Alexander Gasnikov +5

In this paper, we consider a problem of learning supervised PageRank models, which can account for some properties not considered by classical approaches such as the classical Page…

Tensor Methods for Minimizing Convex Functions with HÃ¶lder Continuous Higher-Order Derivatives

Geovani Nunes Grapiglia, Yurii Nesterov

In this paper we study $p$ -order methods for unconstrained minimization of convex functions that are $p$ -times differentiable ( $p \geq 2$ ) with $I^½$ -HÃ¶lder continuous $p$ th derivat…

Inexact Tensor Methods with Dynamic Accuracies

Nikita Doikov, Yurii Nesterov

In this paper, we study inexact high-order Tensor Methods for solving convex optimization problems with composite objective. At every step of such methods, we use approximate solut…

Subgradient Ellipsoid Method for Nonsmooth Convex Problems

Anton Rodomanov, Yurii Nesterov

In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization probl…

math.DS2004

Computationally efficient approximations of the joint spectral radius

Vincent Blondel, Yurii Nesterov

The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate that can be obtained by forming long products of matrices taken from the set. This…

Gradient Methods for Stochastic Optimization in Relative Scale

Yurii Nesterov, Anton Rodomanov

We propose a new concept of a relatively inexact stochastic subgradient and present novel first-order methods that can use such objects to approximately solve convex optimization p…

High-order methods beyond the classical complexity bounds, II: inexact high-order proximal-point methods with segment search

Masoud Ahookhosh, Yurii Nesterov

A bi-level optimization framework (BiOPT) was proposed in [3] for convex composite optimization, which is a generalization of bi-level unconstrained minimization framework (BLUM) g…

Efficient randomized mirror descents in stochastic online convex optimization

Alexander Gasnikov, Yurii Nesterov, Vladimir Spokoiny

In the paper we consider an application of mirror descent (dual averaging) to the stochastic online convex optimization problems. We compare classical mirror descent (Nemirovski-Yu…

Interior-Point Algorithms for Monotone Linear Complementarity Problem Based on Different Predictor Directions

In this paper, we introduce two parabolic target-space interior-point algorithms for solving monotone linear complementarity problems. The first algorithm is based on a universal t…

math.OC2019

Computation of the analytic center of the solution set of the linear matrix inequality arising in continuous- and discrete-time passivity analysis

Daniel Bankmann, Volker Mehrmann, Yurii Nesterov +1

In this paper formulas are derived for the analytic center of the solution set of linear matrix inequalities (LMIs) defining passive transfer functions. The algebraic Riccati equat…

math.OC2019

Primal-dual accelerated gradient methods with small-dimensional relaxation oracle

Yurii Nesterov, Alexander Gasnikov, Sergey Guminov +1

In this paper, a new variant of accelerated gradient descent is proposed. The pro-posed method does not require any information about the objective function, usesexact line search…

Tensor Methods for Finding Approximate Stationary Points of Convex Functions

Geovani Nunes Grapiglia, Yurii Nesterov

In this paper we consider the problem of finding $I^µ$ -approximate stationary points of convex functions that are $p$ -times differentiable with $I^½$ -HÃ¶lder continuous $p$ th derivat…

Affine-invariant contracting-point methods for Convex Optimization

Nikita Doikov, Yurii Nesterov

In this paper, we develop new affine-invariant algorithms for solving composite convex minimization problems with bounded domain. We present a general framework of Contracting-Poin…

math.OC2018

Primal-dual method for searching equillibriums in mixed traffic assignment problems

Alexander Gasnikov, Evgenia Gasnikova, Yurii Nesterov

We consider mixed model of traffic flow distribution in large networks (BMW model, 1954 & Stable Dynamic model, 1999). We build dual problem and consider primal-dual mirror descent…

math.OC2022

Super-Universal Regularized Newton Method

Nikita Doikov, Konstantin Mishchenko, Yurii Nesterov

We analyze the performance of a variant of Newton method with quadratic regularization for solving composite convex minimization problems. At each step of our method, we choose reg…

math.OC2022

Adaptive Third-Order Methods for Composite Convex Optimization

Geovani Nunes Grapiglia, Yurii Nesterov

In this paper we propose third-order methods for composite convex optimization problems in which the smooth part is a three-times continuously differentiable function with Lipschit…

math.OC2022

Quartic Regularity

Yurii Nesterov

In this paper, we propose new linearly convergent second-order methods for minimizing convex quartic polynomials. This framework is applied for designing optimization schemes, whic…

math.OC2017

Relatively-Smooth Convex Optimization by First-Order Methods, and Applications

Haihao Lu, Robert M. Freund, Yurii Nesterov

The usual approach to developing and analyzing first-order methods for smooth convex optimization assumes that the gradient of the objective function is uniformly smooth with some…

A Subgradient Method for Free Material Design

Michal Kocvara, Yurii Nesterov, Yu Xia

A small improvement in the structure of the material could save the manufactory a lot of money. The free material design can be formulated as an optimization problem. However, due…

Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods

Lev Bogolubsky, Pavel Dvurechensky, Alexander Gasnikov +5

In this paper, we consider a non-convex loss-minimization problem of learning Supervised PageRank models, which can account for some properties not considered by classical approach…

physics.soc-ph2020

Online analysis of epidemics with variable infection rate

Yurii Nesterov

In this paper, we continue development of the new epidemiological model HIT, which is suitable for analyzing and predicting the propagation of COVID-19 epidemics. This is a discret…

math.OC2026

Multiconic Optimization for Symmetric Cones and Hyperbolic Coupling

Marianna E. -Nagy, Yurii Nesterov, Petra RenÃ¡ta RigÃ³

We develop a new interior-point algorithm for solving multiconic optimization problems using the parabolic target space approach. The feasible cone in these problems is composed as…

High-Order Reduced-Gradient Methods for Composite Variational Inequalities

Yurii Nesterov

This paper can be seen as an attempt of rethinking the {\em Extra-Gradient Philosophy} for solving Variational Inequality Problems. We show that the properly defined {\em Reduced G…