Convergence analysis of primal-dual augmented Lagrangian methods and duality theory

M.V. Dolgopolik¹¹1Institute for Problems in Mechanical Engineering of the Russian Academy of Sciences, Saint Petersburg, Russia

Abstract

We develop a unified theory of augmented Lagrangians for nonconvex optimization problems that encompasses both duality theory and convergence analysis of primal-dual augmented Lagrangian methods in the infinite dimensional setting. Our goal is to present many well-known concepts and results related to augmented Lagrangians in a unified manner and bridge a gap between existing convergence analysis of primal-dual augmented Lagrangian methods and abstract duality theory. Within our theory we specifically emphasize the role of various fundamental duality concepts (such as duality gap, optimal dual solutions, global saddle points, etc.) in convergence analysis of augmented Lagrangians methods and underline interconnections between all these concepts and convergence of primal and dual sequences generated by such methods. In particular, we prove that the zero duality gap property is a necessary condition for the boundedness of the primal sequence, while the existence of an optimal dual solution is a necessary condition for the boundedness of the sequences of multipliers and penalty parameters, irrespective of the way in which the multipliers and the penalty parameter are updated. Our theoretical results are applicable to many different augmented Lagrangians for various types of cone constrained optimization problems, including Rockafellar-Wets’ augmented Lagrangian, (penalized) exponential/hyperbolic-type augmented Lagrangians, modified barrier functions, etc.

1 Introduction

Augmented Lagrangians play a fundamental role in optimization and many other closely related fields [2, 25, 34, 5, 19], and there is a vast literature on various aspects of augmented Lagrangian theory and corresponding methods. A wide range of topics that is studied within the more theoretically oriented part of the literature includes such important problems as analysis of the zero duality gap property [31, 32, 17, 39, 86, 72, 79], exact penalty representation [31, 32, 86, 9, 72, 87, 85, 12, 24], existence of global saddle points [68, 76, 77, 84, 43, 70, 22], existence of augmented Lagrange multipliers [62, 61, 88, 18, 21], etc.

In turn, more practically oriented papers are usually devoted to convergence analysis of primal-dual augmented Lagrangian methods and do not utilise any theoretical concepts or results from duality theory, except for the zero duality gap property [8, 10, 1, 16, 14]. Very few attempts have been made to connect convergence analysis of such methods with fundamental results from duality theory. Paper [7], in which the equivalence between primal convergence and differentiability of the augmented dual function for the sharp Lagrangian for equality constrained problems was established, is perhaps the most notable among them.

In addition, papers dealing with convergence analysis of primal-dual augmented Lagrangian methods typically consider only one particular augmented Lagrangian for one particular type of constraints. As a consequence of that, very similar results have to be repeated multiple types in different settings (cf. convergence analysis of augmented Lagrangian methods based on the Hestenes-Powell-Rockafellar augmented Lagrangian for mathematical programming problems [5], nonconvex problems with second order cone constraints [40, 41], nonconvex semidefinite programming problems [65, 45, 74], as well as similar convergence analysis of augmented Lagrangian methods based on the exponential-type augmented Lagrangian/modified barrier function for nonconvex problems with second order cone constraints [81] and nonconvex semidefinite programming problems [38]). Some attempts have been made to unify convergence analysis of a number of primal-dual augmented Lagrangian methods [44, 42, 71], but only for finite dimensional inequality constrained optimization problems.

Thus, there are two fundamental challenges within the theory of augmented Lagrangians and corresponding optimization methods. The first one is connected with a noticeable gap that exists between more theoretically oriented results dealing with duality theory and more practically oriented results on convergence analysis of primal-dual methods. Often, the duality theory plays little to no role in convergence analysis of primal-dual methods, and theoretical results from this theory are almost never utilised to help better understand convergence of augmented Lagrangian methods. The second challenge is connected with unification of numerous similar results on duality theory and augmented Lagrangian methods that are scattered in the literature.

The main goal of this article is to present a general theory of augmented Lagrangians for nonconvex cone constrained optimization problems in the infinite dimensional setting that encompasses both fundamental theoretical concepts from duality theory and convergence analysis of primal-dual augmented Lagrangian methods, and also highlights interconnections between them, thus at least partially solving the two aforementioned challenges.

Our other aim is to correct for the bias that exists in the literature on augmented Lagrangians, in which a disproportionate number of papers is devoted to analysis of Rockafellar-Wets’s augmented Lagrangian [58, Section 11.K] and corresponding numerical methods, while very little attention is paid to other classes of augmented Lagrangians. In particular, to the best of the author’s knowledge, many concepts (such as exact penalty map [12], exact penalty representation, and augmented Lagrange multipliers) have been introduced and studied exclusively in the context of Rockafellar-Wets’ augmented Lagrangian. Our aim is to show that these concepts can be defined and be useful in a much more broad setting and to demonstrate that many results from duality theory and convergence analysis of primal-dual methods can be proved for Rockafellar-Wets’ augmented Lagrangian and many other augmented Lagrangians in a unified way.

To achieve our goals, we adopt an axiomatic augmented Lagrangian setting developed by the author in [22] and inspired by [39]. Within this setting, one defines an abstract augmented Lagrangian without specifying its structure, while all theoretical results are proved using a set of axioms (basic assumptions). To demonstrate the broad applicability of this approach, we present many particular examples of well-known augmented Lagrangians and prove that they satisfy these axioms.

We also develop a general duality theory for augmented Lagrangians that compliments the results of the author’s earlier papers [22, 23] and, in particular, provide simple necessary and sufficient conditions for the zero duality gap property to hold true, from which many existing results on this property can be easily derived. Finally, we present a general convergence analysis for a model augmented Lagrangian method with arbitrary rules for updating multipliers and penalty parameter. Under some natural assumptions, that are satisfied in many particular cases, we study primal and dual convergence of this method, making specific emphasis on the role of various fundamental concepts from duality theory in convergence analysis of augmented Lagrangian methods. In particular, we points out direct connections between primal convergence and the zero duality gap property, as well as direct connections between dual convergence, boundedness of the penalty parameter, and the existence of optimal dual solutions/global saddle points.

The paper is organized as follows. An abstract axiomatic augmented Lagrangian setting for cone constrained optimization problems in normed spaces, including a list of basic assumptions (axioms) on an augmented Lagrangian, is presented in Section 2. Many particular examples of augmented Lagrangians for various types of cone constrained optimization problems and the basic assumptions that these augmented Lagrangians satisfy are discussed in details in Section 3. Section 4 is devoted to duality theory. In this section we analyse the zero duality gap property for the augmented Lagrangian, and also study interconnections between global saddle points, globally optimal solutions of the augmented dual problem, augmented Lagrange multipliers, and the penalty map. Finally, a general convergence theory for a model augmented Lagrangian method, that encompasses many existing primal-dual augmented Lagrangian methods as particular cases, is presented in Section 5.

2 Axiomatic augmented Lagrangian setting

We start by presenting an axiomatic approach to augmented Lagrangians that serves as a foundation for our duality and convergence theories. Let $X$ and $Y$ be real normed spaces, $Q\subseteq X$ be a nonempty closed set (not necessarily convex), and $K\subset Y$ be a closed convex cone. Suppose also that some functions $f\colon X\to\mathbb{R}\cup\{+\infty\}$ and $G\colon X\to Y$ are given. In this article we study augmented Lagrangians for the following cone constrained optimization problem:

\min\>f(x)\quad\text{subject to}\quad G(x)\in K,\quad x\in Q.\qquad

(𝒫)

We assume that the feasible region of this problem is nonempty and its optimal value, denoted by $f_{*}$ , is finite.

The topological dual space of $Y$ is denoted by $Y^{*}$ , and let $\langle\cdot,\cdot\rangle$ be either the inner product in $\mathbb{R}^{s}$ , $s\in\mathbb{N}$ , or the duality pairing between $Y$ and its dual, depending on the context. Recall that $K^{*}=\{y^{*}\in Y^{*}\mid\langle y^{*},y\rangle\leq 0\enspace\forall y\in K\}$ is the polar cone of the cone $K$ .

Denote by $\preceq$ the binary relation over $Y\times Y$ defined as $y_{1}\preceq y_{2}$ if and only if $y_{2}-y_{1}\in-K$ . We say that this binary relation is induced by the cone $-K$ . As one can readily check, this binary relation is a partial order on $Y$ if and only if $K\cap(-K)=\{0\}$ . In this case $\preceq$ is called the partial order induced by the cone $-K$ . Note that the cone constraint $G(x)\in K$ can be rewritten as $G(x)\preceq 0$ .

We define an augmented Lagrangian for the problem $(\mathcal{P})$ as follows. Choose any function $\Phi\colon Y\times Y^{*}\times(0,+\infty)\to\mathbb{R}\cup\{\pm\infty\}$ , $\Phi=\Phi(y,\lambda,c)$ . An augmented Lagrangian for the problem $(\mathcal{P})$ is defined as

\mathscr{L}(x,\lambda,c)=f(x)+\Phi(G(x),\lambda,c)

if $\Phi(G(x),\lambda,c)>-\infty$ , and $\mathscr{L}(x,\lambda,c)=-\infty$ , otherwise. Here $\lambda\in Y^{*}$ is a multiplier and $c>0$ is a penalty parameter. Note that only the constraint $G(x)\in K$ is incorporated into the augmented Lagrangian.

Unlike most existing works on augmented Lagrangians and corresponding optimization methods, we do not impose any assumptions on the structure of the function $\Phi$ . It can be defined in an arbitrary way. Instead, being inspired by [39] and following the ideas of our earlier paper [22], we propose to use a set of axioms (assumptions) describing behaviour of the function $\Phi(y,\lambda,c)$ for various types of arguments (e.g. as $c$ increases unboundedly or when $y\in K$ ). This approach allows one to construct an axiomatic theory of augmented Lagrangians and helps one to better understand what kind of assumptions the function $\Phi$ must satisfy to guarantee that the augmented Lagrangian $\mathscr{L}(x,\lambda,c)$ and optimization methods based on this augmented Lagrangian have certain desirable properties. As we will show below, most well-known augmented Lagrangians satisfy our proposed set of axioms, which means that our axiomatic theory is rich enough and can be applied in many particular cases.

In order to unite several particular cases into one general theory, we formulate axioms/assumptions on the function $\Phi$ with respect to a prespecified closed convex cone $\Lambda\subseteq Y^{*}$ of admissible multipliers. Usually, $\Lambda=Y^{*}$ or $\Lambda=K^{*}$ .

We grouped the assumptions on $\Phi$ according to their meaning. If the function $\Phi(y,\lambda,c)$ is viewed as a black box with input $(y,\lambda,c)$ and output $\Phi(y,\lambda,c)$ , then assumptions $(A1)$ – $(A6)$ describe what kind of output is produced by this black box with respect to certain specific kinds of input. Assumptions $(A7)$ – $(A11)$ describe general properties of the function $\Phi$ , such as monotonicity, differentiability, and convexity. Assumptions $(A12)$ – $(A15)$ impose restrictions on the way the function $\Phi(y,\lambda,c)$ behaves as $c$ increases unboundedly or along certain sequences $\{(y_{n},\lambda_{n},c_{n})\}$ . Finally, the subscript “s” indicates a stronger, i.e. more restrictive, version of an assumption.

Denote $\operatorname{dist}(y,K)=\inf_{z\in K}\|y-z\|$ for any $y\in Y$ , and let $B(x,r)$ be the closed ball with centre $x$ and radius $r>0$ . Below is the list of basic assumptions on the function $\Phi$ that are utilised throughout the article:

(A1)

$\forall y\in K\>\forall\lambda\in\Lambda\>\forall c>0$ one has $\Phi(y,\lambda,c)\leq 0$ ;
(A2)

$\forall y\in K\>\forall c>0\>\exists\lambda\in\Lambda$ such that $\Phi(y,\lambda,c)\geq 0$ ;
(A3)

$\forall y\notin K\>\forall c>0\>\exists\lambda\in\Lambda$ such that $\Phi(y,t\lambda,c)\to+\infty$ as $t\to+\infty$ ;
(A4)

$\forall y\in K\>\forall\lambda\in K^{*}\>\forall c>0$ such that $\langle\lambda,y\rangle=0$ one has $\Phi(y,\lambda,c)=0$ ;
(A5)

$\forall y\in K\>\forall\lambda\in K^{*}\>\forall c>0$ such that $\langle\lambda,y\rangle\neq 0$ one has $\Phi(y,\lambda,c)<0$ ;
(A6)

$\forall y\in K\>\forall\lambda\in\Lambda\setminus K^{*}\>\forall c>0$ one has $\Phi(y,\lambda,c)<0$ ;
(A7)

$\forall y\in Y\>\forall\lambda\in\Lambda$ the function $c\mapsto\Phi(y,\lambda,c)$ is non-decreasing;
(A8)

$\forall\lambda\in\Lambda\>\forall c>0$ the function $y\mapsto\Phi(y,\lambda,c)$ is convex and non-decreasing with respect to the binary relation $\preceq$ ;
(A9)

$\forall y\in Y\>\forall c>0$ the function $\lambda\mapsto\Phi(y,\lambda,c)$ is concave;
$(A9)_{s}$

$\forall y\in Y$ the function $(\lambda,c)\mapsto\Phi(y,\lambda,c)$ is concave;
(A10)

$\forall y\in Y$ the function $(\lambda,c)\mapsto\Phi(y,\lambda,c)$ is upper semicontinuous;
(A11)

$\forall y\in K\>\forall\lambda\in K^{*}\>\forall c>0$ such that $\langle\lambda,y\rangle=0$ the function $\Phi(\cdot,\lambda,c)$ is Fréchet differentiable at $y$ and its Fréchet derivative satisfies the equality $D_{y}\Phi(y,\lambda,c)=\Phi_{0}(\lambda)$ for some surjective mapping $\Phi_{0}\colon K^{*}\to K^{*}$ that does not depend on $y$ and $c$ , and such that $\langle\Phi_{0}(\lambda),y\rangle=0$ if and only if $\langle\lambda,y\rangle=0$ ;

(A12)

$\forall\lambda\in\Lambda\>\forall c_{0}>0\>\forall r>0$ one has

\lim_{c\to+\infty}\inf\Big{\{}\Phi(y,\lambda,c)-\Phi(y,\lambda,c_{0})\Bigm{|}\\ y\in Y\colon\operatorname{dist}(y,K)\geq r,\>|\Phi(y,\lambda,c_{0})|<+\infty\Big{\}}=+\infty;

(A12)_{s}

$\forall c_{0}>0\>\forall r>0$ and for any bounded subset $\Lambda_{0}\subseteq\Lambda$ one has

\lim_{c\to+\infty}\inf_{\lambda\in\Lambda_{0}}\inf\Big{\{}\Phi(y,\lambda,c)-\Phi(y,\lambda,c_{0})\Bigm{|}\\ y\in Y\colon\operatorname{dist}(y,K)\geq r,\>|\Phi(y,\lambda,c_{0})|<+\infty\Big{\}}=+\infty;

(A13)

$\forall\lambda\in\Lambda$ and for any sequences $\{c_{n}\}\subset(0,+\infty)$ and $\{y_{n}\}\subset Y$ such that $c_{n}\to+\infty$ and $\operatorname{dist}(y_{n},K)\to 0$ as $n\to\infty$ one has $\liminf\limits_{n\to\infty}\Phi(y_{n},\lambda,c_{n})\geq 0$ ;
$(A13)_{s}$

for any sequences $\{c_{n}\}\subset(0,+\infty)$ and $\{y_{n}\}\subset Y$ such that $c_{n}\to+\infty$ and $\operatorname{dist}(y_{n},K)\to 0$ as $n\to\infty$ and for any bounded subset $\Lambda_{0}\subseteq\Lambda$ one has $\liminf\limits_{n\to\infty}\inf\limits_{\lambda\in\Lambda_{0}}\Phi(y_{n},\lambda,c_{n})\geq 0$ ;
(A14)

$\forall\lambda\in\Lambda\>\forall\{c_{n}\}\subset(0,+\infty)$ such that $c_{n}\to+\infty$ as $n\to\infty$ there exists $\{t_{n}\}\subset(0,+\infty)$ such that $t_{n}\to 0$ as $n\to\infty$ and for any $\{y_{n}\}\subset Y$ with $\operatorname{dist}(y_{n},K)\leq t_{n}$ one has $\lim\limits_{n\to\infty}\Phi(y_{n},\lambda,c_{n})=0$ ;
$(A14)_{s}$

$\forall\{c_{n}\}\subset(0,+\infty)$ such that $c_{n}\to+\infty$ as $n\to\infty$ and for any bounded sequence $\{\lambda_{n}\}\subseteq\Lambda$ there exists $\{t_{n}\}\subset(0,+\infty)$ such that $t_{n}\to 0$ as $n\to\infty$ and for any $\{y_{n}\}\subset Y$ with $\operatorname{dist}(y_{n},K)\leq t_{n}$ the following equality holds true $\lim\limits_{n\to\infty}\Phi(y_{n},\lambda_{n},c_{n})=0$ ;
(A15)

for any bounded sequences $\{\lambda_{n}\}\subset\Lambda$ and $\{c_{n}\}\subset(0,+\infty)$ and for any sequence $\{y_{n}\}\subset Y$ such that $\operatorname{dist}(y_{n},K)\to 0$ as $n\to\infty$ one has $\limsup\limits_{n\to\infty}\Phi(y_{n},\lambda_{n},c_{n})\leq 0$ ;

Remark 1.

In the case of assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , $(A14)_{s}$ , and $(A15)$ , we say that the function $\Phi$ satisfies the restricted version of the corresponding assumption, if one replaces “any sequence $\{y_{n}\}\subset Y$ ” in the formulation of corresponding assumption with “any bounded sequence $\{y_{n}\}\subset Y$ ”. Note that the validity of a (non-restricted) assumption implies that its restricted version also hold true.

Remark 2.

It should be noted that assumption $(A13)_{s}$ can be reformulated as follows: for any sequences $\{c_{n}\}\subset(0,+\infty)$ and $\{y_{n}\}\subset Y$ such that $c_{n}\to+\infty$ and $\operatorname{dist}(y_{n},K)\to 0$ as $n\to\infty$ and for any bounded sequence $\{\lambda_{n}\}\subseteq\Lambda$ one has $\liminf\limits_{n\to\infty}\Phi(y_{n},\lambda_{n},c_{n})\geq 0$ .

Below we will often use the following corollary to assumptions $(A13)$ and $(A13)_{s}$ that can be readily verified directly.

Lemma 1.

If $\Phi$ satisfies assumption $(A13)$ , then for any $\lambda\in\Lambda$ one has

\liminf_{c\to+\infty}\inf_{y\in K}\Phi(y,\lambda,c)\geq 0.

If $\Phi$ satisfies assumption $(A13)_{s}$ , then for any bounded subset $\Lambda_{0}\subseteq\Lambda$ one has

\liminf_{c\to+\infty}\inf_{\lambda\in\Lambda_{0}}\inf\limits_{y\in K}\Phi(y,\lambda,c)\geq 0.

In the following section we will give many particular examples of augmented Lagrangians for different types of cone constrained optimization problems (e.g. equality constrained problems, inequality constrained problems, problems with semidefinite constraints, etc.). If an optimization problem has several different types of constraints simultaneously, it is convenient to represent them as cone constraints of the form $G_{i}(x)\in K_{i}$ for some mappings $G_{i}\colon X\to Y_{i}$ and closed convex cones $K_{i}$ in real Banach spaces $Y_{i}$ , $i\in\{1,\ldots,m\}$ , with $m\in\mathbb{N}$ . Then one can define $Y=Y_{1}\times\ldots\times Y_{m}$ and

G(\cdot)=(G_{1}(\cdot),\ldots,G_{m}(\cdot)),\quad K=K_{1}\times\ldots\times K_{m}

to formally rewrite such optimization problems as the problem $(\mathcal{P})$ . The space $Y$ is equipped with the norm $\|y\|=\|y_{1}\|+\ldots+\|y_{m}\|$ for all $y=(y_{1},\ldots,y_{m})\in Y$ .

In order to define a function $\Phi(y,\lambda,c)$ in this case, one can define corresponding functions $\Phi_{i}(y_{i},\lambda_{i},c)$ for each constraint $G_{i}(x)\in K_{i}$ individually (here $y_{i}\in Y_{i}$ and $\lambda_{i}\in\Lambda_{i}\subseteq Y_{i}^{*}$ ) and then put

\Phi(y,\lambda,c)=\sum_{i=1}^{m}\Phi_{i}(y_{i},\lambda_{i},c),\quad y=(y_{1},\ldots,y_{m}),\quad\lambda=(\lambda_{1},\ldots,\lambda_{m}),

(1)

if $\Phi_{i}(y_{i},\lambda_{i},c)>-\infty$ for all $i$ , and $\Phi(y,\lambda,c)=-\infty$ , otherwise. Most (if not all) existing augmented Lagrangians for problems with several different types constraints are defined in this way. Let us show that, roughly speaking, if $\Lambda=\Lambda_{1}\times\ldots\times\Lambda_{m}$ and all functions $\Phi_{i}$ , $i\in\{1,\ldots,m\}$ , satisfy some basic assumption simultaneously, then the function $\Phi$ also satisfies this basic assumption.

Theorem 1.

Let $\Lambda=\Lambda_{1}\times\ldots\times\Lambda_{m}$ . Then the following statements hold true:

1.

if all functions $\Phi_{i}$ , $i\in I:=\{1,\ldots,m\}$ , satisfy one of the basic assumptions simultaneously, except for assumptions $(A5)$ , $(A6)$ , $(A12)$ , and $(A12)_{s}$ , then the function $\Phi$ defined in (1) satisfies the same basic assumption;
2.

if all functions $\Phi_{i}$ , $i\in I$ , satisfy assumptions $(A1)$ and $(A5)$ (or $(A1)$ and $(A6)$ ) simultaneously, then the function $\Phi$ defined in (1) also satisfies assumption $(A5)$ (or $(A6)$ );
3.

if all functions $\Phi_{i}$ , $i\in I$ , satisfy assumptions $(A7)$ and $(A12)$ (or $(A7)$ and $(A12)_{s}$ ) simultaneously, then the function $\Phi$ defined in (1) also satisfies assumption $(A12)$ (or $(A12)_{s}$ ).

Proof.

Assumption (A1). If $y\in K$ and $\lambda\in\Lambda$ , then $y_{i}\in K_{i}$ and $\lambda_{i}\in\Lambda_{i}$ for all $i\in I$ . Therefore, $\Phi_{i}(y_{i},\lambda_{i},c)\leq 0$ by assumption $(A1)$ , which implies that $\Phi(y_{,}\lambda,c)\leq 0$ .

Assumption (A2). Choose any $y\in K$ and $c>0$ . By assumption $(A2)$ for any $i\in I$ there exists $\lambda_{i}\in\Lambda_{i}$ such that $\Phi_{i}(y_{i},\lambda_{i},c)\geq 0$ . Put $\lambda=(\lambda_{1},\ldots,\lambda_{m})$ . Then $\Phi(y,\lambda,c)\geq 0$ .

Assumption (A3). Choose any $y\in K$ and $c>0$ . By assumption $(A3)$ for any $i\in I$ there exists $\lambda_{i}\in\Lambda_{i}$ such that $\Phi_{i}(y_{i},t\lambda_{i},c)\to+\infty$ as $t\to+\infty$ . Put $\lambda=(\lambda_{1},\ldots,\lambda_{m})$ . Then $\Phi(y,t\lambda,c)\to+\infty$ as $t\to\infty$ .

Assumption (A4). Let $y\in K$ and $\lambda\in K^{*}$ be such that $\langle\lambda,y\rangle=0$ . It is easily seen that the condition $\lambda\in K^{*}$ implies that $\lambda_{i}\in K^{*}_{i}$ for any $i\in I$ and, therefore, $\langle\lambda_{i},y_{i}\rangle\leq 0$ for all $i\in I$ . Hence $\langle\lambda_{i},y_{i}\rangle=0$ for all $i\in I$ and by assumption $(A4)$ one has $\Phi_{i}(y_{i},\lambda_{i},c)=0$ , which yields $\Phi(y,\lambda,c)=0$ .

Assumption (A5). If $y\in K$ and $\lambda\in K^{*}$ are such that $\langle\lambda,y\rangle\neq 0$ , then there exists $k\in I$ such that $\langle\lambda_{k},y_{k}\rangle\neq 0$ . Therefore, $\Phi_{k}(y_{k},\lambda_{k},c)<0$ . In turn, for any $i\neq k$ one has $\Phi_{i}(y_{i},\lambda_{i},c)\leq 0$ by assumption $(A1)$ . Hence $\Phi(y,\lambda,c)<0$ .

Assumption (A6). If $y\in K$ and $\lambda\in\Lambda\setminus K^{*}$ , then $\lambda_{k}\in\Lambda_{k}\setminus K_{k}^{*}$ for some $k\in I$ . Therefore, $\Phi_{k}(y_{k},\lambda_{k},c)<0$ , while $\Phi(y_{i},\lambda_{i},c)\leq 0$ for any $i\neq k$ by assumption $(A1)$ . Consequently, $\Phi(y,\lambda,c)<0$ .

Assumption (A7). The function $\Phi(y,\lambda,c)$ is non-decreasing in $c$ as the sum of non-decreasing in $c$ functions.

Assumption (A8). Note that if the function $\Phi_{i}(\cdot,\lambda_{i},c)$ is non-decreasing with respect to the binary relation induced by the cone $-K_{i}$ , then the function $y\mapsto\Phi_{i}(y_{i},\lambda_{i},c)$ is non-decreasing with respect to the binary relation induced by the cone $-K$ . Therefore the function $\Phi(y,\lambda,c)$ is convex and non-decreasing with respect to the binary relation induced by the cone $-K$ as the sum of convex and non-decreasing functions.

Assumptions (A9) and (A9)_s. The function $\Phi(y,\lambda,c)$ is concave in $\lambda$ (or $(\lambda,c)$ ) as the sum of concave functions.

Assumption (A10). The function $\Phi(y,\lambda,c)$ is upper semicontinuous as the sum of a finite number of upper semicontinuous functions.

Assumption (A11). If $y\in K$ and $\lambda\in K^{*}$ are such that $\langle\lambda,y\rangle=0$ , then, as was noted above, $y_{i}\in K_{i}$ , $\lambda_{i}\in K_{i}^{*}$ , and $\langle\lambda_{i},y_{i}\rangle=0$ for all $i\in I$ . Then each of the functions $\Phi_{i}(\cdot,\lambda_{i},c)$ is Fréchet differentiable at $y_{i}$ and its derivative has the form $D_{y_{i}}\Phi_{i}(y_{i},\lambda_{i},c)=\Phi_{i0}(\lambda_{i})$ for some function $\Phi_{i0}\colon K_{i}^{*}\to K_{i}^{*}$ such that $\langle\Phi_{i0}(\lambda_{i}),y_{i}\rangle=0$ if and only if $\langle\lambda_{i},y_{i}\rangle=0$ . Therefore, the function $\Phi(\cdot,\lambda,c)$ is Fréchet differentiable at the point $y$ and its Fréchet derivative is equal to $\Phi_{0}(\lambda)=(\Phi_{10}(\lambda_{1}),\ldots,\Phi_{m0}(\lambda_{m}))$ . Clearly, one has

	$\displaystyle\langle\Phi_{0}(\lambda),y\rangle=0\enspace\Leftrightarrow\enspace\langle\Phi_{i0}(\lambda_{i}),y_{i}\rangle=0\enspace\forall i\in I\enspace$	$\displaystyle\Leftrightarrow\enspace\langle\lambda_{i},y_{i}\rangle=0\enspace\forall i\in I$
		$\displaystyle\Leftrightarrow\enspace\langle\lambda,y\rangle=0,$

which implies the required result.

Assumption (A12). Fix any $\lambda\in\Lambda$ , $c_{0}>0$ , and $r>0$ . Choose some $\alpha>0$ . Let $y\in Y$ be such that $|\Phi(y,\lambda,c_{0})|<+\infty$ and $\operatorname{dist}(y,K)\geq r$ . Then there exists $i\in I$ such that $\operatorname{dist}(y_{i},K_{i})\geq r/m$ . By assumption $(A12)$ for the functions $\Phi_{j}$ , for any $j\in I$ there exists $c_{j}(r/m,\alpha)\geq c_{0}$ such that for all $c\geq c_{j}(r/m,\alpha)$ one has

\inf\Big{\{}\Phi_{j}(z_{j},\lambda_{j},c)-\Phi_{j}(z_{j},\lambda_{j},c_{0})\Bigm{|}z_{j}\in Y_{j}\colon\operatorname{dist}(z_{j},K_{j})\geq r/m,\\ |\Phi_{j}(z_{j},\lambda_{j},c_{0})|<+\infty\Big{\}}\geq\alpha.

Let $c(r,\alpha):=\max\{c_{j}(r/m,\alpha)\mid j\in I\}$ . Then with the use of assumption $(A7)$ one gets that for any $c\geq c(r,\alpha)$ the following inequalities hold true:

	$\displaystyle\Phi(y,\lambda,c)-\Phi(y,\lambda,c_{0})$	$\displaystyle=\sum_{i=1}^{m}\big{(}\Phi_{i}(y_{i},\lambda_{i},c)-\Phi_{i}(y_{i},\lambda_{i},c_{0})\big{)}$
		$\displaystyle\geq\Phi_{i}(y_{i},\lambda_{i},c)-\Phi_{i}(y_{i},\lambda_{i},c_{0})\geq\alpha.$

Since $y\in Y$ such that $|\Phi(y,\lambda,c_{0})|<+\infty$ and $\operatorname{dist}(y,K)\geq r$ were chosen arbitrarily, one can conclude that for any $\alpha>0$ and $r>0$ there exists $c(r,\alpha)\geq c_{0}$ such that

\inf\Big{\{}\Phi(y,\lambda,c)-\Phi(y,\lambda,c_{0})\Bigm{|}y\in Y\colon\operatorname{dist}(y,K)\geq r,\>\Phi(y,\lambda,c_{0})<+\infty\Big{\}}\geq\alpha

for all $c\geq c(r,\alpha)$ . Consequently, the function $\Phi$ satisfies assumption $(A12)$ .

Assumption (A12)_s. Choose some $c_{0}>0$ and let $\Lambda_{0}\subset\Lambda$ be a bounded set. Clearly, one can find bounded sets $\Lambda_{i0}\subset\Lambda_{i}$ such that $\Lambda_{0}\subseteq\widehat{\Lambda}_{0}$ , where $\widehat{\Lambda}_{0}:=\Lambda_{10}\times\ldots\times\Lambda_{m0}$ .

By assumption $(A12)_{s}$ for the functions $\Phi_{i}$ , for any $i\in I$ , $r>0$ , and $\alpha>0$ one can find $c_{i}(r,\alpha,\Lambda_{i0})\geq c_{0}$ such that

\inf_{\lambda\in\Lambda_{i0}}\inf\Big{\{}\Phi_{i}(y_{i},\lambda_{i},c)-\Phi(y_{i},\lambda_{i},c_{0})\Bigm{|}y_{i}\in Y_{i}(r,\Phi_{i})\Big{\}}\geq\alpha\quad\forall c\geq c_{i}(r,\alpha,\Lambda_{i0}),

where $Y_{i}(r,\Phi_{i}):=\{y_{i}\in Y_{i}\mid\operatorname{dist}(y_{i},K_{i})\geq r,|\Phi_{i}(y_{i},\lambda_{i},c_{0})|<+\infty\}$ .

Denote $Y(r,\Phi)=\{y\in Y\mid\operatorname{dist}(y,K)\geq r,\>|\Phi(y,\lambda,c_{0})|<+\infty\}$ . Fix some $r>0$ and choose any $y\in Y(r,\Phi)$ . Then $\operatorname{dist}(y_{i},K_{i})\geq r/m$ for some $i\in I$ . Hence with the use of assumption $(A7)$ one gets that

\inf_{\lambda\in\Lambda_{0}}\inf\Big{\{}\Phi(y,\lambda,c)-\Phi(y,\lambda,c_{0})\Bigm{|}y\in Y(r,\Phi)\Big{\}}\\ \geq\inf_{\lambda\in\widehat{\Lambda}_{0}}\inf\Big{\{}\Phi(y,\lambda,c)-\Phi(y,\lambda,c_{0})\Bigm{|}y\in Y(r,\Phi)\Big{\}}\\ \geq\inf_{\lambda\in\Lambda_{i0}}\inf\Big{\{}\Phi_{i}(y_{i},\lambda_{i},c)-\Phi(y_{i},\lambda_{i},c_{0})\Bigm{|}y_{i}\in Y_{i}(r/m,\Phi_{i})\Big{\}}\geq\alpha

for any $c\geq c(r,\alpha,\Lambda_{0}):=\max\{c_{j}(r/m,\alpha,\Lambda_{i0})\mid j\in I\}$ . Since $\alpha>0$ was chosen arbitrarily, one can conclude that the function $\Phi$ satisfies assumption $(A12)_{s}$ .

Assumption (A13). If sequences $\{c_{n}\}\subset(0,+\infty)$ and $\{y_{n}\}\subset Y$ are such that $c_{n}\to+\infty$ and $\operatorname{dist}(y_{n},K)\to 0$ as $k\to\infty$ , then $\operatorname{dist}(y_{in},K_{i})\to 0$ as $n\to\infty$ and $\liminf_{n\to\infty}\Phi_{i}(y_{in},\lambda,c_{n})\geq 0$ for all $i\in I$ . From these inequalities it obviously follows that $\liminf_{n\to\infty}\Phi(y_{n},\lambda,c_{n})\geq 0$ as well.

Assumption (A13)_s. The proof is essentially the same as the proof for assumption $(A13)$ .

Assumption (A14). Fix any $\lambda\in\Lambda$ and a sequence $\{c_{n}\}\subset(0,+\infty)$ such that $c_{n}\to+\infty$ as $n\to\infty$ . By our assumption for any $i\in I$ there exists a sequence $\{t_{in}\}\subset(0,+\infty)$ converging to zero and such that for any $\{y_{in}\}\subset Y_{i}$ with $\operatorname{dist}(y_{in},K_{i})\leq t_{in}$ for all $n\in\mathbb{N}$ one has $\Phi_{i}(y_{in},\lambda,c_{n})\to 0$ as $n\to\infty$ .

Define $t_{n}=\min\{t_{1n},\ldots,t_{mn}\}$ and choose any sequence $\{y_{n}\}\subset Y$ such that $\operatorname{dist}(y_{n},K)\leq t_{n}$ for all $n\in\mathbb{N}$ . Then for any $i\in I$ and $n\in\mathbb{N}$ one has $\operatorname{dist}(y_{in},K_{i})\leq t_{in}$ , which implies that $\Phi_{i}(y_{in},\lambda,c_{n})\to 0$ as $n\to\infty$ and, therefore, $\Phi(y_{n},\lambda,c_{n})\to 0$ as $n\to\infty$ .

Assumption (A14)_s. The proof is the same as the proof for assumption $(A14)$ .

Assumption (A15). If $\{\lambda_{n}\}\subset\Lambda$ and $\{c_{n}\}$ are bounded sequences and a sequence $\{y_{n}\}\subset Y$ is such that $\operatorname{dist}(y_{n},K)\to 0$ as $n\to\infty$ , then the sequences $\{\lambda_{in}\}$ are also bounded and $\operatorname{dist}(y_{in},K_{i})\to 0$ as $n\to\infty$ for all $i\in I$ . Consequently, one has

\limsup_{n\to\infty}\Phi_{i}(y_{in},\lambda_{in},c_{n})\leq 0\quad\forall i\in I.

Applying these inequalities one can readily check that $\limsup\limits_{n\to\infty}\Phi(y_{n},\lambda_{n},c_{n})\leq 0$ .

The proof of the claim of the theorem for the restricted versions of assumptions $(A13)$ – $(A15)$ , $(A13)_{s}$ , and $(A14)_{s}$ is essentially the same as the proofs for the non-restricted versions of these assumptions. ∎

Remark 3.

Let us note that assumptions $(A1)$ and $(A7)$ are satisfied for all particular augmented Lagrangians presented in this paper and all augmented Lagrangians known to the author.

Thus, the previous theorem allows one to analyse augmented Lagrangians for each particular type of cone constraints separately and then simply define an augmented Lagrangian for problems with several different types of cone constraints as in (1). Then the basic assumptions will be satisfied for this augmented Lagrangian by Theorem 1.

3 Examples of augmented Lagrangians

Let us present some particular examples of augmented Lagrangians for various types of cone constraints and discuss which of the basic assumptions are satisfied for these augmented Lagrangians. Our aim is to show that the basic assumptions are not restrictive and satisfied for most augmented Lagrangians appearing in the literature.

Many examples of augmented Lagrangians were already presented in the author’s previous paper [22]. However, many of the basic assumptions from this paper are completely new and were not used in [22] (e.g. assumptions $(A9)$ , $(A10)$ , and $(A13)$ – $(A15)$ , as well as their stronger and restricted versions). Therefore, for the sake of completeness we will present detailed descriptions of all examples, even though they partially overlap with the contents of [22, Section 3].

3.1 Augmented Lagrangians for problems with general cone constraints

First, we consider an augmented Lagrangian that is defined for any cone constrained optimization problem of the form $(\mathcal{P})$ . Since particular versions of this augmented Lagrangian are apparently studied and used in optimization methods more often than any other augmented Lagrangian, we will discuss it in more details than other examples.

Example 1 (Rockafellar-Wets’ augmented Lagrangian).

Let $\sigma\colon Y\to[0,+\infty]$ be such that $\sigma(0)=0$ and $\sigma(y)\neq 0$ for any $y\neq 0$ . In particular, one can set $\sigma(y)=\|y\|$ or $\sigma(y)=0.5\|y\|^{2}$ . Define

\Phi(y,\lambda,c)=\inf_{p\in K-y}\big{(}-\langle\lambda,p\rangle+c\sigma(p)\big{)}.

(2)

The augmented Lagrangian with the term $\Phi$ defined in this way was first introduced by Rockafellar and Wets [58, Section 11.K] (see also [31, 62, 32, 21]). Various generalizations of this augmented Lagrangian were studied in [9, 72, 70].

Lemma 2.

Let $\Lambda=Y^{*}$ . Then the function $\Phi$ defined in (2) satisfies:

1.

assumptions $(A1)$ – $(A4)$ , $(A7)$ , $(A9)$ , $(A9)_{s}$ , and $(A10)$ in the general case;
2.

assumptions $(A5)$ and $(A6)$ , if $\sigma(ty)=o(t)$ as $t\to 0$ (that is, $\sigma(ty)/t\to 0$ as $t\to 0$ ) for any $y\in Y$ ;
3.

assumption $(A8)$ , if the function $\sigma$ is convex;
4.

assumption $(A11)$ with $\Phi_{0}(\lambda)\equiv\lambda$ , if $\sigma(y)=0.5\|y\|^{2}$ and $Y$ is a Hilbert space;
5.

assumptions $(A12)$ and $(A12)_{s}$ , if $\sigma$ has a valley at zero, that is, for any neighbourhood $U$ of zero in $Y$ there exists $\delta>0$ such that $\sigma(y)\geq\delta$ for all $y\in Y\setminus U$ ;
6.

assumptions $(A13)$ and $(A13)_{s}$ , if $\sigma(y)\geq\omega(\|y\|)$ for all $y\in Y$ and some continuous function $\omega\colon[0,+\infty)\to[0,+\infty)$ such that $\omega(t)=0$ if and only if $t=0$ , and $\liminf_{t\to+\infty}\omega(t)/t>0$ ;
7.

assumptions $(A14)$ and $(A14)_{s}$ , if $\sigma$ is continuous at zero and there exists a continuous function $\omega\colon[0,+\infty)\to[0,+\infty)$ such that $\sigma(y)\geq\omega(\|y\|)$ for all $y\in Y$ , $\omega(t)=0$ if and only if $t=0$ , and $\liminf_{t\to+\infty}\omega(t)/t>0$ ;
8.

assumption $(A15)$ , if the function $\sigma$ is continuous at zero.

Proof.

We divide the proof of the lemma into several parts corresponding to its separate statements.

Part 1. Assumptions $(A1)$ (set $p=0$ ), $(A2)$ (set $\lambda=0$ ), and $(A7)$ are obviously satisfied. Assumption $(A3)$ is satisfied for $\lambda\in Y^{*}$ from the separation theorem for the sets $\{y\}$ and $K$ . Assumption $(A4)$ is satisfied, since if $\langle\lambda,y\rangle=0$ and $\lambda\in K^{*}$ , then

\Phi(y,\lambda,c)=\inf_{p\in K}\big{(}-\langle\lambda,p\rangle+c\sigma(p-y)\big{)}\geq c\inf_{p\in K}\sigma(p-y)\geq 0,

which along with assumption $(A1)$ implies that $\Phi(y,\lambda,c)=0$ . Assumptions $(A9)$ , $(A9)_{s}$ , and $(A10)$ are satisfied by virtue of the fact that the function $(\lambda,c)\mapsto\Phi(y,\lambda,c)$ is the infimum of a family of linear functions.

Part 2. Let $y\in K$ and $\lambda\in K^{*}$ be such that $\langle\lambda,y\rangle\neq 0$ . For any $t$ in a sufficiently small neighbourhood of zero one has $z(t)=(1+t\operatorname{sign}(\langle\lambda,y\rangle))y\in K$ , which implies that for $p=z(t)-y\in K-y$ the following inequalities hold true:

\Phi(y,\lambda,c)\leq-\langle\lambda,p\rangle+c\sigma(p)=-t\big{|}\langle\lambda,y\rangle\big{|}+c\sigma\big{(}t\operatorname{sign}(\langle\lambda,y\rangle)y\big{)}.

The last expression is negative for any sufficiently small $t$ , since $\sigma(ty)=o(t)$ , that is, assumption $(A5)$ holds true.

Let now $y\in K$ and $\lambda\in\Lambda\setminus K^{*}$ . For any such $\lambda$ one can find $p_{0}\in K$ for which $\langle\lambda,p_{0}\rangle<0$ . Then putting $p=tp_{0}$ for $t>0$ (note that $tp_{0}+y\in K$ , since $y\in K$ and $K$ is a convex cone, which yields $p\in K-y$ ) one gets

\Phi(y,\lambda,c)\leq-t\langle\lambda,p_{0}\rangle+c\sigma(tp_{0})<0

for any sufficiently small $t$ , thanks to the fact that $\sigma(tp_{0})=o(t)$ .

Part 3. Fix any $\alpha\in(0,1)$ and $y_{1},y_{2}\in Y$ . Choose any $M_{i}>\Phi(y_{i},\lambda,c)$ , $i\in\{1,2\}$ . By definition one can find $p_{i}\in K-y_{i}$ such that $M_{i}>-\langle\lambda,p_{i}\rangle+c\sigma(p_{i})$ , $i\in\{1,2\}$ . Then for $p(\alpha)=\alpha p_{1}+(1-\alpha)p_{2}\in K-(\alpha y_{1}+(1-\alpha)y_{2})$ one has

	$\displaystyle\Phi(\alpha y_{1}+(1-\alpha)y_{2},\lambda,c)$	$\displaystyle\leq-\langle\lambda,p(\alpha)\rangle+c\sigma(p(\alpha))$
		$\displaystyle\leq\alpha\Big{(}-\langle\lambda,p_{1}\rangle+c\sigma(p_{1})\Big{)}+(1-\alpha)\Big{(}-\langle\lambda,p_{2}\rangle+c\sigma(p_{2})\Big{)}$
		$\displaystyle<\alpha M_{1}+(1-\alpha)M_{2}.$

Hence by [54, Theorem I.4.2] one can conclude that the function $\Phi(\cdot,\lambda,c)$ is convex. Let us now show that it is non-decreasing with respect to the binary relation induced by the cone $-K$ .

Indeed, fix any $y_{1},y_{2}\in Y$ such that $y_{1}\preceq y_{2}$ , i.e. $y_{2}-y_{1}\in-K$ . One can obviously suppose that $\Phi(y_{2},\lambda,c)<+\infty$ . By definition for any $M>\Phi(y_{2},\lambda,c)$ one can find $p\in K-y_{2}$ such that $M\geq-\langle\lambda,p\rangle+c\sigma(p)$ . Let $z\in K$ be such that $p=z-y_{2}$ . Note that $z-(y_{2}-y_{1})\in K$ due to the fact that $-(y_{2}-y_{1})\in K$ by our assumption. Then $p=z-(y_{2}-y_{1})-y_{1}\in K-y_{1}$ , which yields

\Phi(y_{1},\lambda,c)\leq-\langle\lambda,p\rangle+c\sigma(p)\leq M.

Since $M>\Phi(y_{2},\lambda,c)$ was chosen arbitrarily, one can conclude that the function $\Phi(\cdot,\lambda,c)$ is non-decreasing with respect to the binary relation $\preceq$ .

Part 4. The proof of this statement of the lemma can be found in [62].

Part 5. Fix any $c_{0}>0$ . For any $y\in Y$ and $\lambda\in\Lambda$ such that $\Phi(y,\lambda,c_{0})$ is finite one has

	$\displaystyle\Phi(y,\lambda,c)$	$\displaystyle=\inf_{p\in K-y}\big{(}-\langle\lambda,p\rangle+(c-c_{0}+c_{0})\sigma(p)\big{)}$
		$\displaystyle\geq\inf_{p\in K-y}\big{(}-\langle\lambda,p\rangle+c_{0}\sigma(p)\big{)}+(c-c_{0})\inf_{p\in K-y}\sigma(p)$

for any $c\geq c_{0}$ . If $\operatorname{dist}(y,K)\geq r$ , then $\|p\|\geq r$ for any $p\in K-y$ . Therefore by our assumption there exists $\delta>0$ , independent on $\lambda\in\Lambda$ , $c\geq c_{0}$ , and $y\in\{z\in K\mid\operatorname{dist}(z,K)\geq r\}$ , such that

\Phi(y,\lambda,c)-\Phi(y,\lambda,c_{0})\geq(c-c_{0})\delta.

With the use of this inequality one can easily prove that assumptions $(A12)$ and $(A12)_{s}$ hold true.

Part 6. Let $\{c_{n}\}\subset(0,+\infty)$ be an increasing unbounded sequence. Fix any bounded set $\Lambda_{0}\subset\Lambda$ . Then for any $y\in Y$ and $\lambda\in\Lambda_{0}$ one has

\Phi(y,\lambda,c_{n})\geq\inf_{p\in K-y}\big{(}-\|\lambda\|\|p\|+c_{n}\omega(\|p\|)\big{)}\geq\inf_{t\geq 0}\big{(}-Rt+c_{n}\omega(t)\big{)},

where $R>0$ is such that $\|\lambda\|\leq R$ for all $\lambda\in\Lambda_{0}$ . By applying the assumptions on the function $\omega$ one can readily check that

\liminf_{n\to\infty}\inf_{t\geq 0}\big{(}-Rt+c_{n}\omega(t)\big{)}\geq 0,

which yields

\liminf_{n\to\infty}\inf_{\lambda\in\Lambda_{0}}\inf_{y\in Y}\Phi(y,\lambda,c_{n})\geq 0.

(3)

Consequently, assumptions $(A13)$ and $(A13)_{s}$ hold true.

Part 7. Let $\{\lambda_{n}\}\subset Y^{*}$ be a bounded sequence and a sequence $\{c_{n}\}\subset(0,+\infty)$ be such that $c_{n}\to+\infty$ as $n\to\infty$ . Due to the continuity of $\sigma$ at zero, for any $n\in\mathbb{N}$ one can find $\delta_{n}>0$ such that for all $p\in B(0,\delta_{n})$ one has $\sigma(p)\leq 1/(c_{n}n)$ . One can obviously suppose that $\delta_{n}\to 0$ as $n\to\infty$ .

Define $t_{n}=\delta_{n}/2$ for all $n\in\mathbb{N}$ . Then for any sequence $\{y_{n}\}\subset Y$ such that $\operatorname{dist}(y_{n},K)\leq t_{n}$ for all $n\in\mathbb{N}$ one can find a sequence $\{z_{n}\}\subset K$ such that $\|z_{n}-y_{n}\|\leq\delta_{n}$ for all $n\in\mathbb{N}$ . Observe that for $p_{n}=z_{n}-y_{n}\in K-y_{n}$ one has

\Phi(y_{n},\lambda_{n},c_{n})\leq-\langle\lambda_{n},p_{n}\rangle+c_{n}\sigma(p_{n})\quad\forall n\in\mathbb{N},

(4)

and the right-hand side of this inequality converges to zero, since $p_{n}\to 0$ as $n\to\infty$ and the sequence $\{\lambda_{n}\}$ is bounded. Combining this fact with inequality (3) one obtains that we have found a sequence $\{t_{n}\}$ for which assumptions $(A14)$ and $(A14)_{s}$ hold true.

Part 8. Let $\{\lambda_{n}\}\subset Y^{*}$ and $\{c_{n}\}\subset(0,+\infty)$ be bounded sequences, and a sequence $\{y_{n}\}\subset Y$ be such that $\operatorname{dist}(y_{n},K)\to 0$ as $n\to\infty$ . Then thanks to the continuity of $\sigma$ at zero one can find a sequence $\{z_{n}\}\subset K$ such that $\|p_{n}\|\to 0$ and $\sigma(p_{n})\to 0$ as $n\to\infty$ , where $p_{n}=z_{n}-y_{n}$ . Now, applying inequality (4) and taking into account the fact that the right-hand side of this inequality obviously converges to zero one can conclude that assumption $(A15)$ is valid. ∎

Thus, all basic assumptions are satisfied for $\sigma(y)=0.5\|y\|^{2}$ . In the other important case of the sharp Lagrangian [27, 8, 10, 1, 16], that is, the case when $\sigma(y)=\|y\|$ , all assumptions, except for $(A5)$ , $(A6)$ , and $(A11)$ , hold true. It should be noted that these assumptions are not used in the main results presented in this article and needed only to strengthen some of these results in the convex case.

Remark 4.

Note that neither assumption $(A5)$ nor assumption $(A6)$ are satisfied for $\sigma(y)=\|y\|$ due to the fact that in this case $\Phi(y,\lambda,c)\geq 0$ for all $y\in Y$ , if $c>\|\lambda\|$ . Thus, if $\sigma(ty)\neq o(t)$ for some $y\in Y$ , then assumptions $(A5)$ and $(A6)$ might not hold true.

3.2 Augmented Lagrangians for problems with equality constraints

Let us now consider the following equality constrained problem:

\min\>f(x)\quad\text{subject to}\quad G(x)=0,\quad x\in Q.

The constraint $G(x)=0$ can obviously be rewritten as the cone constraint $G(x)\in K$ , if one puts $K=\{0\}$ . The binary relation $\preceq$ in this case coincides with the equality relation “ $=$ ”, and all functions are non-decreasing with respect to this relation.

Example 2 (Hestenes-Powell’s augmented Lagrangian).

Define $\Lambda=Y^{*}$ and

\Phi(y,\lambda,c)=\langle\lambda,y\rangle+\frac{c}{2}\|y\|^{2}.

Then the corresponding augmented Lagrangian is a particular case of the augmented Lagrangian from Example 1 with $\sigma(y)=0.5\|y\|^{2}$ . Therefore, this function $\Phi$ satisfies all basic assumptions, except for assumption $(A11)$ , in the general case, and it satisfies assumption $(A11)$ with $\Phi_{0}(\lambda)\equiv\lambda$ , if $Y$ is a Hilbert space. Note that in the case $Y=\mathbb{R}^{m}$ the corresponding augmented Lagrangian $\mathscr{L}(\cdot)$ coincides with the Hestenes-Powell augmented Lagrangian [29, 52, 5].

Example 3 (sharp Lagrangian).

Define $\Lambda=Y^{*}$ and

\Phi(y,\lambda,c)=\langle\lambda,y\rangle+c\|y\|.

Then the corresponding augmented Lagrangian is a particular case of the augmented Lagrangian from Example 1 with $\sigma(y)=\|y\|$ . Therefore, this function $\Phi$ satisfied all basic assumptions, except for assumptions $(A5)$ , $(A6)$ , and $(A11)$ .

In the case of equality constrained problems of the form

\min\>f(x)\quad\text{subject to}\quad g_{j}(x)=0,\quad i\in I,\quad x\in Q,

where $I=\{1,\ldots,m\}$ and $g_{i}\colon X\to\mathbb{R}$ are given function, one can define a more general class of augmented Lagrangians. This problem can be written as the problem $(\mathcal{P})$ with $Y=\mathbb{R}^{m}$ , $G(\cdot)=(g_{1}(\cdot),\ldots,g_{m}(\cdot))$ , and $K=\{0\}$ . Note that in this particular case the dual space $Y^{*}$ can be identified with $\mathbb{R}^{m}$ .

Example 4 (Mangasarian’s augmented Lagrangian).

Let $\phi\colon\mathbb{R}\to\mathbb{R}$ be a twice differentiable strictly convex function such that $\phi(0)=\phi^{\prime}(0)=0$ and $\phi^{\prime}(\cdot)$ is surjective. Define

\Phi(y,\lambda,c)=\sum_{i=1}^{m}\frac{1}{c}\big{(}\phi(cy_{i}+\lambda_{i})-\phi(\lambda_{i})\big{)}

for all $y=(y_{1},\ldots,y_{m})\in Y$ and $\lambda=(\lambda_{1},\ldots,\lambda_{m})\in\Lambda$ . Then the corresponding augmented Lagrangian $\mathscr{L}(\cdot)$ coincides with Mangasarian’s augmented Lagrangian from [46] (see also [76]). In the case $\phi(t)=0.5t^{2}$ , this augmented Lagrangian coincides with the Hestenes-Powell augmented Lagrangian. One can also put, e.g. $\phi(t)=|t|t^{2n}/(2n+1)$ or $\phi(t)=t^{2n}/2n$ for any $n\in\{1,2,\ldots\}$ .

Let $\Lambda=Y^{*}\cong\mathbb{R}^{m}$ . Then one can readily check that all assumptions, except for assumptions $(A9)$ and $(A9)_{s}$ , are satisfied in the general case (assumption $(A11)$ holds true with $\Phi_{0}(\lambda)\equiv(\phi^{\prime}(\lambda_{1}),\ldots,\phi^{\prime}(\lambda_{m}))$ ). Assumptions $(A9)$ and $(A9)_{s}$ are satisfied if and only if $\phi(t)=at^{2}$ for some $a>0$ . The validity of these assumptions in the case when the function $\phi$ is quadratic can be readily verified directly. Let us prove the converse statement.

Suppose that the function $\lambda\to\Phi(y,\lambda,c)$ is concave. Then applying the second order derivative test for concavity one gets that $\phi^{\prime\prime}(\lambda_{i})\geq\phi^{\prime\prime}(cy_{i}+\lambda_{i})$ for all $\lambda_{i},y_{i}\in\mathbb{R}$ and $c>0$ or, equivalently, $\phi^{\prime\prime}(\cdot)$ is a constant function. Hence bearing in mind the conditions $\phi(0)=\phi^{\prime}(0)=0$ one gets that $\phi(t)=at^{2}$ for some $a>0$ .

3.3 Augmented Lagrangians for problems with inequality constraints

Next we will present several examples of augmented Lagrangians for the inequality constrained problem

\min\>f(x)\quad\text{subject to}\quad g_{i}(x)\leq 0,\quad i\in I,\quad x\in Q,

(5)

where $I=\{1,\ldots,m\}$ and $g_{i}\colon X\to\mathbb{R}$ are given functions. This problem can be written as the problem $(\mathcal{P})$ with $Y=\mathbb{R}^{m}$ , $G(\cdot)=(g_{1}(\cdot),\ldots,g_{m}(\cdot))$ , and $K=\mathbb{R}_{-}^{m}$ , where $\mathbb{R}_{-}=(-\infty,0]$ . The dual space $Y^{*}$ can be identified with $\mathbb{R}^{m}$ , while $K^{*}$ can be identified with $\mathbb{R}^{m}_{+}$ , where $\mathbb{R}_{+}=[0,+\infty)$ . The binary relation $\preceq$ in this case is the coordinate-wise partial order.

All particular augmented Lagrangians for problem (5) used in optimization methods and known to the author are separable (except for nonlinear Lagrangians; see [60, 17, 72]), that is, the corresponding function $\Phi(y,\lambda,c)$ has the form

\Phi(y,\lambda,c)=\sum_{i=1}^{m}\Phi_{i}(y_{i},\lambda_{i},c)\quad\forall y=(y_{1},\ldots,y_{m}),\>\lambda=(\lambda_{1},\ldots,\lambda_{m})

(6)

for some functions $\Phi_{i}\colon\mathbb{R}^{2}\times(0,+\infty)\to\mathbb{R}\cup\{\pm\infty\}$ . Although one can can choose different functions $\Phi_{i}$ for different $i\in I$ (that is, for different inequality constraints), to the best of the author’s knowledge, only the case when $\Phi_{i}$ are the same for all $i\in I$ is considered in the vast majority of papers on augmented Lagrangians for inequality constrained problems.

Example 5 (essentially quadratic/Hestenes-Powell-Rockafellar’s augmented Lagrangian).

Let $\phi\colon\mathbb{R}\to\mathbb{R}$ be a twice continuously differentiable strictly convex function such that $\phi(0)=\phi^{\prime}(0)=0$ , and the derivative $\phi^{\prime}(\cdot)$ is surjective. Following Bertsekas [2, Section 5.1.2, Example 1], for any $y,\lambda\in\mathbb{R}$ define

P(y,\lambda)=\begin{cases}\lambda y+\phi(y),&\text{if }\lambda+\phi^{\prime}(y)\geq 0,\\ \min_{t\in\mathbb{R}}\big{(}\lambda t+\phi(t)\big{)},&\text{otherwise}\end{cases}

(note that the minimum is finite and attained at any $t$ such that $\lambda+\phi^{\prime}(t)=0$ , which exists due to the surjectivity of $\phi^{\prime}(\cdot)$ ) and put

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{1}{c}P(cy_{i},\lambda)\quad\forall i\in I.

The corresponding augmented Lagrangian $\mathscr{L}(\cdot)$ is called the essentially quadratic augmented Lagrangian for problem (5) (see [68, 39, 71]). In the case $\phi(t)=t^{2}/2$ one has

\Phi_{i}(y_{i},\lambda_{i},c)=\lambda_{i}\max\left\{y_{i},-\frac{\lambda_{i}}{c}\right\}+\frac{c}{2}\max\left\{y_{i},-\frac{\lambda_{i}}{c}\right\}^{2},

and $\mathscr{L}(\cdot)$ is the well-known Hestenes-Powell-Rockafellar augmented Lagrangian [29, 52, 55, 56, 57, 5], which is a particular case of the augmented Lagrangian from Example 1 with $\sigma(y)=\|y\|^{2}/2$ and $\|\cdot\|$ being the Euclidean norm.

Let $\lambda=Y^{*}=\mathbb{R}^{m}$ . Then one can readily verify that all basic assumptions, except for assumption $(A9)_{s}$ , hold true in the general case (assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\lambda$ ). Assumption $(A9)_{s}$ is satisfied for $\phi(t)=at^{2}$ , $a>0$ .

Example 6 (cubic augmented Lagrangian).

Let

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{1}{3c}\Big{(}\max\big{\{}\operatorname{sign}(\lambda_{i})\sqrt{|\lambda_{i}|}+cy_{i},0\big{\}}^{3}-|\lambda_{i}|^{3/2}\Big{)}\quad\forall i\in I.

Then $\mathscr{L}(\cdot)$ coincides with the cubic augmented Lagrangian [36]. One can easily check that all basic assumptions, except for assumptions $(A9)$ and $(A9)_{s}$ , are satisfied in this case with $\Lambda=Y^{*}=\mathbb{R}^{m}$ (assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\lambda$ ). Assumption $(A9)$ holds true, provided $\Lambda\subseteq K^{*}$ , while assumption $(A9)_{s}$ is not satisfied for any choice of $\Lambda$ .

Example 7 (Mangasarian’s augmented Lagrangian).

Let $\phi\colon\mathbb{R}\to\mathbb{R}$ be a twice continuously differentiable strictly convex function such that $\phi(0)=\phi^{\prime}(0)=0$ and the function $\phi^{\prime}(\cdot)$ is surjective. Define

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{1}{c}\Big{(}\phi\big{(}\max\{cy_{i}+\lambda_{i},0\}\big{)}-\phi(\lambda_{i})\Big{)}\quad\forall i\in I.

(7)

Then $\mathscr{L}(\cdot)$ coincides with the augmented Lagrangian introduced by Mangasarian [46] and studied, e.g. in [76]. Let $\Lambda=Y^{*}=\mathbb{R}^{m}$ . Then all basic assumptions, except for assumptions $(A9)$ and $(A9)_{s}$ , hold true (assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)=(\phi^{\prime}(\max\{\lambda_{1},0\}),\ldots,\phi^{\prime}(\max\{\lambda_{m},0\}))$ ). Assumptions $(A9)$ and $(A9)_{s}$ are satisfied for $\phi(t)=at^{2}$ with $a>0$ .

Example 8 (exponential-type augmented Lagrangian).

Let $\phi\colon\mathbb{R}\to\mathbb{R}$ be a twice differentiable strictly increasing function such that $\phi(0)=0$ . Define

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{\lambda_{i}}{c}\phi(cy_{i})\quad\forall i\in I.

If $\phi(t)=e^{t}-1$ , then $\mathscr{L}(\cdot)$ coincides with the exponential penalty function [2, 69, 68, 39, 71]. In turn, if $\phi(t)=2(\ln(e^{t}+1)-\ln 2)$ , then $\mathscr{L}(\cdot)$ is the Polyak’s log-sigmoid Lagrangian [50, 51]. In the general case we call the corresponding function $\mathscr{L}(\cdot)$ the exponential-type augmented Lagrangian.

Let $\Lambda=K^{*}=\mathbb{R}^{m}_{+}$ . Then assumptions $(A1)$ – $(A6)$ , $(A9)$ , $(A10)$ , and $(A15)$ are satisfied in the general case. Assumptions $(A7)$ and $(A8)$ hold true, provided the function $\phi$ is convex. Assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\phi^{\prime}(0)\lambda$ if and only if $\phi^{\prime}(0)\neq 0$ . Restricted versions of assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ (see Remark 1) are satisfied if and only if $\phi(t)/t\to 0$ as $t\to-\infty$ , while non-restricted versions of these assumptions are satisfied if and only if the function $\phi$ is bounded below. Finally, assumptions $(A9)_{s}$ , $(A12)$ , and $(A12)_{s}$ (put $\lambda=0$ ) are never satisfied for the exponential-type augmented Lagrangian.

Thus, all basic assumptions, except for assumptions $(A9)_{s}$ , $(A12)$ , and $(A12)_{s}$ , are valid for the exponential penalty function and the log-sigmoid Lagrangian.

Example 9 (penalized exponential-type augmented Lagrangian).

Suppose that $\phi\colon\mathbb{R}\to\mathbb{R}$ is a twice differentiable strictly increasing function such that $\phi(0)=0$ , and $\xi\colon\mathbb{R}\to\mathbb{R}$ is a twice continuously differentiable non-decreasing function such that $\xi(t)=0$ for all $t\leq 0$ and $\xi(t)>0$ for all $t>0$ (for example, one can set $\xi(t)=\max\{0,t\}^{3}$ ). Following Bertsekas [2, Section 5.1.2, Example 2] define

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{\lambda_{i}}{c}\phi(cy_{i})+\frac{1}{c}\xi(cy_{i})\quad\forall i\in I.

Then the function $\mathscr{L}(\cdot)$ is called the penalized exponential-type augmented Lagrangian [68, 39, 71], since it is obtained from the augmented Lagrangian from the previous example by adding the penalty term $\xi(cy_{i})/c$ .

Let $\Lambda=K^{*}=\mathbb{R}^{m}_{+}$ . Then assumptions $(A1)$ – $(A6)$ , $(A9)$ , $(A10)$ , and $(A15)$ , are satisfied in the general case. Assumptions $(A7)$ and $(A8)$ hold true, provided the functions $\phi$ and $\xi$ are convex. Assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\phi^{\prime}(0)\lambda$ if and only if $\phi^{\prime}(0)\neq 0$ . Assumptions $(A12)$ and $(A12)_{s}$ are valid, provided $\xi(t)/t\to+\infty$ as $t\to\infty$ and $\phi$ is either bounded below or convex. Restricted assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ , hold true if and only if $\phi(t)/t\to 0$ as $t\to-\infty$ , while non-restricted versions of these assumptions hold true if and only if $\phi$ is bounded below.

Thus, if $\phi(t)=e^{t}-1$ or $\phi(t)=2(\ln(e^{t}+1)-\ln 2)$ and $\xi(t)=\max\{0,t\}^{3}$ , then all basic assumptions, except for assumption $(A9)_{s}$ , hold true.

Example 10 (p-th power augmented Lagrangian).

Let $b\geq 0$ and a continuous non-decreasing function $\phi\colon\mathbb{R}\to\mathbb{R}_{+}$ be such that $\phi(t)>\phi(b)>0$ for all $t>b$ . For example, one can set $\phi(t)=e^{t}$ with $b\geq 0$ or $\phi(t)=\max\{0,t\}$ with $b>0$ . By our assumption the inequality $g_{i}(x)\leq 0$ is satisfied if and only if $\phi(g_{i}(x)+b)/\phi(b)\leq 1$ . Furthermore, $\phi(g_{i}(x)+b)\geq 0$ for all $x\in X$ . Define

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{\lambda_{i}}{c+1}\left(\left(\frac{\phi(y_{i}+b)}{\phi(b)}\right)^{c+1}-1\right)\quad\forall i\in I.

Then $\mathscr{L}(\cdot)$ coincides with the p-th power augmented Lagrangian [37, 75, 39].

Let $\Lambda=K^{*}=\mathbb{R}^{m}_{+}$ . Then assumptions $(A1)$ – $(A7)$ , $(A9)$ , $(A10)$ , $(A13)$ – $(A15)$ , $(A13)_{s}$ , and $(A14)_{s}$ hold true. Assumption $(A8)$ is satisfied, if the function $\phi$ is convex. Assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\phi^{\prime}(b)\lambda$ , provided $\phi$ is differentiable and $\phi^{\prime}(b)\neq 0$ . Finally, assumptions $(A9)_{s}$ , $(A12)$ , and $(A12)_{s}$ are not satisfied for the p-th power augmented Lagrangian.

Remark 5.

Let $\phi$ be as in the previous example and $\xi$ be as in Example 9. Then by analogy with the penalized exponential-type augmented Lagrangian one can define the penalized p-th power augmented Lagrangian as follows:

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{\lambda_{i}}{c+1}\left(\left(\frac{\phi(y_{i}+b)}{\phi(b)}\right)^{c+1}-1\right)+\frac{1}{c}\xi(cy_{i})\quad\forall i\in I.

If the function $\phi$ is convex and differentiable, $\phi^{\prime}(b)\neq 0$ , $\xi$ is convex, and $\xi(t)/t\to+\infty$ as $t\to\infty$ , then one can verify that the penalized p-th power augmented Lagrangian satisfies all basic assumption, except for assumption $(A9)_{s}$ . Let us also mention that one can apply this trick of adding the penalty term $\xi(cy_{i})/c$ to any other augmented Lagrangian for inequality constrained problems, if it does not satisfy assumptions $(A12)$ and $(A12)_{s}$ , in order to construct the penalized version of this augmented Lagrangian satisfying assumptions $(A12)$ and $(A12)_{s}$ and having all other properties of the non-penalized version.

Example 11 (hyperbolic-type augmented Lagrangian).

Let $\phi\colon\mathbb{R}\to\mathbb{R}$ be a twice differentiable strictly increasing convex function such that $\phi(0)=0$ . Define

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{1}{c}\phi(c\lambda_{i}y_{i})\quad\forall i\in I.

If $\phi(t)=t+\sqrt{t^{2}+1}-1$ , then $\mathscr{L}(\cdot)$ coincides with the hyperbolic augmented Lagrangian [78, 53]. In the general case we call such function $\mathscr{L}(x,\lambda,c)$ the hyperbolic-type augmented Lagrangian.

Let $\Lambda=K^{*}=\mathbb{R}^{m}_{+}$ . Then assumptions $(A1)$ – $(A8)$ , $(A10)$ , $(A11)$ , and $(A15)$ are satisfied in the general case (assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\phi^{\prime}(0)\lambda$ ). Assumption $(A9)$ is satisfied if and only if $\phi$ is a linear function. Restricted assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ , hold true if and only if $\phi(t)/t\to 0$ as $t\to-\infty$ , while non-restricted versions of these assumptions hold true if and only if $\phi$ is bounded below. Finally, assumptions $(A9)_{s}$ , $(A12)$ , and $(A12)_{s}$ are never satisfied for the hyperbolic-type augmented Lagrangian.

Example 12 (modified barrier function).

Let $\phi\colon(-\infty,1)\to\mathbb{R}$ be a twice differentiable strictly increasing function such that $\phi(0)=0$ and $\phi(t)\to+\infty$ as $t\to 1$ . Define

\Phi_{i}(y_{i},\lambda_{i},c)=\begin{cases}\frac{\lambda_{i}}{c}\phi(cy_{i}),&\text{if }cy_{i}<1,\\ +\infty,&\text{otherwise}\end{cases}\qquad\forall i\in I.

Then augmented Lagrangian $\mathscr{L}(\cdot)$ coincides with the modified barrier function introduced by R. Polyak [49]. In particular, in the case $\phi(t)=-\ln(1-t)$ the augmented Lagrangian $\mathscr{L}(\cdot)$ is the modified Frisch function, while in the case $\phi(t)=1/(1-t)-1$ the augmented Lagrangian $\mathscr{L}(\cdot)$ is the modified Carrol function [49] (see also [68, 39, 71]).

Let $\Lambda=K^{*}=\mathbb{R}^{m}_{+}$ . Then assumptions $(A1)$ – $(A6)$ , $(A9)$ , $(A10)$ , $(A12)$ , $(A12)_{s}$ , and $(A15)$ are satisfied in the general case. Assumptions $(A7)$ and $(A8)$ hold true, if the function $\phi$ is convex. Assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)=\phi^{\prime}(0)\lambda$ if and only if $\phi^{\prime}(0)\neq 0$ . Restricted assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ hold true if and only if $\phi(t)/t\to 0$ as $t\to-\infty$ , while non-restricted versions of these assumptions are valid if and only if the function $\phi$ is bounded below. Finally, assumption $(A9)_{s}$ cannot hold true for the modified barrier function.

Thus, the modified Carrol function satisfies all basic assumptions, except for assumption $(A9)_{s}$ , while the modified Frisch functions satisfies all assumptions, except for $(A9)_{s}$ and non-restricted assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ .

Example 13 (He-Wu-Meng’s augmented Lagrangian).

Let

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{1}{c}\int_{0}^{cy_{i}}\big{(}\sqrt{t^{2}+\lambda_{i}^{2}}+t\big{)}\,dt\quad\forall i\in I.

Then $\mathscr{L}(\cdot)$ coincides with the augmented Lagrangian introduced by He, Wu, and Meng [28]. Let us note that

\Phi_{i}(y_{i},\lambda_{i},c)=\frac{y_{i}}{2}\sqrt{(cy_{i})^{2}+\lambda_{i}^{2}}+\frac{cy_{i}^{2}}{2}+\frac{\lambda_{i}^{2}}{2c}\ln\big{(}\sqrt{(cy_{i})^{2}+\lambda_{i}^{2}}+cy_{i}\big{)}-\frac{\lambda_{i}^{2}}{2c}\ln|\lambda_{i}|,

if $\lambda_{i}\neq 0$ , and $\Phi_{i}(y_{i},0,c)=cy_{i}(y_{i}+|y_{i}|)/2$ .

Let $\Lambda=Y^{*}=\mathbb{R}^{m}$ . Then assumptions $(A1)$ – $(A5)$ , $(A7)$ , $(A8)$ , $(A10)$ , $(A11)$ with $\Phi_{0}(\lambda)\equiv\lambda$ , $(A12)$ , $(A12)_{s}$ , $(A15)$ , and restricted assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ are satisfied in the general case. Assumption $(A6)$ holds true if and only if $\Lambda\subseteq K^{*}$ , since $\Phi(0,\lambda,c)=0$ for all $\lambda\in Y^{*}$ . Finally, assumptions $(A9)$ , $(A9)_{s}$ , $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ are not satisfied for He-Wu-Meng’s augmented Lagrangian in the general case. Let us note that the non-restricted versions of the last 4 assumptions are not satisfied due to the fact that $\Phi_{i}(y,\lambda,c)\to-\infty$ as $y\to-\infty$ .

Remark 6.

Many more particular examples of augmented Lagrangians for inequality constrained optimization problems can be found in [3].

3.4 Augmented Lagrangians for problems with second order cone constraints

Let us now consider nonlinear second order cone programming problems:

\min\>f(x)\quad\text{subject to}\quad g_{i}(x)\in\mathcal{K}_{\ell_{i}+1},\quad i\in I,\quad x\in Q,

(8)

where $g_{i}\colon X\to\mathbb{R}^{\ell_{i}+1}$ , $i\in I:=\{1,\ldots,m\}$ , are given functions,

\mathcal{K}_{\ell_{i}+1}=\Big{\{}y=(y^{0},\overline{y})\in\mathbb{R}\times\mathbb{R}^{\ell_{i}}\Bigm{|}y^{0}\geq\|\overline{y}\|\Big{\}}

is the second order (Lorentz/ice cream) cone of dimension $\ell_{i}+1$ , and $\|\cdot\|$ is the Euclidean norm.

Problem (8) can be rewritten as the problem $(\mathcal{P})$ with

Y=\mathbb{R}^{\ell_{1}+1}\times\ldots\times\mathbb{R}^{\ell_{m}+1},\quad K=\mathcal{K}_{\ell_{1}+1}\times\ldots\times\mathcal{K}_{\ell_{m}+1},

and $G(\cdot)=(g_{1}(\cdot),\ldots,g_{m}(\cdot))$ . Note that the dual space $Y^{*}$ can be identified with $Y$ , while the polar cone $K^{*}$ can be identified with $(-\mathcal{K}_{\ell_{1}+1})\times\ldots\times(-\mathcal{K}_{\ell_{m}+1})$ .

Example 14 (Hestenes-Powell-Rockafellar’s augmented Lagrangian).

For any $y=(y_{1},\ldots,y_{m})\in Y$ , $\lambda=(\lambda_{1},\ldots,\lambda_{m})\in Y^{*}$ , and $c>0$ define

\Phi(y,\lambda,c)=\frac{c}{2}\sum_{i=1}^{m}\left[\operatorname{dist}^{2}\left(y_{i}+\frac{1}{c}\lambda_{i},\mathcal{K}_{\ell_{i}+1}\right)-\frac{1}{c^{2}}\|\lambda_{i}\|^{2}\right].

This function $\Phi$ is a particular case of the function $\Phi$ from Example 1 with $\sigma(y)=(\|y_{1}\|^{2}+\ldots+\|y_{m}\|^{2})/2$ (see [40, 41, 84]). Therefore it satisfies all basic assumptions with $\Lambda=Y^{*}$ (assumption $(A11)$ holds true with $\Phi_{0}(\lambda)\equiv\lambda$ ).

To define another augmented Lagrangian for optimization problems with nonlinear second order cone constraints, recall (see [26, 64]) that in the context of such problems Löwner’s operator associated with a function $\psi\colon\mathbb{R}\to\mathbb{R}$ is defined as follows:

\Psi(y)=\frac{1}{2}\begin{pmatrix}\psi(y^{0}+\|y\|)+\psi(y^{0}-\|y\|)\\ \Big{(}\psi(y^{0}+\|y\|)-\psi(y^{0}-\|y\|)\Big{)}\frac{\overline{y}}{\|\overline{y}\|}\end{pmatrix}

for any $y\in(y^{0},\overline{y})\in\mathbb{R}\times\mathbb{R}^{l}$ with $\overline{y}\neq 0$ , and $\Psi(y)=(\psi(y^{0}),0)$ for $y=(y^{0},0)$ . One can readily verify that if $\psi(0)=0$ and the function $\psi$ is strictly increasing, then $-\Psi(-y)\in\mathcal{K}_{\ell+1}$ for any $y\in\mathcal{K}_{\ell+1}$ , while $-\Psi(-y)\notin\mathcal{K}_{\ell+1}$ for any $y\notin\mathcal{K}_{\ell+1}$ .

Example 15 (exponential-type augmented Lagrangian/modified barrier function).

Let $\psi\colon\mathbb{R}\to\mathbb{R}\cup\{+\infty\}$ be a non-decreasing convex function such that $\operatorname{dom}\psi=(-\infty,\varepsilon_{0})$ for some $\varepsilon_{0}\in(0,+\infty]$ , $\psi(t)\to+\infty$ as $t\to\varepsilon_{0}$ in the case $\varepsilon_{0}<+\infty$ and $\psi(t)/t\to+\infty$ as $t\to+\infty$ in the case $\varepsilon_{0}=+\infty$ . Suppose also that $\psi$ is twice differentiable on $\operatorname{dom}\psi$ , $\psi(0)=0$ , and $\psi^{\prime}(0)=1$ . For any $y=(y_{1},\ldots,y_{m})\in Y$ and $\lambda=(\lambda_{1},\ldots,\lambda_{m})\in Y^{*}$ define

\Phi(y,\lambda,c)=-\frac{1}{c}\sum_{i=1}^{m}\big{\langle}\lambda_{i},\Psi(-cy_{i})\big{\rangle},

if $-y^{0}+\|\overline{y}\|<\varepsilon_{0}/c$ , and $\Phi(y,\lambda,c)=+\infty$ otherwise. The corresponding augmented Lagrangian, which can be viewed as an extension of augmented Lagrangian from Examples 8 and 12 to the case of nonlinear second order cone programming problems, was introduced in [81].

Let $\Lambda=K^{*}$ . Then assumptions $(A1)$ – $(A7)$ , $(A9)$ – $(A11)$ , and $(A15)$ hold true in the general case (assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\lambda$ by [81, Lemma 3.1]). Assumptions $(A12)$ and $(A12)_{s}$ are satisfied if and only if $\varepsilon_{0}<+\infty$ . Restricted assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ hold true if and only if $\psi(t)/t\to 0$ as $t\to-\infty$ , while non-restricted versions of these assumptions hold true if and only if $\psi$ is bounded below. Finally, assumptions $(A8)$ and $(A9)_{s}$ are not satisfied for the function $\Phi$ from this example.

3.5 Augmented Lagrangians for problems with semidefinite constraints

Let us now consider nonlinear semidefinite programming problems of the form:

\min\>f(x)\quad\text{subject to}\quad G(x)\preceq\mathbb{O}_{\ell\times\ell},\quad x\in Q,

(9)

where $G\colon X\to\mathbb{S}^{\ell}$ is a given function, $\mathbb{S}^{\ell}$ is the space of all real symmetric matrices of order $\ell$ endowed with the inner product $\langle A,B\rangle=\operatorname{Tr}(AB)$ and the corresponding norm $\|A\|_{F}=\sqrt{\operatorname{Tr}(A^{2})}$ , $A,B\in\mathbb{S}^{\ell}$ , which is called the Frobenius norm, $\operatorname{Tr}(\cdot)$ is the trace operator, $\mathbb{O}_{\ell\times\ell}$ is the zero matrix of order $\ell\times\ell$ , and $\preceq$ is the Löwner partial order on the space $\mathbb{S}^{\ell}$ , that is, $A\preceq B$ for some $A,B\in\mathbb{S}^{\ell}$ if and only if the matrix $B-A$ is positive semidefinite.

Problem (9) can be written as the problem $(\mathcal{P})$ with $Y=\mathbb{S}^{\ell}$ and $K$ being the cone of negative semidefinite matrices $\mathbb{S}^{\ell}_{-}$ . Note that the binary relation induced by the cone $-K$ coincides with the Löwner partial order. The dual space $Y^{*}$ in this case can be identified with $\mathbb{S}^{\ell}$ , while the polar cone $K^{*}$ can be identified with the cone of positive semidefinite matrices $\mathbb{S}^{\ell}_{+}$ .

Example 16 (Hestenes-Powell-Rockafellar’s augmented Lagrangian).

For any $y,\lambda\in\mathbb{S}^{\ell}$ and $c>0$ define

\Phi(y,\lambda,c)=\frac{1}{2c}\Big{(}\operatorname{Tr}\big{(}[cy+\lambda]_{+}^{2}\big{)}-\operatorname{Tr}(\lambda^{2})\Big{)},

where $[\cdot]_{+}$ is the projection of a matrix onto the cone $\mathbb{S}_{+}^{\ell}$ . This function $\Phi$ is a particular case of the function $\Phi$ from Example 1 with $\sigma(y)=\|y\|_{F}^{2}/2$ and, therefore, it satisfies all basic assumptions with $\Lambda=Y^{*}$ (assumption $(A11)$ holds true with $\Phi_{0}(\lambda)\equiv\lambda$ ). The corresponding augmented Lagrangian and optimization methods for nonlinear semidefinite programming problems utilising this augmented Lagrangian were studied in [33, 67, 65, 83, 73, 66, 45, 74, 77, 80].

One can also extend the exponential-type augmented Lagrangian/modified barrier function for inequality constrained problems to the case of nonlinear semidefinite programming problems. To define such extension, recall that the matrix function/Löwner’s operator [30, 64] associated with a function $\psi\colon\mathbb{R}\to\mathbb{R}$ is defined as follows:

\Psi(y)=E\operatorname{diag}\Big{(}\psi(\sigma_{1}(y)),\ldots,\psi(\sigma_{\ell}(y))\Big{)}E^{T}\quad\forall y\in Y,

where $y=E\operatorname{diag}(\sigma_{1}(y),\ldots,\sigma_{\ell}(y))E^{T}$ is a spectral decomposition of a matrix $y\in\mathbb{S}^{\ell}$ , while $\sigma_{1}(y),\ldots,\sigma_{\ell}(y)$ are the eigenvalue of $y$ listed in the decreasing order. Note that if the function $\psi$ is non-decreasing and $\psi(0)=0$ , then $\Psi(y)\in\mathbb{S}^{\ell}_{-}$ for any $y\in\mathbb{S}_{-}^{\ell}$ .

Example 17 (exponential-type augmented Lagrangian/modified barrier function).

Let a function $\psi\colon\mathbb{R}\to\mathbb{R}\cup\{+\infty\}$ be as in Example 15. For any $y,\lambda\in\mathbb{S}^{\ell}$ and $c>0$ define

\Phi(y,\lambda,c)=\frac{1}{c}\big{\langle}\lambda,\Psi(cy)\big{\rangle},

if $c\sigma_{1}(y)<\varepsilon_{0}$ , and $\Phi(y,\lambda,c)=+\infty$ otherwise. The corresponding augmented Lagrangian $\mathscr{L}(\cdot)$ is an extension of augmented Lagrangians for inequality constrained optimization problems from Examples 8 and 12. It was studied in details in [63, 47, 38, 82, 43].

Let $\Lambda=K^{*}=\mathbb{S}_{+}^{\ell}$ . Then assumptions $(A1)$ – $(A7)$ , $(A9)$ – $(A11)$ , and $(A15)$ hold true in the general case (assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\lambda$ by [43, Proposition 4.2]). Assumption $(A8)$ is satisfied, if the matrix function $\Psi(\cdot)$ is monotone and convex (see, e.g. [30]). Assumptions $(A12)$ and $(A12)_{s}$ are satisfied if and only if $\varepsilon_{0}<+\infty$ . Restricted assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ hold true if and only if $\psi(t)/t\to 0$ as $t\to-\infty$ , while non-restricted versions of these assumptions hold true if and only if $\psi$ is bounded below. Finally, assumption $(A9)_{s}$ is not satisfied for the function $\Phi$ from this example.

Example 18 (penalized exponential-type augmented Lagrangian).

Let a function $\psi\colon\mathbb{R}\to\mathbb{R}$ be a twice continuously differentiable non-decreasing convex function such that $\psi(t)/t\to+\infty$ as $t\to+\infty$ , $\psi(0)=0$ and $\psi^{\prime}(0)=1$ . Let also $\xi\colon\mathbb{R}\to\mathbb{R}$ be a twice continuously differentiable non-decreasing convex function such that $\xi(t)=0$ for all $t\leq 0$ and $\xi(t)>0$ for all $t>0$ . Denote by $\Xi(\cdot)$ the Löwner’s operator associated with $\xi(\cdot)$ . For any $y,\lambda\in\mathbb{S}^{\ell}$ and $c>0$ define

\Phi(y,\lambda,c)=\frac{1}{c}\big{\langle}\lambda,\Psi(cy)\big{\rangle}+\frac{1}{c}\operatorname{Tr}\Big{(}\Xi(cy)\Big{)}.

The corresponding augmented Lagrangian $\mathscr{L}(\cdot)$ was introduced in [43] and is an extrension of the penalized exponential-type augmented Lagrangian from Example 9 to the case of nonlinear semidefinite programming problems.

Let $\Lambda=K^{*}=\mathbb{S}_{+}^{\ell}$ . Then assumptions $(A1)$ – $(A7)$ , $(A9)$ – $(A11)$ , and $(A15)$ hold true in the general case (assumption $(A11)$ is satisfied with $\Phi_{0}(\lambda)\equiv\lambda$ by [43, Proposition 4.2]). Assumption $(A8)$ is satisfied, provided the matrix functions $\Psi(\cdot)$ and $\Xi(\cdot)$ are monotone and convex. Assumptions $(A12)$ and $(A12)_{s}$ are satisfied, if $\xi(t)/t\to+\infty$ as $t\to+\infty$ . Restricted assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ hold true if and only if $\psi(t)/t\to 0$ as $t\to-\infty$ , while non-restricted versions of these assumptions hold true if and only if $\psi$ is bounded below. Finally, assumption $(A9)_{s}$ is not satisfied, regardless of the choice of $\psi$ and $\xi$ .

3.6 Augmented Lagrangians for problems with pointwise inequality constraints

Let $(T,\mathfrak{A},\mu)$ be a measure space and $X$ be some space of functions $x\colon T\to\mathbb{R}^{m}$ . For example, $X$ can be defined as $L^{p}(T,\mathfrak{A},\mu)$ or as the Sobolev space, when $T$ is an open subset of $\mathbb{R}^{d}$ . Let us consider problems with pointwise inequality constraints of the form:

\min\>f(x)\quad\text{subject to}\quad g(x(t),t)\leq 0\enspace\text{for a.e. }t\in T,\quad x\in Q,

(10)

where $g\colon X\times T\to\mathbb{R}$ is a given function such that $g(x(\cdot),\cdot)\in L^{p}(T,\mathfrak{A},\mu)$ for some fixed $p\in[1,+\infty)$ and all $x\in X$ .

One can rewrite problem (10) as the problem $(\mathcal{P})$ with $Y=L^{p}(T,\mathfrak{A},\mu)$ , $K$ being the cone of nonpositive function $L^{p}_{-}(T,\mathfrak{A},\mu)$ , and $G(x)(\cdot)=g(x(\cdot),\cdot)$ for all $x\in X$ . In this case the dual space $Y^{*}$ can be identified with $L^{q}(T,\mathfrak{A},\mu)$ , where $q\in(1,+\infty]$ is the conjugate exponent of $p$ , that is, $1/p+1/q=1$ ( $q=+\infty$ , if $p=1$ ). In turn, the polar cone $K^{*}$ can be identified with the cone of nonnegative functions $L^{q}_{+}(T,\mathfrak{A},\mu)$ .

For the sake of shortness we will consider only an augmented Lagrangian for problem (10) based on the Hestenes-Powell-Rockafellar augmented Lagrangian. However, it should be mentioned that one can define an augmented Lagrangian for this problem based on any other augmented Lagrangian for inequality constrained optimization problems.

Example 19 (Hestenes-Powell-Rockafellar augmented Lagrangian).

Suppose that either $p=2$ or $p\geq 2$ and the measure $\mu$ is finite. For any $y\in Y:=L^{p}(T,\mathfrak{A},\mu)$ , $\lambda\in Y^{*}\cong L^{q}(T,\mathfrak{A},\mu)$ , and $c>0$ define

\Phi(y,\lambda,c)=\int_{T}\left(\lambda(t)\max\left\{y(t),-\frac{\lambda(t)}{c}\right\}+\frac{c}{2}\max\left\{y(t),-\frac{\lambda(t)}{c}\right\}^{2}\right)d\mu(t).

Observe that

\left|\lambda(t)\max\left\{y(t),-\frac{\lambda(t)}{c}\right\}+\frac{c}{2}\max\left\{y(t),-\frac{\lambda(t)}{c}\right\}^{2}\right|\\ \leq\frac{1+c}{2}|y(t)|^{2}+\left(\frac{1}{2}+\frac{1}{2c}\right)|\lambda(t)|^{2}.

Therefore, the value $\Phi(y,\lambda,c)$ is correctly defined and finite for any $y\in Y$ , $\lambda\in Y^{*}$ , and $c>0$ , if $p=2$ or $p\geq 2$ and the measure $\mu$ is finite.

Let $\Lambda=Y^{*}$ . Then one can readily verify that all basic assumptions hold true in the general case, except for assumptions $(A12)$ and $(A12)_{s}$ . Assumptions $(A12)$ and $(A12)_{s}$ are satisfied in the case $p=2$ , since

\Phi(y,\lambda,c)-\Phi(y,\lambda,c_{0})\geq(c-c_{0})\int_{T}\max\{0,y(t)\}^{2}d\mu(t)=(c-c_{0})\operatorname{dist}(y,K)^{2}

for all $y\in Y$ , $\lambda\in\Lambda$ , and $c\geq c_{0}>0$ (see the proof of the validity of assumptions $(A12)$ and $(A12)_{s}$ for the Rockafellar-Wets’ augmented Lagrangian).

3.7 Some comments on particular augmented Lagrangians

Before we proceed to the analysis of the augmented dual problem and primal-dual augmented Lagrangian methods, let us make a few general observations about the presented examples:

1.

All basic assumptions, except for assumption $(A9)_{s}$ , are satisfied for all particular augmented Lagrangians presented above (under appropriate additional assumptions), except for the exponential-type augmented Lagrangian (Examples 8, 15, and 17), the p-th power augmented Lagrangian (Example 10), the hyperbolic-type augmented Lagrangian (Example 11), and He-Wu-Meng’s augmented Lagrangian (Example 13). The exponential-type augmented Lagrangian (the case $\varepsilon_{0}=+\infty$ in Examples 15 and 17) and the p-th power augmented Lagrangian do not satisfy assumptions $(A12)$ and $(A12)_{s}$ , the hyperbolic-type augmented Lagrangian does not satisfy assumptions $(A9)$ , $(A12)$ , and $(A12)_{s}$ , while He-Wu-Meng’s augmented Lagrangian does not satisfy assumption $(A9)$ and non-restricted versions of assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ .
2.

Assumption $(A9)_{s}$ is satisfied only for the Hestenes-Powell-Rockafellar augmented Lagrangian (Examples 2, 5, 14, 16, and 19) and its generalization, Rockafellar-Wets’ augmented Lagrangian (Example 1.
3.

For assumptions $(A1)$ , $(A6)$ – $(A8)$ , $(A12)$ – $(A15)$ , and $(A12)_{s}$ – $(A14)_{s}$ to be satisfied for the exponential-type augmented Lagrangian (Examples 8, 15, and 17), the penalized exponential-type augmented Lagrangian (Examples 9 and 18), the modified barrier function (Example 12), and the p-th power augmented Lagrangian (Example 10), and the hyperbolic-type augmented Lagrangian (Example 11) it is necessary that $\Lambda\subseteq K^{*}$ . In contrast, for all other paritcular augmented Lagrangians presented in this section these assumptions are satisfied for $\Lambda=Y^{*}$ (in the case of the He-Wu-Meng’s augmented Lagrangian only the restricted versions of assumptions $(A13)$ , $(A13)_{s}$ , $(A14)$ , and $(A14)_{s}$ are satisfied for $\Lambda=Y^{*}$ ).
4.

Our theory of augmented Lagrangians encompasses penalty functions of the form $F_{c}(\cdot)=f(\cdot)+c\operatorname{dist}(G(\cdot),K)^{\alpha}$ with $\alpha>0$ . One simply needs to define $\Phi(y,\lambda,c):=c\operatorname{dist}(y,K)^{\alpha}$ . This function $\Phi$ satisfied assumptions $(A1)$ , $(A2)$ , $(A4)$ , $(A7)$ , $(A9)$ , $(A9)_{s}$ , $(A10)$ , $(A12)$ – $(A15)$ and $(A12)_{s}$ – $(A14)_{s}$ for any choice of the set $\Lambda$ (assumption $(A8)$ is satisfied, if $\alpha\geq 1$ , while assumption $(A6)$ is satisfied, if $\Lambda\subseteq K^{*}$ ), which means that the main results of this paper on the zero duality gap and convergence of augmented Lagrangian methods can be applied to the penalty function $F_{c}(\cdot)$ .

4 Duality theory

One of the central concepts of the theory of augmented Lagrangians and corresponding optimization methods is the (augmented) dual problem:

\max_{(\lambda,c)}\>\Theta(\lambda,c)\quad\text{subject to}\quad\lambda\in\Lambda,\enspace c>0,\qquad

(𝒟)

where

\Theta(\lambda,c):=\inf_{x\in Q}\mathscr{L}(x,\lambda,c)\quad\forall\lambda\in\Lambda,\>c>0

(11)

is the (augmented) dual function. As is well-known and will be discussed in details below, convergence of augmented Lagrangian methods is interlinked with various properties of the dual problem. Therefore, before turning to augmented Lagrangian methods, we need to analyse how standard duality results are translated into our axiomatic augmented Lagrangian setting.

Remark 7.

Note that if assumption $(A9)_{s}$ is satisfied, then the dual function $\Theta$ is concave and the augmented dual problem $(\mathcal{D})$ is a concave optimization problem, even if the original problem $(\mathcal{P})$ is nonconvex. Furthermore, assumption $(A10)$ ensures that the dual function is upper semicontinuous, as the infimum of the family $\{\mathscr{L}(x,\cdot)\}$ , $x\in Q$ , of upper semicontinuous functions.

4.1 Zero duality gap property

Let us first study how optimal values of the problems $(\mathcal{P})$ and $(\mathcal{D})$ relate to each other. We start by showing that under an essentially nonrestrictive assumption the optimal value of the augmented dual problem does not exceed the optimal value of the primal problem.

Proposition 1 (weak duality).

Let assumption $(A1)$ hold true. Then

\Theta(\lambda,c)\leq f(x)\quad\forall x\in\Omega,\>\lambda\in\Lambda,\>c>0,

where $\Omega$ is the feasible region of the problem $(\mathcal{P})$ . In pacritular, $\Theta_{*}\leq f_{*}$ , where $\Theta_{*}$ is the optimal value of the problem $(\mathcal{D})$ and $f_{*}$ is the optimal value of the problem $(\mathcal{P})$ .

Proof.

By assumption $(A1)$ for any point $x\in\Omega$ and all $\lambda\in\Lambda$ and $c>0$ one has $\mathscr{L}(x,\lambda,c)\leq f(x)$ . Hence applying the definition of $\Theta$ (see (11)) and the fact that $\Omega\subseteq Q$ one obtains the required result. ∎

As is well-known, the optimal values of the primal and dual problems might not coincide, especially for nonconvex problems. In this case $\Theta_{*}<f_{*}$ and the quantity $f_{*}-\Theta_{*}>0$ is called the duality gap.

Definition 1.

One says that there is zero duality gap between the primal problem $(\mathcal{P})$ and the dual problem $(\mathcal{D})$ (or that the augmented Lagrangian $\mathscr{L}(\cdot)$ has the zero duality gap property, or that the strong duality with respect to the augmented Lagrangian $\mathscr{L}(\cdot)$ holds true), if $\Theta_{*}=f_{*}$ .

Our aim now is to understand what kind of assumptions one must impose on the function $\Phi$ to ensure that the corresponding augmented Lagrangian $\mathscr{L}(x,\lambda,c):=f(x)+\Phi(G(x),\lambda,c)$ has the zero duality gap property. To this end, we extend the standard result (see, e.g. [59]) connecting the optimal value of the dual problem with the behaviour of the optimal value (perturbation) function

\beta(p)=\inf\big{\{}f(x)\bigm{|}x\in Q\colon G(x)-p\in K\big{\}}\quad\forall p\in Y

of the problem $(\mathcal{P})$ to our case. Denote by $\operatorname{dom}_{\lambda}\Theta$ the effective domain of $\Theta$ in $\lambda$ , that is, $\operatorname{dom}_{\lambda}\Theta=\{\lambda\in\Lambda\mid\exists c>0\colon\Theta(\lambda,c)>-\infty\}$ . Note that $\lambda\in\operatorname{dom}_{\lambda}\Theta$ if and only if the function $\mathscr{L}(\cdot,\lambda,c)$ is bounded below on $Q$ for some $c>0$ .

Theorem 2 (optimal dual value formula).

Let assumptions $(A1)$ , $(A7)$ , and $(A12)$ – $(A14)$ hold true. Then

\Theta_{*}:=\sup_{\lambda\in\Lambda,c>0}\Theta(\lambda,c)=\begin{cases}-\infty,&\text{if }\operatorname{dom}_{\lambda}\Theta=\emptyset,\\ \min\left\{f_{*},\liminf_{p\to 0}\beta(p)\right\},&\text{if }\operatorname{dom}_{\lambda}\Theta\neq\emptyset.\end{cases}

In addition, $\Theta_{*}=\lim\limits_{c\to+\infty}\Theta(\lambda,c)$ for all $\lambda\in\operatorname{dom}_{\lambda}\Theta$ .

Proof.

Note that $\Theta(\lambda,c)=-\infty$ for all $\lambda\in\Lambda$ and $c>0$ , and $\Theta_{*}=-\infty$ , if $\operatorname{dom}_{\lambda}\Theta=\emptyset$ . Therefore, below we can suppose that $\operatorname{dom}_{\lambda}\Theta\neq\emptyset$ .

By assumption $(A7)$ the function $\Phi(y,\lambda,c)$ is non-decreasing in $c$ . Therefore the functions $\mathscr{L}(x,\lambda,c)$ and $\Theta(\lambda,c)$ are non-decreasing in $c$ for all $x\in X$ and $\lambda\in\Lambda$ . Hence, as is easy to see, one has

\sup_{\lambda\in\Lambda,c>0}\Theta(\lambda,c)=\sup_{\lambda\in\Lambda}\sup_{c>0}\Theta(\lambda,c)=\sup_{\lambda\in\Lambda}\lim_{c\to+\infty}\Theta(\lambda,c)=\sup_{\lambda\in\operatorname{dom}_{\lambda}\Theta}\lim_{c\to+\infty}\Theta(\lambda,c).

Consequently, it is sufficient to check that

\Theta_{*}(\lambda):=\lim\limits_{c\to+\infty}\Theta(\lambda,c)=\min\left\{f_{*},\liminf_{p\to 0}\beta(p)\right\}\quad\forall\lambda\in\operatorname{dom}_{\lambda}\Theta.

(12)

Let us prove this equality.

Fix any $\lambda\in\operatorname{dom}_{\lambda}\Theta$ and any unbounded strictly increasing sequence $\{c_{n}\}\subset(0,+\infty)$ such that the function $\mathscr{L}(\cdot,\lambda,c_{0})$ is bounded below on $Q$ (such $c_{0}$ exists by the definition of $\operatorname{dom}_{\lambda}\Theta$ ). Then by Proposition 1 one has

\begin{split}f_{*}\geq\Theta_{*}(\lambda)\geq&\Theta(\lambda,c_{n})\geq\Theta(\lambda,c_{0})>-\infty\quad\forall n\in\mathbb{N},\quad\\ &\lim_{n\to\infty}\Theta(\lambda,c_{n})=\Theta_{*}(\lambda).\end{split}

(13)

Let $\{x_{n}\}\subset Q$ be a sequence such that $\mathscr{L}(x_{n},\lambda,c_{n})\leq\Theta(\lambda,c_{n})+1/(n+1)$ for all $n\in\mathbb{N}$ . Observe that from (13) it follows that

\lim_{n\to\infty}\mathscr{L}(x_{n},\lambda,c_{n})=\Theta_{*}(\lambda)\leq f_{*}.

(14)

Note also that due to assumption $(A7)$ for all $r>0$ , $n\in\mathbb{N}$ , and $x\in Q$ such that $\operatorname{dist}(G(x),K)\geq r$ one has $\mathscr{L}(x,\lambda,c_{n})=+\infty$ , if $\Phi(G(x),\lambda,c_{0})=+\infty$ , and

\mathscr{L}(x,\lambda,c_{n})=\mathscr{L}(x,\lambda,c_{0})+\Phi(G(x),\lambda,c_{n})-\Phi(G(x),\lambda,c_{0})\geq\Theta(\lambda,c_{0})\\ +\inf\Big{\{}\Phi(y,\lambda,c_{n})-\Phi(y,\lambda,c_{0})\Bigm{|}y\in Y,\>\operatorname{dist}(y,K)\geq r,\>|\Phi(y,\lambda,c_{0})|<+\infty\Big{\}},

if $\Phi(G(x),\lambda,c_{0})<+\infty$ (note that $\Phi(G(x),\lambda,c_{0})>-\infty$ , since $\lambda\in\operatorname{dom}_{\lambda}\Theta$ ). Therefore, by assumption $(A12)$ for any $r>0$ one has $\mathscr{L}(x,\lambda,c_{n})\to+\infty$ as $n\to\infty$ uniformly on the set $\{x\in Q\mid\operatorname{dist}(G(x),K)\geq r\}$ , which with the use of (14) implies that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ . Let us consider two cases.

Case I. Suppose that there exists a subsequence $\{x_{n_{k}}\}$ that is feasible for the problem $(\mathcal{P})$ . Then with the use of Lemma 1 one gets

	$\displaystyle\lim_{k\to\infty}\mathscr{L}(x_{n_{k}},\lambda,c_{n_{k}})$	$\displaystyle\geq\liminf_{k\to\infty}\Big{(}f(x_{n_{k}})+\inf_{y\in K}\Phi(y,\lambda,c_{n_{k}})\Big{)}$
		$\displaystyle\geq\liminf_{k\to\infty}f(x_{n_{k}})\geq f_{*}.$

Case II. Suppose now that $G(x_{n_{k}})\notin K$ for some subsequence $\{x_{n_{k}}\}$ Then with the use of assumption $(A13)$ one gets

\lim_{k\to\infty}\mathscr{L}(x_{n_{k}},\lambda,c_{n_{k}})\geq\liminf_{k\to\infty}f(x_{n_{k}})\geq\liminf_{k\to\infty}\beta(p_{k})\geq\liminf_{p\to 0}\beta(p),

where $\{p_{k}\}\subset Y$ is any sequence such that $G(x_{n_{k}})-p_{k}\in K$ and $\|p_{k}\|\to 0$ as $k\to\infty$ (note that such sequence exists, since $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ ).

Combining the two cases and inequalities (13) and (14) one obtains that

f_{*}\geq\Theta_{*}(\lambda)\geq\min\{f_{*},\liminf_{p\to 0}\beta(p)\}.

(15)

To prove equality (12), suppose that $f_{*}>\liminf_{p\to 0}\beta(p)=:\beta_{*}$ .

Let $\{p_{k}\}\subset Y$ be any sequence such that $p_{k}\to 0$ and $\beta(p_{k})\to\beta_{*}$ as $k\to\infty$ . Let also $\{t_{n}\}$ be the sequence from assumption $(A14)$ . Clearly, there exists a subsequence $\{p_{k_{n}}\}$ such that $\|p_{k_{n}}\|\leq t_{n}$ for all $n\in\mathbb{N}$ . By the definition of the optimal value function $\beta$ for any $n\in\mathbb{N}$ one can find $x_{n}\in Q$ such that $G(x_{n})-p_{k_{n}}\in K$ (i.e. $\operatorname{dist}(G(x_{n}),K)\leq t_{n}$ ) and $f(x_{n})\leq\beta(p_{k_{n}})+1/(n+1)$ in the case when $\beta_{*}>-\infty$ , and $f(x_{n})\to-\infty$ as $n\to\infty$ in the case when $\beta_{*}=-\infty$ .

If $\beta_{*}>-\infty$ , then thanks to assumption $(A14)$ one has

	$\displaystyle\Theta_{*}(\lambda)=\lim_{n\to\infty}\Theta(\lambda,c_{n})\leq\lim_{n\to\infty}\mathscr{L}(x_{n},\lambda,c_{n})=\lim_{n\to\infty}f(x_{n})$	$\displaystyle=\lim_{n\to\infty}\beta(p_{k_{n}})$
		$\displaystyle=\liminf_{p\to 0}\beta(p),$

which along with (15) implies the required result. In turn, if $\beta_{*}=-\infty$ , then due to assumption $(A14)$ one has

\Theta_{*}(\lambda)=\lim_{n\to\infty}\Theta(\lambda,c_{n})\leq\lim_{n\to\infty}\mathscr{L}(x_{n},\lambda,c_{n})=\lim_{n\to\infty}f(x_{n})=-\infty=\liminf_{p\to 0}\beta(p),

which implies that equality (12) holds true. ∎

Corollary 1 (duality gap formula).

If under the assumptions of the previous theorem one has $\operatorname{dom}_{\lambda}\Theta\neq\emptyset$ , then

f_{*}-\Theta_{*}=\max\left\{0,f_{*}-\liminf_{p\to 0}\beta(p)\right\}.

In particular, if the duality gap is positive, then it is equal to $f_{*}-\liminf_{p\to 0}\beta(p)$ .

Remark 8.

Although in the proof of Theorem 2 we considered the case $\beta_{*}=-\infty$ , in actuality, the assumptions of this theorem ensure that $\beta_{*}>-\infty$ . Namely, if assumptions $(A7)$ and $(A14)$ are satisfied and $\mathscr{L}(\cdot,\lambda,c)$ is bounded below on $Q$ for some $\lambda\in\Lambda$ and $c>0$ , then $\beta_{*}=\liminf_{p\to 0}\beta(p)>-\infty$ . Indeed, suppose by contradiction that $\beta_{*}=-\infty$ . Then there exists a sequence $\{p_{n}\}\in Y$ such that $p_{n}\to 0$ and $\beta(p_{n})\to-\infty$ as $n\to\infty$ . By the definition of the optimal value function one can find a sequence $\{x_{n}\}\subset Q$ such that $G(x_{n})-p_{n}\in K$ for all $n\in\mathbb{N}$ and $f(x_{n})\to-\infty$ as $n\to\infty$ . Note that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ , since $p_{n}$ converges to zero.

Let $\{c_{n}\}\subset(c,+\infty)$ be any increasing unbounded sequence and $\{t_{k}\}$ be the sequence from assumption $(A14)$ . Clearly, one can find a subsequence $\{x_{n_{k}}\}$ such that $\operatorname{dist}(G(x_{n_{k}}),K)\leq t_{k}$ for all $k\in\mathbb{N}$ . Then by assumption $(A14)$ one has $\Phi(G(x_{n_{k}}),\lambda,c_{n_{k}})\to 0$ as $k\to\infty$ , which implies that

\lim_{k\to\infty}\mathscr{L}(x_{n_{k}},\lambda,c_{n_{k}})=\lim_{k\to\infty}f(x_{n_{k}})=-\infty,

which due to assumption $(A7)$ contradicts the fact that $\mathscr{L}(\cdot,\lambda,c)$ is bounded below on $Q$ .

Remark 9.

The claim of Theorem 2 remains to hold true, if only restricted versions of assumptions $(A13)$ and $(A14)$ hold true, and one additionally assumes that the projection of the set $G(Q)$ onto the cone $K$ is bounded. If this projection is bounded, then one can show that the sequences $\{G(x_{n_{k}})\}$ appearing in the proof of the theorem are also bounded. Therefore, only restricted versions of assumptions $(A13)$ and $(A14)$ are needed to prove the theorem in this case, which makes the theorem applicable, for example, to He-Wu-Meng’s augmented Lagrangian (Example 13).

Let us note that the assumption on the boundedness of the projection of $G(Q)$ onto $K$ is not uncommon in the literature on augmented Lagrangians and primal-dual augmented Lagrangian methods (see, e.g. [44, Assumption 2], [39, Assumption 2], [71, Assumption 2], [70, condition (2)], etc.). In many particular cases this assumption is not restrictive from the theoretical point of view. For example, one can always guarantee that this assumption is satisfied for inequality constrainted problems by replacing the constraints $g_{i}(x)\leq 0$ with $e^{g_{i}(x)}-1\leq 0$ .

As a simple corollary to Theorem 2 we can obtain necessary and sufficient conditions for the augmented Lagrangian $\mathscr{L}(x,\lambda,c)$ to have the zero duality gap property.

Theorem 3 (zero duality gap characterisation).

Let assumptions $(A1)$ , $(A7)$ , and $(A12)$ – $(A14)$ be valid. Then the zero duality gap property holds true if and only if the optimal value function $\beta$ is lower semicontinuous (lsc) at the origin and there exist $\lambda\in\Lambda$ and $c>0$ such that the function $\mathscr{L}(\cdot,\lambda,c)$ is bounded below on $Q$ .

Proof.

Suppose that the zero duality gap property holds true. Then the optimal value of the dual problem is finite, which implies that $\operatorname{dom}_{\lambda}\Theta\neq\emptyset$ or, equivalently, there exist $\lambda\in\Lambda$ and $c>0$ such that the function $\mathscr{L}(\cdot,\lambda,c)$ is bounded below on $Q$ . Moreover, $f_{*}=\Theta_{*}=\min\{f_{*},\liminf_{p\to 0}\beta(p)\}$ by Theorem 2, which means that $\liminf_{p\to 0}\beta(p)\geq f_{*}=\beta(0)$ , that is, the optimal value function $\beta$ is lsc at the origin.

Conversely, suppose that $\beta$ is lsc at the origin and $\operatorname{dom}_{\lambda}\Theta\neq\emptyset$ . Then by Theorem 2 one has $\Theta_{*}=f_{*}$ , that is, there is zero duality gap between the primal and dual problems. ∎

Remark 10.

Let us note that one can prove the zero duality gap property for $\mathscr{L}(\cdot)$ under slightly less restrictive assumptions on the function $\Phi$ than in the previous theorems. Namely, instead of assuming that the claims of assumptions $(A12)$ – $(A14)$ , $(A16)$ are satisfied for all $\lambda\in\Lambda$ , it is sufficient to suppose that there exists $\lambda_{0}\in\operatorname{dom}_{\lambda}\Theta$ satisfying these assumptions (in the case of the coercivity assumption one must suppose that the function $\mathscr{L}(\cdot,\lambda,c)$ is coercive for $\lambda=\lambda_{0}$ ). Then arguing in the same way as in the proof of Theorem 2 one can check that

f_{*}\geq\sup_{\lambda\in\Lambda,c>0}\Theta(\lambda,c)\geq\lim_{c\to+\infty}\Theta(\lambda_{0},c)=\min\big{\{}f_{*},\liminf_{p\to 0}\beta(p)\big{\}}.

This inequality obviously implies that the zero duality gap property holds true, provided the optimal value function $\beta$ is lsc at the origin. Although such small change in the assumptions of the theorem might seem insignificant, in actuality it considerably broadens the class of augmented Lagrangians to which the sufficient conditions for the validity of the zero duality gap property can be applied. For example, Theorems 2 and 3 are inapplicable to the exponential-type augmented Lagrangian (Example 8), since this augmented Lagrangian does not satisfy assumption $(A12)$ . However, it satisfies the claim of assumption $(A12)$ for any $\lambda\in\mathbb{R}_{+}^{m}$ that lies in the interior of $\mathbb{R}_{+}^{m}$ (i.e. that does not have zero components) and, therefore, one can conclude that the zero duality gap property holds true for the exponential-type augmented Lagrangian, provided the optimal value function is lsc at the origin and there exists $\lambda_{0}\in\operatorname{dom}_{\lambda}\Theta\cap\operatorname{int}\mathbb{R}_{+}^{m}$ .

Remark 11.

Theorem 3 implies that under suitable assumptions the zero duality gap property depends not on the properties of the augmented Lagrangian $\mathscr{L}(\cdot)$ , but rather properties of the optimization problem $(\mathcal{P})$ itself. Similarly, by Corollary 1 the duality gap $f_{*}-\Theta_{*}$ does not depend on the augmented Lagrangian or even some characteristic of the dual problem $(\mathcal{D})$ . It is completely predefined by the properties of the optimization problem under consideration. Thus, in a sense, the absence of the duality gap between the primal and dual problems, as well as the size of the duality gap, when it is positive, are properties of optimization problems themselves, not augmented Lagrangians or augmented dual problems that are used for analysing and/or solving these problems.

For the sake of completeness, let us also present a simple characterisation of the lower semicontinuity of the optimal value function $\beta$ , from which one can easily derive a number of well-known sufficient conditions for this function to be lsc at the origin.

Proposition 2.

For the optimal value function $\beta$ to be lsc at the origin it is necessary and sufficient that there does not exist a sequence $\{x_{n}\}\subset Q$ such that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ and $\liminf_{n\to\infty}f(x_{n})<f_{*}$ .

Proof.

Necessity. Suppose that $\beta$ is lsc at the origin. Let $\{x_{n}\}\subset Q$ be any sequence such that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ . Denote $p_{n}=G(x_{n})$ . Then $p_{n}\to 0$ as $n\to\infty$ and due to the lower semicontinuity of $\beta$ at the origin one has

\liminf_{n\to\infty}f(x_{n})\geq\liminf_{n\to\infty}\beta(p_{n})\geq\beta(0)=f_{*}.

In other words, there does not exist a sequence $\{x_{n}\}\subset Q$ satisfying the conditions from the formulation of the proposition.

Sufficiency. Suppose by contradiction that the function $\beta$ is not lsc at the origin. Then there exist $\varepsilon>0$ and a sequence $\{p_{n}\}\subset Y$ converging to zero and such that $\beta(p_{n})\leq\beta(0)-\varepsilon$ for all $n\in\mathbb{N}$ . By the definition of the optimal value function for any $n\in\mathbb{N}$ one can find $x_{n}\in Q$ such that $G(x_{n})\in K+p_{n}$ and $f(x_{n})\leq f_{*}-\varepsilon/2$ (recall that $\beta(0)=f_{*}$ ). Therefore $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ and $\liminf_{n\to\infty}f(x_{n})<f_{*}$ , which contradicts the assumptions of the proposition that there does not exist a sequence $\{x_{n}\}\subset Q$ satisfying these conditions. ∎

Corollary 2.

Let the space $X$ be reflexive, the set $Q$ be weakly sequentially closed (in particular, one can suppose that $Q$ is convex), and the functions $f$ and $\operatorname{dist}(G(\cdot),K)$ be weakly sequentially lsc on $Q$ . Then for the optimal value function $\beta$ to be lsc at the origin it is necessary and sufficient there does not exist a sequence $\{x_{n}\}\subset Q$ such that $\|x_{n}\|\to+\infty$ and $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ , and $\liminf_{n\to\infty}f(x_{n})<f_{*}$ .

Proof.

The necessity of the conditions from the formulation of the corollary for the lower semicontinuity of the function $\beta$ follows directly from the previous proposition. Let us prove that they are also sufficient for the lower semicontinuity of $\beta$ .

Taking into account Proposition 2 it is sufficient to prove that there does not exists a bounded sequence $\{x_{n}\}\subset Q$ such that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ and $\liminf_{n\to\infty}f(x_{n})<f_{*}$ . Suppose by contradiction that such bounded sequence exists. Replacing this sequence with a subsequence, if necessary, one can assume that the sequence $\{f(x_{n})\}$ converges. Since the space $X$ is reflexive, one can extract a subsequence $\{x_{n_{k}}\}$ that weakly converges to some point $x_{*}$ that belongs to the set $Q$ , since this set is weakly sequentially closed. Furthermore, $G(x_{*})\in K$ , i.e. $x_{*}$ is feasible for the problem $(\mathcal{P})$ , since $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ and the function $\operatorname{dist}(G(\cdot),K)$ is weakly sequentially lsc. Hence taking into account the fact that $f$ is also weakly sequentially lsc one gets that

f_{*}>\lim_{n\to\infty}f(x_{n})=\lim_{k\to\infty}f(x_{n_{k}})\geq f(x_{*}),

which is impossible by virtue of the fact that the point $x_{*}$ is feasible for the problem $(\mathcal{P})$ . ∎

Corollary 3.

Let the assumptions of the previous corollary be satisfied and one of the following conditions hold true:

1.

the set $Q$ is bounded;
2.

the function $f$ is coercive on $Q$ ;
3.

the function $\operatorname{dist}(G(\cdot),K)$ is coercive on $Q$ ;
4.

the penalty function $f(\cdot)+c\operatorname{dist}(G(\cdot),K)^{\alpha}$ is coercive on $Q$ for some $c>0$ and $\alpha>0$ .

Then the optimal value function $\beta$ is lsc at the origin.

Thus, by Theorem 3 and Corollary 2, in the case when the space $X$ reflexive (in particular, in the finite dimensional case), under some natural lower semicontinuity assumptions the duality gap between the problems $(\mathcal{P})$ and $(\mathcal{D})$ is positive if and only if there exists an unbounded sequence $\{x_{n}\}\subset Q$ such that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ and the lower limit of the sequence $\{f(x_{n})\}$ is smaller than the optimal value of the problem $(\mathcal{P})$ . Furthermore, one can verify that the infimum of all such lower limits is equal to $\liminf_{p\to 0}\beta(p)$ and, therefore, defines the value of the duality gap $f_{*}-\Theta_{*}$ .

Remark 12.

Many existing results on the zero duality gap property for various augmented Lagrangians are either particular cases of Theorems 2 and 3 combined with Corollaries 2 and 3 or can be easily derived directly from these theorems and corollaries, including [31, Theorem 4.1], [32, Theorem 2.2], [8, Theorem 3], [39, Theorem 2.1], [86, Theorem 4.1], [87, Theorem 2.1], the claims about the zero duality gap property in Theorems 7, 9, and 11 in [79], etc.

4.2 Optimal dual solutions and global saddle points

As we will show below, dual convergence of augmented Lagrangian methods (that is, the convergence of the sequence of multipliers) is directly connected with the existence of globally optimal solutions of the dual problem $(\mathcal{D})$ . Therefore, let us analyse main properties of optimal dual solutions that will help us to better understand dual convergence of augmented Lagrangian methods. For the sake of shortness, below we use the term optimal dual solution, instead of globally optimal solution of the dual problem $(\mathcal{D})$ .

First, we make a simple observation about the role of the penalty parameter $c$ in optimal dual solutions.

Proposition 3.

Let assumption $(A7)$ hold true and $(\lambda_{*},c_{*})$ be an optimal dual solution. Then for any $c\geq c_{*}$ the equality $\Theta(\lambda_{*},c)=\Theta(\lambda_{*},c_{*})$ holds true and the pair $(\lambda_{*},c)$ is also an optimal dual solution.

Proof.

Under the assumption $(A7)$ the augmented Lagrangian $\mathscr{L}(x,\lambda,c)$ is non-decreasing in $c$ , which obviously implies that the augmented dual function $\Theta(\lambda,c)=\inf_{x\in Q}\mathscr{L}(x,\lambda,c)$ is non-decreasing in $c$ as well. Therefore, for any $c\geq c_{*}$ one has $\Theta(\lambda_{*},c)\geq\Theta(\lambda,c_{*})$ , which means that $(\lambda_{*},c)$ is a globally optimal solution of the dual problem and $\Theta(\lambda_{*},c)=\Theta(\lambda_{*},c_{*})$ . ∎

With the use of the previous proposition we can describe the structure of the set of optimal dual solutions, which we denote by $\mathscr{D}_{*}$ . Define

c_{*}(\lambda)=\inf\big{\{}c>0\bigm{|}(\lambda,c)\in\mathscr{D}_{*}\big{\}}\quad\forall\lambda\in\Lambda.

Note that by definition $c_{*}(\lambda)=+\infty$ , if $(\lambda,c)\notin\mathscr{D}_{*}$ for any $c>0$ . In addition, if $c_{*}(\lambda)<+\infty$ and assumption $(A7)$ holds true, then according to the previous proposition $(\lambda,c)\in\mathscr{D}_{*}$ for any $c>c_{*}(\lambda)$ . Following the work of Burachik et al. [12], we call the function $c_{*}(\cdot)$ the penalty map.

Let us prove some properties of the penalty map and describe the structure of the set of optimal dual solutions with the use of this map.

Corollary 4.

Let assumptions $(A7)$ , $(A9)$ , and $(A10)$ be valid and the dual problem $(\mathcal{D})$ have a globally optimal solution. Then the set $\operatorname{dom}c_{*}(\cdot)$ is convex, the penalty map $c_{*}(\cdot)$ is a quasiconvex function and

	$\displaystyle\mathscr{D}_{*}$	$\displaystyle=\Big{\{}\{\lambda\}\times[c_{}(\lambda),+\infty)\Bigm{\|}\lambda\in\operatorname{dom}c_{}(\cdot)\colon c_{*}(\lambda)>0\Big{\}}$
		$\displaystyle\bigcup\Big{\{}\{\lambda\}\times(0,+\infty)\Bigm{\|}\lambda\in\operatorname{dom}c_{}(\cdot)\colon c_{}(\lambda)=0\Big{\}}.$

Proof.

Let us first show that the set $\operatorname{dom}c_{*}(\cdot)$ is convex. Indeed, choose any $\lambda_{1},\lambda_{2}\in\operatorname{dom}c_{*}(\cdot)$ , $\alpha\in[0,1]$ , and $c>\max\{c_{*}(\lambda_{1}),c_{*}(\lambda_{2})\}$ . Then by Propositon 3 both $(\lambda_{1},c)\in\mathscr{D}_{*}$ and $(\lambda_{2},c)\in\mathscr{D}_{*}$ . Hence taking into account the fact that the dual function $\Theta(\lambda,c)$ is concave in $\lambda$ by assumption $(A9)$ one gets

\Theta(\alpha\lambda_{1}+(1-\alpha)\lambda_{2},c)\geq\alpha\Theta(\lambda_{1},c)+(1-\alpha)\Theta(\lambda_{2},c)=\alpha\Theta_{*}+(1-\alpha)\Theta_{*}=\Theta_{*}.

Therefore $(\alpha\lambda_{1}+(1-\alpha)\lambda_{2},c)\in\mathscr{D}_{*}$ , which means that $\alpha\lambda_{1}+(1-\alpha)\lambda_{2}\in\operatorname{dom}c_{*}(\cdot)$ and the set $\operatorname{dom}c_{*}(\cdot)$ is convex. Moreover, since $c>\max\{c_{*}(\lambda_{1}),c_{*}(\lambda_{2})\}$ was chosen aribtrarily, one has $c_{*}(\alpha\lambda_{1}+(1-\alpha)\lambda_{2})\leq\max\{c_{*}(\lambda_{1}),c_{*}(\lambda_{2})\}$ , that is, the penalty map is a quasiconvex function.

As was noted above, for any $\lambda\in\operatorname{dom}c_{*}(\cdot)$ and $c>c_{*}(\lambda)$ one has $(\lambda,c)\in\mathscr{D}_{*}$ . Hence bearing in mind the fact that the augmented dual function $\Theta$ is upper semicontinuous (usc) by assumption $(A10)$ one can conclude that

	$\displaystyle\{\lambda\}\times[c_{*}(\lambda),+\infty)$	$\displaystyle\subseteq\mathscr{D}_{}\quad\forall\lambda\in\operatorname{dom}c_{}(\cdot)\colon c_{*}(\lambda)>0,$
	$\displaystyle\{\lambda\}\times(0,+\infty)$	$\displaystyle\subseteq\mathscr{D}_{}\quad\forall\lambda\in\operatorname{dom}c_{}(\cdot)\colon c_{*}(\lambda)=0.$

The validity of the converse inclusions follows directly from the definition of the penalty map and Proposition 3. ∎

Remark 13.

Note that we need to consider the case $c_{*}(\lambda)=0$ separately due to the fact that many particular augmented Lagrangians are not defined for $c=0$ (see examples in Section 3). However, if a given augmented Lagrangian is correctly defined for $c=0$ and assumptions $(A7)$ , $(A9)$ , and $(A10)$ are satisfied for $c\in[0,+\infty)$ , then

\mathscr{D}_{*}=\bigcup_{\lambda_{*}\in\operatorname{dom}c_{*}(\cdot)}\{\lambda_{*}\}\cup[c_{*}(\lambda_{*}),+\infty)=\operatorname{epi}c_{*}(\cdot),

where $\operatorname{epi}c_{*}(\cdot)$ is the epigraph of the penalty map. This equality holds true, in particular, for Rockafellar-Wets’ augmented Lagrangian from Example 1. Let us also note that in the case when assumption $(A9)_{s}$ is satisfied (e.g. in the case of Rockafellar-Wets’ augmented Lagrangian) the penalty map is convex, since in this case the dual function $\Theta$ is concave and, therefore, the set of optimal dual solutions $\mathscr{D}_{*}$ is convex.

Optimal dual solutions can be described in terms of global saddle points of the augmented Lagrangian.

Definition 2.

A pair $(x_{*},\lambda_{*})\in Q\times\Lambda$ is called a global saddle point of the augmented Lagrangian $\mathscr{L}(\cdot)$ , if there exists $c_{*}>0$ such that

\sup_{\lambda\in\Lambda}\mathscr{L}(x_{*},\lambda,c)\leq\mathscr{L}(x_{*},\lambda_{*},c)\leq\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c)<+\infty\quad\forall c\geq c_{*}.

(16)

The infimum of all such $c_{*}$ is denoted by $c_{*}(x_{*},\lambda_{*})$ and is call the least exact penalty parameter for the global saddle point $(x_{*},\lambda_{*})$ .

Remark 14.

It is worth noting that inequalities (16) from the definition of global saddle point are obviously satisfied as (and, therefore, can be replaced with) equalities.

The following theorem, that combines together several well-known results (cf. [58, Theorem 11.59], [62, Theorem 2.1, part (v)], [88, Theorem 2.1], etc.), shows how optimal dual solutions are interconnected with global saddle points. We present a complete proof of this theorem for the sake of completeness and due to the fact that, to the best of the author’s knowledge, all three claims of this theorem cannot be derived from existing results within our axiomatic augmented Lagrangian setting.

Theorem 4.

Let assumptions $(A1)$ – $(A3)$ and $(A7)$ be valid. Then the following statements hold true:

1.

if a global saddle point $(x_{*},\lambda_{*})$ of $\mathscr{L}(\cdot)$ exists, then the zero duality gap property holds true, $x_{*}$ is a globally optimal solution of the problem $(\mathcal{P})$ , and for any $c_{*}>c_{*}(x_{*},\lambda_{*})$ the pair $(\lambda_{*},c_{*})$ is an optimal dual solution;
2.

if $(\lambda_{*},c_{*})$ is an optimal dual solution and the zero duality gap property holds true, then for any globally optimal solution $x_{*}$ of the problem $(\mathcal{P})$ the pair $(x_{*},\lambda_{*})$ is a global saddle point of $\mathscr{L}(\cdot)$ and $c_{*}(x_{*},\lambda_{*})\leq c_{*}$ ;

if $(x_{*},\lambda_{*})$ is a global saddle point of $\mathscr{L}(\cdot)$ , then

f_{*}=\mathscr{L}(x_{*},\lambda_{*},c)=\inf_{x\in Q}\sup_{\lambda\in\Lambda}\mathscr{L}(x,\lambda,c)=\sup_{\lambda\in\Lambda}\inf_{x\in Q}\mathscr{L}(x,\lambda,c)=\Theta_{*}

for all $c>c_{*}(x_{*},\lambda_{*})$ .

Proof.

Part 1. Let $(x_{*},\lambda_{*})$ be a global saddle point of $\mathscr{L}(\cdot)$ and some $c>c_{*}(x_{*},\lambda_{*})$ be fixed. Let us first show that $x_{*}$ is feasible. Indeed, assume that $G(x_{*})\notin K$ . Then by assumption $(A3)$ there exists a multiplier $\lambda_{0}\in\Lambda$ such that $\Phi(G(x_{*}),t\lambda_{0},c)\to+\infty$ as $t\to+\infty$ , which contradicts the inequalities

\mathscr{L}(x_{*},t\lambda_{0},c)\leq\sup_{\lambda\in\Lambda}\mathscr{L}(x_{*},\lambda,c)\leq\mathscr{L}(x_{*},\lambda_{*},c)<+\infty\quad\forall c>c_{*}(x_{*},\lambda_{*})

that follow from the definition of the global saddle point. Thus, $G(x_{*})\in K$ , that is, $x_{*}$ is feasible.

By assumption $(A2)$ there exists $\widehat{\lambda}\in\Lambda$ such that $\Phi(G(x_{*}),\widehat{\lambda},c)\geq 0$ , which by the definition of global saddle point implies that

f(x_{*})\leq\mathscr{L}(x_{*},\widehat{\lambda},c)\leq\sup_{\lambda\in\Lambda}\mathscr{L}(x_{*},\lambda,c)\leq\mathscr{L}(x_{*},\lambda_{*},c)\leq f(x_{*})\quad\forall c>c_{*}(x_{*},\lambda_{*}),

where the last inequality is valid by assumption $(A1)$ . Consequently, one has

\mathscr{L}(x_{*},\lambda_{*},c)=f(x_{*}),\quad\Phi(G(x_{*}),\lambda_{*},c)=0\quad\forall c>c_{*}(x_{*},\lambda_{*}).

Hence applying the definition of global saddle point and assumption $(A1)$ once more one gets that

f(x_{*})=\mathscr{L}(x_{*},\lambda_{*},c)\leq\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c)\leq\inf_{x\in Q\colon G(x)\in K}\mathscr{L}(x,\lambda_{*},c)\leq f(x)

for any feasible $x$ , which means that $x_{*}$ is a globally optimal solution of the problem $(\mathcal{P})$ . Furthermore, one has

\Theta(\lambda_{*},c)=\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c)=\mathscr{L}(x_{*},\lambda_{*},c)=f(x_{*})=f_{*}\quad\forall c>c_{*}(x_{*},\lambda_{*}).

Thetefore, by Proposition 1 the zero duality gap property holds true and the pair $(\lambda_{*},c)$ is an optimal dual solution for any $c>c_{*}(x_{*},\lambda_{*})$ .

Part 2. Let $(\lambda_{*},c_{*})$ and $x_{*}$ be globally optimal solutions of the problems $(\mathcal{D})$ and $(\mathcal{P})$ respectively, and suppose that the zero duality gap between property holds true. Fix any $c\geq c_{*}$ . Then applying assumption $(A1)$ and Proposition 3 one obtains that

\mathscr{L}(x_{*},\lambda_{*},c)\leq f(x_{*})=f_{*}=\Theta_{*}=\Theta(\lambda_{*},c)=\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c)\quad\forall c>c_{*}.

Consequently, $\mathscr{L}(x_{*},\lambda_{*},c)=f(x_{*})$ , and applying assumption $(A1)$ once again one gets

\sup_{\lambda\in\Lambda}\mathscr{L}(x_{*},\lambda,c)\leq f(x_{*})=\mathscr{L}(x_{*},\lambda_{*},c)=\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c)\quad\forall c>c_{*},

which obviously means that $(x_{*},\lambda_{*})$ is a global saddle point of the augmented Lagrangian and $c_{*}(x_{*},\lambda_{*})\leq c_{*}$ .

Part 3. Let $(x_{*},\lambda_{*})$ be a global saddle point. Choose any $c>c_{*}(x_{*},\lambda_{*})$ . From the proof of the first statement of the theorem it follows that

\mathscr{L}(x_{*},\lambda_{*},c)=f_{*}=\Theta_{*}=\Theta(\lambda_{*},c)=\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c)=\sup_{\lambda\in\Lambda}\inf_{x\in Q}\mathscr{L}(x,\lambda,c),

where the last equality and the fact that $\Theta_{*}=\Theta(\lambda_{*},c)$ follow from the fact that $(\lambda_{*},c)$ is an optimal dual solution.

By the definition of global saddle point $\mathscr{L}(x_{*},\lambda_{*},c)=\sup_{\lambda\in\Lambda}\mathscr{L}(x_{*},\lambda,c)$ , which implies that

\mathscr{L}(x_{*},\lambda_{*},c)\geq\inf_{x\in Q}\sup_{\lambda\in\Lambda}\mathscr{L}(x,\lambda,c).

On the other hand, by the same definition one also has

\mathscr{L}(x_{*},\lambda_{*},c)=\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c)\leq\inf_{x\in Q}\sup_{\lambda\in\Lambda}\mathscr{L}(x,\lambda,c).

Thus, $\mathscr{L}(x_{*},\lambda_{*},c)=\inf_{x\in Q}\sup_{\lambda\in\Lambda}\mathscr{L}(x,\lambda,c)$ , and the proof is complete. ∎

Remark 15.

Note that assumption $(A7)$ is not needed for the validity of the first and third statements of the theorem, since it is not used in the proofs of these statements. In turn, assumptions $(A2)$ and $(A3)$ are not needed for the validity of the second statement of the theorem.

Combining the first and second statements of the previous theorem one obtains the two following useful results.

Corollary 5.

Let assumptions $(A1)$ – $(A3)$ and $(A7)$ hold true. Then a global saddle point of $\mathscr{L}(\cdot)$ exists if and only if there exist globally optimal solutions of the primal problem $(\mathcal{P})$ and the dual problem $(\mathcal{D})$ and the zero duality gap property holds true.

Corollary 6.

Let assumptions $(A1)$ – $(A3)$ and $(A7)$ be valid and $(x_{*},\lambda_{*})$ be a global saddle point of $\mathscr{L}(\cdot)$ . Then for any globally optimal solution $z_{*}$ of the problem $(\mathcal{P})$ the pair $(z_{*},\lambda_{*})$ is also a global saddle point of $\mathscr{L}(\cdot)$ and $c_{*}(x_{*},\lambda_{*})=c_{*}(z_{*},\lambda_{*})=c_{*}(\lambda_{*})$ .

Thus, the least exact penalty parameter $c_{*}(x_{*},\lambda_{*})$ does not depend on a globally optimal solution $x_{*}$ of the problem $(\mathcal{P})$ and is equal to the value of the penalty map $c_{*}(\lambda_{*})$ .

Remark 16.

As was shown in [22, Proposition 9], if the functions $f$ and $G$ are differentiable, then under some natural assumptions on the function $\Phi$ any global saddle point of the augmented Lagrangian $\mathscr{L}(\cdot)$ is a KKT-point of the problem $(\mathcal{P})$ . This result implies that if there are two globally optimal solutions of the problem $(\mathcal{P})$ having disjoint sets of multipliers satisfying KKT optimality conditions (note that problems having such optimal solutions are necessarily nonconvex), then there are no global saddle points of the augmented Lagrangian $\mathscr{L}(\cdot)$ and by Corollary 5 either the duality gap between the primal and dual problems is positive or the dual problem has no globally optimal solutions. As we will show below, this fact leads to the unboundedness of the sequence of multipliers or the sequence of penalty parameters generated by augmented Lagrangian methods for problems having optimal solutions with disjoint sets of Lagrange multipliers.

Let us give an example illustrating the previous remark.

Example 20.

Let $X=Y=\mathbb{R}$ . Consider the following optimization problem:

\min\>f(x)=-x^{2}\quad\text{subject to}\enspace g_{1}(x)=x-1\leq 0,\enspace g_{2}(x)=-x-1\leq 0.

(17)

This problem has two globally optimal solutions: $1$ and $-1$ . The corresponding Lagrange multipliers are $(2,0)$ and $(0,2)$ . Thus, the sets of Lagrange multipliers corresponding to two different globally optimal solutions are disjoint.

The optimal value function for problem (17) has the form:

	$\displaystyle\beta(p)$	$\displaystyle=\inf\Big{\{}-x^{2}\Bigm{\|}x-1-p_{1}\leq 0,\>-x-1-p_{2}\leq 0\Big{\}}$
		$\displaystyle=\begin{cases}-\max\big{\{}\|1-p_{1}\|,\|1+p_{2}\|\big{\}}^{2},&\text{if }p_{1}-p_{2}\leq 2,\\ +\infty,&\text{if }p_{1}-p_{2}>2.\end{cases}$

The function $\beta$ is obviously continuous at the origin. Therefore, under the assumptions of Theorem 3 the zero duality gap property holds true. In particular, it holds true for the Hestenes-Powell-Rockafellar augmented Lagrangian for problem (17):

\begin{split}\mathscr{L}(x,\lambda,c)=-x^{2}&+\lambda_{1}\max\left\{x-1,-\frac{\lambda_{1}}{c}\right\}+\frac{c}{2}\max\left\{x-1,-\frac{\lambda_{1}}{c}\right\}^{2}\\ &+\lambda_{2}\max\left\{-x-1,-\frac{\lambda_{2}}{c}\right\}+\frac{c}{2}\max\left\{-x-1,-\frac{\lambda_{2}}{c}\right\}^{2}.\end{split}

(18)

However, the corresponding augmented dual problem has no globally optimal solutions.

Indeed, if an optimal dual solution $(\lambda_{*},c_{*})$ exists, then by Theorem 4 for any globally optimal solution $x_{*}$ of problem (17) the pair $(x_{*},\lambda_{*})$ is a global saddle point of the augmented Lagrangian and $c_{*}(x_{*},\lambda_{*})\leq c_{*}$ . Therefore by the third statement of Theorem 4 and the definition of global saddle point for any $c>c_{*}$ one has

f_{*}=-1=\mathscr{L}(1,\lambda_{*},c)=\mathscr{L}(-1,\lambda_{*},c)=\inf_{x\in\mathbb{R}}\mathscr{L}(x,\lambda_{*},c).

(19)

Hence applying assumption $(A1)$ one gets that

	$\displaystyle 0$	$\displaystyle=\Phi(G(1),\lambda_{},c)=(\lambda_{})_{2}\max\left\{-2,-\frac{(\lambda_{})_{2}}{c}\right\}+\frac{c}{2}\max\left\{-2,-\frac{(\lambda_{})_{2}}{c}\right\}^{2}$
	$\displaystyle 0$	$\displaystyle=\Phi(G(-1),\lambda_{},c)=(\lambda_{})_{1}\max\left\{-2,-\frac{(\lambda_{})_{1}}{c}\right\}+\frac{c}{2}\max\left\{-2,-\frac{(\lambda_{})_{1}}{c}\right\}^{2}$

Clearly, there exists $c_{0}>0$ such that $(\lambda_{*})_{1}/c<2$ and $(\lambda_{*})_{2}/c<2$ for any $c\geq c_{0}$ . Therefore, by the equalities above for any $c\geq c_{0}$ one has

0=-\frac{(\lambda_{*})_{1}^{2}}{2c},\quad 0=-\frac{(\lambda_{*})_{2}^{2}}{2c}

or, equivalently, $\lambda_{*}=0$ . However, as one can easily check,

\inf_{x\in\mathbb{R}}\mathscr{L}(x,\lambda_{*},c)=\inf_{x\in\mathbb{R}}\mathscr{L}(x,0,c)=-1-\frac{2}{c-2}<f_{*}\quad\forall c>2,

which contradicts (19). Thus, the augmented dual problem has no globally optimal solutions. In the following section we will show how a standard primal-dual augmented Lagrangian method behaves for problem (17) (see Example 22).

Another object in the augmented duality theory, that is directly connected with optimal dual solutions and global saddle points, is augmented Lagrange multiplier, which we introduce below by analogy with the theory of Rockafellar-Wets’ augmented Lagrangians [62, 61, 88, 18, 21].

Definition 3.

A vector $\lambda_{*}\in\Lambda$ is called an augmented Lagrange multiplier (of the augmented Lagrangian $\mathscr{L}(\cdot)$ ), if there exists $x_{*}\in Q$ such that the pair $(x_{*},\lambda_{*})$ is a global saddle point of the augmented Lagrangian. The set of all augmented Lagrange multipliers is denoted by $\mathscr{A}_{*}$ .

Remark 17.

(i) Our definition of the augmented Lagrange multiplier is equivalent to the one used in the context of Rockafellar-Wets’ augmented Lagrangians by [62, Theorem 2.1].

(ii) By Theorem 4, in the case when the zero duality gap property is satisfied and there exists a globally optimal solution of the primal problem, a vector $\lambda_{*}\in\Lambda$ is an augmented Lagrange multiplier if and only if there exists $c_{*}>0$ such that $(\lambda_{*},c_{*})$ is an optimal dual solution. Consequently, $\mathscr{A}_{*}=\operatorname{dom}c_{*}(\cdot)$ .

Let us point out some interesting properties of augmented Lagrange multipliers.

Proposition 4.

Let assumption $(A1)$ and the zero duality gap property hold true, and there exist a globally optimal solution of the problem $(\mathcal{P})$ . Then a vector $\lambda_{*}\in\Lambda$ is an augmented Lagrange multiplier if and only if there exists $c_{*}>0$ such that

\Theta(\lambda_{*},c_{*}):=\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c_{*})=f_{*}.

(20)

Furthermore, if this equality and assumptions $(A2)$ , $(A3)$ , and $(A7)$ are satisfied, then the following statements hold true:

1.

$\Theta(\lambda_{*},c)=f_{*}$ for all $c\geq c_{*}$ ;
2.

the infimum of all $c_{*}$ for which (20) holds true is equal to $c_{*}(\lambda_{*})$ ;
3.

for all $c_{*}>c_{*}(\lambda_{*})$ the infimum in (20) is attained at every globally optimal solution of the problem $(\mathcal{P})$ ;
4.

if the function $c\mapsto\Phi(y,\lambda_{*},c)$ is strictly increasing on $\operatorname{dom}\Phi(y,\lambda_{*},\cdot)$ for any $y\notin K$ and on $T(y):=\{c\in(0,+\infty)\colon-\infty<\Phi(y,\lambda_{*},c)<0\}$ for any $y\in K$ , then for all $c_{*}>c_{*}(\lambda_{*})$ the infimum in (20) is attained at some $x\in Q$ if and only if $x$ is a globally optimal solution of the problem $(\mathcal{P})$ .

Proof.

Part 1. Let $\lambda_{*}$ be an augmented Lagrange multiplier. Then by Theorem 4 there exists $c_{*}>0$ such that $(\lambda_{*},c_{*})$ is an optimal dual solution. Hence with the use of the fact that the zero duality gap property holds true one can conclude that equality (20) is valid.

Suppose now that equality (20) is satisfied for some $\lambda_{*}\in\Lambda$ and $c_{*}>0$ . Then by Proposition 1 the pair $(\lambda_{*},c_{*})$ is an optimal dual solution, which by Theorem 4 implies that $\lambda_{*}$ is an augmented Lagrange multiplier.

Part 2.1. Suppose that that equality (20) is satisfied for some $\lambda_{*}\in\Lambda$ and $c_{*}>0$ , and assumptions $(A2)$ , $(A3)$ , and $(A7)$ hold true. Then, as was noted earlier, the function $\Theta(\lambda,c)$ is non-decreasing in $c$ , which along with Proposition 1 imply that $\Theta(\lambda_{*},c)=f_{*}$ for all $c\geq c_{*}$ .

Part 2.2. The fact that the infimum of all $c_{*}$ for which (20) holds true is equal to $c_{*}(\lambda_{*})$ follows directly from the definition of the penalty map.

Part 2.3. If a pair $(\lambda_{*},c_{*})$ satisfies equality (20), then it is an optimal dual solution. Consequently, by Theorem 4 for any globally optimal solution $x_{*}$ of the problem $(\mathcal{P})$ the pair $(x_{*},\lambda_{*})$ is a global saddle point of the augmented Lagrangian. By the definition of global saddle point it means that the infimum in (20) is attained at $x_{*}$ (see (16)).

Part 2.4. Suppose finally that the function $c\mapsto\Phi(y,\lambda_{*},c)$ is strictly increasing on $\operatorname{dom}\Phi(y,\lambda_{*},\cdot)$ for any $y\notin K$ and on $T(y)$ for any $y\in K$ , and the infimum in (20) is attained at some $x\in Q$ . If $x$ is feasible and $\Phi(G(x),\lambda_{*},c_{*})<0$ or $x$ is infeasible, then for any $c_{*}(\lambda_{*})<c<c_{*}$ by our assumption on the function $\Phi$ one has $f_{*}=\mathscr{L}(x,\lambda_{*},c_{*})>\mathscr{L}(x,\lambda_{*},c)\geq f_{*}$ , which is obviously impossible. Therefore, $x$ is feasible and $\Phi(G(x),\lambda_{*},c_{*})=0$ , which means that $f(x)=f_{*}$ , that is, $x_{*}$ is a globally optimal solution of the problem $(\mathcal{P})$ . ∎

Thus, if $\lambda_{*}\in\Lambda$ is an augmented Lagrange multiplier, then under some additional assumptions the problem $(\mathcal{P})$ has the same optimal value and the same globally optimal solutions as the problem

\min_{x}\>\mathscr{L}(x,\lambda_{*},c)\quad\text{subject to }x\in Q

for any $c>c_{*}(\lambda_{*})$ . That is why in [58] augmented Lagrange multipliers were called multipliers supporting an exact penalty representation (see [58, Definition 11.60] and [31, 32, 86, 9, 72, 87, 12]).

Remark 18.

The assumption that the function $c\mapsto\Phi(y,\lambda_{*},c)$ is strictly increasing on $\operatorname{dom}\Phi(y,\lambda_{*},\cdot)$ for any $y\notin K$ and on $T(y)$ for any $y\in K$ is very mild and satisfied in many particular cases. For example, it is satisfied for any $\lambda_{*}\in\Lambda$ for Rockafellar-Wets’ augmented Lagrangian (Example 1), provided the function $\sigma$ has a valley at zero and is continuous at this point, the Hestenes-Powell-Rockafellar augmented Lagrangian (Examples 2, 14, 16, 19), the sharp Lagrangian (Example 3), Mangasarian’s augmented Lagrangian(Examples 4 and 7), the essentially quadratic augmented Lagrangian (Example 5), the cubic augmented Lagrangian (Example 6), the penalized exponential-type augmented Lagrangian (Examples 9 and 18), provided the function $\xi$ is strictly convex on $(0,+\infty)$ , and He-Wu-Meng’s augmented Lagrangian (Example 13). This assumption is also satisfied for any $\lambda_{*}\in\Lambda$ that does not have zero components for the exponential-type augmented Lagrangian (Example 8), the hyperbolic-type augmented Lagrangian (Example 11), and the modified barrier function (Example 12), provided the function $\phi$ is strictly convex in these examples, and for the p-th power augmented Lagrangian (Example 10).

Remark 19.

To the best of the author’s knowledge, the penalty map, augmented Lagrange multipliers, and an exact penalty representation have been introduced and studied earlier only in the context of Rockafellar-Wets’ augmented Lagrangians. In this section we demonatrated (see Corollary 4 and Proposition 4) that there is nothing specific in these concepts that is inherently connected to Rockafellar-Wets’ augmented Lagrangians. They can be naturally introduced and studied for any other augmented Lagrangian, including the (penalized) exponential-type augmented Lagrangian, modified barrier functions, Mangasarian’s augmented Lagrangian, etc., that are typically not considered in the theory of Rockafellar-Wets’ augmented Lagrangians.

4.3 Optimal dual solutions for convex problems

In the case when the problem $(\mathcal{P})$ is convex, optimal dual solutions, roughly speaking, do not depend on the penalty parameter $c$ (more precisely, the penalty map $c_{*}(\lambda_{*})$ does not depend on $\lambda_{*}\in\mathscr{A}_{*}$ ), and one can give a very simple (and well-known) description of the set of optimal dual solutions in terms of Lagrange multipliers.

Let the function $f$ and the set $Q$ be convex, and the mapping $G$ be convex with respect to binary relation $\preceq$ , that is,

G(\alpha x_{1}+(1-\alpha)x_{2})\preceq\alpha G(x_{1})+(1-\alpha)G(x_{2})\quad\forall x_{1},x_{2}\in X,\>\alpha\in[0,1].

Then the problem $(\mathcal{P})$ is convex. Moreover, in this case under assumption $(A8)$ the augmented Lagrangian $\mathscr{L}(x,\lambda,c)$ is convex in $x$ . Indeed, by applying first the fact that $\Phi(\cdot,\lambda,c)$ is non-decreasing with respect to $\preceq$ and then the fact that this function is convex one obtains that for any $x_{1},x_{2}\in X$ and $\alpha\in[0,1]$ the following inequalities hold true:

	$\displaystyle\mathscr{L}(\alpha x_{1}$	$\displaystyle+(1-\alpha)x_{2},\lambda,c)=f(\alpha x_{1}+(1-\alpha)x_{2})+\Phi(G(\alpha x_{1}+(1-\alpha)x_{2}),\lambda,c)$
		$\displaystyle\leq\alpha f(x_{1})+(1-\alpha)f(x_{2})+\Phi(\alpha G(x_{1})+(1-\alpha)G(x_{2}),\lambda,c)$
		$\displaystyle\leq\alpha f(x_{1})+(1-\alpha)f(x_{2})+\alpha\Phi(G(x_{1}),\lambda,c)+(1-\alpha)\Phi(G(x_{2}),\lambda,c)$
		$\displaystyle=\alpha\mathscr{L}(x_{1},\lambda,c)+(1-\alpha)\mathscr{L}(x_{2},\lambda,c),$

which means that the function $\mathscr{L}(\cdot,\lambda,c)$ is convex for any $\lambda\in\Lambda$ and $c>0$ (in the case when $\Phi(\alpha G(x_{1})+(1-\alpha)G(x_{2}),\lambda,c)=-\infty$ , instead of the inequalities above one should apply [54, Theorem I.4.2]).

Denote by $L(x,\lambda)=f(x)+\langle\lambda,G(x)\rangle$ the standard Lagrangian for the problem $(\mathcal{P})$ , where $\lambda\in K^{*}$ . It is easily seen that the function $L(\cdot,\lambda)$ is convex. Recall that a vector $\lambda_{*}\in K^{*}$ is called a Lagrange multiplier of the problem $(\mathcal{P})$ at a feasible point $x_{*}$ , if $0\in\partial_{x}L(x_{*},\lambda_{*})+N_{Q}(x_{*})$ and $\langle\lambda_{*},G(x_{*})\rangle=0$ , where $\partial_{x}L(x_{*},\lambda_{*})$ is the subdifferential of the function $L(\cdot,\lambda_{*})$ at $x_{*}$ in the sense of convex analysis and $N_{Q}(x_{*})=\{x^{*}\in X^{*}\mid\langle x^{*},x-x_{*}\rangle\leq 0\>\forall x\in Q\}$ is the normal cone to the set $Q$ at $x_{*}$ (see, e.g. [6, Definition 3.5]). The existence of a Lagrange multiplier at $x_{*}$ is a sufficient, and in the case when $0\in\operatorname{int}(G(Q)-K)$ necessary, global optimality condition, and the set $\Lambda_{*}$ of Lagrange multipliers of the problem $(\mathcal{P})$ is a nonempty, convex, weak^∗ compact set that does not depend on an optimal solution $x_{*}$ (see [6, Theorem 3.6]). Furthermore, $\lambda_{*}$ is a Lagrange multiplier at $x_{*}$ if and only if $(x_{*},\lambda_{*})$ is a saddle point of the Lagrangian $L(\cdot)$ :

\sup_{\lambda\in K^{*}}L(x_{*},\lambda)\leq L(x_{*},\lambda_{*})\leq\inf_{x\in Q}L(x,\lambda_{*}).

Note finally that if $L(\cdot,\lambda_{*})$ is directionally differentiable at $x_{*}$ , then $\lambda_{*}$ is a Lagrange multiplier at $x_{*}$ if and only if $[L(\cdot,\lambda_{*})]^{\prime}(x_{*},h)\geq 0$ for all $h\in T_{Q}(x_{*})$ and $\langle\lambda_{*},G(x_{*})\rangle=0$ , where $[L(\cdot,\lambda_{*})]^{\prime}(x_{*},h)$ is the directional derivative of $L(\cdot,\lambda_{*})$ at $x_{*}$ in the direction $h$ , and $T_{Q}(x_{*})$ is the contingent cone to the set $Q$ at the point $x_{*}$ (cf. [6, Lemma 3.7]).

Let us now present a complete characterisation of the set optimal dual solutions in terms of Lagrange multipliers in the convex case. Roughly speaking, this result shows that under suitable assumptions there is essentially no difference between standard duality theory, based on the Lagrangian $L(\cdot)$ , and augmented duality theory, based on the augmented Lagrangian $\mathscr{L}(\cdot)$ . For the sake of simplicity we will prove this result under the assumption that the functions $f$ and $G$ are directionally differentiable at a globally optimal solution of the problem $(\mathcal{P})$ , although in various particular cases (e.g. in the case of inequality constrained problems) this result can be proved without this assumption.

Theorem 5.

Let the following conditions hold true:

1.

$f$ and $Q$ are convex, $G$ is convex with respect to the binary relation $\preceq$ ;
2.

assumptions $(A1)$ , $(A4)$ , $(A5)$ , $(A7)$ , $(A8)$ , and $(A11)$ hold true;
3.

$K^{*}\subseteq\Lambda$ ;
4.

$f$ and $G$ are directionally differentiable at a globally optimal solution $x_{*}$ of the problem $(\mathcal{P})$ .

Then a Lagrange multiplier of the problem $(\mathcal{P})$ exists if and only if the zero duality gap property holds true and there exists a globally optimal solution $(\lambda_{*},c_{*})$ of the augmented dual problem $(\mathcal{D})$ with $\lambda_{*}\in K^{*}$ .

Moreover, if a Lagrange multiplier of the problem $(\mathcal{P})$ exists, then $(\lambda_{*},c_{*})$ with $\lambda_{*}\in K^{*}$ is an optimal dual solution if and only if $\Phi_{0}(\lambda_{*})$ is a Lagrange multiplier of the problem $(\mathcal{P})$ and $c_{*}>0$ , where $\Phi_{0}$ is from assumption $(A11)$ .

Proof.

Suppose that a Lagrange multiplier $\lambda_{*}\in K^{*}$ exists. Then, as was noted above, $[L(\cdot,\lambda_{*})]^{\prime}(x_{*},h)\geq 0$ for all $h\in T_{Q}(x_{*})$ . By assumption $(A11)$ the function $\Phi(\cdot,\lambda,c)$ is Fréchet differentiable and its Fréchet derivative $D_{y}\Phi(y,\lambda,c)=\Phi_{0}(\lambda)$ is a surjective mapping from $K^{*}$ onto $K^{*}$ . Therefore, there exists $\mu_{*}\in K^{*}$ such that $\Phi_{0}(\mu_{*})=\lambda_{*}$ . Applying the chain rule for directional derivatives one gets

[\mathscr{L}(\cdot,\mu_{*},c)]^{\prime}(x_{*},h)=f^{\prime}(x_{*},h)+\langle\Phi_{0}(\mu_{*}),G^{\prime}(x_{*},h)\rangle=[L(\cdot,\lambda_{*})]^{\prime}(x_{*},h)\geq 0

for any $c>0$ and $h\in T_{Q}(x_{*})$ . As was noted above, under the assumptions of the theorem the function $\mathscr{L}(\cdot,\mu_{*},c)$ is convex. Consequently, the inequality above implies that $x_{*}$ is a point of global minimum of $\mathscr{L}(\cdot,\mu_{*},c)$ on the set $Q$ . Recall that $\langle\lambda_{*},G(x_{*})\rangle=0$ , since $\lambda_{*}$ is a Lagrange multiplier. Hence by assumption $(A11)$ one has $\langle\mu_{*},G(x_{*})\rangle=0$ , and with the use of assumption $(A4)$ one gets

f_{*}=f(x_{*})=\mathscr{L}(x_{*},\mu_{*},c)=\inf_{x\in Q}\mathscr{L}(x,\mu_{*},c)=\Theta(\mu_{*},c)\quad\forall c>0,

which by Proposition 1 means that the zero duality gap property is satisfied and $(\mu_{*},c)$ with any $c>0$ is an optimal dual solution.

Suppose now that the zero duality gap property holds true and there exists an optimal solution $(\mu_{*},c_{*})$ of the problem $(\mathcal{D})$ with $\mu_{*}\in K^{*}$ . Then by Theorem 4 (see also Remark 15) the pair $(x_{*},\mu_{*})$ is a global saddle point of the augmented Lagrangian and $c_{*}(\mu_{*})\leq c_{*}$ . Therefore, by the definition of global saddle point $x_{*}$ is a point of global minimum of $\mathscr{L}(\cdot,\mu_{*},c)$ on the set $Q$ and

\mathscr{L}(x_{*},\mu_{*},c)=\Theta(\mu_{*},c)=\Theta(\mu_{*},c_{*})=\Theta_{*}=f_{*}\quad\forall c>c_{*}

(21)

(here we used Proposition 3). Hence with the use of assumption $(A11)$ one obtains that

0\leq[\mathscr{L}(\cdot,\mu_{*},c)]^{\prime}(x_{*},h)=f^{\prime}(x_{*},h)+\langle\Phi_{0}(\mu_{*}),G^{\prime}(x_{*},h)\rangle=[L(\cdot,\lambda_{*})]^{\prime}(x_{*},h)

for any $h\in T_{Q}(x_{*})$ , where $\lambda_{*}=\Phi_{0}(\mu_{*})$ . Moreover, $\langle\mu_{*},G(x_{*})\rangle=0$ and, therefore, $\langle\lambda_{*},G(x_{*})\rangle=0$ by assumption $(A11)$ , since otherwise by assumption $(A5)$ one has $\mathscr{L}(x_{*},\mu_{*},c)<f(x_{*})=f_{*}$ , which contradicts (21). Thus, $\lambda_{*}$ is a Lagrange multiplier.

It remains to note that, as was shown above, if $\lambda_{*}$ is a Lagrange multiplier, then for any $c>0$ and $\mu_{*}\in K^{*}$ such that $\Phi_{0}(\mu_{*})=\lambda_{*}$ the pair $(\mu_{*},c)$ is an optimal dual solution. Conversely, if $(\mu_{*},c_{*})$ with $\mu_{*}\in K^{*}$ is an optimal dual solution, then $\lambda_{*}=\Phi_{0}(\mu_{*})$ is a Lagrange multiplier. ∎

Corollary 7.

Let $f$ and $Q$ be convex, $G$ be convex with respect to the binary relation $\preceq$ , $f$ and $G$ be directionally differentiable at an optimal solution $x_{*}$ of the problem $(\mathcal{P})$ , $K^{*}\subseteq\Lambda$ , and suppose that assumptions $(A1)$ – $(A8)$ and $(A11)$ hold true. Then a Lagrange multiplier of the problem $(\mathcal{P})$ exists if and only if the zero duality gap property holds true and there exists an optimal dual solution. Moreover, if a Lagrange multiplier of the problem $(\mathcal{P})$ exists, then $(\lambda_{*},c_{*})$ is a globally optimal solution of the dual problem $(\mathcal{D})$ if and only if $\Phi_{0}(\lambda_{*})$ is a Lagrange multiplier of the problem $(\mathcal{P})$ and $c_{*}>0$ .

Proof.

Let $(\lambda_{*},c_{*})$ be an optimal dual solution. Then by Theorem 4 the pair $(x_{*},\lambda_{*})$ is a global saddle point, and with the use of [22, Proposition 2] one can conclude that $\lambda_{*}\in K^{*}$ . Thus, for any optimal dual solution $(\lambda_{*},c_{*})$ one has $\lambda_{*}\in K^{*}$ and the claim of the corollary follows directly from Theorem 5. ∎

With the use of the previous corollary we can finally describe the structure of the set of optimal dual solutions $\mathscr{D}_{*}$ , the penalty map $c_{*}(\cdot)$ , and the set of augmented Lagrange multipliers $\mathscr{A}_{*}$ in the convex case.

Corollary 8.

Let the assumptions of the previous corollary be valid. Then $\mathscr{A}_{*}=\Phi_{0}^{-1}(\Lambda_{*})$ , $c_{*}(\lambda_{*})=0$ for any $\lambda_{*}\in\mathscr{A}_{*}$ , and the following equality holds true:

\mathscr{D}_{*}=\Phi_{0}^{-1}\big{(}\Lambda_{*}\big{)}\times(0,+\infty).

(22)

Remark 20.

The fact that optimal dual solutions for convex problems do not depend on the penalty parameter motivates one to consider a slightly different augmented dual problem in the convex case:

\min_{\lambda}\>\Theta_{c}(\lambda)\quad\text{subject to }\lambda\in\Lambda.

(23)

Here $\Theta_{c}(\lambda)=\Theta(c,\lambda)$ and $c>0$ is fixed, that is, the penalty parameter is not considered as a variable of augmented dual problem, but rather as a fixed external parameter. Note that the function $\Theta_{c}(\cdot)$ is concave, provided assumption $(A9)$ holds true, which is satisfied for most particular augmented Lagrangians, in contrast to the much more restrictive assumption $(A9)_{s}$ , which is satisfied, to the best of the author’s knowledge, only for Rockafellar-Wets’ augmented Lagrangian and, in particular, the Hestenes-Powell-Rockafellar augmented Lagrangian. Taking into account the concavity of the function $\Theta_{c}(\cdot)$ one can consider primal-dual augmented Lagrangian methods based on solving problem (23), instead of the augmented dual problem $(\mathcal{D})$ , i.e. augmented Lagrangian methods with fixed penalty parameter. Convergence analysis of such methods is always based on the use of a particular structure of an augmented Lagrangian under consideration (see the survey of such methods in [35]), which makes it difficult to extend such analysis to the general axiomatic augmented Lagrangian setting adopted in this article.

Let us show that in the case when assumptions $(A5)$ , $(A6)$ , and $(A11)$ are not satisfied, equality (22) might be no longer valid and the penalty map might not be identically equal to zero on $\operatorname{dom}c_{*}(\cdot)$ , even when the problem $(\mathcal{P})$ is convex.

Example 21.

Let $X=Y=\mathbb{R}$ . Consider the following optimization problem:

\min\>f(x)=-x\quad\text{subject to}\enspace g(x)=x\leq 0.

(24)

Let $\mathscr{L}(\cdot)$ be the sharp Lagrangian for this problem (i.e. the augmented Lagrangian from Example 1 with $\sigma(y)=\|y\|$ ). Then

	$\displaystyle\mathscr{L}(x,\lambda,c)$	$\displaystyle=f(x)+\inf_{p\in(-\infty,-g(x)]}\big{(}-\lambda p+c\|p\|\big{)}$
		$\displaystyle=-x+\begin{cases}\lambda x+c\|x\|,&\text{if }\lambda>c\\ (\lambda+c)\max\{0,x\},&\text{if }\|\lambda\|\leq c\\ -\infty,&\text{if }\lambda<-c,\end{cases}$

and, as one can readily verify by carefully writing down all particular cases,

\Theta(\lambda,c)=\begin{cases}0,&\text{if }c\geq|\lambda-1|,\\ -\infty,&\text{otherwise.}\end{cases}

Consequently, one has

\mathscr{D}_{*}=\Big{\{}(\lambda,c)\in\mathbb{R}^{2}\Bigm{|}c\geq|\lambda-1|\Big{\}},\quad c_{*}(\lambda)=|\lambda-1|\quad\forall\lambda\in\mathbb{R},

that is, the claims of Corollary 8 do not hold true for the sharp Lagrangian (recall that this Lagrangian does not satisfy assumptions $(A5)$ , $(A6)$ , and $(A11)$ ).

5 Convergence analysis of augmented Lagrangian methods

The goal of this section is to prove general convergence theorems for a large class of augmented Lagrangian methods and to analyse interrelations between convergence of augmented Lagrangian methods, zero duality gap property, and the existence of global saddle points/optimal dual solutions. We aim at presenting such results that explicitly highlight this kind of interrelations, instead of implicitly using them within the proofs, as it is usually done in the literature.

5.1 Model augmented Lagrangian method

We present all theoretical results for the following model augmented Lagrangian method given in Algorithm 1. In order to include various particular cases into the general theory, we do not specify a way in which multipliers and the penalty parameter are updated by the method, that is, they can be updated in any way that satisfies certain assumptions presented below. It makes our results applicable to the vast majority of existing augmented Lagrangian methods, including methods with nonmonotone penalty parameter updates as in [4], methods based on maximizing the augmented dual function with the use of bundle methods as in [48], etc. However, one should underline that our convergence analysis is by no means universal and there are augmented Lagrangian methods to which it cannot be applied. We will briefly discuss some such methods further in this section (see Remark 21 below).

Initialization. Choose an initial value of the multipliers

\lambda_{0}\in\Lambda

, a minimal value of the penalty parameter

c_{min}>0

, an initial value of the penalty parameter

c_{0}\geq c_{\min}

, and a sequence

\{\varepsilon_{n}\}\subset(0,+\infty)

of tolerances. Put

n=0

Step 1. Solution of subproblem. Find an

\varepsilon_{n}

-optimal solution

x_{n}

of the problem

\min\>\mathscr{L}(x,\lambda_{n},c_{n})\quad\text{subject to}\quad x\in Q,

that is, find

x_{n}\in Q

such that

\mathscr{L}(x_{n},\lambda_{n},c_{n})\leq\mathscr{L}(x,\lambda_{n},c_{n})+\varepsilon_{n}

for all

x\in Q

Step 2. Multiplier update. Choose some

\lambda_{n+1}\in\Lambda

Step 3. Penalty parameter update. Choose some

c_{n+1}\geq c_{min}

. Set

n\rightarrow n+1

and go to Step 1.

Algorithm 1 Model augmented Lagrangian method

Let us comment on Step 1 on Algorithm 1. For the purposes of theoretical analysis of primal-dual augmented Lagrangian methods it is often assumed that the augmented Lagrangian subproblem

\min\>\mathscr{L}(x,\lambda_{n},c_{n})\quad\text{subject to}\quad x\in Q,

is solved exactly, i.e. that $x_{n}$ is a globally optimal solution of this problem [69, 50, 27, 8, 40, 41, 38, 13, 5]. Moreover, even when it is assumed that this subproblem is solved only approximately as in [15, 44, 71, 10, 7, 11, 16, 14], one almost always assumes that $\varepsilon_{n}\to 0$ as $n\to\infty$ , and the case when $\varepsilon_{n}$ does not tend to zero is not properly analysed (papers [45, 48] are very rare exceptions to this rule). However, from the practical point of view the assumption that $\varepsilon_{n}\to 0$ as $n\to\infty$ cannot be satisfied, especially in the infinite dimensional case, due to round off errors, discretisation errors, etc. The value $\varepsilon_{n}>0$ should be viewed as an unavoidable error reflecting the overall precision with which computations can be performed that does not tend to zero with iterations. To take this unavoidable error into account, below we present a detailed analysis of the model augmented Lagrangian method without assuming that $\varepsilon_{n}\to 0$ as $n\to\infty$ , and then show how corresponding convergence theorems can be clarified and strengthened by imposing this additional purely theoretical assumption.

It should also be noted that practical augmented Lagrangian methods must include stopping criteria. We do not include a stopping criterion in our formulation of the model augmented Lagrangian method, because we are interested only in its theoretical (asymptotic) analysis, that is, in the analysis of the way sequences $\{(x_{n},\lambda_{n},c_{n})\}$ generated by this method behave as $n\to\infty$ . This asymptotic analysis can be used to devise appropriate stopping criteria for practical implementations of augmented Lagrangian methods.

Below we will utilise the following natural assumptions on the model augmented Lagrangian method and sequences generated by this method that are satisfied in many particular cases:

(B1)

for any $n\in\mathbb{N}$ the function $\mathscr{L}(\cdot,\lambda_{n},c_{n})$ is bounded below on $Q$ ;
(B2)

the sequence of multipliers $\{\lambda_{n}\}$ is bounded;
(B3)

if the sequence of penalty parameters $\{c_{n}\}$ is bounded, then one has $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ ; if, in addition, some subsequence $\{\lambda_{n_{k}}\}$ is bounded, then $\Phi(G(x_{n_{k}}),\lambda_{n_{k}},c_{n_{k}})\to 0$ as $k\to\infty$ ;
(B4)

if the sequence of penalty parameters $\{c_{n}\}$ is unbounded, then $c_{n}\to+\infty$ as $n\to\infty$ .

The assumption $(B1)$ is a basic assumption for all primal-dual augmented Lagrangian methods, which is needed to ensure that the sequence $\{x_{n}\}$ is correctly defined. The assumption $(B2)$ is often imposed for the purposes of convergence analysis of augmented Lagrangian methods and, as is noted in [5], is usually satisfied in practice for traditional rules for updating multipliers. Moreover, various techniques can be used to guarantee the validity of assumption $(B2)$ , such as safeguarding and normalization of multipliers [44, 42, 5].

We formulate $(B3)$ as an assumption due to the fact that we do not impose any restrictions on the way in which the penalty parameter $c_{n}$ is updated. For many augmented Lagrangian methods, penalty parameter updates are specifically designed to ensure that assumption $(B3)$ is satisfied by default (see the rules for updating the penalty parameter and corresponding convergence analysis in [44, 42, 71, 5] and other aforementioned papers on augmented Lagrangian methods). Finally, assumption $(B4)$ is needed only in the case of methods with nonmonotone penalty parameter updates. It excludes the undesirable situation of unboundedly increasing oscillations of the penalty parameter (e.g. $c_{2n}=n$ and $c_{2n+1}=1$ for all $n\in\mathbb{N}$ ), which cannot be properly analysed within out general augmented Lagrangian setting.

Remark 21.

(i) Assumption $(B3)$ plays one of the key roles in our convergence analysis of the model augmented Lagrangian method. Therefore, this analysis is inapplicable to those methods for which assumption $(B3)$ is not satisfied, such as the modified subgradient algorithm (the MSG) proposed by Gasimov [27] (the fact that assumption $(B3)$ is not satisfied for the MSG in the general case follows from [8, Example 1]).

(ii) The convergence analysis of the model augmented Lagrangian method presented below heavily relies on the assumption on boundedness of the sequence of multipliers and cannot be applied in the case when the sequence $\{\lambda_{n}\}$ does not have at least a bounded subsequence. However, there are primal-dual augmented Lagrangian methods for which one can prove convergence of the sequence $\{x_{n}\}$ to the set of globally optimal solutions of the problem $(\mathcal{P})$ even in the case when the norm of the multipliers $\lambda_{n}$ increases unboundedly with iterations. Augmented Lagrangian methods with the so-called conditional multiplier updating (see [20], [44, Algorithm 3], [42, Algorithm 3], [45, Algorithm 3]) and the algorithms from [71] are examples of such methods. The main idea behind these methods consists in designing multiplier and penalty parameter updating rules in such a way as to ensure that an increase of the norm of the multipliers $\|\lambda_{n}\|$ is compensated by a sufficient increase of the penalty parameter $c_{n}$ , so that one can prove that

\lim_{n\to\infty}\operatorname{dist}(G(x_{n}),K)=0,\quad\lim_{n\to\infty}\Phi(G(x_{n}),\lambda_{n},c_{n})=0

(25)

even if $\|\lambda_{n}\|\to+\infty$ as $n\to\infty$ . It is possible to extend convergence analysis of these methods to our axiomatic augmented Lagrangian setting by either imposing some restrictive assumptions on the function $\Phi$ or directly assuming that relations (25) hold true. We do not present such extension here and leave it as a problem for future research.

5.2 Convergence analysis of the method

Let us now turn to convergence analysis. We start with two simple observations. The first one can be viewed as a generalization of some existing results (e.g. [27, Theorem 5] and [48, Theorem 1]) to the case of general cone constrained problems and arbitrary augmented Lagrangians satisfying a certain assumption.

Lemma 3.

Let the function $y\mapsto\Phi(y,\lambda,c)$ be non-decreasing with respect to the binary relation $\preceq$ for any $\lambda\in\Lambda$ and $c>0$ , and let $\{(x_{n},\lambda_{n},c_{n})\}$ be the sequence generated by the model augmented Lagrangian method. Then for any $n\in\mathbb{N}$ the point $x_{n}$ is an $\varepsilon_{n}$ -optimal solution of the problem

\min\>f(x)\quad\text{subject to }G(x)\preceq G(x_{n}),\quad x\in Q,

(26)

Moreover, if $G(x_{n})=0$ , then $x_{n}$ is an $\varepsilon_{n}$ -optimal solution of the problem $(\mathcal{P})$ .

Proof.

Suppose by contradiction that the claim of the lemma is false. Then one can find a feasible point $x$ of problem (26) such that $f(x_{n})>f(x)+\varepsilon_{n}$ . Hence by our assumption on the function $\Phi$ one gets

	$\displaystyle\mathscr{L}(x,\lambda_{n},c_{n})=f(x)+\Phi(G(x),\lambda_{n},c_{n})$	$\displaystyle<f(x_{n})-\varepsilon_{n}+\Phi(G(x_{n}),\lambda_{n},c_{n})$
		$\displaystyle=\mathscr{L}(x_{n},\lambda_{n},c_{n})-\varepsilon_{n},$

which contradicts the definition on $x_{n}$ .

Suppose now that $G(x_{n})=0$ . Recall that the inequality $G(x)\preceq G(x_{n})$ means that $G(x_{n})-G(x)\in-K$ or, equivalently, $G(x)\in K+G(x_{n})=K$ . Therefore the feasible region of the problem $(\mathcal{P})$ coincides with the feasible region of problem (26), which implies that an $\varepsilon_{n}$ -optimal solution of this problem is also an $\varepsilon_{n}$ -optimal solution of the problem $(\mathcal{P})$ . ∎

Remark 22.

The assumption that the function $y\mapsto\Phi(y,\lambda,c)$ is non-decreasing is satisfied for all particular augmented Lagrangians presented in this paper, except for the one from Example 15.

The second observation is connected with the augmented dual function. Recall that if the function $\Phi$ satisfies assumption $(A1)$ , then $\mathscr{L}(x,\lambda,c)\leq f(x)$ for any feasible point $x$ . Therefore, the following result holds true.

Lemma 4.

Let assumption $(A1)$ be valid. Then

\Theta(\lambda_{n},c_{n})\leq\mathscr{L}(x_{n},\lambda_{n},c_{n})\leq\Theta(\lambda_{n},c_{n})+\varepsilon_{n}\leq f_{*}+\varepsilon_{n}\quad\forall n\in\mathbb{N}.

Thus, if the sequence $\{\Theta(\lambda_{n},c_{n})\}$ is bounded below, then the corresponding sequence $\{\mathscr{L}(x_{n},\lambda_{n},c_{n})\}$ is bounded. Let us analyse how these sequences behave in the limit. As we will see below, this analysis is a key ingredient in the global convergence theory of augmented Lagrangian methods.

The following cumbersome technical result, which can be viewed as a partial generalization of Theorem 2, plays a key role in our convergence analysis of the model augmented Lagrangian method. The proof of this result is very similar to the proof of Theorem 2, and we include it only for the sake of completeness.

Lemma 5.

Let assumptions $(A1)$ , $(A13)_{s}$ , and $(A14)_{s}$ hold true. Suppose also that a sequence $\{(x_{n},\lambda_{n},c_{n})\}\subset Q\times\operatorname{dom}\Theta$ is such that:

1.

$\operatorname{dist}(G(x_{n},K)\to 0$ as $n\to\infty$ ,
2.

the sequence $\{\lambda_{n}\}$ is bounded,
3.

$c_{n}\to+\infty$ as $n\to\infty$ ,
4.

the sequence $\{\mathscr{L}(x_{n},\lambda_{n},c_{n})-\Theta(\lambda_{n},c_{n})\}$ is bounded above.

Let finally $\varepsilon_{*}=\limsup_{n\to\infty}(\mathscr{L}(x_{n},\lambda_{n},c_{n})-\Theta(\lambda_{n},c_{n}))$ . Then

$\displaystyle\vartheta_{}-\varepsilon_{}\leq\liminf_{n\to\infty}\Theta(\lambda_{n},c_{n})$	$\displaystyle\leq\limsup_{n\to\infty}\Theta(\lambda_{n},c_{n})\leq\vartheta_{*}$	(27)
$\displaystyle\vartheta_{*}\leq\liminf_{n\to\infty}\mathscr{L}(x_{n},\lambda_{n},c_{n})$	$\displaystyle\leq\limsup_{n\to\infty}\mathscr{L}(x_{n},\lambda_{n},c_{n})\leq\vartheta_{}+\varepsilon_{}$	(28)
$\displaystyle\vartheta_{*}\leq\liminf_{n\to\infty}f(x_{n})$	$\displaystyle\leq\limsup_{n\to\infty}f(x_{n})\leq\vartheta_{}+\varepsilon_{}.$	(29)

where $\vartheta_{*}=\min\big{\{}f_{*},\liminf_{p\to 0}\beta(p)\big{\}}$ .

Proof.

Note that the upper estimate for the limit superior in (29) follows directly from the upper estimate in (28) and assumption $(A13)_{s}$ . In turn, the lower estimate for the limit inferior in (29) follows directly from the fact that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ .

Indeed, if some subsequence $\{x_{n_{k}}\}$ is feasible for the problem $(\mathcal{P})$ , then obviously $\liminf_{k\to\infty}f(x_{n_{k}})\geq f_{*}$ . In turn, if each member of a subsequence $\{x_{n_{k}}\}$ is infeasible for the problem $(\mathcal{P})$ , then $f(x_{n_{k}})\geq\beta(p_{k})$ for any $p_{k}\in Y$ such that $G(x_{n_{k}})-p_{k}\in K$ . Since $\operatorname{dist}(G(x_{n_{k}}),K)\to 0$ as $k\to\infty$ , one can choose $p_{k}\in Y$ , $k\in\mathbb{N}$ , such that $p_{k}\to 0$ as $k\to\infty$ . Consequently, one has

\liminf_{k\to\infty}f(x_{n_{k}})\geq\liminf_{k\to\infty}\beta(p_{k})\geq\liminf_{p\to 0}\beta(p),

which obviously implies that the the lower estimate in (29) holds true.

Thus, we need to prove only inequalities (27) and (28). Let us consider two cases.

Case I. Suppose that there exists a subsequence $\{x_{n_{k}}\}$ that is feasible for the problem $(\mathcal{P})$ . Then with the use of Lemma 1 one gets

	$\displaystyle\liminf_{k\to\infty}\mathscr{L}(x_{n_{k}},\lambda_{n_{k}},c_{n_{k}})$	$\displaystyle\geq\liminf_{k\to\infty}\Big{(}f(x_{n_{k}})+\inf_{\lambda\in B(0,\eta)\cap\Lambda}\inf_{y\in K}\Phi(y,\lambda,c_{n_{k}})\Big{)}$
		$\displaystyle\geq\liminf_{k\to\infty}f(x_{n_{k}})\geq f_{*},$

where $\eta=\sup_{k}\|\lambda_{n_{k}}\|$ .

Case II. Suppose now that there exists a subsequence $\{x_{n_{k}}\}$ such that $G(x_{n_{k}})\notin K$ for all $k\in\mathbb{N}$ . Then with the use of assumption $(A13)_{s}$ one gets

\liminf_{k\to\infty}\mathscr{L}(x_{n_{k}},\lambda_{n_{k}},c_{n_{k}})\geq\liminf_{k\to\infty}f(x_{n_{k}})\geq\liminf_{k\to\infty}\beta(p_{k})\geq\liminf_{p\to 0}\beta(p),

where $\{p_{k}\}\subset Y$ is any sequence such that $G(x_{n_{k}})-p_{k}\in K$ for all $k\in\mathbb{N}$ and $\|p_{k}\|\to 0$ as $k\to\infty$ (clearly, such sequence exists, since $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ ).

Combining the two cases one gets that the lower estimates for the limit inferiors in (27) and (28) hold true. Let us now prove the upper estimates for the limit superiors. Note that the upper estimate in (28) follows directly from the upper estimate in (27) and Lemma 4. Therefore, it suffies to prove only the upper estimate for the limit superior of $\{\Theta(\lambda_{n},c_{n})\}$ .

By Proposition 1 one has $\Theta(\lambda_{n},c_{n})\leq f_{*}$ for all $n\in\mathbb{N}$ , which implies that $\limsup_{n\to\infty}\Theta(\lambda_{n},c_{n})\leq f_{*}$ . If $\beta_{*}:=\liminf_{p\to 0}\beta(p)\geq f_{*}$ , then the proof is complete. Therefore, suppose that $\beta_{*}<f_{*}$ .

By the definition of limit inferior there exists a sequence $\{p_{k}\}\subset Y$ such that $p_{k}\to 0$ and $\beta(p_{k})\to\beta_{*}$ as $k\to\infty$ . Let $\{t_{n}\}$ be the sequence from assumption $(A14)_{s}$ . Since $p_{k}\to 0$ as $k\to\infty$ , there exists a subsequence $\{p_{k_{n}}\}$ such that $\|p_{k_{n}}\|\leq t_{n}$ for all $n\in\mathbb{N}$ .

By the definition of the optimal value function $\beta$ for any $n\in\mathbb{N}$ one can find $x_{n}\in Q$ such that $G(x_{n})-p_{k_{n}}\in K$ (which implies that $\operatorname{dist}(G(x_{n}),K)\leq t_{n}$ ) and $f(x_{n})\leq\beta(p_{k_{n}})+1/n$ , if $\beta(p_{k_{n}})>-\infty$ , and $f(x_{n})\leq-n$ otherwise. By applying assumption $(A14)_{s}$ , one gets that

	$\displaystyle\limsup_{n\to\infty}\Theta(\lambda_{n},c_{n})\leq\limsup_{n\to\infty}\mathscr{L}(z_{n},\lambda_{n},c_{n})$	$\displaystyle=\limsup_{n\to\infty}f(z_{n})$
		$\displaystyle=\lim_{n\to\infty}\beta(p_{k_{n}})=\liminf_{p\to 0}\beta(p),$

which means that the upper estimate in (27) holds true. ∎

Remark 23.

The claim of the lemma above (as well as the claim of Theorem 6 based on that lemma) remains to hold true, if only restricted versions of assumptions $(A13)_{s}$ and $(A14)_{s}$ are satisfied, and one additionally assumes that the projection of the set $G(Q)$ onto the cone $K$ is bounded (see Remark 9).

Corollary 9.

Let assumptions $(A1)$ , $(A13)_{s}$ , and $(A14)_{s}$ hold true. Let also a sequence $\{(\lambda_{n},c_{n})\}\subset\operatorname{dom}\Theta$ be such that the sequence $\{\lambda_{n}\}$ is bounded and $c_{n}\to+\infty$ as $n\to\infty$ . Suppose finally that there exists a sequence $\{z_{n}\}\subset Q$ such that $\operatorname{dist}(G(z_{n}),K)\to 0$ and $(\mathscr{L}(z_{n},\lambda_{n},c_{n})-\Theta(\lambda_{n},c_{n}))\to 0$ as $n\to\infty$ . Then

\lim_{n\to\infty}\Theta(\lambda_{n},c_{n})=\min\big{\{}f_{*},\liminf_{p\to 0}\beta(p)\big{\}}

(30)

Proof.

Apply the previous lemma to the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ with $x_{n}=z_{n}$ for all $n\in\mathbb{N}$ . ∎

Remark 24.

The corollary above strengthens Lemma 5. Namely, it states that if there exists a sequence $\{z_{n}\}$ satisfying the assumptions of the corollary, then one can actually replace the lower and upper estimates (27) with equality (30). Note also that by the definition of augmented dual function there always exists a sequence $\{z_{n}\}\subset Q$ such that $(\mathscr{L}(z_{n},\lambda_{n},c_{n})-\Theta(\lambda_{n},c_{n}))\to 0$ as $n\to\infty$ . The main assumption of the corollary is that one can find a sequence $\{z_{n}\}$ not only satisfying this condition, but also such that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ .

Let us also provide necessary and sufficient conditions for the sequence $\{\operatorname{dist}(G(x_{n}),K)\}$ to converge to zero.

Lemma 6.

Let assumptions $(A1)$ , $(A7)$ , and $(A12)_{s}$ hold true and a sequence $\{(x_{n},\lambda_{n},c_{n})\}\subset Q\times\operatorname{dom}\Theta$ be such that:

1.

the sequence $\{\lambda_{n}\}$ is bounded,
2.

$c_{n}\to+\infty$ as $n\to\infty$ ,
3.

the sequence $\{\mathscr{L}(x_{n},\lambda_{n},c_{n})-\Theta(\lambda_{n},c_{n})\}$ is bounded above,
4.

there exists $\tau>0$ such that the function $\inf_{n}\Phi(G(\cdot),\lambda_{n},\tau)$ is bounded below on $Q$ .

Then for the sequence $\{\operatorname{dist}(G(x_{n}),K)\}$ to converge to zero it is sufficient that the sequence $\{f(x_{n})\}$ is bounded below. This condition becomes necessary, when $\liminf_{p\to 0}\beta(p)>-\infty$ .

Proof.

If only a finite number of elements of the sequence $\{x_{n}\}$ is infeasible for the problem $(\mathcal{P})$ , then the claim of the lemma is trivial, since in this case $G(x_{n})\in K$ and $f(x_{n})\geq f_{*}$ for any sufficiently large $n$ . Therefore, replacing, if necessary, the sequence $\{x_{n}\}$ with its subsequence one can suppose that $G(x_{n})\notin K$ for all $n\in\mathbb{N}$ .

Sufficiency. Denote $\varepsilon_{n}=\mathscr{L}(x_{n},\lambda_{n},c_{n})-\Theta(\lambda_{n},c_{n})$ and

\overline{\varepsilon}=\sup_{n}\varepsilon_{n}<+\infty,\quad\underline{f}=\inf_{n}f(x_{n})>-\infty,\quad\underline{\Phi}=\inf_{n}\inf_{x\in Q}\Phi(G(\cdot),\lambda_{n},\tau)>-\infty.

By Lemma 4 one has

\mathscr{L}(x_{n},\lambda_{n},c_{n})\leq\Theta(\lambda_{n},c_{n})+\varepsilon_{n}\leq f_{*}+\overline{\varepsilon}\quad\forall n\in\mathbb{N},

(31)

that is, the sequence $\{\mathscr{L}(x_{n},\lambda_{n},c_{n})\}$ is bounded above.

Fix any $r>0$ . Due to the boundedness of the sequence $\{\lambda_{n}\}$ and assumption $(A12)_{s}$ there exists $t(r)\geq\tau$ such that for any $c\geq t(r)$ , $n\in\mathbb{N}$ , and $x\in E_{n}$ one has

\Phi(G(x),\lambda_{n},c)-\Phi(G(x),\lambda_{n},\tau)\geq f_{*}-\underline{f}+\overline{\varepsilon}+1-\underline{\Phi},

which implies that $\Phi(G(x),\lambda_{n},c)\geq f_{*}-\underline{f}+\overline{\varepsilon}+1$ , where

E_{n}:=\Big{\{}x\in Q\Bigm{|}\operatorname{dist}(G(x),K)\geq r,\>\Phi(G(x),\lambda_{n},\tau)<+\infty\Big{\}}

Therefore, for any $n\in\mathbb{N}$ such that $c_{n}\geq t(r)$ and $\operatorname{dist}(G(x_{n}),K)\geq r$ one has

\mathscr{L}(x_{n},\lambda_{n},c_{n})=f(x_{n})+\Phi(G(x_{n}),\lambda_{n},c_{n})\geq f_{*}+\overline{\varepsilon}+1,

which contradicts (31). Consequently, for any $n\in\mathbb{N}$ such that $c_{n}\geq t(r)$ one has $\operatorname{dist}(G(x_{n}),K)<r$ , which implies that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ .

Necessity. Suppose by contradiction that $\operatorname{dist}(G(x_{n}),K)\to 0$ , but the sequence $\{f(x_{n})\}$ is unbounded below. Then for any sequence $\{p_{n}\}\subset Y$ such that $G(x_{n})-p_{n}\in K$ and $p_{n}\to 0$ as $n\to\infty$ (at least one such sequence exists, since that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ ) one has

-\infty=\liminf_{n\to\infty}f(x_{n})\geq\liminf_{n\to\infty}\beta(p_{n})\geq\liminf_{p\to 0}\beta(p),

which contradicts our assumption. ∎

Remark 25.

(i) The last assumption of the lemma is satisfied, in particular, if for any bounded set $\Lambda_{0}\subset\Lambda$ there exists $\tau>0$ such that the function $\inf_{\lambda\in\Lambda_{0}}\Phi(\cdot,\lambda,\tau)$ is bounded below on $Y$ . This assumption is satisfied for all particular examples of augmented Lagrangians from Section 3, except for He-Wu-Meng’s augmented Lagrangian (Example 13) under appropriate additional assumptions. Namely, in the case of Rockafellar-Wet’s augmented Lagrangian (Example 1) one needs to additionally assume that $\sigma(\cdot)\geq\sigma_{0}\|\cdot\|^{\alpha}$ for some $\sigma_{0}>0$ and $\alpha\geq 1$ , while in the case of the (penalized) exponential-type augmented Lagrangians (Examples 8, 9, 15, 17, and 18) and the hyperbolic-type augmented Lagrangian (Example 11) one needs to additionally assume that the function $\phi$ / $\psi$ is bounded below. In all other example the assumption on the boundedness below of the function $\Phi$ is satisfied without any additional assumptions.

(ii) The last assumption of the lemma is satisfied for He-Wu-Meng’s augmented Lagrangian and the (penalized) exponential/hyperbolic-type augmented Lagrangians with unbounded below functions $\phi$ / $\psi$ , if the projection of the set $G(Q)$ onto $K$ is bounded. In particular, in the case of inequality constrained problems it is sufficient to suppose that the functions $g_{i}$ , defining the constraints $g_{i}(x)\leq 0$ , are bounded below. As was noted in Remark 9, this assumption is not restrictive from the theoretical point of view.

(iii) It should be noted that we used the last assumption of the lemma in order to implicitly prove that assumption $(A12)_{s}$ implies that

\lim_{c\to\infty}\inf_{n\in\mathbb{N}}\inf\Big{\{}\Phi(y,\lambda_{n},c)\Bigm{|}y\in Y\colon\operatorname{dist}(y,K)\geq r\Big{\}}=+\infty

(32)

for any $r>0$ . Therefore one might wonder whether it would be better to formulate (32) as a basic assumption and use it instead of assumption $(A12)_{s}$ and the assumption on the boundedness below of the function $\Phi(G(\cdot),\lambda_{n},\tau)$ . Note, however, that in most particular cases the boundedness below of the function $\Phi$ is a necessary condition for (32) to hold true. In particular, one can easily check that if a separable augmented Lagrangian (see (6)) satisfies condition (32), then each function $\Phi_{i}$ is bounded below. That is why we opted to use assumption $(A12)_{s}$ along with the assumption on the boundedness below of the function $\Phi$ instead of condition (32).

Now we are ready to estimate the limit of the sequence $\{\mathscr{L}(x_{n},\lambda_{n},c_{n})\}$ and the corresponding sequences $\{\Theta(\lambda_{n},c_{n})$ and $\{f(x_{n})\}$ of the augmented dual and objective functions’ values for sequences $\{(x_{n},\lambda,c_{n})\}$ generated by the model augmented Lagrangian method. Recall that $\Theta_{*}$ is the optimal value of the augmented dual problem.

Theorem 6 (main convergence theorem).

Let $\{(x_{n},\lambda_{n},c_{n})\}$ be the sequence generated by the model augmented Lagrangian method, and suppose that the following conditions are satisfied:

1.

assumptions $(A1)$ , $(A7)$ , $(A12)_{s}$ – $(A14)_{s}$ , and $(A15)$ hold true;
2.

assumptions $(B1)$ – $(B4)$ hold true;
3.

the sequence $\{\varepsilon_{n}\}$ is bounded and $\limsup_{n\to\infty}\varepsilon_{n}=\varepsilon_{*}$ ;
4.

for any bounded set $\Lambda_{0}\subset\Lambda$ there exists $\tau>0$ such that the function $\inf_{\lambda\in\Lambda_{0}}\Phi(G(\cdot),\lambda,\tau)$ is bounded below on $Q$ .

Then in the case when the sequence $\{c_{n}\}$ is bounded one has $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ , and in the case when the sequence $\{c_{n}\}$ is unbounded one has $\operatorname{dist}(G(x_{n}),K)\to 0$ if and only if the sequence $\{f(x_{n})\}$ is bounded below. Furthermore, if the sequence $\{f(x_{n})\}$ is bounded below, then

$\displaystyle\Theta_{}-\varepsilon_{}\leq\liminf_{n\to\infty}\Theta(\lambda_{n},c_{n})$	$\displaystyle\leq\limsup_{n\to\infty}\Theta(\lambda_{n},c_{n})\leq\Theta_{*},$	(33)
$\displaystyle\Theta_{*}\leq\liminf_{n\to\infty}\mathscr{L}(x_{n},\lambda_{n},c_{n})$	$\displaystyle\leq\limsup_{n\to\infty}\mathscr{L}(x_{n},\lambda_{n},c_{n})\leq\Theta_{}+\varepsilon_{}$	(34)
$\displaystyle\Theta_{*}\leq\liminf_{n\to\infty}f(x_{n})$	$\displaystyle\leq\limsup_{n\to\infty}f(x_{n})\leq\Theta_{}+\varepsilon_{}.$	(35)

Proof.

If the sequence $\{c_{n}\}$ is unbounded, then by assumption $(B4)$ one has $c_{n}\to+\infty$ as $n\to\infty$ , and the claim of the theorem follows directly from Lemmas 5 and 6 (the fact that $\lim_{p\to 0}\beta(p)>-\infty$ follows directly from Remark 8). Therefore, suppose that the sequence of penalty parameters $\{c_{n}\}$ is bounded. Note that inequalities (33) in this case follow from the first inequality in (34) and the definition of $\Theta_{*}$ . Note further that by assumption $(B3)$ one has $\operatorname{dist}(G(x_{n}),K)\to 0$ and $\Phi(G(x_{n}),\lambda_{n},c_{n})\to 0$ as $n\to\infty$ . Consequently, one has

\liminf_{n\to\infty}\mathscr{L}(x_{n},\lambda_{n},c_{n})=\liminf_{n\to\infty}f(x_{n}),\quad\limsup_{n\to\infty}\mathscr{L}(x_{n},\lambda_{n},c_{n})=\limsup_{n\to\infty}f(x_{n}).

Thus, it is sufficient to prove either of the inequalities (34) and (35). We divide the rest of the proof into two parts.

Part 1. Lower estimate. Let $\{x_{n_{k}}\}$ be any subsequence such that

\lim_{k\to\infty}f(x_{n_{k}})=\liminf_{n\to\infty}f(x_{n})

(at least one such subsequence exists by the definition of limit inferior). Suppose at first that there exists a subsequence of the sequence $\{x_{n_{k}}\}$ , which we denote again by $\{x_{n_{k}}\}$ , that is feasible for the problem $(\mathcal{P})$ . Then $f(x_{n_{k}})\geq f_{*}$ for all $k\in\mathbb{N}$ and the lower estimate for the limit inferior in (35) holds true by Proposition 1.

Suppose now that $x_{n_{k}}$ is infeasible for the problem $(\mathcal{P})$ for all $k$ greater than some $k_{0}\in\mathbb{N}$ . Since $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ , for any $k\in k_{0}$ one can find $p_{k}\in Y$ such that $G(x_{n_{k}})-p_{k}\in K$ and $p_{k}\to 0$ as $k\to\infty$ . Consequently, $f(x_{n_{k}})\geq\beta(p_{k})$ for all $k\geq k_{0}$ and

\lim_{k\to\infty}f(x_{n_{k}})\geq\liminf_{k\to\infty}\beta(p_{k})\geq\liminf_{p\to 0}\beta(p),

which by Theorem 2 implies that the lower estimate for the limit inferior in (35) is valid.

Part 2. Upper estimate. Suppose at first that $f_{*}\leq\liminf_{p\to 0}\beta(p)$ . Then by Lemma 4 and Theorem 2 one has

\limsup_{n\to\infty}\mathscr{L}(x_{n},\lambda_{n},c_{n})\leq f_{*}+\varepsilon_{*}=\Theta_{*}+\varepsilon_{*},

that is, the upper estimate for the limit superior in (34) holds true.

Let us now consider the case $f_{*}>\liminf_{p\to 0}\beta(p)=:\beta_{*}$ . By the definition of limit inferior there exists $\{p_{n}\}\subset Y$ such that $p_{n}\to 0$ and $\beta(p_{n})\to\beta_{*}$ as $n\to\infty$ . Note that $\beta_{*}>-\infty$ by Remark 8 and, therefore, one can suppose that $\beta(p_{n})>-\infty$ for all $n\in\mathbb{N}$ .

By the definition of the optimal value function one can find a sequence $\{z_{n}\}\subset Q$ such that $G(z_{n})-p_{n}\in K$ and $f(z_{n})\leq\beta(p_{n})+1/n$ for all $n\in\mathbb{N}$ . Hence, in particular, $\operatorname{dist}(G(z_{n}),K)\to 0$ as $n\to\infty$ , which by assumption $(A15)$ implies that $\limsup_{n\to\infty}\Phi(G(z_{n}),\lambda_{n},c_{n})\leq 0$ . Consequently, one has

\limsup_{n\to\infty}\Theta(\lambda_{n},c_{n})\leq\limsup_{n\to\infty}\mathscr{L}(z_{n},\lambda_{n},c_{n})\leq\lim_{n\to\infty}f(z_{n})=\lim_{n\to\infty}\beta(p_{n})=\beta_{*}.

Recall that by the definition of $x_{n}$ one has $\mathscr{L}(x_{n},\lambda_{n},c_{n})\leq\Theta(\lambda_{n},c_{n})+\varepsilon_{n}$ . Therefore the inequality above along with Theorem 2 imply that the upper estimate for the limit superior in (34) holds true. ∎

Remark 26.

(i) The previous theorem can be slightly generalized in the following way. Namely, suppose that assumption $(B2)$ does not hold true, but there exists a bounded subsequence $\{\lambda_{n_{k}}\}$ . Then the claim of Theorem 6 holds true for the corresponding subsequence $\{(x_{n_{k}},\lambda_{n_{k}},c_{n_{k}})\}$ . In the case when the sequence $\{c_{n}\}$ is unbounded, one simply needs to apply Lemmas 5 and 6 to this subsequence. In the case when the sequence $\{c_{n}\}$ is bounded, one just needs to repeat the proof of the theorem with the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ replaced by the subsequence $\{(x_{n_{k}},\lambda_{n_{k}},c_{n_{k}})\}$ .

(ii) Note that from the proof of Theorem 6 it follows that the sequence $\{f(x_{n})\}$ is always bounded below in the case when the sequence $\{c_{n}\}$ is bounded.

(iii) In many papers on augmented Lagrangians and augmented Lagrangians methods, it is assumed by default that the function $f$ is bounded below on the set $Q$ (see [44, Assumption 1] [42, Assumption 2.3], [39, Assumption 1] [71, Assumption 1], [45, Assumption 1], [70, Assumption (1)], etc.). From the theoretical point of view this assumption is not restrictive, since one can always replace the objective function $f$ with $e^{f(\cdot)}$ . This assumption ensures that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ for sequences $\{(x_{n},\lambda_{n},c_{n})\}$ generated by the model augmented Lagrangian method, regardless of whether the sequence of penalty parameters is bounded or not. Furthermore, in the case when the sequence $\{c_{n}\}$ increases unboundedly, this assumptions guarantees that estimates (33) can be replaced with equality (30) by Corollary 9 and Lemma 6.

Corollary 10.

Let the assumptions of Theorem 6 hold true, and suppose that $\varepsilon_{n}\to 0$ as $n\to\infty$ . Then

\lim_{n\to\infty}\Theta(\lambda_{n},c_{n})=\lim_{n\to\infty}\mathscr{L}(x_{n},\lambda_{n},c_{n})=\lim_{n\to\infty}f(x_{n})=\Theta_{*}.

5.3 Primal convergence

Now we are ready to prove general theorems on convergence of the sequence $\{x_{n}\}$ generated by the model augmented Lagrangian method. Denote by $\Delta_{*}=f_{*}-\Theta_{*}$ the duality gap between the primal problem $(\mathcal{P})$ and the augmented dual problem $(\mathcal{D})$ .

Theorem 7 (primal convergence vs. duality gap).

Let the assumptions of Theorem 6 be valid, the sequence $\{f(x_{n})\}$ be bounded below, and the functions $f$ and $\operatorname{dist}(G(\cdot),K)$ be lsc on $Q$ . Then the sequence $\{x_{n}\}$ has limit points, only if $\Delta_{*}\leq\varepsilon_{*}$ (that is, the duality gap is smaller than the tolerance with which the augmented Lagrangian subproblems are solved). Furthermore, all limit points of the sequence $\{x_{n}\}$ (if such points exist) are $(\varepsilon_{*}-\Delta_{*})$ -optimal solutions of the problem $(\mathcal{P})$ .

Proof.

Suppose that there exists a limit point $x_{*}$ of the sequence $\{x_{n}\}$ , i.e. there exists a subsequence $\{x_{n_{k}}\}$ that converges to $x_{*}$ . Recall that $\operatorname{dist}(G(x_{n}),K)\to 0$ as $n\to\infty$ and

\limsup_{n\to\infty}f(x_{n})\leq\Theta_{*}+\varepsilon_{*}

by Theorem 6. Hence taking into account the semicontinuity assumptions one can conclude that $\operatorname{dist}(G(x_{*}),K)=0$ , i.e. $x_{*}$ is feasible for the problem $(\mathcal{P})$ , and

f_{*}\leq f(x_{*})\leq\Theta_{*}+\varepsilon_{*}\leq f_{*}+\varepsilon_{*}-\Delta_{*}.

Therefore, $\Delta_{*}\leq\varepsilon_{*}$ and $x_{*}$ is an $(\varepsilon_{*}-\Delta_{*})$ -optimal solution of the problem $(\mathcal{P})$ . ∎

Corollary 11 (primal convergence vs. zero duality gap).

If under the assumptions of the previous theorem $\varepsilon_{n}\to 0$ as $n\to\infty$ , then for the sequence $\{x_{n}\}$ to have limit points it is necessary that there is zero duality gap between the primal problem $(\mathcal{P})$ and the augmented dual problem $(\mathcal{D})$ . Furthermore, in this case all limit points of the sequence $\{x_{n}\}$ (if such points exist) are globally optimal solutions of the problem $(\mathcal{P})$ .

In the case when the space $X$ is reflexive (in particular, finite dimensional), we can prove a somewhat stronger result. Namely, we can show that if the zero duality gap property is not satisfied, then the sequence $\{x_{n}\}$ necessarily escapes to infinity as $n\to\infty$ .

Theorem 8 (boundedness vs. duality gap).

Let the assumptions of Theorem 6 be valid, the space $X$ be reflexive, the set $Q$ be weakly sequentially closed, the functions $f$ and $\operatorname{dist}(G(\cdot),K)$ be weakly sequentially lsc on $Q$ , the sequence $\{f(x_{n})\}$ be bounded below. Then the following statements hold true:

1.

for the sequence $\{x_{n}\}$ to have a bounded subsequence it is necessary that $\Delta_{*}\leq\varepsilon_{*}$ ;
2.

all weakly limit points of the sequence $\{x_{n}\}$ (if such points exist at all) are $(\varepsilon_{*}-\Delta_{*})$ -optimal solutions of the problem $(\mathcal{P})$ ;
3.

if $\varepsilon_{n}\to 0$ as $n\to\infty$ , then for the sequence $\{x_{n}\}$ to have a bounded subsequence it is necessary that the zero duality gap property holds true; furthermore, in this case all weakly limit points of the sequence $\{x_{n}\}$ are globally optimal solutions of the problem $(\mathcal{P})$ .

Proof.

Bearing in mind the fact that any bounded sequence in a reflexive Banach space has a weakly convergent subsequence and arguing in the same way as in the proof of Theorem 7 one can easily verify that all claims of this theorem hold true. ∎

5.4 Dual convergence

Let us now turn to analysis of dual convergence, that is, convergence of the sequence of multipliers $\{\lambda_{n}\}$ or, more precisely, convergence of the dual sequence $\{(\lambda_{n},c_{n})\}$ . Although convergence of multipliers for some particular augmented Lagrangian methods can be studied, even in the case when the sequence of multipliers $\{c_{n}\}$ increases unboundedly, with the use of optimality conditions, only convergence of the whole sequence $\{(\lambda_{n},c_{n})\}$ is apparently connected with some fundamental properties of the augmented dual problem. Such connection might exist in the case when the penalty parameter increases unboundedly, but an analysis of such connection is a challenging task, which we leave as an open problem for future research.

We start our study of the dual convergence with a simple auxiliary result that provides an important characterisation of limit points of the sequence $\{(\lambda_{n},c_{n})\}$ .

Lemma 7.

Let all assumptions of Theorem 6 be valid, except for assumption $(B2)$ . Suppose also that assumption $(A10)$ holds true and the sequence $\{c_{n}\}$ is bounded. Then any limit point $(\lambda_{*},c_{*})$ of the sequence $\{(\lambda_{n},c_{n})\}$ (if such point exists) is an $\varepsilon_{*}$ -optimal solution of the dual problem.

Proof.

Let a subsequence $\{(\lambda_{n_{k}},c_{n_{k}})\}$ converge to some $(\lambda_{*},c_{*})\in\Lambda\times(0,+\infty)$ . Then, in particular, the sequence $\{\lambda_{n_{k}}\}$ is bounded and by Theorem 6 (see also Remark 26) one has

\liminf_{k\to\infty}\Theta(\lambda_{n_{k}},c_{n_{k}})\geq\Theta_{*}-\varepsilon_{*}.

Hence bearing in mind the fact that the function $\Theta$ is upper semicontinuous by assumption $(A10)$ (see Remark 7) one can conclude that $\Theta(\lambda_{*},c_{*})\geq\Theta_{*}-\varepsilon_{*}$ , that is, $(\lambda_{*},c_{*})$ is an $\varepsilon_{*}$ -optimal solution of the dual problem. ∎

Corollary 12.

Let the assumptions of Lemma 7 be valid and suppose that the functions $f$ and $\operatorname{dist}(G(\cdot),K)$ are lsc on $Q$ , while the augmented Lagrangian $\mathscr{L}(\cdot)$ is lsc on $Q\times\Lambda\times(0,+\infty)$ . Then any limit point $(x_{*},\lambda_{*},c_{*})$ of the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ is an $2\varepsilon_{*}$ -saddle point of the augmented Lagrangian, that is,

\sup_{\lambda\in\Lambda}\mathscr{L}(x_{*},\lambda,c_{*})-2\varepsilon_{*}\leq\mathscr{L}(x_{*},\lambda_{*},c_{*})\leq\inf_{x\in Q}\mathscr{L}(x,\lambda_{*},c_{*})+\varepsilon_{*}.

(36)

Proof.

Suppose that a subsequence $\{(x_{n_{k}},\lambda_{n_{k}},c_{n_{k}})\}$ converges to some triplet $(x_{*},\lambda_{*},c_{*})\in Q\times\Lambda\times(0,+\infty)$ . Then by Theorem 6 (see also Remark 26) one has $\operatorname{dist}(G(x_{n_{k}}),K)\to 0$ as $k\to\infty$ and

\limsup_{k\to\infty}f(x_{n_{k}})\leq\Theta_{*}+\varepsilon_{*},\quad\limsup_{k\to\infty}\mathscr{L}(x_{n_{k}},\lambda_{n_{k}},c_{n_{k}})\leq\Theta_{*}+\varepsilon_{*}.

Therefore, by the lower semicontinuity assumptions one has $G(x_{*})\in K$ and

f(x_{*})\leq\Theta_{*}+\varepsilon_{*},\quad\mathscr{L}(x_{*},\lambda_{*},c_{*})\leq\Theta_{*}+\varepsilon_{*}.

On the other hand, Proposition 1 and Lemma 7 imply that

\Theta_{*}\leq f(x_{*}),\quad\Theta_{*}-\varepsilon_{*}\leq\Theta(\lambda_{*},c_{*})\leq\mathscr{L}(x_{*},\lambda_{*},c_{*}).

Hence with the use of assumption $(A1)$ one gets that

\sup_{\lambda\in\Lambda}\mathscr{L}(x_{*},\lambda,c_{*})\leq f(x_{*})\leq\mathscr{L}(x_{*},\lambda_{*},c_{*})+2\varepsilon_{*},

that is, the first inequality in (36) is satisfied.

By the definition of $x_{n}$ one has

\mathscr{L}(x_{n_{k}},\lambda_{n_{k}},c_{n_{k}})\leq\mathscr{L}(x,\lambda_{n_{k}},c_{n_{k}})+\varepsilon_{n_{k}}\quad\forall k\in\mathbb{N}\>\forall x\in Q,

which implies that

\liminf_{k\to\infty}\mathscr{L}(x_{n_{k}},\lambda_{n_{k}},c_{n_{k}})\leq\limsup_{k\to\infty}\mathscr{L}(x,\lambda_{n_{k}},c_{n_{k}})+\varepsilon_{*}\quad\forall x\in Q.

Hence with the use of assumption $(A10)$ and the fact that the function $\mathscr{L}(\cdot)$ is lsc one obtains

\mathscr{L}(x_{*},\lambda_{*},c_{*})\leq\mathscr{L}(x,\lambda_{*},c_{*})+\varepsilon_{*}\quad\forall x\in Q,

that is, the second inequality in (36) is satisfied. ∎

Remark 27.

(i) It should be noted that the augmented Lagrangian is lsc on $Q\times\Lambda\times(0,+\infty)$ for all particular examples of the function $\Phi$ from Section 3, except for Rockafellar-Wets’ augmented Lagrangian, if the function $f$ is lsc on $Q$ and the function $G$ is continuous on this set. In the case of Rockafellar-Wets’ augmented Lagrangian (Example 1) one needs to impose some additional assumptions, such as $\sigma(\cdot)=0.5\|\cdot\|^{2}$ or $K=\{0\}$ and $\sigma(\cdot)=\|\cdot\|$ . Let us also mention that in the case of inequality constrained problems, instead of assuming that $G$ is continuous, it is sufficient to suppose that the functions $g_{i}$ defining the constrained $g_{i}(x)\leq 0$ are only lower semicontinuous.

(ii) If the augmented Lagrangian $\mathscr{L}(\cdot)$ is continuous on $Q\times\Lambda\times(0,+\infty)$ , then one can replace $2\varepsilon_{*}$ in the first inequality in (36) with $\varepsilon_{*}$ . Indeed, in this case by Theorem 6 one has $\mathscr{L}(x_{*},\lambda_{*},c_{*})\geq\Theta_{*}$ and, therefore, $f(x_{*})\leq\mathscr{L}(x_{*},\lambda_{*},c_{*})+\varepsilon_{*}$ , which implies the required result.

With the use of Lemma 7 we can easily show how dual convergence is connected with existence of optimal dual solutions/global saddle points of the augmented Lagrangian.

Theorem 9 (dual convergence vs. existence of optimal dual solutions).

Let $\{(x_{n},\lambda_{n},c_{n})\}$ be the sequence generated by the model augmented Lagrangian method, and suppose that the following conditions are satisfied:

1.

assumptions $(A1)$ , $(A7)$ , $(A10)$ , $(A12)_{s}$ – $(A14)_{s}$ , and $(A15)$ hold true;
2.

assumptions $(B1)$ , $(B3)$ , and $(B4)$ hold true;
3.

$\varepsilon_{n}\to 0$ as $n\to\infty$ ;
4.

for any bounded set $\Lambda_{0}\subset\Lambda$ there exists $\tau>0$ such that the function $\inf_{\lambda\in\Lambda_{0}}\Phi(G(\cdot),\lambda,\tau)$ is bounded below on $Q$ .

Then for the sequence of penalty parameters $\{c_{n}\}$ to be bounded and the sequence of multipliers $\{\lambda_{n}\}$ to have a limit point it is necessary that a globally optimal solution of the dual problem $(\mathcal{D})$ exists.

Proof.

By Lemma 7, under the assumptions of the theorem any limit point of the sequence $\{(\lambda_{n},c_{n})\}$ is a globally optimal solution of the dual problem. Therefore, for the existence of such limit (or, equivalently, for the sequence $\{c_{n}\}$ to be bounded and the sequence $\{\lambda_{n}\}$ to have a limit point) it is necessary that a globally optimal solution of the dual problem exists. ∎

Theorem 10 (full convergence vs. existence of global saddle points).

Let all assumptions of Theorem 9 be valid and suppose that the functions $f$ and $\operatorname{dist}(G(\cdot),K)$ are lsc on the set $Q$ . The for the sequence of penalty parameters $\{c_{n}\}$ to be bounded and the sequence $\{(x_{n},\lambda_{n})\}$ to have a limit point it is necessary that there exists a global saddle point of the augmented Lagrangian $\mathscr{L}(\cdot)$ . Moreover, for any limit point $\{(x_{*},\lambda_{*},c_{*})\}$ of the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ (if such point exists) the pair $(x_{*},\lambda_{*})$ is a global saddle point of the augmented Lagrangian and $c_{*}\geq c_{*}(x_{*},\lambda_{*})$ .

Proof.

Let $(x_{*},\lambda_{*},c_{*})$ be a limit point of the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ . Then by Lemma 7 the pair $(\lambda_{*},c_{*})$ is an optimal dual solution. In turn, by applying Theorem 6 (see also Remark 26) one can readily verify that the zero duality gap property is satisfied and $x_{*}$ is a globally optimal solution of the problem $(\mathcal{P})$ . Therefore, by Theorem 4 the pair $(x_{*},\lambda_{*})$ is a global saddle point of $\mathscr{L}(x,\lambda,c)$ and $c_{*}\geq c_{*}(x_{*},\lambda_{*})$ . Consequently, for the existence of a limit point of the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ it is necessary that there exists a global saddle point of the augmented Lagrangian. ∎

In the case when the space $Y$ is reflexive one can prove somewhat stronger versions of the previous theorems that uncover a connection between the boundedness of the sequences of multipliers and penalty parameters and the existence of optimal dual solutions/global saddle points.

Theorem 11 (boundedness vs. existence of optimal dual solutions).

Suppose that $\{(x_{n},\lambda_{n},c_{n})\}$ is the sequence generated by the model augmented Lagrangian method, and let the following conditions be satisfied:

1.

the space $Y$ is reflexive;
2.

assumptions $(A1)$ , $(A7)$ , $(A9)_{s}$ , $(A10)$ , $(A12)_{s}$ – $(A14)_{s}$ , and $(A15)$ hold true;
3.

assumptions $(B1)$ , $(B3)$ , and $(B4)$ hold true;
4.

the sequence $\{\varepsilon_{n}\}$ is bounded and $\limsup_{n\to\infty}\varepsilon_{n}=\varepsilon_{*}$ .
5.

for any bounded set $\Lambda_{0}\subset\Lambda$ there exists $\tau>0$ such that the function $\inf_{\lambda\in\Lambda_{0}}\Phi(G(\cdot),\lambda,\tau)$ is bounded below on $Q$ .

Then the following statements hold true:

1.

any weakly limit point of the sequence $\{(\lambda_{n},c_{n})\}$ (if such point exists) is an $\varepsilon_{*}$ -optimal solution of the problem $(\mathcal{D})$ ;
2.

if $\varepsilon_{n}\to 0$ as $n\to\infty$ , then for the boundedness of the sequence $\{(\lambda_{n},c_{n})\}$ it is necessary that there exists a globally optimal solution of the augmented dual problem $(\mathcal{D})$ ;
3.

if, in addition, $X$ is reflexive, $Q$ is weakly sequentially closed, the functions $f$ and $\operatorname{dist}(G(\cdot),K)$ are weakly sequentially lsc on $Q$ , and $\varepsilon_{n}\to 0$ as $n\to\infty$ , then for the boundedness of the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ it is necessary that there exists a global saddle point of the augmented Lagrangian; furthermore, for any weakly limit point $(x_{*},\lambda_{*},c_{*})$ of the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ the pair $(x_{*},\lambda_{*})$ is a global saddle point of $\mathscr{L}(x,\lambda,c)$ and $c_{*}\geq c_{*}(x_{*},\lambda_{*})$ .

Proof.

The proof of this theorem almost literally repeats the proofs of Lemma 7 and Theorems 9 and 10. One only needs to use the facts that (i) any bounded sequence from a reflexive Banach space has a weakly convergent subsequence, (ii) the augmented dual function $\Theta(\lambda,c)$ is usc and concave by assumptions $(A9)_{s}$ and $(A10)$ , and (iii) any usc concave function defined on a Banach space is also weakly sequentially usc. ∎

Remark 28.

It should be underlined that the previous theorem provides necessary conditions for the boundedness of sequences $\{(x_{n},\lambda_{n},c_{n})\}$ generated by the model augmented Lagrangian method irrespective of the way in which the sequences of multipliers $\{\lambda_{n}\}$ and penalty parameters $\{c_{n}\}$ are updated. As long as the assumptions of the theorem are satisfied, the existence of a global saddle point is a necessary conditions for the boundedness of the sequence $\{(x_{n},\lambda_{n},c_{n})\}$ . Similarly, the existence of an optimal dual solution is a necessary condition for the boundedness of the sequences $\{\lambda_{n},\}$ and $\{c_{n}\}$ , regardless of the way in which they are updated.

Let us finally return to Example 20 in order to demonstrate how one can apply general convergence results obtained in this seciton to better understand and predict behaviour of primal-dual augmented Lagrangian methods.

Example 22.

Let $X=Y=\mathbb{R}$ . Consider the following optimization problem:

\min\>f(x)=-x^{2}\quad\text{subject to}\enspace g_{1}(x)=x-1\leq 0,\enspace g_{2}(x)=-x-1\leq 0.

(37)

Let $\mathscr{L}(\cdot)$ be the Hestenes-Powell-Rockafellar augmented Lagrangian for this problem (see (18)). As was shown in Example 20, the zero duality gap property holds true in this case, but the augmented dual problem has no globally optimal solutions.

Let the multipliers and the penalty parameter be updated in accordance with the classic augmented Lagrangian method (see, e.g. [5, Algorithm 4.1]), that is,

\lambda_{(n+1),1}=\max\big{\{}\lambda_{n1}+c_{n}g_{1}(x_{n}),0\big{\}},\quad\lambda_{(n+1),2}=\max\big{\{}\lambda_{n2}+c_{n}g_{2}(x_{n}),0\big{\}}

(38)

and

c_{n+1}=\begin{cases}c_{n},&\text{if }n=0\text{ or }\|V_{n}\|\leq\tau\|V_{n-1}\|,\\ \gamma c_{n},&\text{otherwise},\end{cases}

(39)

where $\tau\in(0,1)$ and $\gamma>1$ are fixed parameters and

V_{ni}:=\min\left\{-g_{i}(x_{n}),\frac{\mu_{ni}}{c_{n}}\right\},\quad i\in\{1,2\}.

One can readily check that assumptions $(B1)$ , $(B3)$ , and $(B4)$ hold true in this case, if $c_{\min}\geq 2$ . Hence with the use of Theorem 11 one can conclude that the sequence $\{(\lambda_{n},c_{n})\}$ has no bounded subsequence, which means that either $c_{n}\to+\infty$ or $\|\lambda_{n}\|\to+\infty$ as $n\to\infty$ . Let us provide a numerical example to illustrate this claim.

Table 1: First 10 iterations of the model augmented Lagrangian method for problem (37).

$n$	0	1	2	3	4	5	6	7	8	9
$x_{n}$	2	-3	1.5	-1.5	1.2	-1.2	1.0909	-1.0909	1.0435	-1.0435
$\lambda_{n1}$	1	4	0	3	0	2.4	0	2.1818	0	2.087
$\lambda_{n2}$	1	0	6	0	3	0	2.4	0	2.1818	0
$c_{n}$	3	3	6	6	12	12	24	24	48	48

Let $\tau=0.9$ , $\gamma=2$ , $c_{0}=3$ , and $\lambda_{0}=(1,1)$ . First 10 iterations of the model augmented Lagrangian method with multiplier updates (38) and penalty parameter updates (39) are given in Table 1. Let us note that the points of global minimum of the augmented Lagrangian were computed analytically. The results of computer simulation have shown that $c_{n}\to\infty$ , $\lambda_{2n}\to(2,0)$ , $\lambda_{2n+1}\to(0,2)$ , $x_{2n}\to 1$ , and $x_{2n+1}\to-1$ as $n\to\infty$ (this fact can be proved analytically, but its proof is rather cumbersome, which is why we do not present it here). Thus, the iterations of the method oscillate between gradually shrinking neighbourhoods of two globally optimal solutions of problem (37) and the KKT multipliers corresponding to these solutions, while the penalty parameter increases unboundedly.

Remark 29.

The convergence theory for the model augmented Lagrangian method presented in this paper generalizes and unifies many existing results on convergence of augmented Lagrangian methods. In particular, many such results either directly follow from Theorems 6, 7, and 10 and Lemma 7 or can be easily deduced from them, including [2, Proposition 2.1], [50, Theorem 6.1, part (1)], [44, Theorems 1–3 and 7], [42, Theorems 2.4 and 3.1], [45, Theorems 4 and 7], [5, Theorem 5.2], [48, Theorem 5, part (iii)], etc.

References

[1] A. M. Bagirov, G. Ozturk, and R. Kasimbeyli. A shapr augmented Lagrangian-based method for constrained non-convex optimization. Optim. Methods Softw., 34:462–488, 2019.
[2] D. P. Bertsekas. Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York, 1982.
[3] E. G. Birgin, R. A. Castillo, and J. M. Martinez. Numerical comparison of augmented Lagragian algorithms for nonconvex problems. Comput. Optim. Appl., 31:31–55, 2005.
[4] E. G. Birgin and J. M. Martinez. Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization. Comput. Optim. Appl., 51:941–965, 2012.
[5] E. G. Birgin and J. M. Martinez. Practical Augmented Lagrangian Methods for Constrained Optimization. SIAM, Philadelphia, 2014.
[6] J. F. Bonnans and A. Shapiro. Perturbation analysis of optimization problems. Springer, New York, 2000.
[7] R. S. Burachik. On primal convergence for augmented Lagrangian duality. Optim., 60:979–990, 2011.
[8] R. S. Burachik, R. N. Gasimov, N. A. Ismayilova, and C. Kaya. On a modified subgradient algorithm for dual problems via sharp augmented Lagrangian. J. Glob. Optim., 34:55–78, 2006.
[9] R. S. Burachik, A. N. Iusem, and J. G. Melo. Duality and exact penalization for general augmented Lagrangians. J. Optim. Theory Appl., 147:125–140, 2010.
[10] R. S. Burachik, A. N. Iusem, and J. G. Melo. A primal dual modified subgradient algorithm with sharp Lagrangian. J. Glob. Optim., 46:55–78, 2010.
[11] R. S. Burachik, A. N. Iusem, and J. G. Melo. An inexact modified subgradient algorithm for primal-dual problems via augmented Lagrangians. J. Optim. Theory Appl., 157:108–131, 2013.
[12] R. S. Burachik, A. N. Iusem, and J. G. Melo. The exact penalty map for nonsmooth and nonconvex optimization. Optim., 64:717–738, 2015.
[13] R. S. Burachik and C. Y. Kaya. An update rule and a convergence result for a penalty function method. J. Ind. Manag. Optim., 3:381–398, 2007.
[14] R. S. Burachik, C. Y. Kaya, and X. Liu. A primal-dual algorithm as applied to optimal control problems. arXiv: 2304.03465, 2023.
[15] R. S. Burachik, C. Y. Kaya, and M. Mammadov. An inexact modified subgradient algorithm for nonconvex optimization. Comput. Optim. Appl., 45:1–34, 2008.
[16] R. S. Burachik and X. Liu. An inexact deflected subgradient algorithm in infinite dimensional spaces. arXiv: 2302.02072, 2023.
[17] R. S. Burachik and A. Rubinov. Abstract convexity and augmented Lagrangians. SIAM J. Optim., 18:413–436, 2007.
[18] R. S. Burachik, X. Q. Yang, and Y. Y. Zhou. Existence of augmented Lagrange multipliers for semi-infinite programming problems. J. Optim. Theory Appl., 173:471–503, 2017.
[19] E. Burman, P. Hansbo, and M. G. Larson. The augmented Lagrangian method as a framework for stabilised methods in computational mechanics. Arch. Comput. Methods Eng., 30:2579–2604, 2023.
[20] A. Conn, N. I. M. Gould, and P. Toint. A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal., 28:545–572, 1991.
[21] M. V. Dolgopolik. Existence of augmented Lagrange multipliers: reduction to exact penalty functions and localization principle. Math. Program., 166:297–326, 2017.
[22] M. V. Dolgopolik. Augmented Lagrangian functions for cone constrained optimization: the existence of global saddle points and exact penalty property. J. Glob. Optim., 71:237–296, 2018.
[23] M. V. Dolgopolik. Minimax exactness and global saddle points of nonlinear augmented Lagrangians. J. Appl. Numer. Optim., 3:61–83, 2021.
[24] M. J. Feizollahi, S. Ahmed, and A. Sun. Exact augmented Lagrangian duality for mixed integer linear programming. Math. Program., 161:365–387, 2017.
[25] M. Fortin and R. Glowinski. Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems. North-Holland, Amsterdam, 1983.
[26] M. Fukushima, Z.-Q. Luo, and P. Tseng. Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim., 12:436–460, 2001.
[27] R. N. Gasimov. Augmented Lagrangian duality and nondifferentiable optimization methods in nonconvex programming. J. Glob. Optim., 24:187–203, 2002.
[28] S. He, L. Wu, and H. Meng. A nonlinear Lagrangian for constrained optimization problems. J. Appl. Math. Comput., 38:669–685, 2012.
[29] M. R. Hestenes. Multiplier and gradient methods. J. Optim. Theory Appl., 4:303–320, 1969.
[30] R. A. Horn and C. R. Johnson. Topics in matrix analysis. Cambridge University Press, Cambridge, 1991.
[31] X. X. Huang and X. Q. Yang. A unified augmented Lagrangian approach to duality and exact penalization. Math. Oper. Res., 28:533–552, 2003.
[32] X. X. Huang and X. Q. Yang. Further study on augmented Lagrangian duality theory. J. Glob. Optim., 31:193–210, 2005.
[33] X. X. Huang, X. Q. Yang, and K. L. Teo. Augmented Lagrangian and nonlinear semidefinite programs. In F. Giannessi and A. Maugeri, editors, Variational Analysis and Applications, pages 513–529. Springer, Boston, 2005.
[34] K. Ito and K. Kunisch. Lagrange Multiplier Approach to Variational Problems and Applications. SIAM, Philadelphia, 2008.
[35] A. N. Iusem. Augmented Lagrangian methods and proximal point methods for convex optimization. Investigación Operativa, 8:11–49, 1999.
[36] K. C. Kiwiel. On the twice differentiable cubic augmented Lagrangian. J. Optim. Theory Appl., 88:233–236, 1996.
[37] D. Li and X. L. Sun. Convexification and existence of saddle point in a pth-power reformulation for nonconvex constrained optimization. Nonlinear Anal., 47:5611–5622, 2001.
[38] Y. Li and L. Zhang. A new nonlinear Lagrangian method for nonconvex semidefinite programming. J. Appl. Anal., 15:149–172, 2009.
[39] Q. Liu and X. Yang. Zero duality and saddle points of a class of augmented Lagrangian functions in constrained non-convex optimization. Optim., 57:655–667, 2008.
[40] Y. J. Liu and L. W. Zhang. Convergence analysis of the augmented Lagrangian method for nonlinear second-order cone optimization problems. Nonlinear Anal.: Theory, Methods, Appl., 67:1359–1373, 2007.
[41] Y. J. Liu and L. W. Zhang. Convergence of the augmented Lagrangian method for nonlinear optimization problems over second-order cones. J. Optim. Theory Appl., 139:557–575, 2008.
[42] H. Luo, X. Sun, and H. Wu. Convergence properties of augmented Lagrangian methods for constrained global optimization. Optim. Methods Softw., 23:763–778, 2008.
[43] H. Luo, H. Wu, and J. Liu. On saddle points in semidefinite optimization via separation scheme. J. Optim. Theory Appl., 165:113–150, 2015.
[44] H. Z. Luo, X. L. Sun, and D. Li. On the convergence of augmented Lagrangian methods for constrained global optimization. SIAM J. Optim., 18:1209–1230, 2007.
[45] H. Z. Luo, H. X. Wu, and G. T. Chen. On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming. J. Glob. Optim., 54:599–618, 2012.
[46] O. L. Mangasarian. Unconstrained Lagrangians in nonlinear programming. SIAM J. Control, 12:772–791, 1975.
[47] D. Noll. Local convergence of an augmented Lagrangian method for matrix inequality constrained programming. Optim. Methods Softw., 22:777–802, 2007.
[48] M. C. W. Oliveira and C. Sagastizábal. Revisiting augmented Lagrangian duals. Math. Program., 196:235–277, 2022.
[49] R. Polyak. Modified barrier functions: theory and methods. Math. Program., 54:177–222, 1992.
[50] R. A. Polyak. Log-sigmoid multipliers method in constrained optimization. Ann. Oper. Res., 101:427–460, 2001.
[51] R. A. Polyak. Nonlinear rescaling vs. smoothing technique in convex optimization. Math. Program., 92:197–235, 2002.
[52] M. J. D. Powell. A method for nonlinear constraints in minimization problems. In R. Fletcher, editor, Optimization, pages 283–298. Academic Press, London, 1969.
[53] L. M. Ramirez, N. Maculan, A. E. Xavier, and V. L. Xavier. Dislocation hyperbolic augmented Lagrangian algorithm for nonconvex optimization. RAIRO Oper. Res., 57:2941–2950, 2023.
[54] R. T. Rockafellar. Convex Analysis. Princeton University Press, Princeton, 1970.
[55] R. T. Rockafellar. The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl., 12:555–562, 1973.
[56] R. T. Rockafellar. Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM J. Control Optim., 12:268–285, 1974.
[57] R. T. Rockafellar. Lagrange multipliers and optimality. SIAM Review, 35:183–238, 1993.
[58] R. T. Rockafellar and R. J.-B. Wets. Variational Analysis. Springer-Verlar, Berlin, 1998.
[59] A. M. Rubinov, X. X. Huang, and X. Q. Yang. The zero duality gap property and lower semicontinuity of the perturbation function. Math. Oper. Res., 27:775–791, 2002.
[60] A. M. Rubinov and X. Q. Yang. Lagrange-type functions in constrained nonconvex optimization. Kluwer Academic Publishers, Boston, 2003.
[61] J. J. Rückmann and A. Shapiro. Augmented Lagrangians in semi-infinite programming. Math. Program., 116:499–512, 2009.
[62] A. Shapiro and J. Sun. Some properties of the augmented Lagrangian in cone constrained optimization. Math. Oper. Res., 29:479–491, 2004.
[63] M. Stingl. On the solution of nonlinear semidefinite programs by augmented Lagrangian methods. PhD thesis, Institute of Applied Mathematics II, Friedrech-Alexander University of Erlangen-Nuremberg, Erlangen, Germany, 2006.
[64] D. Sun and J. Sun. Löwner’s operator and spectral functions in euclidean jordan algebras. Math. Oper. Res., 33:421–445, 2008.
[65] D. Sun, J. Sun, and L. Zhang. The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program., 114:349–391, 2008.
[66] J. Sun. On methods for solving nonlinear semidefinite optimization problems. Numer. Algebra Control Optim., 1:1–14, 2011.
[67] J. Sun, L. W. Zhang, and Y. Wu. Properties of the augmented Lagrangian in nonlinear semidefinite optimization. J. Optim. Theory Appl., 129:437–456, 2006.
[68] X. L. Sun, D. Li, and K. I. M. McKinnon. On saddle points of augmented Lagrangians for constrained nonconvex optimization. SIAM J. Optim., 15:1128–1146, 2005.
[69] P. Tseng and D. P. Bertsekas. On the convergence of the exponential multiplier method for convex programming. Math. Program., 60:1–19, 1993.
[70] C. Wang, Q. Liu, and B. Qu. Global saddle points of nonlinear augmented Lagrangian functions. J. Glob. Optim., 68:125–146, 2017.
[71] C. Y. Wang and D. Li. Unified theory of augmented Lagrangian methods for constrained global optimization. J. Glob. Optim., 44:433–458, 2009.
[72] C. Y. Wang, X. Q. Yang, and X. M. Yang. Nonlinear augmented Lagrangian and duality theory. Math. Oper. Res., 38:740–760, 2012.
[73] Z. Wen, D. Goldfarb, and W. Yin. Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput., 2:203–230, 2010.
[74] H. Wu, H. Luo, X. Ding, and G. Chen. Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programming. Comput. Optim. Appl., 56:531–558, 2013.
[75] H. X. Wu and H. Z. Luo. A note on the existence of saddle points of p-th power Lagrangian for constrained nonconvex optimization. Optim., 61:1231–1245, 2012.
[76] H. X. Wu and H. Z. Luo. Saddle points of general augmented Lagrangians for constrained nonconvex optimization. J. Glob. Optim., 53:683–697, 2012.
[77] H. X. Wu, H. Z. Luo, and J. F. Yang. Nonlinear separation approach for the augmented Lagrangian in nonlinear semidefinite programming. J. Glob. Optim., 59:695–727, 2014.
[78] A. E. Xavier. Hyperbolic penalty: a new method for nonlinear programming with inequalities. Int. Trans. Oper. Res., 8:659–671, 2001.
[79] G. D. Yalcin and R. Kasimbeyli. On weak conjugacy, augmented Lagrangians and duality in nonconvex optimization. Math. Methods Oper. Res., 92:199–228, 2020.
[80] H. Yamashita and H. Yabe. A survey of numerical methods for nonlinear semidefinite programming. J. Oper. Res. Soc. Jpn., 58:24–60, 2015.
[81] L. Zhang, J. Gu, and X. Xiao. A class of nonlinear Lagrangians for nonconvex second order cone programming. Comput. Optim. Appl., 49:61–99, 2011.
[82] L. Zhang, Y. Li, and J. Wu. Nonlinear rescaling Lagrangians for nonconvex semidefinite programming. Optim., 63:899–920, 2014.
[83] X. Y. Zhao, D. Sun, and K.-C. Toh. A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim., 20:1737–1765, 2010.
[84] J. Zhou and J. S. Chen. On the existence of saddle points for nonlinear second-order cone programming problems. J. Glob. Optim., 62:459–480, 2015.
[85] J. Zhou, N. Xiu, and C. Wang. Saddle point and exact penalty representation for generalized proximal Lagrangians. J. Glob. Optim., 54:669–687, 2012.
[86] Y. Y. Zhou and X. Q. Yang. Duality and penalization in optimization via an augmented Lagrangian function with applications. J. Optim. Theory Appl., 140:171–188, 2009.
[87] Y. Y. Zhou and X. Q. Yang. Augmented Lagrangian functions for constrained optimization problems. J. Glob. Optim., 52:95–108, 2012.
[88] Y. Y. Zhou, J. C. Zhou, and X. Q. Yang. Existence of augmented Lagrange multipliers for cone constrained optimization problems. J. Glob. Optim., 58:243–260, 2014.