Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs

Introduction

Our main goal in this paper is to describe and establish the iteration-complexity of a quadratic penalty accelerated inexact proximal point (QP-AIPP) method for solving the linearly constrained nonconvex composite minimization problem

where $A\in\Re^{l\times n}$, $b\in\Re^{l}$, $h:\Re^{n}\to(-\infty,\infty]$ is a proper lower-semicontinuous convex function and $f$ is a real-valued differentiable (possibly nonconvex) function whose gradient is $L_{f}$-Lipschitz continuous on ${\mbox{\rm dom\,}}h$. For given tolerances $\hat{\rho}>0$ and $\hat{\eta}>0$, the main result of this paper shows that the QP-AIPP method, started from any point in ${\mbox{\rm dom\,}}h$ (but not necessarily satisfying $Az=b$), obtains a triple $(\hat{z},\hat{v},\hat{p})$ satisfying

in at most ${\cal O}(\hat{\rho}^{-2}\hat{\eta}^{-1})$ accelerated composite gradient (ACG) iterations. It is worth noting that this result is obtained under the mild assumption that the optimal value of (1) is finite and hence assumes neither that ${\mbox{\rm dom\,}}h$ is bounded nor that (1) has an optimal solution.

The QP-AIPP method is based on solving penalized subproblems of the form

for an increasing sequence of positive penalty parameters $c$. These subproblems in turn are approximately solved so as to satisfy the first two conditions in (2) and the QP-AIPP method terminates when $c$ is large enough so as to guarantee that the third condition in (2) also hold. Moreover, each subproblem in turn is approximately solved by an accelerated inexact proximal point (AIPP) method which solves a sequence of prox subproblems of the form

where $z_{k-1}$ is the previous iterate and the next one, namely $z_{k}$, is a suitable approximate solution of (4). Choosing $\lambda$ sufficiently small ensures that the objective function of (4) is a convex composite optimization which is approximately solved by an ACG method.

More generally, the AIPP method mentioned above solves problems of the form

where $h$ is as above and $g$ is a differentiable function whose gradient is $M$-Lipschitz continuous on ${\mbox{\rm dom\,}}h$ and whose lower curvature is bounded below on ${\mbox{\rm dom\,}}h$ by some constant $m\in(0,M]$, i.e.,

Note that the penalized subproblem (3) is a special case of (5) with $g(z)=f(z)+(c/2)\|Az-b\|^{2}$, and hence $m=L_{f}$ and $M=L_{f}+c\|A\|^{2}$. It is well-known that the composite gradient method finds a $\rho$-solution of (5), i.e., a pair $(\bar{z},\bar{v})\in{\mbox{\rm dom\,}}h\times\Re^{n}$ such that $\bar{v}\in\nabla f(\bar{z})+\partial h(\bar{z})$ and $\|\bar{v}\|\leq\rho$, in at most ${\cal O}(M(\phi(z_{0})-\phi_{*})/\rho^{2})$ composite-type iterations where $z_{0}$ is the initial point. On the other hand, the AIPP method finds such solution in at most

composite type-iterations where $d_{0}$ denotes the distance of $z_{0}$ to the set of optimal solutions of (5). Hence, its complexity is better than that for the composite gradient method by a factor of $\sqrt{M/m}$. The main advantage of the AIPP method is that its iteration-complexity bound has a lower dependence on $M$, i.e., it is ${\cal O}(\sqrt{M})$ instead of the ${\cal O}(M)$-dependence of the composite gradient method. Hence, the use of the AIPP method instead of the composite gradient method to solve (4) (whose associated $M={\cal O}(c)$) in the scheme outlined above is both theoretically and computationally appealing.

Related works. Under the assumption that domain of $\phi$ is bounded, presents an ACG method applied directly to (5) which obtains a $\rho$-approximate solution of (5) in

where $D_{h}$ denotes the diameter of the domain of $h$. Motivated by , other papers have proposed ACG methods for solving (5) under different assumptions on the functions $g$ and $h$ (see for example ). In particular, their analyses exploit the lower curvature $m$ and the work , which assumes $h=0$, establishes a complexity which depends on $\sqrt{M}\log M$ instead of $M$ as in . As in the latter work, our AIPP method also uses the idea of solving a sequence of convex proximal subproblems by an ACG method, but solves them in a more relaxed manner and, as a result, achieves the complexity bound (6) which improves the one in by a factor of $\log(M/\rho)$. It should be noted that the second complexity bound in (6) in terms of $d_{0}$ is new in the context of the composite nonconvex problem (5) and follows as a special case of a more general bound, namely (61), which actually unifies both bounds in (6). Moreover, in contrast to the analysis of , ours does not assume that $D_{h}$ is finite. Also, inexact proximal point methods and HPE variants of the ones studied in for solving convex-concave saddle point problems and monotone variational inequalities, which inexactly solve a sequence of proximal suproblems by means of an ACG variant, were previously proposed by . The behavior of an accelerated gradient method near saddle points of unconstrained instances of (5) (i.e., with $h=0$) is studied in .

Finally, complexity analysis of first-order quadratic penalty methods for solving special convex instances of (1) where $h$ is an indicator function was first studied in and further analyzed in . Papers study the iteration-complexity of first-order augmented Lagrangian methods for solving the latter class of convex problems. The authors are not aware of earlier papers dealing with complexity analysis of quadratic penalty methods for solving nonconvex constrained optimization problems. However, studies the complexity of a proximal augmented Lagrangian method for solving nonconvex instances of (1) under the very strong assumption that $\nabla f$ is Lipschitz continuous everywhere and $h=0$.

Organization of the paper. Subsection 1.1 contains basic definitions and notation used in the paper. Section 2 is divided into two subsections. The first one introduces the composite nonconvex optimization problem and discusses some approximate solutions criteria. The second subsection is devoted to the study of a general inexact proximal point framework to solve nonconvex optimization problems. In this subsection, we also show that a composite gradient method can be seen as an instance of the latter framework. Section 3 is divided into two subsections. The first one reviews an ACG method and its properties. Subsection 3.2 presents the AIPP method and its iteration-complexity analysis. Section 4 states and analyzes the QP-AIPP method for solving linearly constrained nonconvex composite optimization problems. Section 5 presents computational results. Section 6 gives some concluding remarks. Finally, the appendix gives the proofs of some technical results needed in our presentation.

This subsection provides some basic definitions and notation used in this paper.

The set of real numbers is denoted by $\Re$. The set of non-negative real numbers and the set of positive real numbers are denoted by $\Re_{+}$ and $\Re_{++}$, respectively. We let $\Re^{2}_{++}:=\Re_{++}\times\Re_{++}$. Let $\Re^{n}$ denote the standard $n$-dimensional Euclidean space with inner product and norm denoted by $\left\langle\cdot,\cdot\right\rangle$ and $\|\cdot\|$, respectively. For $t>0$, define $\log^{+}_{1}(t):=\max\{\log t,1\}$. The diameter of a set $D\subset\Re^{n}$ is defined as $\sup\{\|z-z^{\prime}\|:z,z^{\prime}\in D\}$.

Let $\psi:\Re^{n}\rightarrow(-\infty,+\infty]$ be given. The effective domain of $\psi$ is denoted by ${\mbox{\rm dom\,}}\psi:=\{x\in\Re^{n}:\psi(x)<\infty\}$ and $\psi$ is proper if ${\mbox{\rm dom\,}}\psi\neq\emptyset$. Moreover, a proper function $\psi:\Re^{n}\rightarrow(-\infty,+\infty]$ is $\mu$-strongly convex for some $\mu\geq 0$ if

Also, for $\varepsilon\geq 0$, its $\varepsilon$-subdifferential at $z\in{\mbox{\rm dom\,}}\psi$ is denoted by

The subdifferential of $\psi$ at $z\in{\mbox{\rm dom\,}}\psi$, denoted by $\partial\psi(z)$, corresponds to $\partial_{0}\psi(z)$. The set of all proper lower semi-continuous convex functions $\psi:\Re^{n}\rightarrow(-\infty,+\infty]$ is denoted by $\overline{\mbox{\rm Conv}}\,(\Re^{n})$.

The proof of the following result can be found in [13, Proposition 4.2.2].

Let $\psi:\Re^{n}\rightarrow(-\infty,+\infty]$, $z,\bar{z}\in{\mbox{\rm dom\,}}\psi$ and $v\in\Re^{n}$ be given and assume that $v\in\partial\psi(z)$. Then, $v\in\partial_{\varepsilon}\psi(\bar{z})$ where $\varepsilon=\psi(\bar{z})-\psi(z)-\langle v,\bar{z}-z\rangle\geq 0.$

Inexact proximal point method for nonconvex optimization

This section contains two subsections. The first one states the composite nonconvex optimization (CNO) problem and discusses some notions of approximate solutions. The second subsection proposes and analyzes a general framework for solving nonconvex optimization problems and shows under very mild conditions that the composite gradient method is an instance of the general framework.

This subsection describes the CNO problem which will be the main subject of our analysis in Subsection 3.2. It also describes different notions of approximate solutions for the CNO problem and discusses their relationship.

The CNO problem we are interested in is (5) where the following conditions are assumed to hold:

$h\in\overline{\mbox{\rm Conv}}\,(\Re^{n})$;

$g$ is a differentiable function on ${\mbox{\rm dom\,}}h$ which, for some $M\geq m>0$, satisfies

We now make a few remarks about the above assumptions. First, if $\nabla g$ is assumed to be $M$-Lipschitz continuous, then (10) holds with $m=M$. However, our interest is in the case where $0<m\ll M$ since this case naturally arises in the context of penalty methods for solving linearly constrained composite nonconvex optimization problems as will be seen in Section 4. Second, it is well-known that a necessary condition for $z^{*}\in{\mbox{\rm dom\,}}h$ to be a local minimum of (5) is that $z^{*}$ be a stationary point of $g+h$, i.e., $0\in\nabla g(z^{*})+\partial h(z^{*})$.

The latter inclusion motivates the following notion of approximate solution for problem (5): for a given tolerance $\hat{\rho}>0$, a pair $(\hat{z},\hat{v})$ is called a $\hat{\rho}$-approximate solution of (5) if

Another notion of approximate solution that naturally arises in our analysis of the general framework of Subsection 2.2 is as follows. For a given tolerance pair $(\bar{\rho},\bar{\varepsilon})\in\Re^{2}_{++}$, a quintuple $(\lambda,z^{-},z,w,\varepsilon)\in\Re_{++}\times\Re^{n}\times\Re^{n}\times\Re^{n}\times\Re_{+}$ is called a $(\bar{\rho},\bar{\varepsilon})$-prox-approximate solution of (5) if

Note that the first definition of approximate solution above depends on the composite structure $(g,h)$ of $\phi$ but the second one does not.

The next proposition, whose proof is presented in Appendix A, shows how an approximate solution as in (11) can be obtained from a prox-approximate solution by performing a composite gradient step.

Let $h\in\overline{\mbox{\rm Conv}}\,(\Re^{n})$ and $g$ be a differentiable function on ${\mbox{\rm dom\,}}h$ whose gradient satisfies the second inequality in (10). Let $(\bar{\rho},\bar{\varepsilon})\in\Re^{2}_{++}$ and a $(\bar{\rho},\bar{\varepsilon})$-prox-approximate solution $(\lambda,z^{-},z,w,\varepsilon)$ be given and define

$q_{g}\in\nabla g(z)+\partial h(z_{g})$ and

$\delta_{g}\geq 0$, $q_{g}\in\nabla g(z)+\partial_{\delta_{g}}h(z)$ and

if $\nabla g$ is $M$-Lipschitz continuous on ${\mbox{\rm dom\,}}h$, then

Proposition 2.1 shows that a prox-approximate solution yields three possible ways of measuring the quality of an approximate solution of (5). Note that the ones described in (a) and (b) do not assume $\nabla g$ to be Lipschitz continuous while the one in (c) does. This paper only derives complexity results with respect to prox-approximate solutions and approximate solutions as in (c) but we remark that complexity results for the ones in (a) or (b) can also be obtained. Finally, we note that Lemma A.3 in Appendix A provides an alternative way of constructing approximate solutions as in (a), (b) or (c) from a given prox-approximate solution.

2 A general inexact proximal point framework

This subsection introduces a general inexact proximal point (GIPP) framework for solving the CNO problem (5).

Although our main goal is to use the GIPP framework in the context of the CNO problem, we will describe it in the context of the following more general problem

where $\phi:\Re^{n}\to(-\infty,\infty]$ is a proper lower semi-continuous function, and $\phi_{*}>-\infty$.

We now state the GIPP framework for computing prox-approximate solutions of (17).

Let $\sigma\in(0,1)$ and $z_{0}\in{\mbox{\rm dom\,}}\phi$ be given, and set $k=1$;

Then, it follows from (18) that the quintuple $(\lambda,\hat{z},z,v,\varepsilon)=(\lambda_{k},z_{k-1},z_{k},v_{k},\varepsilon_{k})$ satisfies the inclusion in (12) for every $k\geq 1$. In what follows, we will derive the iteration complexity for the quintuple $(\lambda_{k},z_{k-1},z_{k},v_{k},\varepsilon_{k})$ to satisfy: i) the first inequality in (12) only, namely, $\|v_{k}+r_{k}\|\leq\bar{\rho}$; and ii) both inequalities in (12), namely, $\|v_{k}+r_{k}\|\leq\bar{\rho}$ and $\varepsilon_{k}\leq\bar{\varepsilon}$, and hence a $(\bar{\rho},\bar{\varepsilon})$-prox-approximate solution of (5).

where $\sigma\in[0,1)$ is a given parameter. Note that if (19) is assumed then $\delta_{k}=0$.

First note that the inclusion in (18) is equivalent to

Setting $z=z_{i-1}$ in the above inequality and using the definition of $\delta_{i}$ given in (21), we obtain

and hence the proof of the second inequality in (22) follows after simple rearrangements. The first inequality in (22) follows immediately from (21).

Using a simple algebraic manipulation, it is easy to see that (19) yields

Now, letting $\theta:=(1-\sigma)/\sigma>0$, recalling definition (9), using (18) and (23), and the fact that $\langle v,v^{\prime}\rangle\leq(\theta/2)\|v\|^{2}+(1/2\theta)\|v^{\prime}\|^{2}$ for all $v,v^{\prime}\in\Re^{n}$, we conclude that

and hence that the conclusion of the lemma holds due to the definition of $\theta$.

Let $z_{0}\in\Re^{n},\sigma\in(0,1)$, and $\lambda\geq 0$ be given and consider the following quantity

where $\phi_{*}$ is as in (17). Clearly, $R(u;\phi,\lambda)\in\Re_{+}$ for all $u\in{\mbox{\rm dom\,}}h$ and $R(\phi;\lambda)\in\Re_{+}$.

for every $k>1$, there exists $i\leq k$ such that

where $\Lambda_{k}$ and $R(\cdot;\cdot)$ are as in (21) and (24), respectively.

(a) The proof of (25) follows immediately from (22) and the fact that (19) is equivalent to $\delta_{k}=0$.

(b) It follows from definitions of $\phi_{*}$ and $R(\cdot;\cdot,\cdot)$ in (17) and (24), respectively, (25) and Lemma 2.4 with $k=1$ that for all $u\in\Re^{n}$,

and hence that (26) holds in view of the definition of $R(\cdot;\cdot)$ in (24).

Proposition 2.6(a) shows that GIPP enjoys the descent property (25) which many frameworks and/or algorithms for solving (17) also share. It is worth noting that, under the assumption that $\phi$ is a KL-function, frameworks and/or algorithms sharing this property have been developed for example in where it is shown that the generated sequence $\{z_{k}\}$ converges to some stationary point of (17) with a well-characterized asymptotic (but not global) convergence rate, as long as $\{z_{k}\}$ has an accumulation point.

The following result, which follows immediately from Proposition 2.6, considers the instances of the GIPP framework in which $\{\lambda_{k}\}$ is constant. For the purpose of stating it, define

Note that $d_{0}<\infty$ if and only if (17) has an optimal solution in which case the above infimum can be replaced by a minimum in view of the first assumption following (17).

for every $k>1$, there exists $i\leq k$ such that

where $R(\cdot;\cdot)$ and $d_{0}$ are as in (24) and (27), respectively;

(a) The proof of the first inequality follows immediately from Proposition 2.6(b) and the fact that $\lambda_{k}=\lambda$ for every $k\geq 1$. Now, note that due to (24), we have $R(\phi;\lambda)\leq R(z_{0};\phi,\lambda)=(1-\sigma)\lambda[\phi(z_{0})-\phi_{*}$] and $R(\phi;\lambda)\leq R(z^{*};\phi,\lambda)=\|z_{0}-z^{*}\|^{2}/2$ for every optimal solution $z^{*}$ of (17). The second inequality now follows from the previous observation and the definition of $d_{0}$ in (27).

(b) This statement follows immediately from the first inequality in (a).

In the above analysis, we have assumed that $\phi$ is quite general. On the other hand, the remaining part of this subsection assumes that $\phi$ has the composite structure as in (5), i.e., $\phi=g+h$ where $g$ and $h$ satisfy conditions (A1)-(A3) of Subsection 2.1.

We now briefly discuss some specific instances of the GIPP framework. Recall that, for given stepsize $\lambda>0$ and initial point $z_{0}\in{\mbox{\rm dom\,}}h$, the composite gradient method for solving the CNO problem (5) computes recursively a sequence $\{z_{k}\}$ given by

The following result, whose proof is given in Appendix B, shows that the composite gradient method with $\lambda$ sufficiently small is a special case of the GIPP framework in which $\lambda_{k}=\lambda$ for all $k$.

Under the assumption that $\lambda<2/M$ and $\nabla g$ is $M$-Lipschitz continuous, it is well-known that the composite gradient method obtains a $\hat{\rho}$-approximate solution in $\mathcal{O}([\phi(z_{0})-\phi_{*}]/(\lambda\hat{\rho}^{2}))$ iterations. On the other hand, under the assumption that $\lambda\leq 1//M$ and $\nabla g$ is $M$-Lipschitz continuous, we can easily see that the above result together with Corollary 2.8(b) imply that the composite gradient method obtains a $\hat{\rho}$-approximate solution in $\mathcal{O}(R(\phi;\lambda)/(\lambda^{2}\hat{\rho}^{2}))$ iterations.

We now make a few general remarks about our discussion in this subsection so far. First, the condition on the stepsize $\lambda$ of Proposition 2.10 forces it to be ${\cal O}(1/M)$ and hence quite small whenever $M\gg m$. Second, Corollary 2.8(b) implies that the larger $\lambda$ is, the smaller the complexity bound (29) becomes. Third, letting $\lambda_{k}=\lambda$ in the GIPP framework for some $\lambda\leq 1/m$ guarantees that the function $\lambda_{k}\phi+\|\cdot-z_{k-1}\|^{2}/2$ which appears in (18) is convex.

and hence that $z_{k}$ is an optimal solution of the prox-subproblem

Accelerated gradient methods

This subsection reviews an ACG variant and its convergence properties for solving the following optimization problem

where the following conditions are assumed to hold

$\psi_{n}:\Re^{n}\rightarrow(-\infty,+\infty]$ is a proper, closed and $\mu$-strongly convex function with $\mu\geq 0$;

The ACG variant () for solving (34) is as follows.

Let a pair of functions $(\psi_{s},\psi_{n})$ as in (34) and initial point $x_{0}\in{\mbox{\rm dom\,}}\psi_{n}$ be given, and set $y_{0}=x_{0}$, $A_{0}=0$, $\Gamma_{0}\equiv 0$ and $j=0$;

Some remarks about the ACG method follow. First, the main core and usually the common way of describing an iteration of the ACG method is as in step 1. Second, the extra sequences $\{u_{j}\}$ and $\{\eta_{j}\}$ computed in step 2 will be used to develop a stopping criterion for the ACG method when the latter is called as a subroutine in the context of the AIPP method stated in Subsection 3.2. Third, the ACG method in which $\mu=0$ is a special case of a slightly more general one studied by Tseng in (see Algorithm 3 of ). The analysis of the general case of the ACG method in which $\mu\geq 0$ was studied in [12, Proposition 2.3].

The next proposition summarizes the basic properties of the ACG method.

Let $\{(A_{j},\Gamma_{j},x_{j},u_{j},\eta_{j})\}$ be the sequence generated by the ACG method applied to (34) where $(\psi_{s},\psi_{n})$ is a given pair of data functions satisfying (B1) and (B2) with $\mu\geq 0$. Then, the following statements hold

for every $j\geq 1$, we have $\Gamma_{j}\leq\psi_{s}$ and

for every solution $x^{*}$ of (34), we have

For the proofs of (a) and (b) see [12, Proposition 2.3].

(c) It follows from the optimality condition for $y_{j}$ and the definition of $u_{j}$ that $u_{j}\in\partial(\Gamma_{j}+\psi_{n})(y_{j})$, for all $j\geq 1$. Hence Proposition 1.1 yields

Then adding the above two identities we obtain

Hence, the inequality in (38) follows from the last inequality, the definition of $y_{j}$ and (35).

The following result essentially analyzes the iteration-complexity to compute the aforementioned triple.

Let $\{(A_{j},x_{j},u_{j},\eta_{j})\}$ be the sequence generated by the ACG method applied to (34) where $(\psi_{s},\psi_{n})$ is a given pair of data functions satisfying (B1) and (B2) with $\mu\geq 0$. Then, for any $\sigma>0$ and index $j$ such that $A_{j}\geq 2(1+\sqrt{\sigma})^{2}/\sigma$, we have

As a consequence, the ACG method obtains a triple $(x,u,\eta)=(x_{j},u_{j},\eta_{j})$ satisfying

in at most $\left\lceil 2\sqrt{2L}(1+\sqrt{\sigma})/\sqrt{\sigma}\right\rceil$ iterations.

Using the triangle inequality for norms, the relation $(a+b)^{2}\leq 2(a^{2}+b^{2})$ for all $a,b\in\Re$, and the inequality in (38), we obtain

where the last inequality is due to $A_{j}\geq 2(1+\sqrt{\sigma})^{2}/\sigma$. On the other hand, the triangle inequality for norms and simple calculations yield

Combining the previous estimates, we obtain

which easily implies (42). Now if $j\geq\left\lceil 2\sqrt{2L}(1+\sqrt{\sigma})/\sqrt{\sigma}\right\rceil$ then it follows from (36) that $A_{j}\geq 2(1+\sqrt{\sigma})^{2}/\sigma$ and hence, due to the first statement of the lemma, (42) holds. The last conclusion combined with the inclusion in (38) prove the last statement of the lemma.

Note that Proposition 3.1 and Lemma 3.3 hold for any $\mu\geq 0$. On the other hand, the next two results hold only for $\mu>0$ and derive some important relations satisfied by two distinct iterates of the ACG method. They will be used later on in Subsection 3.2 to analyze the refinement phase (step 3) of the AIPP method stated there.

Let $\{(A_{j},x_{j},u_{j},\eta_{j})\}$ be generated by the ACG method applied to (34) where $(\psi_{s},\psi_{n})$ is a given pair of data functions satisfying (B1) and (B2) with $\mu>0$. Then,

where $x^{*}$ is the unique solution of (34). As a consequence, for all indices $i,j\geq 1$ such that $A_{i}\mu>1$, we have

First note that condition (B1) combined with (34) imply that $\psi$ is $\mu$-strongly convex. Hence, it follows from (37) that

which are due to the triangle inequality for norms, together with (46) clearly implies (44). The last statement of the lemma follows immediately from (44).

As a consequence of Lemma 3.5, the following result obtains several important relations on certain quantities corresponding to two arbitrary iterates of the ACG method.

Let $\{(A_{j},x_{j},u_{j},\eta_{j})\}$ be generated by the ACG method applied to (34) where $(\psi_{s},\psi_{n})$ is a given pair of data functions satisfying (B1) and (B2) with $\mu>0$. Let $i$ be an index such that $A_{i}\geq\max\{8,9/\mu\}$. Then, for every $j\geq i$, we have

The first inequality in (47) follows from (45) and the assumption that $A_{i}\mu\geq 9$. Now, using the inequality in (38) and the triangle inequality for norms, we easily see that

which, combined with the first inequality in (47), prove the second and the third inequalities in (47). Noting that $A_{i}\geq 8$ by assumption, Lemma 3.3 implies that (42) holds with $\sigma=1$ and $j=i$, and hence that

Using the triangle inequality, the first two inequalities in (47) and relation (49), we conclude that

and that the first inequality in (48) holds. Now, the last inequality in (47), combined with the triangle inequality for norms and the relation $(a+b)^{2}\leq 2(a^{2}+b^{2})$, imply that

Hence, in view of (49), the last inequality in (48) follows.

2 The AIPP method

This subsection introduces and analyzes the AIPP method to compute approximate solutions of the CNO problem (5). The main results of this subsection are Theorem 3.11 and Corollary 3.13 which analyze the iteration-complexity of the AIPP method to obtain approximate solutions of the CNO problem in the sense of (12) and (11), respectively.

Let $z_{0}\in{\mbox{\rm dom\,}}h$, $\sigma\in(0,1)$, a pair $(m,M)$ satisfying (10), a scalar $0<\lambda\leq 1/(2m)$ and a tolerance pair $(\bar{\rho},\bar{\varepsilon})\in\Re^{2}_{++}$ be given, and set $k=1$;

perform at least $\left\lceil 6\sqrt{2\lambda M+1}\right\rceil$ iterations of the ACG method started from $z_{k-1}$ and with

to obtain a triple $(x,u,\eta)\in\Re^{n}\times\Re^{n}\times\Re_{+}$ satisfying

The next proposition summarizes some facts about the AIPP method.

The following statements about the AIPP method hold:

at every outer iteration, the call to the ACG method in step 1 finds a triple $(x,u,\eta)$ satisfying (51) in at most

the AIPP method is a special implementation of the GIPP framework in which $\lambda_{k}=\lambda$ for every $k\geq 1$;

the number of outer iterations performed by the AIPP method is bounded by

where $R(\cdot;\cdot)$ is as defined in (24).

(a) First note that the function $\psi_{s}$ defined in (50) satisfies condition (B2) of Subsection 3.1 with $L=\lambda M+1/2$, in view of (10). Hence, it follows from the last statement of Lemma 3.3 that the ACG method obtains a triple $(x,u,\eta)$ satisfying (51) in at most

inner iterations. Hence, (a) follows from the above conclusion and the fact that the ACG method performs at least $\left\lceil 6\sqrt{2\lambda M+1)}\right\rceil$ inner iterations, in view of step 1.

Noting the stopping criterion (53) and using the last inequality above, the fact that $\mu=1/2$ and $L=\lambda M+1/2$, and the relation that $\log(1+t)\geq t/2$ for all $t\in$, we can easily see that (b) holds.

(d) This statement follows by combining (c), the stopping criterion (52), and Corollary 2.8(b) with $\bar{\rho}$ replaced by $\bar{\rho}/5$.

Next we state one of our main results of this paper which derives the iteration-complexity of the AIPP method to obtain prox-approximate solutions of the CNO problem in the sense of (12). Recall that the AIPP method assumes that $\lambda\leq 1/(2m)$.

Under assumptions (A1)-(A3), the AIPP method terminates with a prox-solution $(\lambda,z^{-},z,w,\varepsilon)$ within

inner iterations where $R(\cdot;\cdot)$ is as defined in (24).

It follows from the second statement following the AIPP method and the definition of $(\lambda,z^{-},z,w,\varepsilon)$ in step 3 that the quintuple $(\lambda,z^{-},z,w,\varepsilon)$ satisfies the inclusion in (12). Now, the bound in (59) follows by multiplying the bounds in Lemma 54(a) and (b), and adding the result to the bound in Lemma 54(d).

Before stating the next result, we make two remarks about the above result. First, even though our main interest is in the case where $m\leq M$ (see assumption (A.2)), bound (59) also holds for the case in which $m>M$. Second, the AIPP version in which $\lambda=1/(2m)$ yields the the best complexity bound under the reasonable assumption that, inside the squared bracket in (59), the first term is larger than the second one.

The following result describes the inner iteration complexity of the AIPP method with $\lambda=1/(2m)$ to compute approximate solutions of (5) in the sense of (11).

Assume that (A1)-(A3) hold and let a tolerance $\hat{\rho}>0$ be given. Also, let $(\lambda,z^{-},z,w,\varepsilon)$ be the output obtained by the AIPP method with inputs $\lambda=1/(2m)$ and $(\bar{\rho},\bar{\varepsilon})$ defined as

inner iterations where $R(\cdot;\cdot)$ is as in (24).

if $\nabla g$ is $M$-Lipschitz continuous, then the pair $(\hat{z},\hat{v})=(z_{g},v_{g})$ computed according to (13) and (16) is a $\hat{\rho}$-approximate solution of (5), i.e., (11) holds.

(a) This statement follows immediately from Theorem 3.11 with $\lambda=1/(2m)$ and $(\bar{\rho},\bar{\varepsilon})$ as in (60) and the fact that $m\leq M$ due to (A2).

(b) First note that Theorem 3.11 implies that the AIPP output $(\lambda,z^{-},z,w,\varepsilon)$ satisfies criterion (12) with $(\bar{\rho},\bar{\varepsilon})$ as in (60). Since (60) also implies that

the conclusion of (b) follows from Proposition 2.1(c) and the fact that $\lambda=1/2m$.

We now make a few remarks about the iteration-complexity bound (61) and its relationship to two other ones obtained in the literature under the reasonable assumption that the term $\mathcal{O}(1/\hat{\rho}^{2})$ in (61) dominates the other one, i.e., bound (61) reduces to

First, using the definition of $R(\phi;\lambda)$, it is easy to see that the above bound is majorized by the one in (6) (see the proof of Corollary 2.8(a)). Second, since the iteration-complexity bound for the composite gradient method with $\lambda=1/M$ is ${\cal O}(M(\phi(z_{0})-\phi_{*})/\hat{\rho}^{2})$ (see the discussion following Proposition 2.10), we conclude that (6), and hence (61), is better than the first bound by a factor of $(M/m)^{1/2}$. Third, bound (6), and hence (61), is also better than the one established in Corollary 2 of for an ACG method applied directly to the nonconvex problem (5), namely (7), by at least a factor of $(M/m)^{1/2}$. Note that the ACG method of assumes that the diameter $D_{h}$ of ${\mbox{\rm dom\,}}h$ is bounded while the AIPP method does not.

The QP-AIPP method

This section presents the QP-AIPP method for obtaining approximate solutions of the linearly constrained nonconvex composite optimization problem (1) in the sense of (2).

Throughout this section, it is assumed that (1) satisfies the following conditions:

$h\in\overline{\mbox{\rm Conv}}\,(\Re^{n})$, $A\neq 0$ and ${\cal F}:=\left\{z\in{\mbox{\rm dom\,}}h:Az=b\right\}\neq\emptyset$;

$f$ is a differentiable function on ${\mbox{\rm dom\,}}h$ and there exist scalars $0<m_{f}\leq L_{f}$ such that for every $u,z\in{\mbox{\rm dom\,}}h$,

there exists $\hat{c}\geq 0$ such that $\hat{\varphi}_{\hat{c}}>-\infty$ where

We make two remarks about conditions (C1)-(C3). First, (C1) and (C3) imply that the optimal value of (1) is finite but not necessarily achieved. Second, (C3) is quite natural in the sense that the penalty approach underlying the QP-AIPP method would not make sense without it. Finally, (62) implies that

and hence that (63) automatically holds with $m_{f}=L_{f}$, i.e., (63) is redundant when $m_{f}=L_{f}$. Our analysis in this section also considers the case in which a scalar $0<m_{f}<M_{f}$ satisfying (63) is known.

Given a tolerance pair $(\hat{\rho},\hat{\eta})\in\Re^{2}_{++}$, a triple $(\hat{z},\hat{v},\hat{p})$ is said to be a $(\hat{\rho},\hat{\eta})$-approximate solution of (1) if it satisfies (2). Clearly, a $(\hat{\rho},\hat{\eta})$-approximate solution $(\hat{z},\hat{v},\hat{p})$ for the case in which $(\hat{\rho},\hat{\eta})=(0,0)$ means that $0=\hat{v}\in\nabla f(\hat{z})+\partial h(\hat{z})+A^{*}\hat{p}$ and $A\hat{z}=b$, and hence that $(\hat{z},\hat{p})$ is a first-order stationary pair of (1).

The QP-AIPP method is essentially a quadratic penalty approach where the AIPP method is applied to the penalty subproblem (64) associated with (1) for a fixed $c>0$ or for $c$ taking values on an increasing sequence $\{c_{k}\}$ converging to infinity. Note that (64) is a particular case of (5) in which

Moreover, we easily see that (63) and (65) imply that $\nabla g_{c}$ satisfies condition (10) with $(m,M)=(m_{f},L_{f}+c\|A\|^{2})$.

Lemmas 4.1 and 4.5 below describe how a $\bar{\rho}$-approximate solution of (64) in the sense of (11) yields a $(\hat{\rho},\hat{\eta})$-approximate solution of (1) whenever $c$ is sufficiently large. Lemma 4.3 introduces an important quantity associated with the penalized problem (64) which plays a fundamental role in expressing the inner iteration complexity of the QP-AIPP method stated below for the case in which ${\mbox{\rm dom\,}}h$ is not necessarily bounded (see Theorem 4.7). It also establishes a few technical inequalities involving this quantity, one of which plays an important role in the proof of Theorem 4.7 and the statement of Lemma 4.5.

Let $(c,\hat{\rho})\in\Re^{2}_{++}$ be given and let $(\hat{z},\hat{v})$ be a $\hat{\rho}$-approximate solution of (64) in the sense of (11) with $g=g_{c}$ where $g_{c}$ is as in (66). Then the triple $(\hat{z},\hat{v},\hat{p})$ where $\hat{p}:=c(A\hat{z}-b)$ satisfies the inclusion and the first inequality in (2).

Since $(\hat{z},\hat{v})$ is a $\hat{\rho}$-approximate solution of (64), we have $\hat{v}\in\nabla g_{c}(\hat{z})+\partial h(\hat{z})$ and $\|\hat{v}\|\leq\hat{\rho}$. Hence the result follows from the definition of $\hat{p}$ and the fact that $\nabla g_{c}(\hat{z})=\nabla g(\hat{z})+A^{*}(c(A\hat{z}-b))=\nabla g(\hat{z})+A^{*}\hat{p}$.

The above result is quite general in the sense that it holds for any $c>0$. We will now show that, by choosing $c$ sufficiently large, we can actually guarantee that $(\hat{z},\hat{v},\hat{p})$ of Lemma 4.1 also satisfies the second inequality in (2) as long as $(\hat{z},\hat{v})$ is generated by an instance of the GIPP framework. We first establish the following technical result.

Moreover, if (1) has an optimal solution $z^{*}$, then

where $\hat{\varphi}_{*}$ denotes the optimum value of (1).

Using (64) and assumption (C3), it easy to see that for every $c\geq\hat{c}$, we have $\hat{\varphi}_{c}\geq\hat{\varphi}_{\hat{c}}>-\infty$ and $\varphi_{c}(u)=\varphi_{\hat{c}}(u)=(f+h)(u)$ for every $u\in{\cal F}$. Hence, the conclusion of the lemma follows immediately from (67) and the definition of $R(\cdot\,;\cdot,\cdot)$ in (24).

We are now ready to describe the feasibility behavior of a GIPP instance applied to (64).

where $R_{\hat{c}}(\cdot)$ is as defined in (67). Then for every $\hat{z}\in\Re^{n}$ such that $\varphi_{c}(\hat{z})\leq\varphi_{c}(z_{1})$, we have

As a consequence, if $c\geq T_{\hat{\eta}}(\lambda_{1})$ then

First note that the definitions of $\varphi_{c}$ and $\hat{\varphi}_{c}$ in (64) imply that for every $c>0$,

Now, let $\hat{z}\in\Re^{n}$ be such that $\varphi_{c}(\hat{z})\leq\varphi_{c}(z_{1})$. Lemma 2.4 with $\phi=\varphi_{c}$ and $k=1$, the previous inequality on $\hat{z}$, and (73) with $u=\hat{z}$, then imply that for every $u\in\mathcal{F}$,

Since $\varphi_{c}(u)=\varphi_{\hat{c}}(u)$ for every $u\in{\cal F}$, it then follows from the above inequality and the definition of $R(\cdot\,;\cdot,\cdot)$ in (24) that

We now make some remarks about the above result. First, it does not assume that ${\cal F}$, and hence ${\mbox{\rm dom\,}}h$, is bounded. Also, it does not even assume that (1) has an optimal solution. Second, it implies that all iterates (excluding the starting one) generated by an instance of the GIPP framework applied to (64) satisfy the feasibility requirement (i.e., the last inequality) in (2) as long as $c$ is sufficiently large, i.e., $c\geq T_{\hat{\eta}}(\lambda_{1})$ where $T_{\hat{\eta}}(\cdot)$ is as in (71). Third, since the quantity $R_{\hat{c}}(\lambda_{1})$, which appears in the definition of $T_{\hat{\eta}}(\lambda_{1})$ in (71), is difficult to estimate, a simple way of choosing a penalty parameter $c$ such that $c\geq T_{\hat{\eta}}(\lambda_{1})$ is not apparent. The QP-AIPP method described below solves instead a sequence of penalized subproblems (64) for increasing values of $c$ (i.e., updated according to $c\leftarrow 2c$). Moreover, despite solving a sequence of penalized subproblems, it is shown that its overall ACG iteration complexity is the same as the one for the ideal method corresponding to solving (64) with $c=T_{\hat{\eta}}(\lambda_{1})$.

We are ready to state the QP-AIPP method.

Let $z_{0}\in{\mbox{\rm dom\,}}h$, $\sigma\in(0,1)$, $L_{f}$ satisfying (65), $m_{f}$ satisfying (63), and a tolerance pair $(\hat{\rho},\hat{\eta})\in\Re^{2}_{++}$ be given, and set

apply the AIPP method with inputs $z_{0}$, $\sigma$, $\lambda$,

and $(\bar{\rho},\bar{\varepsilon})$ as in (60) to find a $(\bar{\rho},\bar{\varepsilon})$-prox approximate solution $(\lambda,z^{-},z,w,\varepsilon)$ of problem (5) (according to (12)) with $g:=g_{c}$ and $g_{c}$ as in (66);

use $(\lambda,z^{-},z,w,\varepsilon)$ to compute $(z_{g},v_{g})$ as in Proposition 2.1 with $g=g_{c}$;

if $\|Az_{g}-b\|>\hat{\eta}$ then set $c=2c$ and go to (1); otherwise, stop and output $(\hat{z},\hat{v},\hat{p})=(z_{g},v_{g},c(Az_{g}-b))$.

Every loop of the QP-AIPP method invokes in its step 1 the AIPP method of Subsection 3.2 to compute a $(\bar{\rho},\bar{\varepsilon})$-prox approximate solution of (5). The latter method in turn uses the ACG method of Subsection 3.1 as a subroutine in its implementation (see step 1 of the AIPP method). For simplicity, we refer to all ACG iterations performed during calls to the ACG method as inner iterations.

We now make a few remarks about the QP-AIPP method. First, it follows from Corollary 3.13(b) that the pair $(z_{g},v_{g})$ is a $\hat{\rho}$-approximate solution of (64) in the sense of (11) with $g=g_{c}$ and $g_{c}$ as in (66). As a consequence, Lemma 4.1 implies that the output $(\hat{z},\hat{v},\hat{p})$ satisfies the inclusion and the first inequality in (2). Second, since $(\lambda,z^{-},z,w,\varepsilon)$ computed at step 1 is an iterate of the AIPP method, which in turn is a special instance of the GIPP framework, and $\phi_{c}(z_{g})\leq\phi_{c}(z)$ due to (91) of Lemma A.1, we conclude from Lemma 4.5 that $\hat{z}=z_{g}$ satisfies (72). Third, since every loop of the QP-AIPP method doubles $c$, the condition $c>T_{\hat{\eta}}(\lambda_{1})$ will be eventualy satisfied. Hence, in view of the previous remark, the $z_{g}$ corresponding to this $c$ will satisfy the feasibility condition $\|Az_{g}-b\|\leq\hat{\rho}$ and the QP-AIPP method will stop in view of its stopping criterion in step 3. Finally, in view of the first and third remarks, we conclude that the QP-AIPP method terminates in step 3 with a triple $(\hat{z},\hat{v},\hat{p})$ satisfying (2).

The next result derives a bound on the overall number of inner iterations of the quadratic penalty AIPP method to obtain an approximate solution of (1) in the sense of (2).

where $R_{\hat{c}}(\lambda)$ is as in (67). Then, the QP-AIPP method outputs a triple $(\hat{z},\hat{v},\hat{p})$ satisfying (2) in a total number of inner iterations bounded by

Let $c_{1}:=\hat{c}+L_{f}/\|A\|^{2}$. Noting the stopping criterion in step 3, using the second remark preceding the theorem and the fact that (74) implies $c=c_{l}:=2^{l-1}c_{1}$ at the $l$-th loop of the QP-AIPP method, we conclude that the QP-AIPP method stops in at most $\bar{l}$ loops where $\bar{l}$ is the first index $l\geq 1$ such that $2^{l-1}c_{1}>T_{\hat{\eta}}.$ We claim that

Before establishing the above claim, we will use it to show that the conclusion of the theorem holds. Indeed, first note that the definition of $c_{1}$ and the above definition of $c_{l}$ imply that $c_{l}\geq c_{1}\geq\hat{c}$ for every $l\geq 1$. Hence, it follows from the second inequality in (69) with $(c,\hat{\lambda})=(c_{l},\lambda)$ that $R_{c_{l}}(\lambda)\leq R_{\hat{c}}(\lambda)$. Since (24) and (67) easily imply that $R(\varphi_{c_{l}},\lambda)\leq R_{c_{l}}(\lambda)$, we then conclude that $R(\varphi_{c_{l}},\lambda)\leq R_{\hat{c}}(\lambda)$. The latter conclusion, (78) and Corollary 3.13(a) with $\phi=\varphi_{c_{l}}$ and $(m,M)$ as in (75) then imply that the number of inner iterations during the $l$-th loop of the QP-AIPP method is bounded by

Hence, the total number of inner iterations performed by the QP-AIPP method is bounded by the sum of the previous bound over $l=1,\ldots,\bar{l}$ which is equal to (77) in view of (78).

We will now show that (78) holds. If $\bar{l}=1$ then it follows from the definitions of $\Theta$ in (76) and $c_{1}$ in the beginning of the proof that

and hence (78) holds. Consider now the case in which $\bar{l}>1$. Using the fact that $c_{l}=2^{l-1}c_{1}$ together with the first equality in (80), we have that $c_{l}\|A\|^{2}/m_{f}\geq c_{1}|A\|^{2}/m_{f}\geq L_{f}/m_{f}$ and hence

Using the definition of $\bar{l}$ and the fact that $\bar{l}>1$, we easily see that $2^{\bar{l}-1}c_{1}\leq 2T_{\hat{\eta}}$ and hence that $(\sqrt{2})^{\bar{l}}\leq 2(T_{\hat{\eta}}/c_{1})^{1/2}$. The last inequality together with (81) and the definition of $\Theta$ in (76) then imply (78).

Before ending this section, we make three remarks about Theorem 4.7. First, (70) implies the quantity $R_{\hat{c}}(\lambda)$ admits the upper bound

where $\hat{d}_{0}:=\left\{\|z_{0}-z_{*}\|:z_{*}\text{ is an optimal solution of \eqref{eq:probintro}}\right\}$. Second, in terms of the tolerance pair $(\hat{\rho},\hat{\eta})$ only, the iteration-complexity bound (77) reduces to $\mathcal{O}\left(1/(\hat{\rho}^{2}\hat{\eta})\right)$ for an arbitrary initial point $z_{0}\in{\mbox{\rm dom\,}}h$. Third, the iteration-complexity bound (77) is almost the same as the one corresponding to the case in which $T_{\hat{\eta}}=T_{\hat{\eta}}(\lambda)$ as in (71) is known and the penalty parameter is set to $c=T_{\hat{\eta}}$, namely,

which follows as a consequence of Corollary 3.13 with $M$ as in (75). Note that the two bounds differ only in that the quantity $R_{c}(\lambda)$, which appears in the above bound, may be strictly smaller than the quantity $R_{\hat{c}}(\lambda)$ in (77) (see (69)).

Computational Results

The goal of this section is to present a few computational results that show the performance of the AIPP method, which would consequently assess the performance of the QP-AIPP method. In particular, while the experiments are limited in the sense that they do not directly test the actual behavior of the QP-AIPP method, they can be considered as examples of subproblems in the execution of the penalty-based method. The AIPP method is benchmarked against two other nonconvex optimization methods, namely the projected gradient (PG) method and the accelerated gradient (AG) method recently proposed and analyzed in .

Several instances of the quadratic programming (QP) problem

were considered where $A\in\Re^{l\times n}$, $B\in\Re^{n\times n}$, $D\in\Re^{n\times n}$ is a diagonal matrix, $b\in\Re^{l\times 1}$, $(\xi,\tau)\in\Re^{2}_{++}$, and $\Delta_{n}:=\left\{z\in\Re^{n}:\sum_{i=1}^{n}z_{i}=1,\;\;z_{i}\geq 0\right\}$. More specifically, we set the dimensions to be $(l,n)=(20,300)$. We also generated the entries of $A,B$ and $b$ by sampling from the uniform distribution ${\cal U}$ and the diagonal entries of $D$ by sampling from the discrete uniform distribution ${\cal U}\{1,1000\}$. By appropriately choosing the scalars $\xi$ and $\tau$, the instance corresponding to a pair of parameters $(M,m)\in\Re^{2}_{++}$ was generated so that $M=\lambda_{\max}(\nabla^{2}g)$ and $-m=\lambda_{\min}(\nabla^{2}g)$ where $\lambda_{\max}(\nabla^{2}g)$ and $\lambda_{\min}(\nabla^{2}g)$ denote the largest and smallest eigenvalues of the Hessian of $g$ respectively. The parameters $(\lambda,\sigma)$ were set to be $(0.9/m,0.3)$. The AIPP, PG, and AG methods were implemented in MATLAB 2016a scripts and were run on Linux 64-bit machines each containing Xeon E5520 processors and at least 8 GB of memory.

All three methods use the centroid of the set $\Delta_{n}$ as the initial starting point $z_{0}$ and were run until a pair $(z,v)$ was generated satisfying the condition

From the tables, we can conclude that if the curvature ratio $M/m$ is sufficiently large then the AIPP method performs fewer iterations than the PG and the AG methods. This indicates that the QP-AIPP, which is based on the AIPP method, might be a promising approach towards solving linearly constrained nonconvex optimization problems. This is due to the fact that the curvature ratios of the penalty subproblems grow substantially as $c$ increases and, as a result, AIPP can efficiently solve them. On the other hand, AIPP does not do well on instances whose associated curvature ratio is small. However, preliminary computational experiments seem to indicate that a variant of AIPP can also efficiently solve instances with small curvature ratios by significantly choosing $\lambda$ much larger than $0.9/m$. Since this situation is not covered by the theory presented in this paper, we are not reporting these results in this paper, opting instead to leave this preliminary investigation for a future work.

Concluding remarks

Paper proposed a linearized version of the augmented Lagrangian method to solve (1) but assumes the strong condition (among a few others) that $h=0$, which most important problems arising in applications do not satisfy. To circumvent this technical issue, proposed a penalty ADDM approach which introduces an artificial variable $y$ in (1) and then penalizes $y$ to obtain the penalized problem

which is then solved by a two-block ADMM. Since (84) satisfies the assumption that its $y$-block objective function component has Lipschitz continuous gradient everywhere and its $y$-block coefficient matrix is the identity, an iteration-complexity of the two-block ADDM for solving (84), and hence (1), can be established. More specifically, it has been shown in Remark 4.3 of that the overall number of composite gradient steps performed by the aforementioned two-block ADMM penalty scheme to obtain a triple $(\hat{z},\hat{v},\hat{p})$ satisfying (2) is bounded by ${\cal O}(\hat{\rho}^{-6})$ under the assumptions that $\hat{\eta}=\hat{\rho}$, the level sets of $f+h$ are bounded and the initial triple $(z_{0},y_{0},p_{0})$ satisfies $(y_{0},p_{0})=(0,0)$, $Az_{0}=b$ and $z_{0}\in{\mbox{\rm dom\,}}h$.

Note that the last complexity bound is derived under a boundedness assumption and is worse than the one obtained in this paper for the QP-AIPP method, namely ${\cal O}(\hat{\rho}^{-2}\hat{\eta}^{-1})$, without any boundedness assumption. Moreover, in contrast to the complexity of the QP-AIPP which is established for an arbitrary infeasible point $z_{0}\in{\mbox{\rm dom\,}}h$, the complexity bound of the aforementioned two-block ADMM penalty scheme assumes that $z_{0}$ is feasible for (1). In fact, as far as we know, QP-AIPP is the first method for solving (1) from an infeasible starting point with a guaranteed complexity bound under the general assumptions considered in this paper.

Appendix A Proof of Proposition 2.1

We first state two technical lemmas before giving the proof of Proposition 2.1.

Assume that $h\in\overline{\mbox{\rm Conv}}\,(\Re^{n})$, $z\in{\mbox{\rm dom\,}}h$ and $f$ is a differentiable function on ${\mbox{\rm dom\,}}h$ which, for some $L>0$, satisfies

We first show that (89) holds. The optimality condition for (86) and the definition of $q_{f}$ in (87) immediately yield the first inclusion in (89). Hence, it follows from Proposition 1.1 and the definition of $\delta_{f}$ in (88) that the second inclusion and the inequality in (89) also hold.

We now show that (90) holds. Clearly, the second inclusion in (89) implies that $(q_{f},\delta_{f})$ is feasible to (90). Assume now that $(r,\varepsilon)$ satisfies $r\in\nabla f(z)+\partial_{\varepsilon}h(z)$, or equivalently,

Using the above inequality with $u=z_{f}$ and the definitions of $q_{f}$ and $\delta_{f}$ given in (87) and (88), respectively, we then conclude that

Assume that $h\in\overline{\mbox{\rm Conv}}\,(\Re^{n})$, $z\in{\mbox{\rm dom\,}}h$ and $g$ is a differentiable function on ${\mbox{\rm dom\,}}h$ which, for some $M>0$, satisfies (85) with $(f,L)$ replaced by $(g,M)$. Let $\lambda>0$, $(z^{-},z,w,\varepsilon)\in\Re^{n}\times{\mbox{\rm dom\,}}h\times\Re^{n}\times\Re_{+}$ and $\rho>0$ be such that

where the quantities $z(z;f)$, $q(z;f)$ and $\delta(z;f)$ are defined in (86), (87) and (88), respectively. Then, the following statements hold:

if $\nabla g$ is $M$-Lipschitz continuous, then the pair $(z_{f},v_{f})$ where

(a) First note that the pair $(f,L)$ defined in (93) satisfies (85) and that $\lambda$ and $(z^{-},z,w,\varepsilon)$ satisfy the inclusion in (92) if and only if $0\in\partial_{\varepsilon}(f+h)(z),$ or equivalently, $(f+h)(u)\geq(f+h)(z)-\varepsilon$ for every $u$. In particular, the latter inequality with $u=z_{f}$ implies that $(f+h)(z)-(f+h)(z_{f})\leq\varepsilon.$ Hence, combining the last inequality, Lemma A.1 with $(f,L)$ as in (93), and the definition of $v$ given in (94), we conclude that the relations in (95) hold and

Now, the inequality in (92), definition of $v$ in (94) and the triangle inequality for norms imply that $\|v\|\leq\rho+\|q_{f}\|$, and hence, in view of (99), that