This paper considers the problem of unconstrained minimization of smooth convex functions having Lipschitz continuous gradients with known Lipschitz constant. We recently proposed the optimized gradient method for thi...
详细信息
This paper considers the problem of unconstrained minimization of smooth convex functions having Lipschitz continuous gradients with known Lipschitz constant. We recently proposed the optimized gradient method for this problem and showed that it has a worst-case convergence bound for the cost function decrease that is twice as small as that of Nesterov's fast gradient method, yet has a similarly efficient practical implementation. Drori showed recently that the optimized gradient method has optimal complexity for the cost function decrease over the general class of first-order methods. This optimality makes it important to study fully the convergence properties of the optimized gradient method. The previous worst-case convergence bound for the optimized gradient method was derived for only the last iterate of a secondary sequence. This paper provides an analytic convergence bound for the primary sequence generated by the optimized gradient method. We then discuss additional convergence properties of the optimized gradient method, including the interesting fact that the optimized gradient method has two types of worst-case functions: a piecewise affine-quadratic function and a quadratic function. These results help complete the theory of an optimal first-order method for smooth convex minimization.
We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle (Math Program 145(1-2):451-482, 2014. doi: 10.1007/s10107-013-0653-0"10.1007/s10107-013-0653-0"...
详细信息
We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle (Math Program 145(1-2):451-482, 2014. doi: 10.1007/s10107-013-0653-0"10.1007/s10107-013-0653-0" TargetType=) recently described a numerical method for computing the N-iteration optimal step coefficients in a class of first-order algorithms that includes gradient methods, heavy-ball methods (Polyak in USSR Comput Math Math Phys 4(5):1-17, 1964. doi: 10.1016/0041-5553(64)90137-510.1016/0041-5553(64)90137-5" TargetType="DOI), and Nesterov's fast gradient methods (Nesterov in Sov Math Dokl 27(2):372-376, 1983;Math Program 103(1):127-152, 2005. doi: 10.1007/s10107-004-0552-510.1007/s10107-004-0552-5" TargetType=). However, the numerical method in Drori and Teboulle (2014) is computationally expensive for large N, and the corresponding numerically optimized first-order algorithm in Drori and Teboulle (2014) requires impractical memory and computation for large-scale optimization problems. In this paper, we propose optimized first-order algorithms that achieve a convergence bound that is two times smaller than for Nesterov's fast gradient methods;our bound is found analytically and refines the numerical bound in Drori and Teboulle (2014). Furthermore, the proposed optimized first-order methods have efficient forms that are remarkably similar to Nesterov's fast gradient methods.
We propose an iterative gradient-based algorithm to efficiently solve the portfolio selection problem with multiple spectral risk constraints. Since the conditional value-at-risk (CVaR) is a special case of the spectr...
详细信息
We propose an iterative gradient-based algorithm to efficiently solve the portfolio selection problem with multiple spectral risk constraints. Since the conditional value-at-risk (CVaR) is a special case of the spectral risk measure, our algorithm solves portfolio selection problems with multiple CVaR constraints. In each step, the algorithm solves very simple separable convex quadratic programs;hence, we show that the spectral risk constrained portfolio selection problem can be solved using the technology developed for solving mean-variance problems. The algorithm extends to the case where the objective is a weighted sum of the mean return and either a weighted combination or the maximum of a set of spectral risk measures. We report numerical results that show that our proposed algorithm is very efficient;it is at least one order of magnitude faster than the state-of-the-art general purpose solver for all practical instances. One can leverage this efficiency to be robust against model risk by including constraints with respect to several different risk models.
The Lasso is an optimization problem devoted to finding a sparse representation of some signal with respect to a pre-defined dictionary. An original and computationally-efficient method is proposed here to solve this ...
详细信息
ISBN:
(纸本)9780992862619
The Lasso is an optimization problem devoted to finding a sparse representation of some signal with respect to a pre-defined dictionary. An original and computationally-efficient method is proposed here to solve this problem, based on a dynamic screening principle. It makes it possible to accelerate a large class of optimization algorithms by iteratively reducing the size of the dictionary during the optimization process, discarding elements that are provably known not to belong to the solution of the Lasso. The iterative reduction of the dictionary is what we call dynamic screening. As this screening step is inexpensive, the computational cost of the algorithm using our dynamic screening strategy is lower than that of the base algorithm. Numerical experiments on synthetic and real data support the relevance of this approach.
暂无评论