Interior-point polynomial algorithms in convex programming

By Yurii E. Nesterov, Arkadi Nemirovski. 1994

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “The class of self-concordant functions was ﬁrst introduced by Nesterov and Nemirovskii (1994) and has been extended to include common losses such as (multi-class) logistic regression (Bach et al., 2010).”
Introduction to Online Convex Optimization (2016, methodology): “Self-concordant barrier functions were devised in the context of polynomial-time algorithms for convex optimization in the seminal work of Nesterov and Nemirovskii (79).”
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) (2013, methodology): “(10) Assumption (B3) is satisfied for the logistic loss and extends to all generalized linear models (see more details in [21]), and the relationship between the third derivative and second derivative of the loss l is often referred to as self-concordance (see [24, 25] and references therein).”
Geometric median in nearly linear time (2016, methodology): “Our algorithm is broadly inspired by interior point methods, a broad class of methods for efficiently solving convex optimization problems [32, 22].”
Computational Optimal Transport (2018, background): “With this extra variable, it is thus possible to solve the discretized problem using standard interior point solvers for quadratic-cone programs [Nesterov and Nemirovskii, 1994].”
Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming (2010, methodology): “In turn, this allows us to implement the estimator using efficient algorithmic methods, such as interior-point methods, which provide polynomial-time bounds on computational time [16, 17], and modern first-order methods [14, 15, 11, 1].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “Such programs may be efficiently solved by active-set methods [171] or interior point methods [170].”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, background): “which can often be efficiently solved by simplex or interior-point methods [30,103, 105,151,155].”
LQR-trees: Feedback Motion Planning via Sums-of-Squares Verification (2010, methodology): “This results in a semidefinite program and can be solved efficiently using interior point methods [22].”
Direction-of-Arrival Estimation Using a Sparse Representation of Array Covariance Vectors (2011, background): “In addition, if the noise in (1) is assumed to be colored, a prewhitening procedure (see [12]) needs to be introduced beforehand, the detailed analysis of which, however, is beyond the scope of this paper.”
Transmit beamforming for MIMO radar systems using signal cross-correlation (2008, methodology): “In order to solve this problem we can use a simple technique from convex optimization called a barrier function, [1, 2, 9].”
TIGHT BOUNDS ON EXPECTED ORDER STATISTICS (2006, background): “Formulation (24) is a semidefinite optimization problem that can be solved within > 0 of the optimal solution in polynomial time in the problem data and log((1) ) [19].”
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow (2014, methodology): “1994 Nesterov and Nemirovskii [30] O( √ rank(A)L) Volume computation”
Complexity bounds for primal-dual methods minimizing the model of objective function (2017, background): “• is an indicator function of a closed convex set Q : (2.2) • is a self-concordant barrier for a closed convex set Q (see [13,17]).”
Nonlinear Discrete Optimization (2010, background): “by efficiently minimizing a convex function over a polytope, see, for instance, [80].”
An improved stability criterion for systems with distributed delays (2001, background): “The development of efficient computational algorithm for non-smooth convex optimization problem [2], which made it possible to efficiently solve linear matrix inequalities (LMI) [3, 4], inspired intensive activities to formulate such problems in an LMI form.”
Optimal Affine-Invariant Smooth Minimization Algorithms (2018, methodology): “In fact, the complexity analysis of Newton’s method based on the self-concordance argument developed in [Nesterov and Nemirovskii, 1994] produces affine invariant complexity bounds and the iterates themselves are invariant.”