FBF_PRIMAL_DUAL - forward backward forward primal dual

Usage

sol = fbf_primal_dual(x_0,f1, f2, f3, param);
sol = fbf_primal_dual(x_0,f1, f2, f3);
[sol,info,objective] = fbf_primal_dual(...);

Input parameters

x_0 Starting point of the algorithm
f1 First function to minimize
f2 Second function to minimize
f3 Third function to minimize
param Optional parameters

Output parameters

sol Solution
info Structure summarizing informations at convergence

Description

fbf_primal_dual (using forward backward forward based primal dual) solves:

\begin{equation*} sol = \min_x f_1(x) + f_2( L x) + f_3(x) \end{equation*}

where \(x\) is the optimization variable with \(f_1\) or \(f_3\) a smooth function and \(L\) a linear operator. \(f_1\) and \(f_3\) are defined like other traditional functions.

Note that f2 is a structure of a functions with:

  • f2.eval(x_i) : an operator to evaluate the function
  • f2.prox(x_i, gamma) : an operator to evaluate the prox of the function

Optionally you can define

  • f2.L : linear operator, matrix or operator (default identity)

  • f2.Lt : adjoint of linear operator, matrix or operator (default identity)

  • f2.norm_L : bound on the norm of the operator L (default: 1), i.e.

    \begin{equation*} \|L x\|^2 \leq \nu \|x\|^2 \end{equation*}

param a Matlab structure containing solver paremeters. See the function solvep for more information. Additionally it contains those aditional fields:

  • param.tol : is stopping criterion for the loop. The algorithm stops if

    \begin{equation*} \max_i \frac{ \| y_i(t) - y_i(t-1)\| }{ \|y_i(t)\|} < tol, \end{equation*}

    where \(y_i(t)\) are the dual variable of function i at itertion t by default, tol=10e-4.

    Warning! This stopping criterion is different from other solvers!

  • param.mu : parameter mu of paper [1]

  • param.epsilon: parameter epsilon of paper [1]

  • param.normalized_timestep: from 0 to 1, mapping to [epsilon, (1-epsilon)/mu]

References:

N. Komodakis and J.-C. Pesquet. Playing with duality: An overview of recent primal-dual approaches for solving large-scale optimization problems. arXiv preprint arXiv:1406.5429, 2014.