A single-phase, proximal path-following framework

DOI10.1287/MOOR.2017.0907zbMATH Open1440.90025arXiv1603.01681OpenAlexW2962970587WikidataQ129405825 ScholiaQ129405825MaRDI QIDQ5219702FDOQ5219702

Authors: Quoc Tran Dinh, Anastasios Kyrillidis, Volkan Cevher 

Publication date: 12 March 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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 $mathcalO(sqrtulog(1/varepsilon))$ worst-case iteration-complexity with standard approaches cite{Nesterov2004,Nesterov1994} without requiring an initial phase, where $u$ is the barrier parameter and $varepsilon$ 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.

Full work available at URL: https://arxiv.org/abs/1603.01681

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

zbMATH Keywords

self-concordant barriernonsmooth convex optimizationinterior-point methodproximal Newton methodpath-following scheme

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Cites Work

• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Disciplined convex programming
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Templates for convex cone problems with applications to sparse signal recovery
• Solving semidefinite-quadratic-linear programs using SDPT3
• Phase retrieval via matrix completion
• Title not available (Why is that?)
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex analysis and monotone operator theory in Hilbert spaces
• Introductory lectures on convex optimization. A basic course.
• Adaptive restart for accelerated gradient schemes
• A Singular Value Thresholding Algorithm for Matrix Completion
• Gradient methods for minimizing composite functions
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Proximal splitting methods in signal processing
• Title not available (Why is that?)
• Interior point methods 25 years later
• A mathematical view of interior-point methods in convex optimization
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Convex Approximations of Chance Constrained Programs
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
• Interior-point method for nuclear norm approximation with application to system identification
• Structured variable selection with sparsity-inducing norms
• Interior Point Methods for Linear Optimization
• Composite self-concordant minimization
• Interior-point methods for optimization
• An inexact proximal path-following algorithm for constrained convex minimization
• Efficient evaluation of scaled proximal operators
• Barrier subgradient method
• Group-Sparse Model Selection: Hardness and Relaxations
• Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms
• Structured sparsity: discrete and convex approaches
• Self-concordant barriers for hyperbolic means

Cited In (4)

• An inexact proximal path-following algorithm for constrained convex minimization
• An inexact interior-point Lagrangian decomposition algorithm with inexact oracles
• An object-oriented implementation of structural path-following
• Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization

Uses Software

• SeDuMi
• SDPT3
• YALMIP
• Mosek
• Robotics
• TFOCS
• PhaseLift

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)