Search

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 assumption being that the third derivative of the objective is bounded by the second derivative. The second branch studies cubic regularized Newton methods (CRNMs) with the main assumption that the second derivative is Lipschitz continuous. We develop a new theoretical analysis for a path-following scheme (PFS) for general self-concordant functions, as opposed to the classical path-following scheme developed for self-concordant barriers. We show that the complexity bound for this scheme is better than that of the Damped Newton Method (DNM) and show that our method has global superlinear convergence. We propose also a new predictor-corrector path-following scheme (PCPFS) that leads to further improvement of constant factors in the complexity guarantees for minimizing general self-concordant functions. We also apply path-following schemes to different classes of constrained optimization problems and obtain the resulting complexity bounds. Finally, we analyze an important subclass of general self-concordant functions, namely a class of strongly convex functions with Lipschitz continuous second derivative, and show that for this subclass CRNMs give even better complexity bounds.

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 theoretical guarantees and the practical performance. In this work, we define a global lower bound for smooth differentiable objectives that is optimal with respect to the collected oracle information. The bound can be readily employed by the Gradient Method with Memory to improve its performance. Further using the machinery underlying the optimal bounds, we introduce a modified version of the estimate sequence that we use to construct an Optimized Gradient Method with Memory possessing the best known convergence guarantees for its class of algorithms, even in terms of the proportionality constant. We additionally equip the method with an adaptive convergence guarantee adjustment procedure that is an effective replacement for line-search. Simulation results on synthetic but otherwise difficult smooth problems validate the theoretical properties of the bound and proposed methods., Comment: 29 pages, 1 figure

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 Gradients} can be used instead for finding approximate solutions to Composite Variational Inequalities by the higher-order schemes. Our methods are optimal since their performance is proportional to the lower worst-case complexity bounds for corresponding problem classes. They enjoy the provable hot-start capabilities even being applied to minimization problems. The primal version of our schemes demonstrates a linear rate of convergence under an appropriate uniform monotonicity assumption.

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 normalization of subgradient, or on the knowledge of optimal value of the objective function, need corrections when they are applied to optimization problems with constraints. Their proper modifications allow a significant acceleration of these schemes when the objective function has favorable properties (smoothness, strong convexity). We show how the new methods can be used for solving optimization problems with functional constraints with possibility to approximate the optimal Lagrange multipliers. One of our primal-dual methods works also for unbounded feasible set.

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 algorithms for quadratic inverse problems with a difference-of-convex structure. We design a first-order method called Homogenized Gradient, along with an accelerated version, which enjoy fast convergence rates of respectively $\mathcal{O}(\kappa^2/K^2)$ and $\mathcal{O}(\kappa^2/K^4)$ in relative accuracy, where $K$ is the iteration counter. The constant $\kappa$ is the quartic condition number of the problem. Then, we show that for a certain class of problems, it is possible to compute a preconditioner for which this condition number is $\sqrt{n}$, where $n$ is the problem dimension. To establish this, we study the more general problem of finding the best quadratic approximation of an $\ell_p$ norm composed with a quadratic map. Our construction involves a generalization of the so-called Lewis weights., Comment: 27 pages, 2 figures

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 problems in relative scale. An important example where relatively inexact subgradients naturally arise is given by the Power or Lanczos algorithms for computing an approximate leading eigenvector of a symmetric positive semidefinite matrix. Using these algorithms as subroutines in our methods, we get new optimization schemes that can provably solve certain large-scale Semidefinite Programming problems with relative accuracy guarantees by using only matrix-vector products.

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 regularization parameter proportional to a certain power of the gradient norm at the current point. We introduce a family of problem classes characterized by H\"older continuity of either the second or third derivative. Then we present the method with a simple adaptive search procedure allowing an automatic adjustment to the problem class with the best global complexity bounds, without knowing specific parameters of the problem. In particular, for the class of functions with Lipschitz continuous third derivative, we get the global $O(1/k^3)$ rate, which was previously attributed to third-order tensor methods. When the objective function is uniformly convex, we justify an automatic acceleration of our scheme, resulting in a faster global rate and local superlinear convergence. The switching between the different rates (sublinear, linear, and superlinear) is automatic. Again, for that, no a priori knowledge of parameters is needed.

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 Lipschitz continuous third-order derivatives. The methods are adaptive in the sense that they do not require the knowledge of the Lipschitz constant. Trial points are computed by the inexact minimization of models that consist in the nonsmooth part of the objective plus a quartic regularization of third-order Taylor polynomial of the smooth part. Specifically, approximate solutions of the auxiliary problems are obtained by using a Bregman gradient method as inner solver. Different from existing adaptive approaches for high-order methods, in our new schemes the regularization parameters are adjusted taking into account the progress of the inner solver. With this technique, we show that the basic method finds an $\epsilon$-approximate minimizer of the objective function performing at most $\mathcal{O}\left(|\log(\epsilon)|\epsilon^{-\frac{1}{3}}\right)$ iterations of the inner solver. An accelerated adaptive third-order method is also presented with total inner iteration complexity of $\mathcal{O}\left(|\log(\epsilon)|\epsilon^{-\frac{1}{4}}\right)$.

In this paper, we propose new linearly convergent second-order methods for minimizing convex quartic polynomials. This framework is applied for designing optimization schemes, which can solve general convex problems satisfying a new condition of quartic regularity. It assumes positive definiteness and boundedness of the fourth derivative of the objective function. For such problems, an appropriate quartic regularization of Damped Newton Method has global linear rate of convergence. We discuss several important consequences of this result. In particular, it can be used for constructing new second-order methods in the framework of high-order proximal-point schemes. These methods have convergence rate $\tilde O(k^{-p})$, where $k$ is the iteration counter, $p$ is equal to 3, 4, or 5, and tilde indicates the presence of logarithmic factors in the complexity bounds for the auxiliary problems, which are solved at each iteration of the schemes.

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 with regularization parameter proportional to the square root of the norm of the current gradient. For the basic scheme, as applied to the composite optimization problem, we establish the global convergence rate of the order $O(k^{-2})$ both in terms of the functional residual and in the norm of subgradients. Our main assumption on the smooth part of the objective is Lipschitz continuity of its Hessian. For uniformly convex functions of degree three, we justify global linear rate, and for strongly convex function we prove the local superlinear rate of convergence. Our approach can be seen as a relaxation of the Cubic Regularization of the Newton method, which preserves its convergence properties, while the auxiliary subproblem at each iteration is simpler. We equip our method with adaptive line search procedure for choosing the regularization parameter. We propose also an accelerated scheme with convergence rate $O(k^{-3})$, where $k$ is the iteration counter.

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) given in [20]. In this continuation paper, we introduce a $p$th-order proximal-point segment search operator which is used to develop novel accelerated methods. Our first algorithm combines the exact element of this operator with the estimating sequence technique to derive new iteration points, which are shown to attain the convergence rate $\mathcal{O}(k^{-(3p+1)/2})$, for the iteration counter $k$. We next consider inexact elements of the high-order proximal-point segment search operator to be employed in the BiOPT framework. We particularly apply the accelerated high-order proximal-point method at the upper level, while we find approximate solutions of the proximal-point segment search auxiliary problem by a combination of non-Euclidean composite gradient and bisection methods. For $q=\lfloor p/2 \rfloor$, this amounts to a $2q$th-order method with the convergence rate $\mathcal{O}(k^{-(6q+1)/2})$ (the same as the optimal bound of $2q$th-order methods) for even $p$ ($p=2q$) and the superfast convergence rate $\mathcal{O}(k^{-(3q+1)})$ for odd $p$ ($p=2q+1$).

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 involves two levels of methodologies. At the upper level of BiOPT, we first regularize the objective by a $(p+1)$th-order proximal term and then develop the generic inexact high-order proximal-point scheme and its acceleration using the standard estimation sequence technique. At the lower level, we solve the corresponding $p$th-order proximal auxiliary problem inexactly either by one iteration of the $p$th-order tensor method or by a lower-order non-Euclidean composite gradient scheme with the complexity $\mathcal{O}(\log \tfrac{1}{\varepsilon})$, for the accuracy parameter $\varepsilon>0$. Ultimately, if the accelerated proximal-point method is applied at the upper level, and the auxiliary problem is handled by a non-Euclidean composite gradient scheme, then we end up with a $2q$-order method with the convergence rate $\mathcal{O}(k^{-(p+1)})$, for $q=\lfloor p/2 \rfloor$, where $k$ is the iteration counter.

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 problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimensionality of the problem is sufficiently large. For generating accuracy certificates in our algorithm, we propose an efficient technique, which ameliorates the previously known recipes.

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 and $H$ with $K$ rows, such that $WH$ approximates $V$ as well as possible. In this paper, we propose two new approaches for computing high-quality NMF solutions using conic optimization. These approaches rely on the same two steps. First, we reformulate NMF as minimizing a concave function over a product of convex cones--one approach is based on the exponential cone, and the other on the second-order cone. Then, we solve these reformulations iteratively: at each step, we minimize exactly, over the feasible set, a majorization of the objective functions obtained via linearization at the current iterate. Hence these subproblems are convex conic programs and can be solved efficiently using dedicated algorithms. We prove that our approaches reach a stationary point with an accuracy decreasing as $\mathcal{O}(\frac{1}{i})$, where $i$ denotes the iteration number. To the best of our knowledge, our analysis is the first to provide a convergence rate to stationary points for NMF. Furthermore, in the particular cases of rank-one factorizations (that is, $K=1$), we show that one of our formulations can be expressed as a convex optimization problem implying that optimal rank-one approximations can be computed efficiently. Finally, we show on several numerical examples that our approaches are able to frequently compute exact NMFs (that is, with $V = WH$), and compete favorably with the state of the art., Comment: Accepted in Optimization Methods and Software

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 convergence towards the optimal solution. This information is used in the form of a piece-wise linear model of the objective function, which provides us with much better prediction abilities as compared with the standard linear model. To the best of our knowledge, this approach was never really applied in Convex Minimization to differentiable functions in view of the high complexity of the corresponding auxiliary problems. However, we show that all necessary computations can be done very efficiently. Consequently, we get new optimization methods, which are better than the usual Gradient Methods both in the number of oracle calls and in the computational time. Our theoretical conclusions are confirmed by preliminary computational experiments., Comment: This is an Accepted Manuscript of an article published by Taylor \& Francis in Optimization Methods and Software on 13 Jan 2021, available at https://www.tandfonline.com/doi/10.1080/10556788.2020.1858831

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 minimization problems, and problems of Composite Minimization, where the objective can have simple nondifferentiable components. We treat all these formulations in a unified way, highlighting the existence of very natural optimization schemes of different order. We prove the global convergence rates for our methods under the most general conditions. Assuming that the upper-level component of our objective function is subhomogeneous, we develop efficient modification of the basic Fully Composite first-order and second-order Methods, and propose their accelerated variants.

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. We present an approach to adjust prices based on the observed online market data. The key idea is to characterize optimal prices as minimizers of a total expected revenue function, which turns out to be convex. We assume that consumers face information processing costs, hence, follow a discrete choice demand model, and suppliers are equipped with quantity adjustment costs. We prove the strong smoothness of the total expected revenue function by deriving the strong convexity modulus of its dual. Our gradient-based pricing schemes outbalance supply and demand at the convergence rates of $\mathcal{O}(\frac{1}{t})$ and $\mathcal{O}(\frac{1}{t^2})$, respectively. This suggests that the imperfect behavior of consumers and suppliers helps to stabilize the market.

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-Point methods, which solve at each iteration an auxiliary subproblem restricting the smooth part of the objective function onto contraction of the initial domain. This framework provides us with a systematic way for developing optimization methods of different order, endowed with the global complexity bounds. We show that using an appropriate affine-invariant smoothness condition, it is possible to implement one iteration of the Contracting-Point method by one step of the pure tensor method of degree $p \geq 1$. The resulting global rate of convergence in functional residual is then ${\cal O}(1 / k^p)$, where $k$ is the iteration counter. It is important that all constants in our bounds are affine-invariant. For $p = 1$, our scheme recovers well-known Frank-Wolfe algorithm, providing it with a new interpretation by a general perspective of tensor methods. Finally, within our framework, we present efficient implementation and total complexity analysis of the inexact second-order scheme $(p = 2)$, called Contracting Newton method. It can be seen as a proper implementation of the trust-region idea. Preliminary numerical results confirm its good practical performance both in the number of iterations, and in computational time.

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 discrete-time model allowing a reconstruction of the dynamics of asymptomatic virus holders using the available daily statistics on the number of new cases. We suggest to use a new indicator, the total infection rate, to distinguish the propagation and recession modes of the epidemic. We check our indicator on the available data for eleven different countries and for the whole world. Our reconstructions are very precise. In several cases, we are able to detect the exact dates of the disastrous political decisions, ensuring the second wave of the epidemics. It appears that for all our examples the decisions made on the basis of the current number of new cases are wrong. In this paper, we suggest a reasonable alternative. Our analysis shows that all tested countries are in a dangerous zone except Sweden., Comment: 24 pages, 13 figures

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 on global second-order lower approximation for the smooth component of the objective. Our approach has an interpretation both as a second-order generalization of the conditional gradient method, or as a variant of trust-region scheme. Under the assumption, that the problem domain is bounded, we prove $\mathcal{O}(1/k^{2})$ global rate of convergence in functional residual, where $k$ is the iteration counter, minimizing convex functions with Lipschitz continuous Hessian. This significantly improves the previously known bound $\mathcal{O}(1/k)$ for this type of algorithms. Additionally, we propose a stochastic extension of our method, and present computational results for solving empirical risk minimization problem.

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 improvement in the currently known estimates of the convergence rates for these methods. In particular, we show that the corresponding rate of the Broyden-Fletcher-Goldfarb-Shanno method depends only on the product of the dimensionality of the problem and the logarithm of its condition number., Comment: J Optim Theory Appl (2021). arXiv admin note: text overlap with arXiv:2003.09174

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 converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular, for the well-known DFP and BFGS methods, we obtain the rates of the form $(\frac{n L^2}{\mu^2 k})^{k/2}$ and $(\frac{n L}{\mu k})^{k/2}$ respectively, where $k$ is the iteration counter, $n$ is the dimension of the problem, $\mu$ is the strong convexity parameter, and $L$ is the Lipschitz constant of the gradient.

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$. Our method can be seen both as a {\em stochastic} extension of the cubically-regularized Newton method of Nesterov and Polyak (2006), and a {\em second-order} enhancement of stochastic subspace descent of Kozak et al. (2019). We prove that as we vary the minibatch size, the global convergence rate of SSCN interpolates between the rate of stochastic coordinate descent (CD) and the rate of cubic regularized Newton, thus giving new insights into the connection between first and second-order methods. Remarkably, the local convergence rate of SSCN matches the rate of stochastic subspace descent applied to the problem of minimizing the quadratic function $\frac12 (x-x^*)^\top \nabla^2f(x^*)(x-x^*)$, where $x^*$ is the minimizer of $f$, and hence depends on the properties of $f$ at the optimum only. Our numerical experiments show that SSCN outperforms non-accelerated first-order CD algorithms while being competitive to their accelerated variants., Comment: 29 pages, 5 figures, 1 table, 1 algorithm

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 solution of the auxiliary problem, defined by the bound for the residual in function value. We propose two dynamic strategies for choosing the inner accuracy: the first one is decreasing as $1/k^{p + 1}$, where $p \geq 1$ is the order of the method and $k$ is the iteration counter, and the second approach is using for the inner accuracy the last progress in the target objective. We show that inexact Tensor Methods with these strategies achieve the same global convergence rate as in the error-free case. For the second approach we also establish local superlinear rates (for $p \geq 2$), and propose the accelerated scheme. Lastly, we present computational results on a variety of machine learning problems for several methods and different accuracy policies.

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 includes the well-known DFP, BFGS and SR1 updates. However, in contrast to the classical quasi-Newton methods, which use the difference of successive iterates for updating the Hessian approximations, our methods apply basis vectors, greedily selected so as to maximize a certain measure of progress. For greedy quasi-Newton methods, we establish an explicit non-asymptotic bound on their rate of local superlinear convergence, which contains a contraction factor, depending on the square of the iteration counter. We also show that these methods produce Hessian approximations whose deviation from the exact Hessians linearly convergences to zero.

We show that H\"older 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 first-order Taylor approximation. We also relate this global upper bound to the H\"older constant of the gradient. This relation is expressed as an interval, depending on the H\"older constant, in which the error of the first-order Taylor approximation is guaranteed to be. We show that, for the Lipschitz continuous case, the interval cannot be reduced. An application to the norms of quadratic forms is proposed, which allows us to derive a novel characterization of Euclidean norms.

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 contracted version of the objective function augmented by a regularization term in the form of Bregman divergence. We provide global convergence analysis for a general scheme admitting inexactness in solving the auxiliary subproblem. In the case of using for this purpose high-order tensor methods, we demonstrate an acceleration effect for both convex and uniformly convex composite objective functions. Thus, our construction explains acceleration for methods of any order starting from one. The augmentation of the number of calls of oracle due to computing the contracted proximal steps is limited by the logarithmic factor in the worst-case complexity bound.

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 under the assumption of uniform convexity of the smooth component, having Lipschitz-continuous high-order derivative. The convergence both in function value and in the norm of minimal subgradient is established. Global complexity bounds for the Composite Tensor Method in convex and uniformly convex cases are also discussed. Lastly, we show how local convergence of the methods can be globalized using the inexact proximal iterations.

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, we explicitly derive the convexity parameter of discrete choice prox-functions associated with generalized extreme value models, and specifically with generalized nested logit models. Incorporated into subgradient schemes, discrete choice prox-functions lead to natural probabilistic interpretations of the iteration steps. As illustration we discuss an economic application of discrete choice prox-functions in consumer theory. The dual averaging scheme from convex programming naturally adjusts demand within a consumption cycle.

In this paper we study the auxiliary problems that appear in $p$-order tensor methods for unconstrained minimization of convex functions with $\nu$-H\"{o}lder continuous $p$th derivatives. This type of auxiliary problems corresponds to the minimization of a $(p+\nu)$-order regularization of the $p$th order Taylor approximation of the objective. For the case $p=3$, we consider the use of Gradient Methods with Bregman distance. When the regularization parameter is sufficiently large, we prove that the referred methods take at most $\mathcal{O}(\log(\epsilon^{-1}))$ iterations to find either a suitable approximate stationary point of the tensor model or an $\epsilon$-approximate stationary point of the original objective function.

In this paper, we study derivatives of powers of Euclidean norm. We prove their H\"older continuity and establish explicit expressions for the corresponding constants. We show that these constants are optimal for odd derivatives and at most two times suboptimal for the even ones. In the particular case of integer powers, when the H\"older continuity transforms into the Lipschitz continuity, we improve this result and obtain the optimal constants., Comment: J Optim Theory Appl (2020)

In this paper we consider the problem of finding $\epsilon$-approximate stationary points of convex functions that are $p$-times differentiable with $\nu$-H\"{o}lder continuous $p$th derivatives. We present tensor methods with and without acceleration. Specifically, we show that the non-accelerated schemes take at most $\mathcal{O}\left(\epsilon^{-1/(p+\nu-1)}\right)$ iterations to reduce the norm of the gradient of the objective below a given $\epsilon\in (0,1)$. For accelerated tensor schemes we establish improved complexity bounds of $\mathcal{O}\left(\epsilon^{-(p+\nu)/[(p+\nu-1)(p+\nu+1)]}\right)$ and $\mathcal{O}\left(|\log(\epsilon)|\epsilon^{-1/(p+\nu)}\right)$, when the H\"{o}lder parameter $\nu\in [0,1]$ is known. For the case in which $\nu$ is unknown, we obtain a bound of $\mathcal{O}\left(\epsilon^{-(p+1)/[(p+\nu-1)(p+2)]}\right)$ for a universal accelerated scheme. Finally, we also obtain a lower complexity bound of $\mathcal{O}\left(\epsilon^{-2/[3(p+\nu)-2]}\right)$ for finding $\epsilon$-approximate stationary points using $p$-order tensor methods., Comment: arXiv admin note: text overlap with arXiv:1904.12559

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 the notion of second-order condition number of a certain degree and justify the linear rate of convergence in a nondegenerate case for the method with an adaptive estimate of the regularization parameter. The algorithm automatically achieves the best possible global complexity bound among different problem classes of uniformly convex objective functions with H\"older continuous Hessian of the smooth part of the objective. As a byproduct of our developments, we justify an intuitively plausible result that the global iteration complexity of the Newton method is always better than that of the gradient method on the class of strongly convex functions with uniformly bounded second derivative.

In this paper we study $p$-order methods for unconstrained minimization of convex functions that are $p$-times differentiable ($p\geq 2$) with $\nu$-H\"{o}lder continuous $p$th derivatives. We propose tensor schemes with and without acceleration. For the schemes without acceleration, we establish iteration complexity bounds of $\mathcal{O}\left(\epsilon^{-1/(p+\nu-1)}\right)$ for reducing the functional residual below a given $\epsilon\in (0,1)$. Assuming that $\nu$ is known, we obtain an improved complexity bound of $\mathcal{O}\left(\epsilon^{-1/(p+\nu)}\right)$ for the corresponding accelerated scheme. For the case in which $\nu$ is unknown, we present a universal accelerated tensor scheme with iteration complexity of $\mathcal{O}\left(\epsilon^{-p/[(p+1)(p+\nu-1)]}\right)$. A lower complexity bound of $\mathcal{O}\left(\epsilon^{-2/[3(p+\nu)-2]}\right)$ is also obtained for this problem class., Comment: arXiv admin note: text overlap with arXiv:1907.07053

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 equations that are usually associated with such systems are related to boundary points of the convex set defined by the solution set of the LMI. It is shown that the analytic center is described by closely related matrix equations, and their properties are analyzed for continuous- and discrete-time systems. Numerical methods are derived to solve these equations via steepest ascent and Newton-like methods. It is also shown that the analytic center has nice robustness properties when it is used to represent passive systems. The results are illustrated by numerical examples., Comment: Supplementary code: https://doi.org/10.5281/zenodo.2643171

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 for the practical accelerations of convergence, converges accordingto the well-known lower bounds for both convex and non-convex objective functions,possesses primal-dual properties and can be applied in the non-euclidian set-up. Asfar as we know this is the rst such method possessing all of the above properties atthe same time. We also present a universal version of the method which is applicableto non-smooth problems. We demonstrate how in practice one can efficiently use thecombination of line-search and primal-duality by considering a convex optimizationproblem with a simple structure (for example, linearly constrained).

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 Lipschitz constant $L$. However, in many settings the differentiable convex function $f(\cdot)$ is not uniformly smooth -- for example in $D$-optimal design where $f(x):=-\ln \det(HXH^T)$, or even the univariate setting with $f(x) := -\ln(x) + x^2$. Herein we develop a notion of "relative smoothness" and relative strong convexity that is determined relative to a user-specified "reference function" $h(\cdot)$ (that should be computationally tractable for algorithms), and we show that many differentiable convex functions are relatively smooth with respect to a correspondingly fairly-simple reference function $h(\cdot)$. We extend two standard algorithms -- the primal gradient scheme and the dual averaging scheme -- to our new setting, with associated computational guarantees. We apply our new approach to develop a new first-order method for the $D$-optimal design problem, with associated computational complexity analysis. Some of our results have a certain overlap with the recent work \cite{bbt}.

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 to its large scale, second-order methods cannot solve the free material design problem in reasonable size. We formulate the free material optimization (FMO) problem into a saddle-point form in which the inverse of the stiffness matrix A(E) in the constraint is eliminated. The size of A(E) is generally large, denoted as N by N. This is the first formulation of FMO without A(E). We apply the primal-dual subgradient method [17] to solve the restricted saddle-point formula. This is the first gradient-type method for FMO. Each iteration of our algorithm takes a total of $O(N^2)$ foating-point operations and an auxiliary vector storage of size O(N), compared with formulations having the inverse of A(E) which requires $O(N^3)$ arithmetic operations and an auxiliary vector storage of size $O(N^2)$. To solve the problem, we developed a closed-form solution to a semidefinite least squares problem and an efficient parameter update scheme for the gradient method, which are included in the appendix. We also approximate a solution to the bounded Lagrangian dual problem. The problem is decomposed into small problems each only having an unknown of k by k (k = 3 or 6) matrix, and can be solved in parallel. The iteration bound of our algorithm is optimal for general subgradient scheme. Finally we present promising numerical results., Comment: SIAM Journal on Optimization (accepted)

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 method for the dual problem. There are two ways to recover the solution of the primal problem. First technique is based on "models" approach and second one is based on Lagrange multiplyers technique. Both approaches have its own advantages and drawbacks. We discuss them., Comment: 11 pages, in Russian

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 geometric description. We generalize TM for convex and strictly convex composite optimization problems. Then we propose Universal Triangle Method (UTM) for convex and strictly convex composite optimization problems (see Yu. Nesterov, Math. Program. 2015. for more details about what is Universal Fast Gradient Method). Finally, based on mini-batch technique we propose Stochastic Universal Triangle Method (SUTM). SUTM can be applied to stochastic convex and strictly convex composite optimization problems. Denote, that all the methods TM, UTM, SUTM are continuous on strictly convexity parameter and all of them reach known lower bounds. With additional assumption about the structure of the problems these methods work better than the lower bounds., Comment: in Russian

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 approaches such as the classical PageRank model. We propose gradient-based and random gradient-free methods to solve this problem. Our algorithms are based on the concept of an inexact oracle and unlike the state state-of-the-art gradient-based method we manage to provide theoretically the convergence rate guarantees for both of them. In particular, under the assumption of local convexity of the loss function, our random gradient-free algorithm guarantees decrease of the loss function value expectation. At the same time, we theoretically justify that without convexity assumption for the loss function our gradient-based algorithm allows to find a point where the stationary condition is fulfilled with a given accuracy. For both proposed optimization algorithms, we find the settings of hyperparameters which give the lowest complexity (i.e., the number of arithmetic operations needed to achieve the given accuracy of the solution of the loss-minimization problem). The resulting estimates of the complexity are also provided. Finally, we apply proposed optimization algorithms to the web page ranking problem and compare proposed and state-of-the-art algorithms in terms of the considered loss function., Comment: 34 pages, 5 figures

In this paper, we propose three methods to solve the PageRank problem for the transition matrices with both row and column sparsity. Our methods reduce the PageRank problem to the convex optimization problem over the simplex. The first algorithm is based on the gradient descent in L1 norm instead of the Euclidean one. The second algorithm extends the Frank-Wolfe to support sparse gradient updates. The third algorithm stands for the mirror descent algorithm with a randomized projection. We proof converges rates for these methods for sparse problems as well as numerical experiments support their effectiveness., Comment: 26 pages; Accepted to Optimization Methods and Software

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 combination of Universal Gradient Method proposed by Yu. Nesterov (2013) and conception of inexact oracle (Devolder--Glineur--Nesterov, 2011). In particular our technique allows us to calculate Wasserstein's Barycenter in a fast manner (this results generalized M. Cuturi et al. (2014))., Comment: 26 pages, in Russian, TRUDY MIPT. 2016. V. 8. no. 3

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 PageRank algorithm. Due to huge hidden dimension of the optimization problem we use random gradient-free methods to solve it. We prove a convergence theorem and estimate the number of arithmetic operations needed to solve it with a given accuracy. We find the best settings of the gradient-free optimization method in terms of the number of arithmetic operations needed to achieve given accuracy of the objective. In the paper, we apply our algorithm to the web page ranking problem. We consider a parametric graph model of users' behavior and evaluate web pages' relevance to queries by our algorithm. The experiments show that our optimization method outperforms the untuned gradient-free method in the ranking quality., Comment: 11 pages

In the article we lead a brief survey of contemporary gradient type methods (with inexact oracle) for stochastic optimization problems., Comment: 60 pages, in Russian

We propose an efficient dual algorithm for ELP based on Fast Gradient Method. The basic idea - to solve properly regularized dual problem., Comment: 19 pages, in Russian

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-Yudin, 1979) with dual averaging (Nesterov, 2005) and Grigoriadis-Khachiyan algorithm (1995). Grigoriadis-Khachiyan algorithm has just proved to be a randomized mirror descent (dual averaging) with randomization in KL-projection of (sub)gradient to a unit simplex. We found out that this randomization is an optimal way of solving sparse matrix games and some other problems arising in convex optimization and experts weighting., Comment: 26 pages, in Russian

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 model and the model of the equilibrium distribution of flows (Stable dynamic model, Nesterov - de Palma, 2003). To best of our knowledge, this is the first attempt to combine this three models. Previously such attempts were done for other types of equlibrium models, mainly with the BMW-model (1955), the calibration of which is significantly more difficult. We also remark, that our model much better then traditional from computational point of view., Comment: 48 pages, Russian

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 problem, aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively. While the initial formulations involve nonconvex functions, and are therefore computationally intractable, we rewrite them into the form of an optimization program involving maximization of a convex function on a compact set. The dimension of the search space is decreased enormously if the data matrix has many more columns (variables) than rows. We then propose and analyze a simple gradient method suited for the task. It appears that our algorithm has best convergence properties in the case when either the objective function or the feasible set are strongly convex, which is the case with our single-unit formulations and can be enforced in the block case. Finally, we demonstrate numerically on a set of random and gene expression test problems that our approach outperforms existing algorithms both in quality of the obtained solution and in computational speed., Comment: Submitted

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 quantity appears in a number of application contexts but is notoriously difficult to compute and to approximate. We introduce in this paper a procedure for approximating the joint spectral radius of a finite set of matrices with arbitrary high accuracy. Our approximation procedure is polynomial in the size of the matrices once the number of matrices and the desired accuracy are fixed.