A single-phase, proximal path-following framework
From MaRDI portal
Publication:5219702
Abstract: We propose a new proximal, path-following framework for a class of constrained convex problems. We consider settings where the nonlinear---and possibly non-smooth---objective part is endowed with a proximity operator, and the constraint set is equipped with a self-concordant barrier. Our approach relies on the following two main ideas. First, we re-parameterize the optimality condition as an auxiliary problem, such that a good initial point is available; by doing so, a family of alternative paths towards the optimum is generated. Second, we combine the proximal operator with path-following ideas to design a single-phase, proximal, path-following algorithm. Our method has several advantages. First, it allows handling non-smooth objectives via proximal operators; this avoids lifting the problem dimension in order to accommodate non-smooth components in optimization. Second, it consists of only a emph{single phase}: While the overall convergence rate of classical path-following schemes for self-concordant objectives does not suffer from the initialization phase, proximal path-following schemes undergo slow convergence, in order to obtain a good starting point cite{TranDinh2013e}. In this work, we show how to overcome this limitation in the proximal setting and prove that our scheme has the same worst-case iteration-complexity with standard approaches cite{Nesterov2004,Nesterov1994} without requiring an initial phase, where is the barrier parameter and is a desired accuracy. Finally, our framework allows errors in the calculation of proximal-Newton directions, without sacrificing the worst-case iteration complexity. We demonstrate the merits of our algorithm via three numerical examples, where proximal operators play a key role.
Recommendations
- An inexact proximal path-following algorithm for constrained convex minimization
- Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
- Common fixed points of an infinite family of nonexpansive mappings in uniformly convex metric spaces
- A weighted path-following method for linearly constrained convex programming
- A new homotopy proximal variable-metric framework for composite convex minimization
Cites work
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Singular Value Thresholding Algorithm for Matrix Completion
- A mathematical view of interior-point methods in convex optimization
- Adaptive restart for accelerated gradient schemes
- An inexact proximal path-following algorithm for constrained convex minimization
- Barrier subgradient method
- Composite self-concordant minimization
- Convex Approximations of Chance Constrained Programs
- Convex analysis and monotone operator theory in Hilbert spaces
- Disciplined convex programming
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Efficient evaluation of scaled proximal operators
- Gradient methods for minimizing composite functions
- Group-Sparse Model Selection: Hardness and Relaxations
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Interior Point Methods for Linear Optimization
- Interior point methods 25 years later
- Interior-point method for nuclear norm approximation with application to system identification
- Interior-point methods for optimization
- Introductory lectures on convex optimization. A basic course.
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Phase retrieval via matrix completion
- Proximal splitting methods in signal processing
- Self-Scaled Barriers and Interior-Point Methods for Convex Programming
- Self-concordant barriers for hyperbolic means
- Solving semidefinite-quadratic-linear programs using SDPT3
- Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms
- Structured sparsity: discrete and convex approaches
- Structured variable selection with sparsity-inducing norms
- Templates for convex cone problems with applications to sparse signal recovery
- Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(4)- An inexact interior-point Lagrangian decomposition algorithm with inexact oracles
- Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization
- An object-oriented implementation of structural path-following
- An inexact proximal path-following algorithm for constrained convex minimization
This page was built for publication: A single-phase, proximal path-following framework
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219702)
