text:
\section{Introduction}

Nonconvex and nonsmooth sparse optimization problems
have been becoming a prevalent research topic in many disciplines of applied mathematics and engineering.  Indeed, there has been a tremendous increase in a number of application areas in which
nonconvex sparsity-inducing techniques  have been employed, such as machine learning \cite{bradley1998feature,ml2, bach2012optimization}, wireless communications \cite{Shi2016Smoothed,gsbf, Tao_TWC16, qin2018sparse}, image reconstruction \cite{image1,ochs2015iteratively}, sparse recovery \cite{daubechies2010iteratively,malek2014iterative}, signal processing \cite{candes2008enhancing,miosso2009compressive}, and high-dimensional statistics \cite{wainwright2014structured, hastie2015statistical}.
This is mainly because of their superior ability to  reduce the complexity of a system, improve the generalization of the prediction performance, or enhance the robustness of the solution via enhancing the sparsity, compared with conventional convex sparsity-inducing techniques.

Despite their wide application, nonconvex and nonsmooth sparse optimization problems are computationally challenging to solve
due to the nonconvex and nonsmooth nature of the sparsity-inducing functions. A popular method for handling the nonconvex penalty problems is the iteratively reweighted algorithm, which approximates the nonconvex and nonsmooth problem by a sequence of trackable convex subproblems.
There have been some  iteratively reweighted algorithms   proposed for special cases of the nonconvex and nonsmooth problems.
For example, in~\cite{chartrand2008iteratively,ling2013decentralized}, Yin \emph{et al}. designed an  iteratively reweighted algorithm  for solving the unconstrained nonconvex $\ell_p$ norm model.    In~\cite{lu2014iterative}, Lu has  analyzed the global convergence of a class of reweighted algorithms  for the unconstrained nonconvex $\ell_p$ regularized problem.
The constrained $\ell_p$-regularization problem is studied to improve the image restoration using a priori information and  the optimality condition of this problem is provided in \cite{wang2015optimality}.
The critical technique of this type of algorithms is to add relaxation parameters to transform the nonconvex and nonsmooth sparsity-inducing terms into smooth approximate functions and then use linearization to obtain convex subproblems \cite{chen2010convergence,lai2011unconstrained}. It should be noticed that the relaxation parameter should be driven to zero in order to obtain the solution of the original unrelaxed problem.
Two most popular variants of iteratively reweighted type of algorithms are the iteratively reweighted $\ell_1$ minimization and the iteratively reweighted $\ell_2$ minimization. The former has  convex but nonsmooth subproblem, while  the latter leads to  convex and smooth  subproblems.
It has been reported by Candes \emph{et al.} in  \cite{candes2008enhancing} that the reweighted $\ell_1$ minimization can significantly enhance sparsity of the solution.  It has been demonstrated that iteratively reweighted least-squares have greatly promoted the computation and correctness of robust regression estimation \cite{holland1977robust,street1988note}.

However, iteratively reweighed algorithms are generally difficult to track and analyze. This is mainly because most nonconvex functions are  non-Lipschitz continuous, especially around sparse solutions that we are particularly interested in.  The major issue caused by this situation is  that the optimal solution cannot be  characterized by common optimality conditions. For some special cases where the sparsity-inducing term is $\ell_p$-norm and no constraint is involved, the first-order and second-order sufficient optimality conditions have been investigated  in \cite{ochs2015iteratively,wang2015optimality}.
Chen \emph{et al} have derived a first-order necessary optimality condition for local minimizers  and defined the generalized stationary point of the constrained optimization
problems with nonconvex regularization \cite{bian2017optimality}.
These results are adopted in \cite{lu2014iterative} to derive  the global convergence of a class of iteratively reweighed $\ell_1$ and $\ell_2$ methods for unconstrained $\ell_p$ regularization problems.
For the sum of a convex function and a (nonconvex) nondecreasing function applied to another convex function, the convergence to a critical point of the iteratively reweighed $\ell_1$ algorithm   is provided when the objective function is coercive \cite{ochs2015iteratively}.

As for more general cases, the analysis in current work has many limitations due to  this obstacle for theoretical  analysis.
First, instead of driving the relaxation parameter to zero,  many existing  methods    \cite{chartrand2008iteratively,EPS}  aim to show the convergence
to the optimal solution of the relaxed sparse optimization
problems. An iteratively reweighted least squares   algorithm for the relaxed problem $\ell_p$ problem  in sparse signal recovery has been investigated in \cite{ba2014convergence}  with  local convergence rate analysis.
 A critical aspect of any implementation of such an approach is the selection of the relaxation parameters which prevents the weights from becoming overwhelmingly large. As been explained in  \cite{chartrand2008iteratively}, large relaxation parameters will smooth out many local minimizers, whereas small values can cause  the subproblems difficult to solve and the algorithm too quickly get trapped into local minimizers. For this purpose, updating strategies of the relaxation parameter have been studied in \cite{EPS}, but it is only designed  for constrained convex problems.

Second,  some methods assume Lipschitz continuity of the objective  function in their analysis, which only holds true for few nonconvex sparsity-inducing terms such as log-sum penalty \cite{lu2014iterative,ochs2015iteratively}.  Though this assumption is not explicitly required by some other researchers,  they need another assumption that  the negative of the sparsity-inducing term--which is convex--is subdifferentiable everywhere \cite{ochs2015iteratively}. However, it should be noticed that this is a quite strong assumption and  generally not suitable for most sparsity-inducing terms, e.g., $\ell_p$-norm, consequently limiting their applicability to general cases.

Third, this situation may become even worse when a general convex set constraint is added to the problem.  To the best of our knowledge, only simple cases such as linearly constrained cases have been studies by current work.
To circumvent the obstacle for analysis, current methods either focus on the relaxed problem as explained above, or unconstrained reformulations   where the constraint violation is  penalized in the objective \cite{chartrand2008iteratively,lu2014iterative,wang2015optimality}.  The latter approach
then arises the issue of  how to select the proper penalty parameter value.

Moreover,   some work \cite{lu2014proximal} assumes the coercivity  of the objective function to guarantee that the iterates generated by the algorithms must have clustering points.
This sets the limitation  as many sparsity-inducing terms is bounded above, e.g.,  arctan function. This assumption therefore requires the rest part of the objective must be coercive, which is generally not the case.

In summary, for  cases involving  more general nonconvex and nonsmooth sparsity-inducing functions and convex-set constraints, the analysis of the behavior of iteratively reweighted algorithms still remains an open question.

\subsection{Contributions}

In this paper, we consider a unified formulation of the convex-set constrained nonconvex and nonsmooth sparse optimization problems. A general algorithmic framework of \emph{Adaptively Iterative Reweighted (AIR)} algorithm is presented for solving the nonconvex and nonsmooth problems. We   then derive  the first-order  condition to characterize the optimal solutions and analyze global  convergence of the proposed AIR algorithm to the first-order optimal solutions. The most related research work mainly includes
the iteratively  reweighted algorithms proposed by \cite{EPS}  for solving generally constrained convex problems,   the reweighted methods by  \cite{lu2014iterative, lu2017ell} for solving unconstrained $\ell_p$ regularization problems, and the algorithmic framework proposed  in \cite{ochs2015iteratively}  for solving the unconstrained nonsmooth and nonconvex optimization problems. However, we emphasize again  that our  focus is  dealing with cases with general nonconvex and nonsmooth sparsity-inducing terms and general convex-set constraints---a stark contrast to the situations considered by most existing methods.

The major contributions of this paper are summarized as follows:

\begin{itemize}

\item The presented unified problem formulation   can take into account  most existing types of  nonconvex sparsity-inducing functions, including the group-structured  sparsity. A general algorithmic framework of adaptively iteratively reweighted algorithms is developed    by  solving a sequence of trackable convex subproblems with variable smoothing parameter.  A unified first-order  necessary conditions are derived to characterize the optimal solutions  by using Fr\'echet subdifferentials. The global convergence of the proposed algorithm is established.

\item For the iteratively reweighed $\ell_1$-algorithm, we derive the  global convergence analysis for cases with diminishing relaxation parameter.  We show that every limit point  generated by this algorithm  satisfies the first-order necessary optimality condition for the original unrelaxed problem, instead of the relaxed problem---a novel result that most current work does not possess.

\item For iteratively reweighed $\ell_2$-algorithm, our algorithm allows for adaptively decreasing relaxation parameter, which can avoid the issue of selecting appropriate value for the relaxation parameter.
The conditions for existence of the cluster points, guaranteeing the boundedness,
selecting the starting point and the initial relaxation parameters are also  provided  to establish the global convergence. This makes our methods applicable for cases  where the objective is not coercive.
\end{itemize}

\subsection{Organization}
In the remainder of this section, we outline our notation
and introduce various concepts that will be employed throughout the paper. In Section~\ref{s.Pd},
we describe our problem of interests and explain its connection to various existing types of sparsity-inducing techniques.
In Section~\ref{s.Ad}, we describe the details of our proposed AIR algorithm and apply it to different types of nonconvex sparsity-inducing terms.
The optimality condition and the global convergence of the proposed algorithm in different situations are  provided in Section~\ref{s.Conv}.
We discuss implementations of our methods and the
results of numerical experiments in Section~\ref{sec.experiment}.  Concluding remarks are provided in Section~\ref{sec.conclusion}.

\subsection{Notation and Preliminaries}
Much of the notation that we use is standard, and when it is not, a definition is provided. For convenience, we review some of this notation and preliminaries here.

 Let $\mathbb{R}^n$ be the space of real $n$-vectors, $\mathbb{R}^n_+$ be the nonnegative orthant of $\mathbb{R}^n$, $\mathbb{R}^n_+=
 \{\xbf \in\mathbb{R}^n : \xbf \ge 0\}$  and the nonpositive orthant
 $\{\xbf \in\mathbb{R}^n : \xbf \le 0\}$. Moreover,  let  $\mathbb{R}^n_{++}$ be the interior of $\mathbb{R}^n_+$, $\mathbb{R}_{++}^n:=\{\xbf\in\mathbb{R}^n:
 \xbf > 0\}$.  The set of $m\times n$ real matrices is denoted by $\mathbb{R}^{m\times n }$.
For a pair of vectors $(\ubf, \vbf)\in\mathbb{R}^n\times \mathbb{R}^n$, their inner product is written as
$\la \ubf, \vbf\ra$.  The set of nonnegative integers is denoted by $\Nb$.
Suppose  $\mathbb{R}^n$ be the product space of subspaces $\mathbb{R}^{n_i}, i=1,\ldots, m$ with $\sum_{i=1}^mn_i=n$, i.e., it takes decomposition $\mathbb{R}^n = \mathbb{R}^{n_1}\times \ldots \times \mathbb{R}^{n_m}$.
Given a closed convex set $X \subset \mathbb{R}^n$, the normal cone to $X$ at a point $\bar\xbf \in X$ is given by
\[ N(\bar\xbf|X) := \{\zbf |  \langle \zbf, \xbf-\bar\xbf \rangle \leq 0,  \  \forall \xbf\in X\}.\]
The characteristic  function of $X$ is defined as
\[ \delta(\xbf|X) = \begin{cases}  0 & \text{ if } \xbf\in X,\\
+ \infty & \text{ otherwise.}
\end{cases}
\]
The indicator operator $\mathbb{I}(\cdot)$  is an indicator function that takes a value of 1 if the statement is true and 0 otherwise.

For a given $\alpha \in\mathbb{R}$,  denote the  level set of $f $ as
\[ L (\alpha; f) := \{\xbf \in \mathbb{R}^n  |  f(\xbf)\le  \alpha\}.\]
In particular, we are interested in level set with an upper bound reachable for $f$:
\[ L (f(\hat\xbf); f) := \{\xbf \in \mathbb{R}^n  |  f(\xbf)\le  f(\hat\xbf)\}.\]
The subdifferential of a convex function $f$ at $\xbf$ is a set defined by
\[ \partial f(\xbf) = \{ \zbf \in \mathbb{R}^n  |  f(\ybf) - f(\xbf) \ge \la \zbf, \ybf - \xbf\ra, \forall \ybf\in\mathbb{R}^n\}. \]
Every  element $\zbf \in \partial f(\xbf)$ is referred to as a subgradient.
 To characterize the optimality conditions for nonsmooth problems, we need to
introduce the concepts  of Fr\'echet subdifferentiation.
In fact, there are a variety of   subdifferentials known by now including limiting subdifferentials, approximate subdifferentials
and Clarke's generalized gradient, many of which
can be used here for deriving the optimality conditions.
The major tool we choose in this paper is the Fr\'echet subdifferentials,
which were introduced in \cite{bazaraa1974cones, kruger1981varepsilon} and discussed in \cite{kruger2003frechet}.

\begin{definition}[Fr\'echet subdifferential] Let $f$ be a function from a real Banach space into an extended real line
$\bar{\mathbb{R} }= \mathbb{R} \cup \{+\infty\}$, finite at $\xbf$.  The Fr\'echet subdifferential of $f$ at $\xbf$, denoted as
$\partial_F f(\xbf)$, is the set
$$
\begin{aligned}
&\partial_F f(\xbf) = \\
&\left\{ \xbf^* \in \mathbb{R}^n:  \liminf\limits_{\ubf\to \xbf} \frac{f(\ubf)-f(\xbf)-\la \xbf^*, \ubf-\xbf\ra }{\|\ubf-\xbf\|} \ge 0\right\}.
\end{aligned}
$$
Its elements are referred to as Fr\'echet subgradients.
\end{definition}

For a composite function $r\ensuremath\mathop{\scalebox{.7}{$\circ$}} c(\xbf)$, where $c: \mathbb{R}^n\to\mathbb{R}$ and $r: \mathbb{R} \to \mathbb{R}$,  denote $\partial_F r\ensuremath\mathop{\scalebox{.7}{$\circ$}} c(\xbf)$ as the Fr\'echet subdifferential of $r$ with respect to $\xbf$,
$\partial_F r(c(\xbf))$ (or simply $\partial_F r(c)$) as the Fr\'echet subdifferential of $r$ with respect to $c$, and
$r'(c(\xbf))$ (or simply $r'(c)$) as the derivative of $r$ with respect to $c(\xbf)$ if $r$ is differentiable at $c(\xbf)$.

\section{Problem Statement and Analysis}\label{s.Pd}
In this section, we present a unified formulation of the constrained nonconvex and nonsmooth sparse optimization problem, followed by the specific applications and problem analysis.
\subsection{Problem Statement}
We consider the following constrained nonconvex and nonsmooth sparse optimization problem
\begin{equation}\label{f.sparse}
\begin{aligned}
\min_{\xbf\in\mathbb{R}^n} & \quad  f(\xbf)+  \Phi(\xbf)\\
\st &\quad   \xbf \in  X,
\end{aligned}
\end{equation}
where function $f:\mathbb{R}^n\to \mathbb{R}$ is smooth and convex
and $X\subset\mathbb{R}^n$ is a closed convex set.
Here  $\Phi=r\ensuremath\mathop{\scalebox{.7}{$\circ$}} c(x) = r(c(\xbf))$ is a nonconvex and nonsmooth composite function
with $c$  convex and $r$ nonconvex. This type of problem is a staple for many applications in signal processing~\cite{candes2008introduction, liu2018sparse}, wireless communications~\cite{qin2018sparse, shi2018generalized}, machine learning~\cite{bach2012optimization,hastie2015statistical} and high-dimensional statistics \cite{wainwright2014structured}. For example, in signal processing, $f$ may be the mean-squared error for signal recovery, $X$ may be a nonnegative constraint for signal~\cite{khajehnejad2011sparse}; in wireless communications, $f$ may represent the system performance such as transmit power consumption, $X$ models the transmit power constraints and quality of service constraints~\cite{gsbf};
in machine learning, $f$ can represent the convex loss function, such as the cross-entropy loss for logistic regression~\cite{harrell2015ordinal}.

In a large amount of applications, the ground-truth vector $\xbf$ is expected to have the structured  sparsity property. To handle this type of structured sparsity, various types of group-based sparsity inducing function $\Phi$ has been studied in \cite{wainwright2014structured}.
Specifically, consider a collection of groups $\Gcal = \{\Gcal_1,\Gcal_2,\cdots,\Gcal_m\}$ with $|\Gcal_i| = n_i$ and $\sum_{i=1}^{m} n_i
= n$.
The union over all groups covers the full index set. The structured vector $\xbf$ thus can be written as follows:
\[\xbf = [ \underbrace{x_1,x_2,\cdots,x_{n_1}}_{\xbf_{\Gcal_1}^T},\cdots,\underbrace{x_{n-n_{m} + 1},\cdots,x_{n}}_{\xbf_{\Gcal_m}^T}]^T.
\]
With these ingredients, the associated group-based sparsity inducing function $\Phi$ takes the form
\[ \Phi(\xbf) =   \sum\limits_{i\in\Gcal} r_{i}(c_{i}(\xbf_{i})),\]
where  $c_i: \mathbb{R}^{n_i}\to \mathbb{R}$ is convex and $r_i: \mathbb{R}\to \mathbb{R}$ is concave for each $i$.
Throughout this paper, we make the following assumptions about $f$, $r_i$, $c_i$  and $X$.

\begin{assumption} \label{basic assumption}
The functions $f$, $r_i$, $c_i$, $i=1,\ldots, m$, and set $ X$   are such that
\begin{enumerate}
\item[(i)] $ X$ is closed and convex.
\item[(ii)] $f$ is smooth, convex and bounded below by $\underline f$ on $ X$.
\item[(iii)] $r_i$ is  smooth on $\mathbb{R}\setminus\{0\}$,   concave  and strictly increasing on $\mathbb{R}_{+}$ with $r_i(-c) = r_i(c)$ and $r_i(0) = 0$, and is  Fr\'echet subdifferentiable at 0.
\item[(iv)] $c_i$ is convex and coercive with $c_i(\xbf_i)\ge0, \forall \xbf\in X$ where the equality holds if and only if $\xbf_i=0$.
\end{enumerate}
 \end{assumption}

\begin{remark}
The the  symmetry of $r_i$ is not a requirement, since $c_i(\xbf) \ge 0$ is assumed always true; the purpose of this assumption is to simplify the presentation.
 \end{remark}

Formulation \eqref{f.sparse} provides a unified framework for most existing sparse optimization problems. In next subsection,
we shall describe the important applications of problem~\eqref{f.sparse}
and explain the specific forms of the functions  $f$, $r_i$, $c_i$ in the examples.
Based on different formulations of the composite function $\Phi(\xbf)$, there are a great deal of
nonconvex sparsity-inducing techniques to promote sparse solutions via approximating the $\ell_0$ norm of $\xbf$.

\subsection{Sparsity-Inducing Functions}

Many applications including signal processing, wireless communications, machine learning and high-dimensional statistics involve the minimization of  the $\ell_0$-norm of the variables $\|\xbf\|_0$, i.e., the number of nonzero components in $\xbf$.
However,  this   is    known   as an NP-hard problem,  thus various approximations of $\ell_0$ norm have been proposed.
By   different choices of the formulation  $r_i$ and $c_i$ in \eqref{f.sparse}, there exist many nonsmooth and tight approximations to $\ell_0$ norm, yielding
 \[ \|\xbf\|_0\approx \Phi(\xbf) = \sum_{i=1}^n r_i(c_i(x_i)).\]
 In the following discussion, we only provide the expression of $r_i$ on $\mathbb{R}_+$, since
 by Assumption~\ref{basic assumption}, $r_i$ can be defined accordingly on $\mathbb{R}_-$.

 The first instance is the feature selection algorithm via concave minimization proposed by Bradley and Mangasarian   \cite{bradley1998feature} with approximation
\begin{equation}\label{f.exp}\tag{EXP}
\|\xbf\|_0 \approx \sum_{i=1}^{n}1-e^{-p|x_i|}\  \text{ with }\  p> 0,
\end{equation}
where $p$ is chosen to be sufficiently large to promote sparse solutions. The concavity of this function leads to a finitely terminating algorithm and a more accurate
representation of the feature selection algorithm. It is reported  that the algorithms with this formulation obtained a reduction in error with selected features fewer in number and they are faster compared with the traditional convex feature selection algorithms.
For example, we can choose
\[c_i(x_i) = |x_i|,\ r_i =1-e^{-pc_i}  \text{ or  }  c_i = x_i^2,\ r_i =1-e^{-p \sqrt{c_i}},\]
so that this approximation  can be viewed  as a specific formulation of $\Phi$.

The second instance, which is widely used in many applications currently, is to approximate
the $\ell_0$ norm by $\ell_p$ quasi-norm  \cite{fazel2003log}
\begin{equation}\label{f.lp}\tag{LPN}
\|\xbf\|_0 \approx \sum_{i=1}^{n}|x_i|^p \ \text{ with }  p\in(0,1),
\end{equation}
where  $p$ is chosen close to 0 to enforce sparsity in the solutions.  Based on this approximation, numerous applications and algorithms have emerged.
Here we can choose
\[ c_i(x_i) =|x_i|, r_i(c_i)=c_i^p  \text{ or  }  c_i(x_i)=x_i^2,   r_i (c_i)= c_i^{p/2}\]
in the formulation of $\Phi$.

 Another option for approximating $\ell_0$ norm, proposed in \cite{lobo2007portfolio}, is to use the log-sum approximation
\begin{equation}\label{f.log}\tag{LOG}
 \|\xbf\|_0 \approx \sum_{i=1}^{n}\log{(1+p|x_i|)}  \  \text{ with } p > 0,
\end{equation}
and setting  $p$   sufficiently large leads to sparse solutions.
We can choose
$$ c_i(x_i) = |x_i|, r_i (c_i)= \log{(1+pc_i)},
$$
 or
 $$  c_i(x_i)=x_i^2, r_i(c_i)=\log(1+p\sqrt{c_i}).$$

The approximation technique proposed in  \cite{fazel2003log} suggests
\begin{equation}\label{f.inv}\tag{FRA}
\|\xbf\|_0 \approx \sum_{i=1}^{n}\frac{|x_i|}{|x_i|+p}, \text{ with } p > 0,
\end{equation}
where   $p$ is required to be sufficiently small to promote sparsity.  One can use
$$c_i(x_i) = |x_i|,\ r_i (c_i)= \frac{c_i}{c_i+p}, $$ or
$$ c_i x_i= x_i^2,\ r_i (c_i)= \frac{\sqrt{c_i}}{\sqrt{c_i}+p}.$$

Cand\`es \emph{et al.}   proposed an approximation to the $\ell_0$ norm in \cite{candes2008enhancing}
\begin{equation}\label{f.atan}\tag{TAN}
\|\xbf\|_0 \approx \sum_{i=1}^{n}\arctan(p|x_i|), \text{ with } p>0,
\end{equation}
where sufficiently small $p$ can cause sparsity in the solution. The function $\arctan$ is bounded above and $\ell_0$-like.
It is reported that this approximation tends to work well and often  better than the log-sum \eqref{f.log}. In this case,
we can choose
$$c_i(x_i) = |x_i|,   r_i(c_i) = \arctan{(pc_i)}, $$ or
$$ c_i(x_i)=x_i^2, r_i(c_i)=\arctan{(p\sqrt{c_i})}.$$

Another nonconvex sparsity-inducing technique needs to be mentioned is the SCAD penalty proposed in \cite{fan2001variable}, which requires the derivative of $\phi_i$ to satisfy
\begin{equation}\label{f.scad}\tag{SCAD}
 c_i(x_i)=|x_i|,  \phi_i'(c_i) = \lambda\{\mathbb{I}(c_i\le \lambda ) + \frac{(a\lambda - c_i)_+}{(a-1)\lambda} \mathbb{I}(c_i>\lambda)\},\end{equation}
for some $a > 2$ and typically $a=3.7$ is used.  Alternatively, the MCP \cite{zhang2007penalized} penalty uses
\begin{equation}\label{f.mcp}\tag{MCP}
 c_i(x_i)=|x_i|,  \phi_i'(c_i) = (a\lambda-c_i)_+/a   \text{ for some } a \ge 1.
 \end{equation}

\begin{remark}
        The sparsity-inducing functions can also take into account group structures. For example, $\ell_{p,q}$-norm with $p\ge 1$ and $0<q<1$ is defined as
        $$\|\xbf\|_{p,q} = \(\sum_{i\in\Gcal} \|\xbf_{i}\|_p^q\)^{1/q}. $$
        Therefore,   we can choose
        $$\Phi(\xbf) = \|\xbf\|_{p,q}^q,\ \text{ with }  c_i(\xbf_{i}) = \|\xbf_{i}\|_p\ \text{ and }\  r_i(c_i)=c_i^q,$$
to induce group structured sparsity in vector $\bf{x}$.
\end{remark}

\subsection{Problem Analysis}
There have been various literatures for solving the nonconvex and nonsmooth sparse optimization problems. In~\cite{chartrand2008iteratively,ling2013decentralized}, Yin \emph{et al}. proposed to solve the sparse signal recovery problem by using the unconstrained nonconvex $\ell_p$ norm model, followed by the associated iterative reweighted unconstrained $\ell_p$ algorithm. The  convergence analysis for the reweighted $\ell_2$ case was provided. In~\cite{lu2014iterative},  Lu have provided the first-order optimality condition for the unconstrained nonconvex $\ell_p$ norm problem, and the convergence analysis for both $\ell_1$ and $\ell_2$ types reweighted algorithm. However, it is not clear for analyzing the first-order optimality condition for the constrained nonconvex and nonsmooth sparse optimization problem~\eqref{f.sparse}. In order to address this issue, we shall propose the adaptively iterative reweighted (AIR) algorithm in \S~\ref{s.Ad}, and then provide the first-order optimality condition for~\eqref{f.sparse} and the convergence analysis for the AIR algorithm in \S~\ref{s.Conv}.

\section{Adaptively Iterative Reweighted Algorithm}\label{s.Ad}
In this section, we shall present the adaptively iterative reweighted  algorithm  for solving the nonconvex and nonsmooth sparse optimization problem~\eqref{f.sparse}. This is achieved by smoothing the objective function, followed by solving a sequence of linearized subproblems.
\subsection{Smoothing Method}
In this subsection, we show how we deal with the nonsmoothness of the objective function in \eqref{f.sparse} .
Before proceeding, we define the following functions for  $\xbf\in X$.
Problem \eqref{f.sparse}  can be rewritten as
\beq\label{prob.J0} \min_{\xbf}\ J_0(\xbf) := f(\xbf)+  \sum_{i \in \Gcal}r_i(c_i(\xbf_i )) + \delta(\xbf|X).\eeq
Adding  relaxation parameter $\epsbf \in \mathbb{R}_+^m$ to smooth the (possibly) nondifferentiable $r_i$, we propose the relaxed problem as
\beq\label{prob.J}
\min_{\xbf}\ J(\xbf; \epsbf):= f(\xbf)+  \sum_{i\in\Gcal}r_i(c_i(\xbf _i)+\eps_i)  + \delta(\xbf|X),
\eeq
and in particular, $J(\xbf; 0) = J_0(\xbf)$. Here we extend the notation of $\phi_i$ and use  $\phi_i(\xbf_i; \eps_i)$ to denote the relaxed sparsity-inducing function, such  that
$$
\phi_i(\xbf_i; \eps_i) := r_i(c_i(\xbf_i)+\eps_i),
$$
$$
\Phi(\xbf; \epsbf): = \sum_{i\in\Gcal}\phi_i(\xbf_i;\eps_i) \  \text{ and }\  \phi_i(\xbf_i)=\phi_i(\xbf_i; 0).
$$
The following theorem shows that the pointwise convergence of $J(\xbf;\epsbf)$ to $J_0(\xbf)$ on $X$ as $\epsbf\to\bm{0}$.
\begin{theorem}\label{thm.j approx j0}
For any $\xbf\in X$ and $\epsbf\in\mathbb{R}_{++}^m$, it holds true that
 \[\begin{aligned}
 J_0(\xbf)  &\le   J(\xbf; \epsbf) \\ & \le  J_0(\xbf)
 + \sum_{c_i(\xbf_i) = 0} r_i(\eps_i) +\sum_{ c_i(\xbf_i) > 0} r'(c_i(\xbf_i)) \eps_i.
 \end{aligned}\]
This implies that $J(\xbf;\epsbf)$ pointwise convergence to $J_0(\xbf)$ on $X$ as $\epsbf\to\bm{0}$.
 \end{theorem}
\begin{proof}
The first inequality is trivial, so we only have to show the second inequality.
 Since $r(\dotv )$ is concave on $\mathbb{R}_+$, we have
\beq\label{eq.lem.2.1}
r_i(z) \le r_i(z_0) + r_i'(z_0) (z-z_0)\quad \text{ for any } z, z_0 \in\mathbb{R}_+,\eeq
Therefore,
\[\begin{aligned}
J(\xbf; \epsbf)  = & f(\xbf) + \sum_{i\in\Gcal} r_i(c_i(\xbf_i)+\eps_i) \\
= & f(\xbf) +  \sum_{c_i(\xbf_i) = 0} r_i(\eps_i)  +    \sum_{ c_i(\xbf_i) > 0} r_i(c_i(\xbf_i)+\eps_i) \\
\le &  f(\xbf)   + \sum_{c_i(\xbf_i) = 0} r_i(\eps_i) \\
  &  + \sum_{c_i(\xbf_i) > 0} r_i(c_i(\xbf_i)) +  \sum_{c_i(\xbf_i) > 0}   r'(c_i(\xbf_i)) \eps_i \\
= & J_0(\xbf)  + \sum_{c_i(\xbf_i) = 0} r_i(\eps_i) +\sum_{ c_i(\xbf_i) > 0} r'(c_i(\xbf_i)) \eps_i,
\end{aligned}
\]
where the inequality follows by~\eqref{eq.lem.2.1}. This completes the first statement.

On the other hand, since
\[ \lim\limits_{\bm{\eps}\to \bm{0}}\sum_{c_i(\xbf_i) = 0} r_i(\eps_i) +\sum_{ c_i(\xbf_i) > 0} r'(c_i(\xbf_i)) \eps_i = 0,
\]
it holds
\[\lim\limits_{\epsbf\to \bm{0}} J(\xbf; \epsbf) = J_0(\xbf),\quad \xbf\in X.
\]
\end{proof}

\subsection{Adaptively Iterative Reweighted Algorithm}

A convex and smooth function $G_{(\tilde{\xbf}, \tilde \epsbf)}(\xbf)$ can be derived as an approximation of $J(\tilde \xbf,\tilde \epsbf)$ at $\tilde\xbf$
by linearizing $r_i$ at $c_i(\tilde\xbf_i)+\tilde \eps_i$, yielding the subproblem
\beq\label{prob.G}
G_{(\tilde{\xbf}, \tilde \epsbf)}(\xbf) :=  f(\xbf)+   \sum_{i\in\Gcal} w_i(\tilde \xbf_i, \tilde \eps_i) c_i(\xbf_i )  + \delta(\xbf|X) ,
\eeq
where the weights are given by
\[ w_i(\xbf,\eps_i)=  r_i'(c_i(\xbf_i)+\eps_i),\quad i\in\Gcal.\]
Note that the relaxation parameter can be simply chosen as $\epsbf = \bm{0}$ if $r$ is smooth at $\bm{0}$.

At iterate $\xbf^k$, the new iterate   is   obtained by
\[ \xbf^{k+1} \in \arg\min_{\xbf}   G_{(\xbf^k, \epsbf^k)}(\xbf).\]
Therefore,  $\xbf^{k+1} $ satisfies optimality condition
\[ \bm{0}\in \partial  G_{(\xbf^k,\epsbf^k)}(\xbf^{k+1} ) .\]
The relaxation parameter is selected such that  $\epsbf^{k+1} \le \epsbf^k$ and possibly  driven to $\bm{0}$ as the algorithm proceeds.

Our proposed \emph{A}daptively \emph{I}terative \emph{R}eweighted algorithm for nonconvex and nonsmooth sparse optimization problems is presented in Algorithm~\ref{alg.1}.

\begin{algorithm}
        \caption{AIR: Adaptively Iterative Reweighted Algorithm}
        \label{alg.1}
        \begin{algorithmic}[1]
                \State (Initialization)  Choose $\xbf^0\in X$ and  $\epsbf^0\in\mathbb{R}_{++}^n$. Set $k=0$.
                \State (Subproblem Solution)  Compute new iterate
                \[ \xbf^{k+1}\in\arg\min   G_{(\xbf^k, \epsbf^k)}(\xbf).\]
                \State (Reweighting)
                Choose $\epsbf^{k+1} \in(\bm{0},  \epsbf^k]$.
                \State Set $k\gets k+1$. Go to Step 2.
        \end{algorithmic}
\end{algorithm}

\subsection{Iteratively Reweighted $\ell_1$-Algorithm \& $\ell_2$-Algorithm}\label{sub.L12}
In this subsection, we describe the details of how to construct $G_{(\tilde \xbf,\tilde\epsbf)}(\xbf)$ for the nonconvex and nonsmooth sparsity-inducing functions
 \eqref{f.exp}--\eqref{f.mcp}  in Section~\ref{s.Pd}.
  Notice that the relaxation parameter  $\eps_i$ could set as 0 if $\lim\limits_{c_i\to0+}r_i'(c_i)<+\infty$.
 For simplicity, denote
$ \tilde w_i = w_i(\tilde x_i, \tilde\eps_i).$  In Table~\ref{tab.1},  we provide the explicit forms of the weights $\tilde w_i$ at $(\tilde x_i,\tilde \epsilon_i)$ when choosing  $c_i(x_i) = | x_i |$ and   $c_i(x_i) = x_i^2$  for each case, so that the corresponding subproblem is an $\ell_1$-norm sparsity-inducing problem and an $\ell_2$-norm sparsity-inducing problem
\[\begin{aligned}
 G_{(\tilde \xbf,\tilde\epsbf)}(\xbf) & = f(\xbf) + \sum\limits_{i\in\Gcal} \tilde w_i |x_i|+ \delta(\xbf|X)\quad\text{and }\\
G_{(\tilde \xbf,\tilde\epsbf)}(\xbf)  & = f(\xbf) + \sum\limits_{i\in\Gcal} \tilde w_i x_i^2 +\delta(\xbf|X).
\end{aligned}
\]
For each sparsity-inducing function, we consider $c_i(x_i)= |x_i |$ in the first row and $c_i(x_i)=x_i^2$ in the second row.  We also list the properties of the
$r_i$ with $c_i\to\infty$ and its side-derivative of $r_i$ at $0$ in the fourth and fifth columns. This is because these properties can lead to different behaviors of each AIR algorithm as shown in the theoretical analysis.

\begin{table}[h]
        \caption{Different AIR algorithm weights based on different choices of $r_i$ and $c_i$.}
        \label{tab.1}
        \centering
        \begin{tabular}{|C{2.3em}|C{5.84em}|C{9.25em}|C{2.5em}|C{2.5em}|}\hline
                $\phi_i $       &   $r_i(c_i)$   &   $\tilde w_i$ & $r_i(\infty)$ & $r_i'(0+)$  \\ \hline
                \multirow{2}{*}{\eqref{f.exp}}      &  $1-e^{-pc_i}$  & $pe^{-p(|\tilde x_i|+\tilde\eps_i)}$  & $<\infty$ & $<\infty$ \\  \cline{2-5}
                  &  $1-e^{-p\sqrt{c_i}}$ & $\frac{pe^{-p\sqrt{\tilde x_i^2+\tilde\epsilon_i}}}{2\sqrt{\tilde x_i^2+\tilde\epsilon_i}}$ &  $<\infty$ & $<\infty$ \\ \hline
                \multirow{2}{*}{\eqref{f.lp}}       &  $c_i^p$  & $p(|\tilde x_i|+\tilde\epsilon_i)^{p-1}$  &   $+\infty$ & $+\infty$ \\  \cline{2-5}
                  &  $c_i^{p/2}$ & $\frac{p}{2}(\tilde x_i^2+\epsilon_i)^{\frac{p}{2}-1}$ &    $+\infty$& $+\infty$ \\ \hline
                \multirow{2}{*}{\eqref{f.log} }      &  $\log(1+pc_i)$      & $\frac{p}{1+p|\tilde x_i|}$  &  $+\infty$ & $<\infty$ \\  \cline{2-5}
                  &  $ \log(1+p\sqrt{c_i})$ & $\frac{p}{2\sqrt{\tilde x_i^2+\tilde\epsilon_i}(1+p\sqrt{\tilde x_i^2+\tilde\epsilon_i})}$ &  $+\infty$ & $+\infty$ \\ \hline
                \multirow{2}{*}{\eqref{f.inv}}    &  $\frac{c_i}{c_i+p}$      & $\frac{p}{(|\tilde x_i|+p)^2}$  &  $<\infty$ & $<\infty$ \\  \cline{2-5}
                  &  $\frac{\sqrt{c_i}}{\sqrt{c_i}+p}$ & $\frac{p}{2\sqrt{\tilde x_i^2+\tilde\epsilon_i}(\sqrt{\tilde x_i^2+\tilde\epsilon_i}+p)^{2}}$ &  $<\infty$ & $ +\infty$ \\ \hline
                \multirow{2}{*}{\eqref{f.atan}  }  &  $\arctan{(pc_i)}$      & $\frac{p}{1+p^2(|\tilde x_i|)^2}$  &  $<\infty$ & $<\infty$ \\  \cline{2-5}
                  &  $\arctan{(p\sqrt{c_i})}$ & $\frac{p}{2\sqrt{\tilde x_i^2+\tilde\epsilon_i}(1+p^2(\tilde x_i^2+\tilde\epsilon_i))}$ &  $<\infty$ & $ +\infty$ \\ \hline

        \end{tabular}
\end{table}

As for SCAD and MCP, the explicit forms of $r_i$ are not necessary to be known, but it can be easily verified using $r_i'$ that Assumption~\eqref{basic assumption}
still holds true.  The  reweighted   $\ell_1$ subproblem for SCAD has weights
\[ \tilde w_i =  \lambda\{\mathbb{I}(|\tilde x_i |+\tilde\eps_i\le \lambda )   + \frac{(a\lambda - |\tilde x_i| - \tilde\eps_i)_+}{(a-1)\lambda} \mathbb{I}(|\tilde x_i|+ \tilde\eps_i>\lambda)\}.\]
The weights of reweighted $\ell_2$ subproblem for SCAD are
\[\begin{aligned} \tilde w_i =  &  \frac{\lambda}{2\sqrt{\tilde x_i^2+\tilde\epsilon_i)}}\{\mathbb{I}(\sqrt{\tilde x_i^2+\tilde\epsilon_i)}\le\lambda) \\
& + \frac{(a\lambda-\sqrt{\tilde x_i^2+\tilde\epsilon_i)})_{+}}{(a-1)\lambda}\mathbb{I}(\sqrt{\tilde x_i^2+\tilde\epsilon_i)}>\lambda)\}.
\end{aligned}\]
As for MCP, the reweighted $\ell_1$ subproblem has weights
\[\tilde w_i  =  (a\lambda-|\tilde x_i |-\tilde\eps_i)_+/a,\]
and the weights for reweighted $\ell_2$ subproblem are
\[\tilde w_i =  (a\lambda-\sqrt{\tilde x_i^2+\tilde\epsilon_i})_+/a.\]

\section{Global Convergence analysis}
\label{s.Conv}

In this section, we shall analyze the global convergence   of our proposed AIR algorithm. Specifically,  we first provide a unified first-order optimality condition for the constrained nonconvex and nonsmooth sparse optimization problem~\eqref{f.sparse}. Then we establish the global convergence analysis followed by the existence of cluster points.
For simplicity, we denote
$w^k_i = w_i(\xbf_i^k, \eps_i^k),  \wbf_i^k = w_i^k \ebf_{n_i},$
$ \wbf^k = [ \wbf_1^k; \wbf_2^k; \ldots; \wbf_m^k], \text{ and  }   \Wbf^k = \text{diag}(\wbf^k),$
and so forth.

\subsection{First-Order Optimality Condition}

In this subsection, we    derive the conditions to characterize the optimal solution of \eqref{f.sparse}.
Due to the nonconvex and nonsmooth nature of the sparsity-inducing function, we use  Fr\'echet subdifferentials as the major tool in our analysis.
Some important properties of Fr\'echet subdifferentials derived in  \cite{kruger2003frechet}  that will be used in this paper are  summarized below. Part $(i)$-$(iv)$ are Proposition 1.1, 1.2, 1.10, 1.13 and  1.18 in  \cite{kruger2003frechet}, respectively.
\begin{proposition}\label{prop.sub}
The following statements about Fr\'echet subdifferentials are true:
\begin{enumerate}
\item[(i)] If $f$ is
differentiable at $\xbf$ with gradient  $\nabla f(\xbf)$, then $\partial_F f(\xbf) = \{\nabla f(\xbf)\}$.
\item[(ii)]  If $f$ is convex, then $\partial_F f(\xbf) = \partial f(\xbf)$.
\item[(iii)]  If $f$ is Fr\'echet subdifferential at $\xbf$ and attains local minimum at $\xbf$, then
\[ \bm{0}\in\partial_F f(\xbf).\]
\item[(iv)] Let $r(\cdot )$ be Fr\'echet subdifferentiable at $c^*=c(\xbf^*)$ with $c(\xbf)$ being convex,
then $r\ensuremath\mathop{\scalebox{.7}{$\circ$}} c(\xbf)$ is Fr\'echet subdifferentiable at $\xbf^*$ such that
\[y^*\partial c(\xbf^*) \subset \partial_F r\ensuremath\mathop{\scalebox{.7}{$\circ$}} c(\xbf^*)\]
 for any $y^*\in\partial_F r(c^*)$.
 \item[(v)] $ N(\xbf |   X) = \partial_F\delta(\xbf |   X)$ if $X$ is   closed and convex.
\end{enumerate}
\end{proposition}

The properties of Fr\'echet subdifferentials in Proposition~\ref{prop.sub} can be used to characterize the optimal solution
of \eqref{f.sparse}. The following theorem is straightforward from Proposition~\ref{prop.sub}, which describes  the necessary optimality condition of problem \eqref{f.sparse}.
\begin{theorem}\label{thm.opt cond}
If   \eqref{prob.J} attains a local minimum at $\xbf$, then it holds true that
\begin{equation}\label{optimality}
 \bm{0} \in \partial_F J(\xbf; \epsbf) = \nabla f(\xbf) +  \partial_F\Phi(\xbf; \epsbf) + N(\xbf |  X).
 \end{equation}

\end{theorem}

Next we shall     further investigate the properties of $\partial_F \phi(\xbf; \epsbf)$.
\begin{lemma}\label{lem.1aaa}
It holds that
  \[\nabla f(\xbf) +   \prod_{i\in\Gcal} y_i \partial c_i(\xbf_i)  +  N(\xbf|X)  \subset  \partial_F J(\xbf; \epsbf)\]
  for any $y_i\in\partial_F r_i(c_i(\xbf_i)+\eps_i)$.
\end{lemma}
 \begin{proof}

Note that $\phi(\xbf; \epsbf)$ takes structure
\[\Phi(\xbf;\epsbf) = \sum_{i\in\Gcal} \phi_i(\xbf_i;\eps_i)\quad \text{ with } \phi_i(\xbf_i;\eps_i)= r_i( c_i(\xbf_i)+\eps_i).\]  Thus we can write the Fr\'echet subdifferentials of $\phi$
$$
\begin{aligned}
\partial_F \Phi(\xbf;\epsbf) &=\prod_{i\in\Gcal}  \partial_F \phi_i(\xbf_i;\eps_i)   \\
&= \partial_F \phi_1(\xbf_1;\eps_1)\times\ldots\times \partial_F \phi_m(\xbf_m;\eps_m),
\end{aligned}
$$
meaning that
\[  \partial_F J(\xbf;\epsbf) =  \nabla f(\xbf) +   \prod_{i\in\Gcal}  \partial_F \phi_i(\xbf_i;\eps_i)
+ N(\xbf|X).\]
On the other hand, every $c_i$ is assumed to be convex. From Proposition~\ref{prop.sub}, we know that
 \[ y_i  \partial c_i(\xbf_i) \subset   \partial_F \phi_i(\xbf_i;\eps_i),\quad \forall y_i\in\partial_F r_i(c_i(\xbf_i)+\eps_i),\]
completing the proof.
 \end{proof}

If  $c_i(\xbf_i) > 0$ or $\eps_i > 0$,    $r_i$ is   differentiable at  $c_i+\eps_i$
  so that $\partial_F \phi_i(\xbf_i;\eps_i) = r'_i(c_i(\xbf_i^*)+\eps_i) \partial  c_i(\xbf^*)$ by Proposition~\ref{prop.sub}.
 Of particular interests are the properties of $\partial_F r_i(0)$.
 Notice that $r'_i$ is decreasing on $\mathbb{R}_{++}$.
 We investigate  $\partial_F \phi_i(\xbf_i;\eps_i) $ based on  the limits (possibly infinite) in the lemma below.

\begin{lemma}\label{sub diff r}
Let $ y_i^*:= \lim\limits_{ c_i \to 0^+} r'_i(c_i)  \ge 0$. It holds true that
  \[
 \begin{cases}
    \partial_F r_i( c_i)  =  r'_i(c_i),    & \text{     if  }\    c_i > 0,\\
     \ \partial_F r_i (0) =  [-  y_i^*,   y_i^*],    &\text{     if  }\    y_i^* < +\infty,\\
     \ \partial_F r_i (0) =  \mathbb{R},                       &\text{   if }\    y_i^* = +\infty,
   \end{cases}
   \]
so that
\begin{enumerate}
        \item If $c_i(\xbf^*) + \eps_i > 0,$
        $$\partial_F \phi_i(\xbf_i;\eps_i) =     r'_i(c_i(\xbf_i^*)+\eps_i)\partial  c_i(\xbf^*);$$
        \item If $c_i(\xbf^*)+\eps_i = 0,  y_i^* < +\infty,$
        $$y_i \partial c_i(\xbf^*)   \subset  \partial_F \phi_i(\xbf_i;\eps_i), \ \forall y_i\in[-  y_i^*,   y_i^*];$$
        \item If $c_i(\xbf^*)+\eps_i = 0, y_i^* = +\infty,$
        $$y_i \partial c_i(\xbf^*)  \subset  \partial_F \phi_i(\xbf_i;\eps_i),\ \forall y_i\in\mathbb{R}.$$
\end{enumerate}
   \end{lemma}

 \begin{proof} The statement about the case that $c_i(\xbf^*) > 0$ is obviously true.  We only need consider the case that   $c_i(\xbf^*) = 0$.
  Notice that
 \[ \liminf_{c_i \to 0^+} \frac{r_i(c_i) - r_i(0)}{c_i} = \liminf_{0 < \tilde c_i < c_i \atop c_i \to 0^+}  r_i'(\tilde c_i)

  = r'_i(0+)=   y_i^* \ge 0\]
 by Assumption~\ref{basic assumption}$(ii)$.
 It can be easily verified by \cite[Proposition  1.17] {kruger2003frechet} that
  \[
   \partial_F r_i(0)  =
   \begin{cases}  [-  y_i^*,   y_i^*]  & \text{if  }    y_i^* < +\infty,\\
   \mathbb{R} & \text{if }    y_i^* = +\infty.
   \end{cases}
   \]
It then follows from Proposition~\ref{prop.sub}$(iv)$  that
\[\left\{
   \begin{aligned} y_i \partial c_i(\xbf^*) & \subset  \partial_F \phi_i(\xbf_i;\eps_i), \forall y_i\in[-  y_i^*,   y_i^*],    &\text{if  }    y_i^* < +\infty,\\
   y_i \partial c_i(\xbf^*)  & \subset \partial_F \phi_i(\xbf_i;\eps_i), \forall y_i\in\mathbb{R},                    &\text{if }    y_i^* = +\infty.
   \end{aligned}\right.
\]

\end{proof}

Note that we only require $\epsbf\in\mathbb{R}_+^m$.  If $\epsbf = \bm{0}$,  all the results we have derived for $J(\dotv; \epsbf)$ in this subsection also hold for $J_0$.

\subsection{Global Convergence of the AIR Algorithm}

 In this subsection, we analyze the global convergence of AIR algorithm under Assumption~\ref{basic assumption}.  First of all, we need to show that the subproblem always has a solution.    For $\hat\epsbf\in\mathbb{R}_{++}$, the subproblem is obviously well-defined on $X$ since the weights $w_i^k = r'_i(\xbf^k_i+\eps_i^k) < +\infty$. To guarantee the proposed AIR algorithm is well defined, we must show the existence of the subproblem solution.
We have  the following lemma about the solvability of the subproblems.

\begin{lemma} For $\epsbf^k \in\mathbb{R}_{++}^m$,  $\arg\min_{\xbf} G_{(\xbf^k,\epsbf^k)}(\xbf)$ is    nonempty, so that $\xbf^{k+1}$ is well-defined.
\end{lemma}

\begin{proof}  Pick $\tilde\xbf\in X$ and let $\alpha:= G_{(\xbf^k,\epsbf^k)}(\tilde\xbf)$.   The level set
\[  \{ \xbf \in X | G_{(\xbf^k,\epsbf^k)} (\xbf) \le G_{(\xbf^k,\epsbf^k)}(\tilde\xbf) \}   \]
must be nonempty since it contains $\tilde\xbf$,  and bounded  due to the coercivity of $w_i^k c_i$, $i\in\Gcal$ and the lower boundedness of $f$ on $X$.
This completes the proof  by  \cite[Theorem 4.3.1]{ortega1970iterative}.
 \end{proof}

We have the following key facts about solutions to \eqref{prob.G}, which implies that the new iterate $\xbf^{k+1}$ causes a decrease in the model   $J(\xbf, \epsbf^k)$.

\begin{lemma}\label{lem.J decrease.case1}
Let $\tilde\xbf \in X$, $\hat\epsbf, \tilde\epsbf\in\mathbb{R}_{++}^m$ with $\hat\epsbf\le \tilde\epsbf$ and $\tilde w_i = w_i(\tilde\xbf_i, \tilde\eps_i)$ for $i\in\Gcal$.
Suppose that $\hat\xbf \in \arg\min_{\xbf\in X} G_{(\tilde \xbf, \tilde \epsbf)}(\xbf)$.
Then, for any $k$, it holds true that
\[ J(\hat\xbf,\hat\epsbf) - J(\tilde\xbf, \tilde\epsbf) \le G_{(\tilde\xbf, \tilde\epsbf)}(\hat\xbf ) - G_{(\tilde\xbf , \tilde\epsbf)}(\tilde\xbf) \le 0.\]
\end{lemma}

\begin{proof}

First of all,
$\hat \xbf  \in\arg\min_\xbf   G_{(\tilde\xbf, \tilde\epsbf)}(\xbf)$, so that
$G_{(\tilde\xbf, \tilde\epsbf)}(\hat\xbf ) - G_{(\tilde\xbf , \tilde\epsbf)}(\tilde\xbf) \le 0$.
Hence
$$\begin{aligned} J(\hat\xbf; \hat \epsbf ) \le & J(\hat \xbf; \tilde \epsbf) =  f(\hat \xbf ) +  \sum_{i\in\Gcal}
r_i( c_i(\hat \xbf_i ) + \tilde\eps_i )\\
\le & f(\tilde\xbf)+f(\hat\xbf )-f(\tilde\xbf) +  \sum_{i\in\Gcal}
r_i( c_i(\tilde\xbf) +\tilde\eps_i) \\
&+  \sum_{i\in\Gcal}
\tilde w_i ( c_i(\hat\xbf )-c_i(\tilde\xbf)  )\\
= & J(\tilde\xbf; \tilde\epsbf) + [G_{(\tilde\xbf, \tilde\epsbf)}(\hat\xbf )-G_{(\tilde\xbf,\tilde\epsbf)}(\tilde\xbf)],\\
\end{aligned}
$$
where the second inequality follows from \eqref{eq.lem.2.1}.
\end{proof}

 Lemma~\ref{lem.J decrease.case1} indicates $J(\xbf; \epsbf)$ is monotonically decreasing for any $\xbf^0\in X, \epsbf^0\in \mathbb{R}_{++}^m$.
 Define the model reduction
\[ \Delta G_{(\xbf^k,\epsbf^k)}(\xbf^{k+1}) = G_{(\xbf^k,\epsbf^k)}(\xbf^k) - G_{(\xbf^k,\epsbf^k)}(\xbf^{k+1}).\]
The next lemma indicates this model reduction converges to zero, which naturally follows from Lemma~\ref{lem.J decrease.case1}.

\begin{lemma}\label{lem.delta to 0}
Suppose
$\xbf^0\in  X$, $\epsbf^0 \in \Rb^m_{++}$, and $\{\xbf^k\}$ are generated by the AIR algorithm.  The following statements hold true:
\begin{enumerate}
        \item[(i)] The sequence $\{\xbf^k\} \subset L(J(\xbf^0; \epsbf^0); J_0)$.
        \item[(ii)]    $\lim\limits_{k\to\infty}\Delta G_{(\xbf^k,\epsbf^k)}(\xbf^{k+1})\to \bm{0}$.
\end{enumerate}
\end{lemma}

 \begin{proof}
Part $(i)$ follows naturally  from   the fact that
 \[ J_0(\xbf^k) \le  J(\xbf^k,\epsbf^k) \le J(\xbf^0, \epsbf^0),\]
for all $k \in \Nb$ by Lemma~\ref{lem.J decrease.case1}.

For part $(ii)$, by Assumption~\ref{basic assumption},  $\tilde{J}:=\inf\limits_kJ(\xbf^{k}; \epsbf^k) > -\infty$. It follows from Lemma~\ref{lem.J decrease.case1}, that
$$
J(\xbf^{k+1},\epsbf^{k+1}) \le J(\xbf^k,\epsbf^k) - \Delta G_{(\xbf^k,\epsbf^k)}(\xbf^{k+1} ).
$$
Summing up both sides of the above inequality from $0$ to $t$, we have
$$
\begin{aligned}
0&\le \sum\limits_{k=1}^{t} \Delta G_{(\xbf^k,\epsbf^k)}(\xbf^{k+1}) \\
&\le J(\xbf^{0},\epsbf^{0}) - J(\xbf^{t+1},\epsbf^{t+1})\le J(\xbf^{0},\epsbf^{0}) - \tilde{J}.
\end{aligned}
$$
Letting $t\to\infty$,  we know part $(ii)$ holds true.
\end{proof}

\subsubsection{Convergence Analysis for Bounded Weights}
We first analyze the convergence when $\epsbf^k\to\epsbf^*\in\mathbb{R}_{++}^m$  or $\lim\limits_{c_i\to 0^+}r'_i(c_i) < + \infty$, $i\in\Gcal$.
In this case, $w_i^k \to w_i^*<+\infty$ if $\xbf_i^k\to \bm{0}$.
The  ``limit subproblem'' takes form
 \beq\label{general.sub.alter.0}
\min_{\xbf}  \quad  \widetilde G_{(\tilde\xbf,\tilde\epsbf)}(\xbf) := f(\xbf) + \sum_{i\in\Gcal} \tilde w_i c_i(\xbf_i) + \delta(\xbf | X).
\eeq
 The existence of the solution to \eqref{general.sub.alter.0} is shown in the next lemma.

\begin{lemma}\label{lem.limit problem.0}
For $\tilde\epsbf\in\mathbb{R}_{++}^m$,  the optimal solution set of \eqref{general.sub.alter.0} is  nonempty.  Furthermore, if $\tilde\xbf$ is an optimal solution of \eqref{general.sub.alter.0}, then $\tilde\xbf$ also satisfies the first-order optimality condition of \eqref{prob.J}.
\end{lemma}
\begin{proof}
Notice that
  $\tilde\xbf$ is feasible for \eqref{general.sub.alter.0} by the definition of $\widetilde G$.
 The level set
\[  \{ \xbf \in X \mid  \widetilde G_{(\xbf^k,\epsbf^k)} (\xbf) \le \widetilde G_{(\xbf^k,\epsbf^k)}(\tilde\xbf)\}  \]
must be nonempty since it contains $\tilde\xbf$ and  bounded  due to the coercivity of $\tilde w_i c_i$, $i\in\Gcal$ and the lower boundedness of $f$ on $X$.
This completes the proof  by  \cite[Theorem 4.3.1]{ortega1970iterative}.

 Therefore, any optimal solution $\xbf$ must satisfies
\[ \bm{0}=  \nabla f(\xbf)_i +  \zbf_i + \nubf_i, i\in\Gcal \]
where $\nubf\in N(\xbf | X)$, $\zbf_i=\tilde w_i \xibf_i $ with
\[ \tilde w_i = r_i(c_i(\tilde\xbf_i)+\tilde\epsbf_i),\ \xibf_i\in\partial c_i(\xbf_i),\ i\in\Gcal.\]
The KKT conditions thus can be rewritten as following by Lemma~\ref{sub diff r}
$$\bm{0}=  \nabla f(\xbf)_i + \tilde w_i\xibf_i  + \nubf_i,$$  $$  \tilde w_i\in\partial_F r_i(c_i(\tilde \xbf_i) + \tilde \eps_i),\ \xibf_i\in\partial c_i(\xbf_i),$$
where $i\in\Gcal$.
If $\tilde\xbf$ is an optimal solution, then we have
\[ \bm{0} \in \nabla f(\tilde\xbf) + \partial_F \Phi(\tilde\xbf;\tilde\epsbf) + N(\tilde\xbf | X),\]
implying $\tilde\xbf$ is optimal for $J(\dotv; \tilde\epsbf)$.
\end{proof}

Now we are ready to prove our main result in this section.

\begin{theorem}\label{main.1.0}
Suppose     $\{\xbf^k\}_{k=0}^\infty$ is generated by the AIR algorithm with initial point
$\xbf^0 \in X$ and  relaxation vector $\epsbf^0 \in \bR^m_+$ with $\epsbf^k\to\epsbf^*$.  Assume either
\[ \eps_i^*>0 \text{ or }   r'(0+) < +\infty, \  i\in\Gcal\]
is true. Then  if $\{ \xbf^k\}$ has any cluster point,   it satisfies the optimality condition \eqref{optimality} for $J(\xbf; \epsbf^*)$.
\end{theorem}

\begin{proof} Let $\xbf^*$ be a cluster point of $\{\xbf^k\}$.  From Lemma~\ref{lem.limit problem}, it suffices to show that
$\xbf^*\in\arg\min_{\xbf}\widetilde G_{(\xbf^*,\epsbf^*)}(\xbf)$.
We prove this by contradiction.  Assume that there exists a point $\bar\xbf$ such that
$\varepsilon := G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^*, \epsbf^*)}(\bar{\xbf}) >0$.
Suppose  $\{\xbf^k\}_\Scal\to\xbf^*$,  $\Scal \subset \mathbb{N}$. Based on Lemma~\ref{lem.delta to 0}$(ii)$, there exists $k_1 >0$, such that for all $k> k_1$
\begin{equation}\label{g is small 0}
        G_{(\xbf^k, \epsbf^k)}(\xbf^k) - G_{(\xbf^k, \epsbf^k)}(\xbf^{k+1})\le \varepsilon/4.
\end{equation}
To derive a contradiction, notice that  $\xbf_i^k\overset{\Scal}{\to} \xbf_i^*$ and   $w_i^k \overset{\Scal}{\to} w_i^*$. There exists $k_2$ such that for all $k>k_2, k\in\Scal$,
 \[
 \begin{aligned}
   \sum_{i\in \Gcal}(w_i^*-w_i^k)c_i(\bar\xbf_i) & > - \varepsilon/12,  \\
  \sum_{i\in \Gcal}(w_i^k c_i(\xbf_i^k)-w_i^*c_i( \xbf_i^*) ) & > - \varepsilon/12,\\
  f(\xbf^k) - f(\xbf^*) & > - \varepsilon/12.
  \end{aligned}
   \]
Therefore,  for all $k>k_2, k\in\Scal$,
\[
\begin{aligned}
&\ G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^k, \epsbf^k)}(\bar\xbf)\\
 = &\  [f(\xbf^*)+ \sum_{i\in \Gcal} w_i^* c_i(\xbf_i^*) ] - [f(\bar\xbf)\\
 &+ \sum_{i\in \Gcal} [w_i^*-(w_i^*-w_i^k)] c_i(\bar\xbf_i) \\
= &\ [G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^*, \epsbf^*)}(\bar\xbf) ] + \sum_{i\in \Gcal}(w_i^*-w_i^k)c_i(\bar\xbf_i),\\
\ge &\  [G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^*, \epsbf^*)}(\bar\xbf) ] - \varepsilon/12\\
\ge &\ \varepsilon - \varepsilon/12 = 11\varepsilon/12,
\end{aligned}
\]
and that
\[
\begin{aligned}
 & \ G_{(\xbf^k, \epsbf^k)}(\xbf^k) - G_{(\xbf^*, \epsbf^*)}(\xbf^*) \\
=  &\ [f(\xbf^k)   + \sum_{i\in \Gcal} w_i^k c_i(\xbf_i^k)]- [f(\xbf^*)+ \sum_{i\in \Gcal}w_i^* c_i(\xbf_i^*) ]\\
 \ge  & \ -\varepsilon/6
\end{aligned}
\]
Hence, for all $k>\max(k_1,k_2), k\in\Scal$,  it holds that
\[
\begin{aligned}
& G_{(\xbf^k, \epsbf^k)}(\xbf^k) - G_{(\xbf^k, \epsbf^k)}(\bar\xbf) \\
= &  G_{(\xbf^k, \epsbf^k)}(\xbf^k) - G_{(\xbf^*, \epsbf^*)}(\xbf^*) + G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^k, \epsbf^k)}(\bar\xbf)\\
= &11\varepsilon/12 -\varepsilon/6 = 3\varepsilon/4,
\end{aligned}
  \]
  contradicting with \eqref{g is small 0}. Therefore, $\xbf^*\in\arg\min_{\xbf}\widetilde G_{(\xbf^*,\epsbf^*)}(\xbf)$.
By Lemma~\ref{lem.limit problem.0}, $\xbf^*$ satisfies the first-order optimality for \eqref{prob.J}.
\end{proof}

\begin{remark}
 The convexity of $f$ is not necessary if $\xbf^{k+1}$ is found as the global minimizer of \eqref{prob.J}. In this case, the global convergence  we have derived so far can be modified accordingly, and in  the statement of Lemma~\ref{lem.limit problem},  a global minimizer $\tilde\xbf$ of
 \eqref{general.sub.alter} implies its optimality of \eqref{prob.J}.
\end{remark}

\subsubsection{Convergence Analysis for Degenerated Weights}

We have shown the convergence of the AIR algorithm with fixed $\epsilon$.  By Theorem~\ref{thm.j approx j0}, we can choose sufficiently small
$\epsilon$ and minimize $J(\cdot; \epsbf)$ instead of $J_0$ to obtain an approximate solution. However, as also shown  by Theorem~\ref{thm.j approx j0},  $J(\cdot; \epsbf)$   converges to $J_0$ only pointwisely. It then may be difficult to assert that the minimizer of $J(\cdot; \epsbf)$ is sufficiently
close to the minimizer of $J_0$ for given $\epsbf$.  Therefore, we consider to minimize  a sequence of $J(\cdot; \epsbf)$ with $\epsbf$ driven to $\bm{0}$.
We analyze the global convergence of the AIR algorithm in this case with $c_i(\xbf_i) = \|\xbf_i\|_1$.  Notice that
\[ \partial c_i(\bm{0})  = \{ \xibf_i\in\mathbb{R}^{n_i} \mid \|\xibf_i\|_\infty \le 1\}. \]

 As the algorithm proceeds, of particular interest is the properties  of  the ``limit subproblem'' as the (sub)sequence of iterates converges. Notice that it may happen
$w_i^k\to\infty$ if $\xbf^k_i\to 0$ and $\eps_i^k \to 0$, so that $G$ may be not well-defined. Therefore, we consider an alternative form of the ``limit
subproblem'' for $\tilde\epsbf\in\mathbb{R}_+^m$
\beq\label{general.sub.alter}
\begin{aligned}
\min_{\xbf} & \quad  \widetilde G_{(\tilde\xbf,\tilde\epsbf)}(\xbf) := f(\xbf) + \sum_{i\in\Ncal(\tilde\xbf,\tilde\epsbf)} \tilde w_i c_i(\xbf_i) + \delta(\xbf | X),\\  \st&\quad  \xbf_i = \bm{0},\  i\in \Acal(\tilde\xbf,\tilde\epsbf),
\end{aligned}
\eeq
where       $\Acal(\tilde\xbf,\tilde\epsbf):=\{i\mid \tilde\xbf_i = \bm{0}, \tilde \eps_i= 0 \}$ and $\Ncal(\tilde\xbf,\tilde\epsbf):=\Gcal\setminus\Acal(\tilde\xbf, \tilde\epsbf)$.
The existence of the solution to \eqref{general.sub.alter} is shown in the next lemma.

\begin{lemma}\label{lem.limit problem}
For $\tilde\epsbf\in\mathbb{R}_{+}$,  the optimal solution set of \eqref{general.sub.alter} is  nonempty.  Furthermore, if $\tilde\xbf$ is an optimal solution of \eqref{general.sub.alter}, then $\tilde\xbf$ also satisfies the first-order optimality condition of \eqref{prob.J}.
\end{lemma}
\begin{proof}
Notice that
  $\tilde\xbf$ is feasible for \eqref{general.sub.alter} by the definition of $\widetilde G$.
 The level set
\[  \{ \xbf \in X \mid  \widetilde G_{(\xbf^k,\epsbf^k)} (\xbf) \le \widetilde G_{(\xbf^k,\epsbf^k)}(\tilde\xbf); \  \xbf_i = \bm{0}, i\in\Acal(\tilde\xbf, \tilde\epsbf)\}  \]
must be nonempty since it contains $\tilde\xbf$ and  bounded  due to the coercivity of $\tilde w_i c_i$, $i\in\Gcal$ and the lower boundedness of $f$ on $X$.
This completes the proof  by  \cite[Theorem 4.3.1]{ortega1970iterative}.

Obviously  Slater's condition holds at any feasible point of \eqref{general.sub.alter}.  Therefore, any optimal solution $\xbf$ must satisfies the KKT conditions
\[ \bm{0}=  \nabla f(\xbf)_i +  \zbf_i + \nubf_i, i\in\Gcal \]
with $\nubf\in N(\xbf | X)$, $\zbf_i=\tilde y_i \xibf_i $ with $\tilde y_i:= \tilde w_i= r_i'(c_i(\tilde\xbf_i)+\tilde\epsbf_i), \xibf_i\in\partial c_i(\xbf_i), i\in\Ncal(\tilde\xbf,\tilde\epsbf)$.
Now for $i\in \Acal(\tilde\xbf,\tilde\epsbf)$, let $\tilde y_i = \|\zbf_i\|_\infty$ and $\xibf_i=  \zbf_i/\|\zbf_i\|_\infty$ so that $\xibf_i \in \partial c_i(0) = \partial c_i(\tilde\xbf_i+\tilde\eps_i)$. The KKT conditions can be rewritten as
$$ \bm{0}=  \nabla f(\xbf)_i +  \tilde y_i \xibf_i  + \nubf_i,$$    $$y_i\in\partial_F r_i(c_i(\tilde \xbf_i) + \tilde \eps_i),$$  $$\xibf_i\in\partial c_i(\xbf_i),  i\in\Gcal, $$
by Lemma~\ref{sub diff r}.
If $\tilde\xbf$ is an optimal solution, then we have
\[ \bm{0} \in f(\tilde\xbf) + \partial_F \phi(\tilde\xbf;\tilde\epsbf) + N(\tilde\xbf | X),\]
implying $\tilde\xbf$ is optimal for $J(\dotv; \tilde\epsbf)$.
\end{proof}

Now we are ready to prove our main result in this section.

\begin{theorem}\label{main.1}
Suppose   sequence $\{\xbf^k\}_{k=0}^\infty$ is generated by the AIR algorithm with initial point
$\xbf^0 \in X$ and relaxation vector $\epsbf^0 \in \bR^m_{++}$.
If  $\{ \xbf^k\}$ has any cluster point $\xbf^*$, then it satisfies the optimality condition.
\end{theorem}

\begin{proof} Let $\xbf^*$ be a cluster point of $\{\xbf^k\}$ and $\epsbf^*=\lim\limits_{k\to\infty} \epsbf^k$.  From Lemma~\ref{lem.limit problem}, it suffices to show that
$\xbf^*\in\arg\min_{\xbf}\widetilde G_{(\xbf^*,\epsbf^*)}(\xbf)$.
We prove this by contradiction.  Assume that there exists a point $\bar\xbf$ such that $c_i(\bar\xbf_i)= 0$ for all $i \in\mathcal{A}(\xbf^*,\epsbf^*)$ and $G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^*, \epsbf^*)}(\bar{\xbf})>\varepsilon>0$.
Suppose  $\{\xbf^k\}_\Scal$,  $\Scal \subset \mathbb{N}$. Based on Lemma~\ref{lem.delta to 0}$(ii)$, there exists $k_1 >0$, such that for all $k> k_1$
\begin{equation}\label{g is small}
        G_{(\xbf^k, \epsbf^k)}(\xbf^k) - G_{(\xbf^k, \epsbf^k)}(\xbf^{k+1})\le \varepsilon/4.
\end{equation}
To derive a contradiction, notice that  $\xbf_i^k\overset{\Scal}{\to} \xbf_i^*$ and   $w_i^k \overset{\Scal}{\to} w_i^*$. There exists $k_2$ such that for all $k>k_2, k\in\Scal$,
 \[
 \begin{aligned}
   \sum_{i\in \Ncal(\xbf^*, \epsbf^*)}(w_i^*-w_i^k)c_i(\bar\xbf_i) & > - \varepsilon/12,  \\
  \sum_{i\in \Ncal(\xbf^*, \epsbf^*)}(w_i^k c_i(\xbf_i^k)-w_i^*c_i( \xbf_i^*) ) & > - \varepsilon/12,\\
  f(\xbf^k) - f(\xbf^*) & > - \varepsilon/12.
  \end{aligned}
   \]
Therefore,  for all $k>k_2, k\in\Scal$,
\[
\begin{aligned}
&\ G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^k, \epsbf^k)}(\bar\xbf)\\
 = &\  [f(\xbf^*)+ \sum_{i\in \Ncal(\xbf^*, \epsbf^*)} w_i^* c_i(\xbf_i^*) ]\\
 & -[f(\bar\xbf)+ \sum_{i\in \Ncal(\xbf^*, \epsbf^*)} [w_i^*-(w_i^*-w_i^k)] c_i(\bar\xbf_i)] \\
= &\ [G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^*, \epsbf^*)}(\bar\xbf) ] + \sum_{i\in \Ncal(\xbf^*, \epsbf^*)}(w_i^*-w_i^k)c_i(\bar\xbf_i),\\
\ge &\  [G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^*, \epsbf^*)}(\bar\xbf) ] - \varepsilon/12\\
\ge &\ \varepsilon - \varepsilon/12 = 11\varepsilon/12,
\end{aligned}
\]
and that
\[
\begin{aligned}
 & \ G_{(\xbf^k, \epsbf^k)}(\xbf^k) - G_{(\xbf^*, \epsbf^*)}(\xbf^*) \\
=  &\ [f(\xbf^k) + \sum_{i\in \Acal(\xbf^*, \epsbf^*)} w_i^k c_i(\xbf_i^k) + \sum_{i\in \Ncal(\xbf^*, \epsbf^*)} w_i^k c_i(\xbf_i^k)]\\
&- [f(\xbf^*)+ \sum_{i\in \Ncal(\xbf^*, \epsbf^*)}w_i^* c_i(\xbf_i^*) ]\\
\ge &\ [f(\xbf^k)   + \sum_{i\in \Ncal(\xbf^*, \epsbf^*)} w_i^k c_i(\xbf_i^k)]\\
&- [f(\xbf^*)+ \sum_{i\in \Ncal(\xbf^*, \epsbf^*)}w_i^* c_i(\xbf_i^*) ]\\
\ge  & \ -\varepsilon/6.
\end{aligned}
\]
Hence, for all $k>\max(k_1,k_2), k\in\Scal$,  it holds that
\[
\begin{aligned}
& \  G_{(\xbf^k, \epsbf^k)}(\xbf^k) - G_{(\xbf^k, \epsbf^k)}(\xbf^{k+1}) \\
= & \  G_{(\xbf^k, \epsbf^k)}(\xbf^k) - G_{(\xbf^*, \epsbf^*)}(\xbf^*) + G_{(\xbf^*, \epsbf^*)}(\xbf^*) - G_{(\xbf^k, \epsbf^k)}(\bar\xbf)\\
= &11\varepsilon/12 -\varepsilon/6 = 3\varepsilon/4,
\end{aligned}
  \]
  contradicting with \eqref{g is small}. Therefore, $\xbf^*\in\arg\min_{\xbf}\widetilde G_{(\xbf^*,\epsbf^*)}(\xbf)$.
By Lemma~\ref{lem.limit problem}, $\xbf^*$ satisfies the first-order optimality for \eqref{prob.J}.
\end{proof}

\begin{remark}
 The convexity of $f$ is not necessary if $\xbf^{k+1}$ is found as the global minimizer of \eqref{prob.J}. In this case, the global convergence  we have derived so far can be modified accordingly, and in  the statement of Lemma~\ref{lem.limit problem},  a global minimizer $\tilde\xbf$ of
 \eqref{general.sub.alter} implies its optimality of \eqref{prob.J}.

\end{remark}

 \subsection{Existence of Cluster Points}

 We shall show that our proposed AIR algorithm  is a descent method for the function $J(\xbf, \epsbf)$.  Consequently, both the existence of solutions to
 \eqref{f.sparse} as well as the existence of the cluster point to the AIR algorithm can be guaranteed by understanding conditions under which the iterates generated by AIR
 is bounded. For this purpose, we need to investigate the asymptotic geometry of $J$ and $X$.
In the following a series of results, we discuss the conditions guaranteeing  the  boundedness of $L(J(\xbf^0; \epsbf^0); J_0) $.
The concept of horizon cone is a useful tool to characterize the boundedness of a set, which is defined as follows.

\begin{definition} \cite[Definition 3.3]{Roc98} Given $Y\subset \mathbb{R}^n$, the horizon cone of $Y$ is
\[ Y^\infty := \{ \zbf \mid \exists t^k\downarrow 0, \{\ybf^k\}\subset Y \text{  such that  }   t^k\ybf^k \to \zbf \}.\]
\end{definition}

We have the basic properties about horizon cones given in the following proposition, where the first case is trivial  to show and others are from \cite{Roc98}.

\begin{proposition}\label{prop.cone}
  The following statements hold:
\begin{enumerate}
\item[(i)] If $X\subset Y \subset \mathbb{R}^n$,  then $X^\infty\subset Y^\infty$.
\item[(ii)] \cite[Theorem 3.5]{Roc98} The set $Y\subset \mathbb{R}^n$ is bounded if and only if $Y^\infty = \{\bm{0}\}$.
\item[(iii)] \cite[Exercise 3.11]{Roc98} Given $Y_i\subset \mathbb{R}^{n_i}$ for $i\in\Gcal$, we have $(Y_1\times \ldots \times Y_m)^\infty
= Y_1^\infty \times \ldots \times Y_m^\infty$.
\item[(iv)] \cite[Theorem 3.6]{Roc98} If $C\subset \mathbb{R}^n$ is non-empty, closed, and convex, then
\[ C^\infty = \{\zbf \mid C+\zbf \subset C\}.\]
\end{enumerate}
\end{proposition}

Next we investigate the boundedness of $L(J(\xbf^0; \boldsymbol{\epsilon}^0), J_0)$, and provide upper and lower estimates
of $L(J(\xbf^0; \boldsymbol{\epsilon}^0), J_0)$.  For this purpose, define
\[\begin{aligned}
H(\xbf^0, \epsbf^0) := &\  \{ \bar \xbf \mid   \bar \xbf \in X^\infty, \bar \xbf \in L(f(\xbf^0); f)^\infty, \\
   &\bar\xbf_i\in L(c_i(\xbf_i^0)+\eps_i^0; c_i)^\infty, i\in\Gcal  \},
    and
\end{aligned}
\]
\[\begin{aligned}
\tilde H(\xbf^0, \epsbf^0)  := &\ X^\infty \cap L(J(\xbf^0; \epsbf^0); f)^\infty\\
& \cap (\prod_{i\in\Gcal} L(J(\xbf^0; \epsbf^0)-\underline f; r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i)^\infty ).
\end{aligned}
\]
We now prove the following result about the lower level sets of $L(J(\xbf^0; \boldsymbol{\epsilon}^0), J_0)$.
\begin{theorem}\label{thm.level.set}
  Let $\xbf^0\in X$ and $\epsbf^0\in\mathbb{R}^m_{++}$. Then
  \[ L( r_i(c_i(\xbf_i^0)+\eps_i^0); r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i ) = L(c_i(\xbf_i^0)+\eps_i^0; c_i) \]
     for $i\in\Gcal$. Moreover, it holds that
  \begin{equation}\label{level.set1}
 \hat H(\xbf^0, \epsbf^0)   \subset  L(J(\xbf^0; \epsbf^0); J_0)^\infty.
  \end{equation}
Furthermore, suppose $\underline f := \inf_{\xbf\in X} f(\xbf) > -\infty$. Then
\begin{equation}\label{level.set2}
      L(J(\xbf^0; \epsbf^0); J_0)^\infty \subset \tilde H(\xbf^0, \epsbf^0).
 \end{equation}
 \end{theorem}

\begin{proof}
The convexity of $L(\xbf_i^0; r_i(c_i(\dotv)+\eps_i^0))$ is by the fact that
\[\begin{aligned}
  & \xbf_i \in L( r_i(c_i(\xbf_i^0)+\eps_i^0); r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i ) \\
  \iff  &r_i(c_i(\xbf_i) ) \le r_i(c_i(\xbf_i^0)+\eps_i^0)\\
  \iff &    c_i(\xbf_i) \le  c_i(\xbf_i^0)+\eps_i^0\\
   \iff &    \xbf_i \in L(c_i(\xbf_i^0)+\eps_i^0; c_i),
 \end{aligned}
\]
where the second equivalence is from the monotonic increasing property of $r_i$. Notice that $L(c_i(\xbf_i^0)+\eps_i^0; c_i)$ is convex.

Now we prove~\eqref{level.set1}.  Let $\xbf\in L(J(\xbf^0; \epsbf^0); J_0)$ and $\bar \xbf$ be an element of  $\hat H(\xbf^0, \epsbf^0)$.
$$ \xbf + \lambda\bar \xbf\in X,\   \xbf + \lambda\bar\xbf \in L(f(\xbf^0); f)^\infty, $$
and
$$  \xbf_i + \lambda\bar\xbf_i \in L(c_i(\xbf_i^0)+\eps_i^0; c_i)^\infty. $$
Therefore, it holds that
\[ \begin{aligned}
J_0( \xbf + \lambda\bar\xbf) = & f(\xbf + \lambda\bar\xbf) + \sum_{i\in\Gcal} r_i(c_i(\xbf_i + \lambda\bar\xbf_i))\\
\le & f(\xbf^0) + \sum_{i\in\Gcal} r_i(c_i(\xbf^0_i)+\eps_i^0)\\
= & J(\xbf^0; \epsbf^0).
\end{aligned}
\]
Consequently, $\bar\xbf\in L(J(\xbf^0; \epsbf^0); J_0)$, proving \eqref{level.set1}.

For \eqref{level.set2}, let $\bar\xbf \in L (J(\xbf^0; \epsbf^0); J_0)^\infty$.   We need to show that   $\bar \xbf$ is an element of  $\tilde H(\xbf^0, \epsbf^0)$.  For this, we may as well assume that $\bar\xbf\neq0$.  By the fact that $L(J(\xbf^0; \epsbf^0); J_0)^\infty$, there exists $t^k\downarrow 0$ and $\{\xbf^k\}\subset X$ such that $J_0(\xbf^k) \le J(\xbf^0; \epsbf^0)$ and $t^k\xbf^k \to \bar \xbf$. Consequently, $\bar\xbf\in X^\infty$.  Hence
\beq\label{sub.level.set1}
L (J(\xbf^0; \epsbf^0); J_0)^\infty \subset X^\infty.
\eeq
On the other hand, let $\tilde\xbf\in L (J(\xbf^0; \epsbf^0); J_0)$. It then follows that
\[ f(\tilde\xbf) = J_0(\tilde \xbf) - \sum_{i\in\Gcal} r_i(c_i(\tilde\xbf_i)) \le J_0(\tilde \xbf) \le  J(\xbf^0; \epsbf^0), \]
where the first inequality is by the fact that $r_i\ge 0$. Consequently,
$\tilde\xbf\in L(J(\xbf^0; \epsbf^0); f)$, implying $L(J(\xbf^0; \epsbf^0); J_0) \subset L(J(\xbf^0; \epsbf^0); f)$. Hence
\beq\label{sub.level.set2}
L(J(\xbf^0; \epsbf^0); J_0)^\infty \subset L(J(\xbf^0; \epsbf^0); f)^\infty.
\eeq
Now considering $c_i$, we have for $i\in \Gcal$
\[ r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i(\tilde \xbf_i) = J_0(\tilde\xbf) - f(\tilde\xbf)-\sum_{j\in\Gcal,j\ne i} r_i(c_i(\tilde\xbf_i)) \le J(\xbf^0; \epsbf^0) - \underline f,\]
implying $\tilde\xbf_i \in L(J(\xbf^0; \epsbf^0); r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i)$, $i\in\Gcal$. Therefore,
\[ L(J(\xbf^0; \epsbf^0); J_0) \subset \prod_{i\in\Gcal} L(J(\xbf^0; \epsbf^0) - \underline f; r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i), \]
This implies that
$$
\begin{aligned}
 L(J(\xbf^0; \epsbf^0); J_0)^\infty
 &\subset  (\prod_{i\in\Gcal} L(J(\xbf^0; \epsbf^0)-\underline f; r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i))^\infty  \\
 &=   \prod_{i\in\Gcal} L(J(\xbf^0; \epsbf^0)-\underline f; r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i)^\infty,
\end{aligned}
$$
which, combined with \eqref{sub.level.set1} and \eqref{sub.level.set2}, yields \eqref{level.set2}.
\end{proof}

The following results follow directly from  Theorem~\ref{thm.level.set}.
\begin{corollary}\label{coro.bound}
If there exists $\bar\xbf\neq0$ such that
\[ \bar \xbf \in X^\infty,\  \bar \xbf \in L(f(\xbf^0); f)^\infty,  \  \bar\xbf_i\in L(c_i(\xbf_i^0)+\eps_i^0; c_i)^\infty, i\in\Gcal, \]
then $L(J(\xbf^0;\epsbf^0); J_0)$ is unbounded.   Conversely, if one of the sets
\[ X^\infty, \  L(J(\xbf^0; \epsbf^0); f)^\infty,  \text{ and  }\  (\prod_{i\in\Gcal} L(J(\xbf^0; \epsbf^0)-\underline f; r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i)^\infty )\]
is empty, then $L(J(\xbf^0;\epsbf^0); J_0)$ is bounded.
\end{corollary}

Based on Corollary~\ref{coro.bound},
we provide    specific  cases in the following proposition  that can guarantee the boundedness of $L(J(\xbf^0;\epsbf^0); J_0)$.

\begin{proposition}\label{lem.AIR2}
Suppose
$\xbf^0\in  X$ and relaxation vector $\epsbf^0 \in \Rb^m_{++}$. Then the level set  $L(J(\xbf^0, \epsbf^0), J_0)$ is bounded, if  one of the following conditions holds true
\begin{enumerate}
\item[(i)] $X$ is compact.
\item[(ii)] $f$ is coercive.
\item[(iii)] $r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i$, $i\in\Gcal$ are all coercive.
\item[(iv)] Assume
\[  \gamma_i := \sup_{\|\xbf_i\|\to \infty} r_i(c_i(\xbf_i)) < +\infty, \ i\in\Gcal.\]
Suppose $(\xbf^0, \epsbf^0)$ is selected to satisfy $\sum\limits_{i\in\Gcal} r_i(c_i(\xbf_i^0)+\eps_i^0) \le \underline f + \min\limits_i   \gamma_i$.
\end{enumerate}
 \end{proposition}

\begin{proof}
Part $(i)$-$(iii)$ are  trivial true by Corollary~\ref{coro.bound}.  We only prove part $(iv)$.

Assume by contradiction that  $L(J(\xbf^0;\epsbf^0); J_0)$ is unbounded, then there exists   $\bar\xbf\in L(J(\xbf^0;\epsbf^0); J_0)^\infty$ with  $\bar\xbf \ne\bm{0}$.  By the definition of horizon cone, there exists $\{t^k\}\subset \mathbb{R}$ and $\{\xbf^k\}\subset X$ such that
\[ t^k\downarrow 0,  J_0(\xbf^k) \le J(\xbf^0; \epsbf^0),  \text{ and }  t^k\xbf^k\to \bar \xbf.\]
Therefore, there must be an $\bar i \in \Gcal$, such that $\|\xbf^k_{\bar i}\|_2 \to \infty$, implying $r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i(\xbf_{\bar i}^k) \to \gamma_{\bar i}$. This means,
$$
\begin{aligned}
 J(\xbf^0;\epsbf^0)   &\ge \lim_{k\to\infty} J_0(\xbf^k) \ge \underline f+ \lim_{k\to\infty} r_i\ensuremath\mathop{\scalebox{.7}{$\circ$}} c_i(\xbf_{\bar i}^k) \\
 &=\underline f+  \gamma_{\bar i} \ge \underline f+ \min\limits_{i\in\Gcal} \gamma_i,
\end{aligned}
 $$
a contradiction.  Therefore, $L(J(\xbf^0, \epsbf^0), J_0)$ is bounded.
\end{proof}

Proposition~\ref{lem.AIR2} (iv) indicates that the initial iterate $\xbf^0$ and $\epsbf^0$ may need to be chosen sufficiently close to $\bm{0}$ to  enforce convergence
if $\phi_i$ is not coercive such as
\eqref{f.inv}.

\section{Numerical Experiments}
\label{sec.experiment}

In this section, we test  our proposed  AIR algorithm for solving the nonconvex and nonsmooth sparse optimization problems in two numerical experiments and demonstrate its performance.
In both experiments, the test problems  have   $f(\xbf)\equiv  0$.
The algorithm is implemented in Matlab with the subproblems solved by the CVX solver~\cite{cvx}.
We consider  two ways of choosing $c_i$, $c_i(x_i)=|x_i|$ and $c_i=x_i^2$,  as described in Table~\ref{tab.1}, yielding AIR $\ell_1$- and $\ell_2$-algorithm, respectively.  In subproblems, we use identical value for each component of the relaxation parameter $\epsbf^k$, i.e., $\epsbf^k = \epsilon^k \ebf$. In following two experiments, we define \emph{sparsity} as the nonzeros of the vectors.

\subsection{Sparse Signal Recovery}
In this subsection, we consider a sparse signal recovery problem~\cite{candes2008enhancing}, which aims to recover individual sparsity vectors from linear measurements. The method of $\ell_1$ minimization is a well-established sparsity-inducing approach to this problem. To further enhance sparsity, we replace the $\ell_1$-norm objective by the $\ell_p$ quasi-norm~\eqref{f.lp} with $p\in(0,1)$, and solve the following nonconvex and nonsmooth sparse optimization problem
\begin{equation}\label{f.cs}
\begin{aligned}
\min_{\xbf\in\mathbb{R}^n}\quad & \|\xbf\|_p^p\\
\st \quad & \Abf\xbf = \bbf,
\end{aligned}
\end{equation}
where $\Abf\in \mathbb{R}^{m\times n}$ is the measurement matrix, and $\bbf\in \mathbb{R}^{m\times 1}$ is the measurement vector.

In the numerical experiments, we fix $n=256$ and the measurement numbers $m=100$. Draw the measurement matrix $\Abf\in \mathbb{R}^{m\times n}$ with entries normally distributed.
Denote $s$ as the nonzero entries of $\xbf_0$.
For each $s\in\{1,2,\cdots,100\}$, we repeat the following procedure $100$ times:
\begin{enumerate}
        \item[(i)] Construct $\xbf_0\in \mathbb{R}^{n\times 1}$ with randomly zeroing $n-s$ components. Each nonzero entry is chosen randomly from a zero-mean unit-variance Gaussian distribution.
        \item[(ii)] Form $\bbf_0=\Abf\xbf_0$.
        \item[(iii)] Solve~\eqref{f.cs} for $\hat{\xbf}_0$.
        \item[(iv)] Declare \emph{success} if $\|\hat{\xbf}_0-\xbf_0\|_{\infty}\le 10^{-3}$.
\end{enumerate}

We solve~\eqref{f.cs} by the AIR $\ell_1$- and $\ell_2$-algorithm proposed in \S~\ref{sub.L12}.
In both implementations for the two algorithms, we set $\epsilon_i^0=1$ for the AIR algorithm and update by $\epsilon_i^{k+1} = 0.7\epsilon_i^k$ ($i = 1,\cdots,L$) at each iteration with  the threshold as $10^{-6}$. Set $p=0.1$. The algorithm is terminated whenever
$ {|f(\xbf^{k+1}) - f(\xbf^k)|}  \le 10^{-5},$
or the number of iterations reaches $500$.

In Fig.~\ref{fig.SSR}, we compare our proposed AIR $\ell_1$- and $\ell_2$-algorithms to the $\ell_1$-norm minimization algorithm.
It shows that both AIR $\ell_1$- and $\ell_2$-algorithm make a marked improvement over the $\ell_1$-norm minimization algorithm in sparse signal recovery. The requisite oversampling factor $m/k$ for empirical success probability has dropped from approximately
$100/25=4$ for unweighted $\ell_1$-norm algorithm, $100/30\approx 3.3$ for AIR $\ell_2$-algorithm, and $100/37= 2.7$ for AIR $\ell_1$-algorithm.
\begin{figure}[t]
        \center
        \includegraphics[scale = 0.3]{SSR.png}
        \caption{Empirical success recovery probability  versus sparsity.}
        \label{fig.SSR}
\end{figure}

\subsection{Group Sparse Optimization for Network Power Minimization}

In the second experiment, we consider the cloud radio access network power consumption problem~\cite{gsbf}.
In order to solve this problem, a three-stage group sparse beamforming method (GSBF) was proposed in~\cite{gsbf}. Specifically, the GSBF method solves a group sparse optimization problem in the first stage to induce the group sparsity for the beamformers to guide the remote radio head (RRH) selection. This group sparse problem is addressed by minimizing the mixed $\ell_1/\ell_2$-norm. For further enhancing the group sparsity, we replace the $\ell_1/\ell_2$-norm by the nonconvex $\ell_p/\ell_2$ quasi-norm~\eqref{f.lp} with $p\in(0,1)$~\cite{Shi2016Smoothed}, yielding the following problem:
\begin{equation}
\begin{aligned}
\min_{\vbf}\quad & \sum_{l=1}^{L}\sqrt{\frac{\rho_l}{\eta_l}}\|\tilde{\vbf}_l\|_2^p\\
\st \quad & \left({\sum\nolimits_{i\neq k} \| h_k^{\sf{H}} \vbf_i \|_2^2 + \sigma _k^2}\right)^{1/2}\leq \frac{1}{\gamma _k}\Re (h_k^{\sf{H}} \vbf_k)\\
& \| {\tilde{\vbf}}_{l}  \| _2\leq \sqrt{P_l},\ l =1,\cdots,L, k = 1,\ldots, K.
\end{aligned}\label{f.GS}
\end{equation}
Here, we consider the Cloud-RAN architecture with $L$ RRHs and $K$ single-antenna mobile users (MUs), where the $l$-th RRH is equipped with $N_l$ antennas.
$\vbf_{lk} \in \mathbb{C}^{N_l}$ is the transmit beamforming vector from the $l$-th RRH to the $k$-th user with the group structure of transmit vectors ${\tilde{\vbf}}_{l}=[\vbf_{l1}^T,\cdots, \vbf_{lK}^T]^T\in \mathbb{C}^{K\times N_l}$. Denote the relative fronthaul link power consumption by $\rho_l$, and the inefficient of drain efficiency of the radio frequency power amplifier by $\eta_l$.
The channel propagation between user $k$ and RRH $l$ is denoted as $\hbf_{lk}\in \mathbb{C}^{N_l}$.
$P_l$ is the maximum transmit power of the $l$-th RRH.
$\sigma _k$ is the noise at MU $k$.
$\bm{\gamma} = (\gamma_1,..., \gamma_K)^T$ is the target signal-to-interference-plus-noise ratio (SINR).

In our experiment, we consider a network with $L=10$ $2$-antenna RRHs (i.e., $N_l=2$), and $K=6$ single-antenna MUs uniformly and independently distributed in the square region $[-1000,\ 1000]\times[-1000,\ 1000]$ meters. We set $P_l =1$, $\rho_l = 13$, $\eta_l=\frac{1}{4}$ for $l \in\{1,\cdots,L\}$, $\sigma_k = 1$ for $k \in\{1,\ldots, K\}$.
For each quality of service (QoS) $q$ in $\{0,2,4,6\}$, we set the target SINR $\gamma_k = 10^{q/10}$ for $k= 1,\ldots, K$.
Repeat the following procedure $50$ times:
\begin{enumerate}
        \item[(i)]  Randomly generated network realizations for the channel propagations $\hbf_{lk}$, $l\in\{1,\cdots,L\}$, $k\in\{1,\cdots,K\}$ based on the channel model in \cite{gsbf}.
        \item[(ii)] Adopt the AIR $\ell_1$- and $\ell_2$-algorithm to solve~\eqref{f.GS} for $\tilde{\vbf}^*$.
        \item[(iii)] Regard the $l$-th component of $\tilde{\vbf}^*$ as zero, if $\|\tilde{\vbf}_l^*\|\le 10^{-3}$ for $l\in\{1,\cdots,L\}$.
\end{enumerate}

We set the maximum number of iterations as $T = 500$, $\epsilon_i^0=100$ for the AIR algorithm and update by $\epsilon^{k+1} = 0.7\epsilon^k$  at each iteration with minimum threshold $10^{-6}$. Set $p=0.1$. The algorithm is terminated whenever
$ |f(\xbf^{k+1}) - f(\xbf^k)| \le 10^{-4}$
is satisfied.

In Fig.~\ref{fig.sparsity}, we demonstrate the sparsity of the final solution returned by the mixed $\ell_1/\ell_2$ algorithm \cite{gsbf}, AIR $\ell_1$- and $\ell_2$-algorithms for solving problems \eqref{f.GS} with different SINR. The proposed AIR $\ell_1$- and $\ell_2$-algorithms outperform the mixed $\ell_1/\ell_2$ algorithm in promoting the group sparsity. And it is witnessed again that the AIR  $\ell_1$-algorithm outperforms AIR $\ell_2$-algorithm in the ability of  inducing sparse solutions.

\begin{figure}[t]
        \center
        \includegraphics[scale = 0.3]{sparsity.png}
        \caption{Average sparsity level versus target SINR.}
        \label{fig.sparsity}
\end{figure}

\section{Conclusions}
\label{sec.conclusion}
In this paper, we considered solving  a general formulation for nonconvex and nonsmooth sparse optimization problems, which can take into account  different nonconvex sparsity-inducing terms.  An iteratively reweighted algorithmic framework  is proposed by solving  a sequence of weighted convex penalty subproblems.  We have  established the optimality condition for the nonconvex and nonsmooth sparse optimization problem, and provided the global convergence analysis for the proposed iteratively reweighted methods. Two variants of our proposed algorithm, the iteratively reweighted $\ell_1$-algorithm and the iteratively reweighted $\ell_2$-algorithm,  were  implemented and tested. Numerical results demonstrated their ability to recover sparse signals and enhancing sparsity.

\bibliographystyle{ieeetr}

redpajama_set_name: RedPajamaArXiv


A former governor of England's only NHS gender clinic has aired his concerns with the trust, claiming that clinicians are searching for "quick solutions" when working with children and young people in the clinic.
Dr Marcus Evans, a psychoanalyst who resigned from the Tavistock and Portman NHS Foundation Trust last week, told the BBC's Today programme that he was concerned with the gender clinic acting too quickly to give children and young people gender reassignment treatment.
Dr Evans told the Today programme: "There is a lot at stake here as these decisions have far reaching consequences.
"Adolescence and childhood is a time when people are developing socially and biologically – a time when young people are identifying with different groups, and with male and female aspects of themselves.
"There is pressure from the child who is in a distressed state, there is pressure from the family and the peer group and from the pro-trans lobbies – and all of this puts pressure on the clinician who may want to help the individual to resolve their distressed state by going along with a quick solution.
Over the past five years, the number of children referred to the Tavistock Centre has risen from 468 to 2,519 a year – a surge of five times the original number over that time period.
Director of the Gender Identity Development Services (GIDS) at Tavistock told the BBC that the centre has been "under pressure for years" from people who argue the centre should increase the pace of gender reassignment treatment.
"The service has really long assessments over periods of time, with the specific aim of allowing young people to think about what is right for them," she noted.
NHE has contacted the Tavistock Centre for comment.


Terryl Givens did graduate work at Cornell University in Intellectual History and UNC Chapel Hill where he received his PhD in Comparative Literature. He holds the James A. Bostwick chair of English, and is Professor of Literature and Religion at the University of Richmond, where he teaches courses in 19th century studies, and the Bible's influence on western literature. As a commentator on Mormon religion and culture, he has appeared on PBS, NPR, and CNN. Author of ten books, his writing has been praised by the New York Times as "provocative reading," and includes, most recently, When Souls had Wings, a history of the idea of premortal life in western thought, and a two volume history of Mormon theology underway for Oxford University Press.
Boyd Jay Petersen is the Mormon Studies Coordinator at both Utah Valley University, where he also teaches in the English Department, including courses on Mormon literature. He is also an adjunct instructor at Brigham Young University. In this delightful conversation hosted by Dan Wotherspoon, Boyd shares about many aspects of his spiritual journey, centering on a several-decades-long process of coming to be able to testify that the "Church is true." His framings and how he got to them reveal an active mind and open heart, a person who is deeply thoughtful and who takes the challenges of history, human foibles, the call to actively work for social justice, and spiritual and other meaningful experiences seriously. In sharing this journey, he offers a wonderful and powerful analogy about similarities in the ways he makes sense of his relationship with the Church and how he does it in his relationship with his wife. One recurring struggle in Boyd's life is with depression, which he talks about openly in this episode. The discussion also includes anecdotes about Boyd's experiences with Hugh Nibley, his father-in-law (Boyd is married to Zina Nibley Petersen), including some about the processes involved in his writing of the award-winning biography, Hugh Nibley: A Consecrated Life (Greg Kofford Books, 2003).
In the 5th and final part of this multi-part interview with Dr. Richard Bushman, the world's foremost scholar on Joseph Smith and early Mormonism and author of Joseph Smith: Rough Stone Rolling, John Dehlin offers some final thoughts on his time with Brother Bushman, and Dr. Bushman himself provides some final musings on the challenges of dealing with tough Mormon issues. He then concludes with his testimony of Joseph Smith.
In part 4 of this multi-part interview with Dr. Richard Bushman, the world's foremost scholar on Joseph Smith and early Mormonism and author of Joseph Smith: Rough Stone Rolling, Brother Bushman discusses the historicity of the Book of Mormon, and the credibility of the 3 and 8 witnesses to the Book of Mormon.
In part 3 of this multi-part interview with Dr. Richard Bushman, the world's foremost scholar on Joseph Smith and early Mormonism and author of Joseph Smith: Rough Stone Rolling, Brother Bushman discusses Joseph Smith's bringing to light of the Book of Mormon, from angel Moroni's visit, to the obtaining of the plates, to the actual mechanics of the translation process. He also discusses the process of receiving revelation within Mormonism, as a Patriarch in the LDS Church.
In part 2 of this multi-part interview with Dr. Richard Bushman, the world's foremost scholar on Joseph Smith and early Mormonism and author of Joseph Smith: Rough Stone Rolling, we tackle 4 main topics. First, brother Bushman provides a high level review of the major Joseph Smith biographies that preceded Rough Stone Rolling, including Fawn Brodie's "No man knows my history." Next, brother Bushman discusses the art of writing history, and the challenges involved in trying to arrive at "the facts" and "the truth" for both historians, and readers of history. Finally, we discuss in depth the first 2 of our top 10 tough Joseph Smith issues: 1) The multiple and somewhat varying accounts of Joseph Smith's first vision story, and 2) Joseph Smith's involvement in folk magic and treasure digging. The slight audio buzz from the previous interview continues on this one, with an additional static sound that lasts for about 2 minutes at the beginning of the interview.
In part 1 of this multi-part interview, Dr. Richard Bushman, the world's foremost scholar on Joseph Smith and early Mormonism and the author of Joseph Smith: Rough Stone Rolling, discusses his years as a Mormon historian, including his struggle with faith as a Harvard undergraduate, his decision to get a PhD in history, and his experiences with Leonard Arrington, Dialogue and Sunstone. He also discusses the role of candid, honest history within the modern LDS Church.
Jeff and Amy have a unique perspective of what it is like to be fully active, participating members of the church even though they aren't members of the social club. Infertility and the struggles that come with it created a situation where they felt that they were always looking in from the outside. In this interview we explore their experience and the wisdom that comes with many years of knowing what it feels like to be rejected and excluded. These are two great people who share a compelling message.
Dr. Jeremy Timothy MD is a Pediatric Neurologist for Cardon Children's Medical Center in Mesa, Arizona. In this podcast Dr. Timothy shares how his Social Anxiety Disorder presented formative challenges throughout his life, and how bouts of depression and severe anxiety during his Residency almost ended his medical career. Through a combination of good medicine and therapy he emerged as a leader in his specialty, which requires him to treat to injured, mentally disabled, and handicapped children. On a daily basis he is confronted with the incredible tensions of faith and science, suffering and theodicy, and life and death. How he has learned to cope with his own weaknesses and bear the burdens of his patients and their families has shaped his faith in God and his connection to Mormonism.
The theory of Cognitive Dissonance is a well-established concept in the field of psychology that explains why we all experience discomfort and anxiety when we are exposed to new ideas and beliefs or engage in behavior that conflict with our pre-existing views, ideals, and beliefs. I've been extremely interested in producing an episode of A Thoughtful Faith that could explore the concept of Cognitive Dissonance as it relates to an LDS faith crisis / faith transition. When the opportunity came to produce a collaborative episode with the wonderful Nathasha Helfer Parker at the Mormon Mental Health Podcast, this seemed like a really good fit for both audiences. So, I couldn't be more thrilled about sharing my discussion with Natasha Helfer Parker and the amazing Jennifer Finlayson-Fife.
Both Natasha Helfer Parker and Jennifer Finlayson-Fife are active Latter-Day Saints, as well as marriage and family therapists. Natasha and Jennifer each have experience with treating Mormon individuals and couples, and have observed the function of Cognitive Dissonance as it pertains to Mormon culture and ideals. Please visit their respective websites below.
In the first part of this episode we explore the clinical definition of Cognitive Dissonance, including some of the history behind the theory, as well as common examples from day-t0-day life. Afterwards, we transition into how understanding Cognitive Dissonance can be useful in understanding and navigating faith transitions and crises. We hope you enjoy, and please share your thoughts and comments with us below. Thanks again to Natasha and Jennifer for sharing their experience and expertise with me and our audience.
I had the privilege of speaking with Brian Hales about his upcoming three-volume history of Joseph Smith's Polygamy, published by Greg Kofford Books. Brian is a practicing anesthesiologist, author and scholar of Mormon History, with emphasis on Mormon Fundamentalism and Plural Marriage. He is also an active, faithful Latter-Day Saint. In this interview, Brian discusses his research of the historical context, circumstances, and theology that gave rise to Joseph Smith's secret practice of polygamy in the Kirtland and Nauvoo periods. We talk about specific cases and incidents, including Fanny Alger, polyandry, Helen Mar Kimball, Emma Smith's struggle with the Principle, as well as Brian's perspective as a faithful Latter-Day Saint who embraces the theological necessity for the Mormon doctrine of Plural Marriage.
We are incredibly excited to feature this fascinating interview by Daniel Parkinson at Gay Mormon Stories Podcast of John Gustav-Wrathall. John shares his amazing story, including his LDS upbringing, his wrestling with his sexual identity, his journey away from Mormonism, his sexual awakening, and the path that led him back to the LDS Church.
John's story of courage, love, and faith is a wonderful example of the diversity and possibilities of Mormonism's future. Thanks again to Gay Mormon Stories and John Gustav-Wrathall for sharing this interview with our audience.
Bob Rees and I recorded this interview a little while ago. I've been holding on to it, hoping to release it to our audience at the right moment. This past week I re-listened to our conversation and found myself moved and enlightened all over again by Bob's wisdom and insight. Though I don't know what's special about this week, for some reason the timing feels right. I hope you will enjoy Bob's perspective on Mormonism as well as his take on faith crisis and how to successfully engage with the Modern Church as an unconventional Mormon.
Bob Rees is no stranger to the Intellectual Mormon community. He was the second editor of Dialogue, and has been contributing to to progressive Mormon thought and scholarship most of his life. We hope our listeners enjoy Bob's unique approach. Please leave us your comments and feedback below.
DISCLAIMER: This audio was a low-resolution recovery of Bob's interview, and so the quality may be a little spotty. Sorry for the inconvenience.


text:
Watch music video "Hold My Hand"
Youtube Instagram Apple Spotify Facebook-f Twitter Soundcloud Deezer
Music For Sex
Kid Vibes In The Lost World
Flappy Kid Vibes
Most firms have set up a war room to triage their immediate response to the crisis. But the lack of visibility around future demand complicates efforts to restart stalled portfolio companies, recapitalize them and plan for a longer-term recovery. Making smart decisions requires coming to a quick understanding of two things: What impact is Covid-19 having on customer demand right now, and what sort of shape will demand take as the economic downturn.
IV Columns
A faceting effect livens up and interrupts the cubism that sets the morphology of the West system apart from the cliches.
III Columns
Characterised by its suitability for use in a wide range of different contemporary and traditional arrangements, West also features glints of pure creativity, such as the chaise longue.
II Columns
Characterised by its suitability for use in a wide range of contemporary and traditional arrangements, West also features glints of pure creativity, such as the chaise longue, available in pentagonal or hexagonal form and the elements that stand out for their striking backrests in saddle hide.
Text Elements
Three of these curves describe an initial Covid-related spike in demand, and three describe a short-term hit. Where each group begins to diverge, however, is in what's likely to happen to demand over the next several years. Think, for example, of personal computer monitors or other types of goods that were declining pre-pandemic and fall into the "short-term spike, long-term decline" archetype. The story is different for online grocery shopping and collaboration services like Zoom (short-term spike, long-term growth), both of which were growing steadily before the pandemic. Experimentation during the crisis has convinced more and more customers that ordering or meeting online makes sense, pulling forward demand that will likely stick.
Most firms have set up a war room to triage their immediate response to the crisis. But the lack of visibility around future demand complicates efforts to restart stalled portfolio companies, recapitalize them and plan for a longer-term recovery. Making smart decisions requires coming to a quick understanding of two things: What impact is Covid-19 having on customer demand right now, and what sort of shape.
"I cannot give you the formula for success, but I can give you the formula for failure. It is: Try to please everybody." david oswald
Follow Kid Vibes:
Copyright © 2010-2021 Kid Vibes.

redpajama_set_name: RedPajamaCommonCrawl


Vagabond: A. adj. 1. Of persons, etc: Roaming or wandering from place to place without settled habitation or home. OED.
Anyone who wants to meet Jesus, to understand or be with Jesus, must be willing to relocate..
So to my fellow believers I would want to say, are you 'travelling with Jesus' or have you got used to a settled existence, where all your beliefs are neatly settled and nothing much changes in your life from month to month, year to year? Come on, get following.
And to any of my skeptic, unbelieving friends, there's nothing boring about being a follower of Jesus. It's uncomfortable at times, and indeed the lifelong process of conversion is challenging often, but would I swap it for any other way? Nah, i'm glad to be a follower of the vagabond from Galiliee.


F A Barretts Sub Of W1-2 O in Fort Lauderdale is really a wonderful location. The Fort Lauderdale location is amazing. But, if this isn't the community for you, you might like one of the other local communities like Warwick Condo or Sunrise Key or Grandeur that are located here as well.


There are many types of dependency visas available and we can help you through the process of choosing what is applicable to you. Recent changes within the United Kingdom Immigration laws have made it difficult for people who are unfamiliar with the Immigration laws to comply with the requirements needed for the process and applications itself. However, with our help and guidance, we are hoping to make this process easier and more convenient for you.


text:
Mayor Coleman Unveils 2014 City Budget Proposal
Published November 15, 2013 at 2:20 PM EST
Columbus Mayor Michael Coleman today (Friday) outlined his budget plan for 2014. And it's full of black ink. Coleman is head of a financially sound city. It's in better financial shape than most other U-S cities. The proposed $796-million dollar spending blueprint restores most of the budget cuts made during lean years in 2007 and 2008 before the Great Recession. It includes an eight million dollar payment to the city's 'rainy day fund.' Coleman credits passage of a city income tax increase four years ago for the black ink. The income tax is now bringing in more money than projected. Should the tax be rolled back? "No, I've been the mayor through two major recessions," says Coleman. "Overnight, things can change and I've seen that happen. We've had that experience in the city of Columbus, overnight." Coleman cited the recent federal government shutdown as one reason to keep the income tax at 2 and half percent. He says the city has added about 100-thousand people during the last decade while the number of city workers has been reduced by 11 percent. Instead Coleman proposes re-opening all recreation centers full time beginning in April at a cost of $726,000. He calls the rec centers, "points of light." He 'll also add $355,000 for park maintenance. City Council President Andrew Ginther welcomed the mayor's proposal. He says this is not the time to rollback the city income tax. "But now is the time to be restoring services that were cut. That's why we're excited about the rec centers, all rec centers being open full time again." says Ginther. "And, I think we're going to continue to look to see what needs there are in health and safety.to make sure we're restoring services and adding them in critical areas that are going to help neighborhoods thrive." Along those lines, council will be asked to approve the hiring of eight new code enforcement officers to boost the city's fight against vacant and abandoned houses in city neighborhoods. The mayor also wants council to approve stiffer penalties for what he called "irresponsible landlords." Mayor Coleman also proposes the creation of an "education fund" within the city budget. "We have 33,000 children living in Columbus City school district attending "D" or "F" schools. This entire community must continue to fight for these kids," says Coleman. The proposal comes two weeks after school district voters rejected a proposed levy-bond issue to fund a package of school reforms developed by a commission he appointed. The "education fund" will be targeted at what he calls the school's most critical needs. "We will allocate $7.5 million dollars in 2014 for an education fund for educational priorities. We will however, take time to identify areas of greatest economic impact," Coleman adds. Coleman says the city "education fund" will be used to attract more money from the private sector, state and federal governments, foundations, and from the school district. The mayor's budget now goes to City Council for possible changes.
Newscolumbus mayor michael coleman; budget proposal


A: I have always loved being out on the ocean, and was fascinated by the adaptations that animals, (especially mammals, that breath air just like us) have that allow them to live in a totally aquatic environment. We would never survive there without thing like scuba or submarines, but they not only survive, they thrive!
A: In high school I was part of my school's Envirothon team. Envirothon is an environmental competition where students learn about and compete in challenges in different aspects of environmental science (soils, aquatics, forestry, wildlife, and a special current event that changes each year). Through Envirothon I learned firsthand many of the challenges of making science accessible to the public, and the challenges of integrating science into policy and management. The lessons I learned by doing Envirothon really helped shape way I think about science.
I was always interested in marine science, but in high school, I also became really interested in wetland ecology and forestry. I thought I wanted to pursue an undergraduate degree in marine biology, however, I was encouraged to get a basic biology degree instead. I was told that it would be better to start with a broad undergraduate degree; I could always narrow my field of study later on through a master's degree or PhD. This is some of the best advice I've ever gotten. As an undergraduate I got to take classes in microbiology, mammology, ornithlogy, plant ecology, environmental science, veterinary medicine and more.
Although I went to a landlocked college, I had the chance to take marine biology classes by studying abroad. I spent the spring semester of my junior year of college in Baja California, Mexico, where I took classes in coastal ecology, marine resource management, and studied the effects of whale watch tourism on gray whales. While I was in Mexico I realized that I wanted to go on to graduate school and pursue a career in marine biology. I am very grateful for the strong biology background that I received in at UVM, however, because it helped to make me a well rounded scientist.
A: I am studying the effects of bird predation on juvenile salmon in two central California watersheds. Basically, we are trying to figure out how many fish the birds are eating! I find it interesting because it pulls together several of my interests: ecology, wetlands, marine birds, and fisheries management. The project is grounded in good, basic science, and also will provide useful information for management purposes.