Fast alternating linearization methods for minimizing the sum of two convex functions (Q378095): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(12 intermediate revisions by 9 users not shown) | |||
Property / author | |||
Property / author: Shi-Qian Ma / rank | |||
Property / author | |||
Property / author: Shi-Qian Ma / rank | |||
Normal rank | |||
Property / review text | |||
The authors propose the following convex optimization problem: (1) \(\min_{x \in \mathbb R^n} F(x) \equiv f(x) + g(x)\), where \((f,g):\mathbb R^n \rightarrow \mathbb R\) are both convex functions such that two problems are easy to solve for any \(\mu >0\) and \(z \in \mathbb R^n\) relative to minimizing \(F(x)\): (2) \(\min_{x \in \mathbb R^n} \{f(x) + \frac{1}{2\mu}\|x-z\|^2\}\) and (3) \(\min_{x \in \mathbb R^n} \{g(x) + \frac{1}{2\mu}\|x-z\|^2\}\) where \(f(.)\) (\(g(.)\), resp.) is a function of a matrix \(X \in \mathbb R^{m\times n}\). Problem (2) ((3), resp.) is associated with a matrix \(Z \in \mathbb R^{m \times n}\) instead of \(z \in \mathbb R^n\) and the \(\|. \|\) norm is the Frobenius norm. For large-scale problems, the class of alternating direction methods that are based on a variable splitting combined with the augmented Lagrangian method are particularly important. In these methods, one splits the variable \(x\) into two variables, i.e., one introduces a new variable \(y\) and rewrites Problem (1) as (4) \(\min \{ f(x) + g(y): x-y = 0\). Since problem (4) is an equality constrained problem, the augmented Lagrangian method can be used to solve it. Another important and related class of algorithms for solving (1) is based on operator splitting. The aim of these algorithms is to find an \(x\) such that \(0 \in T_1 (x) + T_2 (x)\), where \(T_1\) and \(T_2\) are maximal monotone operators. This is a more general problem than (1). Main result: The global convergence results for various splitting and alternating direction algorithms are established under appropriate conditions, the authors' interest here is on iteration complexity bounds for such algorithms. Finally, numerical results are proposed. These results demonstrate the efficiency and the practical potential of authors' algorithms. | |||
Property / review text: The authors propose the following convex optimization problem: (1) \(\min_{x \in \mathbb R^n} F(x) \equiv f(x) + g(x)\), where \((f,g):\mathbb R^n \rightarrow \mathbb R\) are both convex functions such that two problems are easy to solve for any \(\mu >0\) and \(z \in \mathbb R^n\) relative to minimizing \(F(x)\): (2) \(\min_{x \in \mathbb R^n} \{f(x) + \frac{1}{2\mu}\|x-z\|^2\}\) and (3) \(\min_{x \in \mathbb R^n} \{g(x) + \frac{1}{2\mu}\|x-z\|^2\}\) where \(f(.)\) (\(g(.)\), resp.) is a function of a matrix \(X \in \mathbb R^{m\times n}\). Problem (2) ((3), resp.) is associated with a matrix \(Z \in \mathbb R^{m \times n}\) instead of \(z \in \mathbb R^n\) and the \(\|. \|\) norm is the Frobenius norm. For large-scale problems, the class of alternating direction methods that are based on a variable splitting combined with the augmented Lagrangian method are particularly important. In these methods, one splits the variable \(x\) into two variables, i.e., one introduces a new variable \(y\) and rewrites Problem (1) as (4) \(\min \{ f(x) + g(y): x-y = 0\). Since problem (4) is an equality constrained problem, the augmented Lagrangian method can be used to solve it. Another important and related class of algorithms for solving (1) is based on operator splitting. The aim of these algorithms is to find an \(x\) such that \(0 \in T_1 (x) + T_2 (x)\), where \(T_1\) and \(T_2\) are maximal monotone operators. This is a more general problem than (1). Main result: The global convergence results for various splitting and alternating direction algorithms are established under appropriate conditions, the authors' interest here is on iteration complexity bounds for such algorithms. Finally, numerical results are proposed. These results demonstrate the efficiency and the practical potential of authors' algorithms. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jan Lovíšek / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65K05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C06 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6225201 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
convex optimization | |||
Property / zbMATH Keywords: convex optimization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
variable splitting | |||
Property / zbMATH Keywords: variable splitting / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
alternating linearization method | |||
Property / zbMATH Keywords: alternating linearization method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
alternating direction method | |||
Property / zbMATH Keywords: alternating direction method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
augmented Langrangian method | |||
Property / zbMATH Keywords: augmented Langrangian method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
optimal gradient method | |||
Property / zbMATH Keywords: optimal gradient method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Gauss-Seidel method | |||
Property / zbMATH Keywords: Gauss-Seidel method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Peaceman-Rachford method | |||
Property / zbMATH Keywords: Peaceman-Rachford method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
convergence | |||
Property / zbMATH Keywords: convergence / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
algorithm | |||
Property / zbMATH Keywords: algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
subgradient | |||
Property / zbMATH Keywords: subgradient / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Lipschitz constant | |||
Property / zbMATH Keywords: Lipschitz constant / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Lipschitz continuous gradient | |||
Property / zbMATH Keywords: Lipschitz continuous gradient / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
large-scale problems | |||
Property / zbMATH Keywords: large-scale problems / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
maximal monotone operators | |||
Property / zbMATH Keywords: maximal monotone operators / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
iteration complexity bounds | |||
Property / zbMATH Keywords: iteration complexity bounds / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
numerical results | |||
Property / zbMATH Keywords: numerical results / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q101200642 / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: RecPF / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: glasso / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2010286849 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0912.4571 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Image Recovery Using Variable Splitting and Constrained Optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3096116 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3151174 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Robust principal component analysis? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Exact matrix completion via convex optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Power of Convex Relaxation: Near-Optimal Matrix Completion / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Solving monotone inclusions via compositions of nonexpansive averaged operators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Signal Recovery by Proximal Forward-Backward Splitting / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Compressed sensing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A family of projective splitting methods for the sum of two maximal monotone operators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An EM algorithm for wavelet-based image restoration / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sparse inverse covariance estimation with the graphical lasso / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A dual algorithm for the solution of nonlinear variational problems via finite element approximation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3995612 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Multiple-Splitting Algorithms for Convex Optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convergence of fixed-point continuation algorithms for matrix rank minimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast first-order methods for composite convex optimization with backtracking / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Split Bregman Method for L1-Regularized Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new inexact alternating directions method for monotone variational inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An alternating direction-based contraction method for linearly constrained separable convex programming problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matrix Completion From a Few Entries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Proximal Decomposition Via Alternating Linearization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Splitting Algorithms for the Sum of Two Nonlinear Operators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fixed point and Bregman iterative methods for matrix rank minimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Regularization Methods for Semidefinite Programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Introductory lectures on convex optimization. A basic course. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Smooth minimization of non-smooth functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Numerical Solution of Parabolic and Elliptic Differential Equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Partial inverse of a monotone operator / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3161693 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Alternating direction augmented Lagrangian methods for semidefinite programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Model selection and estimation in the Gaussian graphical model / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4908856 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:37, 7 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast alternating linearization methods for minimizing the sum of two convex functions |
scientific article |
Statements
Fast alternating linearization methods for minimizing the sum of two convex functions (English)
0 references
11 November 2013
0 references
The authors propose the following convex optimization problem: (1) \(\min_{x \in \mathbb R^n} F(x) \equiv f(x) + g(x)\), where \((f,g):\mathbb R^n \rightarrow \mathbb R\) are both convex functions such that two problems are easy to solve for any \(\mu >0\) and \(z \in \mathbb R^n\) relative to minimizing \(F(x)\): (2) \(\min_{x \in \mathbb R^n} \{f(x) + \frac{1}{2\mu}\|x-z\|^2\}\) and (3) \(\min_{x \in \mathbb R^n} \{g(x) + \frac{1}{2\mu}\|x-z\|^2\}\) where \(f(.)\) (\(g(.)\), resp.) is a function of a matrix \(X \in \mathbb R^{m\times n}\). Problem (2) ((3), resp.) is associated with a matrix \(Z \in \mathbb R^{m \times n}\) instead of \(z \in \mathbb R^n\) and the \(\|. \|\) norm is the Frobenius norm. For large-scale problems, the class of alternating direction methods that are based on a variable splitting combined with the augmented Lagrangian method are particularly important. In these methods, one splits the variable \(x\) into two variables, i.e., one introduces a new variable \(y\) and rewrites Problem (1) as (4) \(\min \{ f(x) + g(y): x-y = 0\). Since problem (4) is an equality constrained problem, the augmented Lagrangian method can be used to solve it. Another important and related class of algorithms for solving (1) is based on operator splitting. The aim of these algorithms is to find an \(x\) such that \(0 \in T_1 (x) + T_2 (x)\), where \(T_1\) and \(T_2\) are maximal monotone operators. This is a more general problem than (1). Main result: The global convergence results for various splitting and alternating direction algorithms are established under appropriate conditions, the authors' interest here is on iteration complexity bounds for such algorithms. Finally, numerical results are proposed. These results demonstrate the efficiency and the practical potential of authors' algorithms.
0 references
convex optimization
0 references
variable splitting
0 references
alternating linearization method
0 references
alternating direction method
0 references
augmented Langrangian method
0 references
optimal gradient method
0 references
Gauss-Seidel method
0 references
Peaceman-Rachford method
0 references
convergence
0 references
algorithm
0 references
subgradient
0 references
Lipschitz constant
0 references
Lipschitz continuous gradient
0 references
large-scale problems
0 references
maximal monotone operators
0 references
iteration complexity bounds
0 references
numerical results
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references