# Well-Posedness and Primal-Dual Analysis of Some Convex Separable Optimization Problems

Authors: Stefan M. Stefanov
Journal: Advances in Operations Research
 (2013)

---

## Abstract

We focus on some convex separable optimization problems, considered by the author in previous papers, for which problems, necessary and sufficient conditions or sufficient conditions have been proved, and convergent algorithms of polynomial computational complexity have been proposed for solving these problems. The concepts of well-posedness of optimization problems in the sense of Tychonov, Hadamard, and in a generalized sense, as well as calmness in the sense of Clarke, are discussed. It is shown that the convex separable optimization problems under consideration are calm in the sense of Clarke. The concept of stability of the set of saddle points of the Lagrangian in the sense of Gol'shtein is also discussed, and it is shown that this set is not stable for the “classical” Lagrangian. However, it turns out that despite this instability, due to the specificity of the approach, suggested by the author for solving problems under consideration, it is not necessary to use modified Lagrangians but only the “classical” Lagrangians. Also, a primal-dual analysis for problems under consideration in view of methods for solving them is presented.


---

## Body

## 1. Introduction

### 1.1. Statement of Problems under Consideration: Preliminary Results

In this paper, we study well-posedness and present primal-dual analysis of some convex separable optimization problems, considered by the author in previous papers. For the sake of convenience, in this subsection we recall main results of earlier papers that are used in this study.In paper [1], the following convex separable optimization problem was considered:(
C
)
(1)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
,
(2)
subject
to
∑
j
∈
J
‍
d
j
(
x
j
)
≤
α
,
(3)
subject
to
a
j
≤
x
j
≤
b
j
,
j
∈
J
,
where cj(xj) are twice differentiable strictly convex functions, and dj(xj) are twice differentiable convex functions, defined on the open convex sets Xj in  ℝ,j∈J, respectively, dj′(xj)>0 for every j∈J,  x=(xj)j∈J, and J≡{1,…,n}.Assumptions for problem(C) are as follows.(I.1)
aj≤bj for all j∈J. If ak=bk for some k∈J, then the value xk∶=ak=bk is determined a priori.(II.1)
∑j∈J‍dj(aj)≤α. Otherwise, the constraints (2) and (3) are inconsistent and the feasible set X, defined by (2)-(3), is empty. In addition to this assumption, we suppose that α≤∑j∈J‍dj(bj) in some cases which are specified below.(III.1)
(Slater’s constraint qualification) There exists a pointx¯=(x¯1,…,x¯n)∈X such that ∑j∈J‍dj(x¯j)<α.Under these assumptions, the following characterization theorem (necessary and sufficient condition) for problem(C) was proved in [1].Denote byhj≤,hj=,hj≥ the values of xj, for which cj′(xj)=0 for the three problems under consideration in this paper, respectively.Theorem 1 (characterization of the optimal solution to problem(C)).
Under the above assumptions, a feasible solutionx*=(xj*)j∈J∈X is an optimal solution to problem (C) if and only if there exists a λ∈ℝ+1 such that
(4)xj*=aj,j∈Jaλ≝{j∈J:λ≥-cj′(aj)dj′(aj)}(5)xj*=bj,j∈Jbλ≝{j∈J:λ≤-cj′(bj)dj′(bj)}(6)xj*:λdj′(xj*)=-cj′(xj*),j∈Jλ≝{j∈J:-cj′(bj)dj′(bj)<λ<-cj′(aj)dj′(aj)}.The following polynomial algorithm for solving problem(C) with strictly convex differentiable functions cj(xj),j∈J, was suggested in [1].Algorithm 2.
(0)
Initialization:J:={1,…,n},  k:=0,  α(0):=α,  n(0):=n,J(0):=J,   Jaλ:=∅,   Jbλ:=∅, initialize  hj≤,  j∈J.
If∑j∈J‍dj(aj)≤α go to Step (1), else go to Step (9).
(1)
Construct the setsJa0,  Jb0,  J0 by using (4), (5), (6) with λ=0.
Calculate(7)δ(0)∶=∑j∈Ja0‍dj(aj)+∑j∈Jb0‍dj(bj)+∑j∈J0‍dj(hj≤)-α.
Ifδ(0)≤0 then λ:=0, go to Step (8)
else ifδ(0)>0, then
ifα≤∑j∈J‍dj(bj) go to Step (2)
else ifα>∑j∈J‍dj(bj) go to Step (9)
(there does not existλ*>0 such that δ(λ*)=0).
(2)
J
λ
(
k
)
:
=
J
(
k
). Calculate λ(k) by using the explicit expression of λ, calculated from the equality ∑j∈Jλ(k)‍dj(xj)=α(k), where xj,j∈Jλ(k), are given by (6). Go to Step (3).
(3)
Construct the setsJaλ(k),  Jbλ(k),  Jλ(k) through (4), (5), (6) (with j∈J(k) instead of j∈J) and find their cardinal numbers|Jaλ(k)|,  |Jbλ(k)|,  |Jλ(k)|, respectively. Go to Step (4).
(4)
Calculate(8)δ(λ(k))≔∑j∈Jaλ(k)‍dj(aj)+∑j∈Jbλ(k)‍dj(bj)+∑j∈Jλ(k)‍dj(xj*)-α(k),
wherexj*,j∈Jλ(k), are calculated from (6) with λ=λ(k). Go to Step (5).
(5)
Ifδ(λ(k))=0 or Jλ(k)=∅ then λ:=λ(k),  Jaλ:=Jaλ∪Jaλ(k),Jbλ∶=Jbλ∪Jbλ(k),  Jλ∶=Jλ(k), go to Step (8)
else ifδ(λ(k))>0 go to Step (6)
else ifδ(λ(k))<0 go to Step (7).
(6)
x
j
*
:
=
a
j for j∈Jaλ(k),  α(k+1):=α(k)-∑j∈Jaλ(k)‍dj(aj),  J(k+1):=J(k)∖Jaλ(k),
n
(
k
+
1
)
:
=
n
(
k
)
-
|
J
a
λ
(
k
)
|,  Jaλ:=Jaλ∪Jaλ(k),  k:=k+1. Go to Step (2).
(7)
x
j
*
:
=
b
j for j∈Jbλ(k),  α(k+1):=α(k)-∑j∈Jbλ(k)‍dj(bj),  J(k+1):=J(k)∖Jbλ(k),
n
(
k
+
1
)
:
=
n
(
k
)
-
|
J
b
λ
(
k
)
|,  Jbλ:=Jbλ∪Jbλ(k),  k:=k+1. Go to Step (2).
(8)
x
j
*
∶
=
a
j for j∈Jaλ; xj*∶=bj for j∈Jbλ; assign xj* the value calculated from (6) for j∈Jλ. Go to Step (10).
(9)
Problem(C) has no optimal solution because X=∅ or there does not existλ>0 satisfying Theorem 1.
(10)
End.It is proved in [1] that this algorithm is convergent.Theorem 3 (convergence of Algorithm2).
Let{λ(k)} be the sequence generated by Algorithm 2. Then, (i)
ifδ(λ(k))>0, then λ(k)≤λ(k+1),(ii)
ifδ(λ(k))<0, then λ(k)≥λ(k+1).In paper [2], the following two convex separable optimization problems were considered:(
C
=
)
(9)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
(10)
subject
to
∑
j
∈
J
‍
d
j
x
j
=
α
,
(11)
subject
to
a
j
≤
x
j
≤
b
j
,
j
∈
J
,
and(
C
≥
)
(12)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
(13)
subject
to
∑
j
∈
J
‍
d
j
x
j
≥
α
(14)
subject
to
a
j
≤
x
j
≤
b
j
,
j
∈
J
,
where for both problems, cj(xj) are twice differentiable convex functions, defined on the open convex sets Xj in ℝ, j∈J, respectively, dj>0, for every j∈J, x=(xj)j∈J, and J={1,…,n}.Assumptions for problem(C=) are as follows.(I.2)
aj≤bj for each j∈J.(II.2)
∑j∈J‍djaj≤α≤∑j∈J‍djbj. Otherwise the constraints (10), (11) are inconsistent and XL=∅, where XL is defined by (10)-(11).Under these assumptions, the following characterization theorem (necessary and sufficient condition) for problem(C=) is proved in [2].Theorem 4 (characterization of the optimal solution to problem(C=)).
A feasible solutionx*=(xj*)j∈J∈XL is an optimal solution to problem (C=) if and only if there exists a λ∈ℝ1 such that
(15)xj*=aj,j∈Jaλ≝{j∈J:λ≥-cj′(aj)dj},(16)xj*=bj,j∈Jbλ≝{j∈J:λ≤-cj′(bj)dj},(17)xj*:λdj=-cj′(xj*),j∈Jλ≝{j∈J:-cj′(bj)dj<λ<-cj′(aj)dj}.Assumptions for problem(C≥) are as follows.(I.3)
aj≤bj for all j∈J.(II.3)
α≤∑j∈J‍djbj. Otherwise the constraints (13), (14) are inconsistent and X≥=∅, where X≥ is defined by (13)-(14).Under these assumptions, the following theorem (sufficient condition) for problem(C≥) is proved in [2].Theorem 5 (sufficient condition for optimal solution to problem(C≥)).
Letxj*, j∈Jbe components of the optimal solution to problem C=. Then:(i)
Ifλ=-cj′(xj*)/dj≤0, then xj*,j∈J, solve problem (C≥) as well.(ii)
Ifλ=-cj′(xj*)/dj>0, then xj≥,j∈J defined as follows:xj≥=bj,j∈Jbλ,xj≥=min{bj,hj≥},j∈Jλ,xj≥=min{bj,hj≥}for all j∈Jaλ such that cj′(aj)<0,xj≥=aj  for all  j∈Jaλ, such that cj′(aj)≥0
solve problem(C≥).The following polynomial algorithm for solving problem(C=) with strictly convex differentiable functions cj(xj) was suggested in [2].Algorithm 6.
(1)
Initialization:J:={1,…,n},  k:=0,  α(0):=α,  n(0):=n,J(0):=J,  Jaλ:=∅,  Jbλ:=∅, initialize hj=,j∈J.
If∑j∈J‍djaj≤α≤∑j∈J‍djbj go to Step (2), else go to Step (9).
(2)
J
λ
(
k
)
:
=
J
(
k
). Calculate λ(k) by using the explicit expression of λ, calculated from the equality constraint ∑j∈Jλ(k)‍djxj=α(k), where xj,j∈Jλ(k), are given by (17). Go to Step (3).
(3)
Construct the setsJaλ(k),Jbλ(k),Jλ(k) through (15), (16), (17) (with J(k) instead of J) and find their cardinalities |Jaλ(k)|,|Jbλ(k)|,|Jλ(k)|, respectively. Go to Step (4).
(4)
Calculate(18)δ(λ(k))∶=∑j∈Jaλ(k)‍djaj+∑j∈Jbλ(k)‍djbj+∑j∈Jλ(k)‍djxj*-α(k),
wherexj*,j∈Jλ(k), are calculated from (17) with λ=λ(k). Go to Step (5).
(5)
Ifδ(λ(k))=0 or Jλ(k)=∅ then λ:=λ(k),  Jaλ:=Jaλ∪Jaλ(k),Jbλ∶=Jbλ∪Jbλ(k),  Jλ:=Jλ(k), go to Step (8)
else ifδ(λ(k))>0 go to Step (6)
else ifδ(λ(k))<0 go to Step (7).
(6)
x
j
*
:
=
a
j for j∈Jaλ(k),  α(k+1):=α(k)-∑j∈Jaλ(k)‍djaj,  J(k+1):=J(k)∖Jaλ(k),
n
(
k
+
1
)
:
=
n
(
k
)
-
|
J
a
λ
(
k
)
|,  Jaλ:=Jaλ∪Jaλ(k),  k:=k+1. Go to Step (2).
(7)
x
j
*
:
=
b
j for j∈Jbλ(k),  α(k+1):=α(k)-∑j∈Jbλ(k)djbj,  J(k+1):=J(k)∖Jbλ(k),
n
(
k
+
1
)
:
=
n
(
k
)
-
|
J
b
λ
(
k
)
|,  Jbλ:=Jbλ∪Jbλ(k),  k:=k+1. Go to Step (2).
(8)
x
j
*
:
=
a
j for j∈Jaλ;xj*:=bj for j∈Jbλ; assign xj* the value, calculated from (17) for j∈Jλ. Go to Step (10).
(9)
The problem has no optimal solution becauseXL=∅.
(10)
End.It is proved in [2] that this algorithm is convergent.Theorem 7 (convergence of Algorithm6).
Let{λ(k)} be the sequence generated by Algorithm 6. Then,(i)
ifδ(λ(k))>0, then λ(k)≤λ(k+1),(ii)
ifδ(λ(k))<0, then λ(k)≥λ(k+1).The following algorithm for solving problem(C≥) with strictly convex differentiable functions cj(xj) is suggested in [2].Algorithm 8.
(1)
Initialization:J:={1,…,n},  k:=0,  α(0):=α,  n(0):=n,J(0):=J,  Jaλ:=∅,  Jbλ:=∅,   initialize hj≥,j∈J.
If∑j∈J‍djaj≤α≤∑j∈J‍djbj then go to Step (2), else go to Step (9).
Steps (2)–(7) are the same as Steps (2)–(7) of Algorithm6, respectively.
(8)
Ifλ≤0 then xj≥:=aj for j∈Jaλ;  xj≥:=bj for j∈Jbλ;
assignxj≥ the value, calculated through (17) for j∈Jλ, go to Step (10)
else ifλ>0 then
x
j
≥
:
=
b
j for j∈Jbλ,
x
j
≥
:
=
min
{
b
j
,
h
j
≥
} for j∈Jλ,
ifj∈Jaλ and cj′(aj)<0 then xj≥:=min{bj,hj≥}
else ifj∈Jaλ and cj′(aj)≥0 then xj≥:=aj,
go to Step (10).
(9)
Problem(C≥) has no optimal solution because X≥=∅
or there do not existxj*∈[aj,bj],j∈J, such that ∑j∈J‍djxj*=α.
(10)
End.Since Algorithm8 is based on Theorem 5 and Algorithm 6, and since the “iterative” Steps (2)–(7) of Algorithms 6 and 8 are the same, then the “convergence” of Algorithm 8 follows from Theorem 7 as well.


### 1.2. Organization of the Paper

The rest of the paper is organized as follows. In Section2, the concepts of well-posedness of optimization problems in the sense of Tychonov, Hadamard, and in a generalized sense, as well as calmness in the sense of Clarke, are discussed. It is shown in Section 2.3 that the convex separable optimization problems under consideration are calm in the sense of Clarke. In Section 3, the concept of stability of the set of saddle points of the Lagrangian in the sense of Gol’shtein is also discussed and it is shown that this set is not stable for the “classical” Lagrangian. However, it is explained that despite this instability, due to the specificity of the approach, suggested by the author in previous papers for solving problems under consideration, it is not necessary to use modified Lagrangians but only the “classical” Lagrangians. In Section 4, primal-dual analysis of the problems under consideration in view of methods for solving them is presented. Main results of well-posedness and primal-dual analysis are included in Section 2.3 and in Sections 3 and 4.


## 1.1. Statement of Problems under Consideration: Preliminary Results

In this paper, we study well-posedness and present primal-dual analysis of some convex separable optimization problems, considered by the author in previous papers. For the sake of convenience, in this subsection we recall main results of earlier papers that are used in this study.In paper [1], the following convex separable optimization problem was considered:(
C
)
(1)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
,
(2)
subject
to
∑
j
∈
J
‍
d
j
(
x
j
)
≤
α
,
(3)
subject
to
a
j
≤
x
j
≤
b
j
,
j
∈
J
,
where cj(xj) are twice differentiable strictly convex functions, and dj(xj) are twice differentiable convex functions, defined on the open convex sets Xj in  ℝ,j∈J, respectively, dj′(xj)>0 for every j∈J,  x=(xj)j∈J, and J≡{1,…,n}.Assumptions for problem(C) are as follows.(I.1)
aj≤bj for all j∈J. If ak=bk for some k∈J, then the value xk∶=ak=bk is determined a priori.(II.1)
∑j∈J‍dj(aj)≤α. Otherwise, the constraints (2) and (3) are inconsistent and the feasible set X, defined by (2)-(3), is empty. In addition to this assumption, we suppose that α≤∑j∈J‍dj(bj) in some cases which are specified below.(III.1)
(Slater’s constraint qualification) There exists a pointx¯=(x¯1,…,x¯n)∈X such that ∑j∈J‍dj(x¯j)<α.Under these assumptions, the following characterization theorem (necessary and sufficient condition) for problem(C) was proved in [1].Denote byhj≤,hj=,hj≥ the values of xj, for which cj′(xj)=0 for the three problems under consideration in this paper, respectively.Theorem 1 (characterization of the optimal solution to problem(C)).
Under the above assumptions, a feasible solutionx*=(xj*)j∈J∈X is an optimal solution to problem (C) if and only if there exists a λ∈ℝ+1 such that
(4)xj*=aj,j∈Jaλ≝{j∈J:λ≥-cj′(aj)dj′(aj)}(5)xj*=bj,j∈Jbλ≝{j∈J:λ≤-cj′(bj)dj′(bj)}(6)xj*:λdj′(xj*)=-cj′(xj*),j∈Jλ≝{j∈J:-cj′(bj)dj′(bj)<λ<-cj′(aj)dj′(aj)}.The following polynomial algorithm for solving problem(C) with strictly convex differentiable functions cj(xj),j∈J, was suggested in [1].Algorithm 2.
(0)
Initialization:J:={1,…,n},  k:=0,  α(0):=α,  n(0):=n,J(0):=J,   Jaλ:=∅,   Jbλ:=∅, initialize  hj≤,  j∈J.
If∑j∈J‍dj(aj)≤α go to Step (1), else go to Step (9).
(1)
Construct the setsJa0,  Jb0,  J0 by using (4), (5), (6) with λ=0.
Calculate(7)δ(0)∶=∑j∈Ja0‍dj(aj)+∑j∈Jb0‍dj(bj)+∑j∈J0‍dj(hj≤)-α.
Ifδ(0)≤0 then λ:=0, go to Step (8)
else ifδ(0)>0, then
ifα≤∑j∈J‍dj(bj) go to Step (2)
else ifα>∑j∈J‍dj(bj) go to Step (9)
(there does not existλ*>0 such that δ(λ*)=0).
(2)
J
λ
(
k
)
:
=
J
(
k
). Calculate λ(k) by using the explicit expression of λ, calculated from the equality ∑j∈Jλ(k)‍dj(xj)=α(k), where xj,j∈Jλ(k), are given by (6). Go to Step (3).
(3)
Construct the setsJaλ(k),  Jbλ(k),  Jλ(k) through (4), (5), (6) (with j∈J(k) instead of j∈J) and find their cardinal numbers|Jaλ(k)|,  |Jbλ(k)|,  |Jλ(k)|, respectively. Go to Step (4).
(4)
Calculate(8)δ(λ(k))≔∑j∈Jaλ(k)‍dj(aj)+∑j∈Jbλ(k)‍dj(bj)+∑j∈Jλ(k)‍dj(xj*)-α(k),
wherexj*,j∈Jλ(k), are calculated from (6) with λ=λ(k). Go to Step (5).
(5)
Ifδ(λ(k))=0 or Jλ(k)=∅ then λ:=λ(k),  Jaλ:=Jaλ∪Jaλ(k),Jbλ∶=Jbλ∪Jbλ(k),  Jλ∶=Jλ(k), go to Step (8)
else ifδ(λ(k))>0 go to Step (6)
else ifδ(λ(k))<0 go to Step (7).
(6)
x
j
*
:
=
a
j for j∈Jaλ(k),  α(k+1):=α(k)-∑j∈Jaλ(k)‍dj(aj),  J(k+1):=J(k)∖Jaλ(k),
n
(
k
+
1
)
:
=
n
(
k
)
-
|
J
a
λ
(
k
)
|,  Jaλ:=Jaλ∪Jaλ(k),  k:=k+1. Go to Step (2).
(7)
x
j
*
:
=
b
j for j∈Jbλ(k),  α(k+1):=α(k)-∑j∈Jbλ(k)‍dj(bj),  J(k+1):=J(k)∖Jbλ(k),
n
(
k
+
1
)
:
=
n
(
k
)
-
|
J
b
λ
(
k
)
|,  Jbλ:=Jbλ∪Jbλ(k),  k:=k+1. Go to Step (2).
(8)
x
j
*
∶
=
a
j for j∈Jaλ; xj*∶=bj for j∈Jbλ; assign xj* the value calculated from (6) for j∈Jλ. Go to Step (10).
(9)
Problem(C) has no optimal solution because X=∅ or there does not existλ>0 satisfying Theorem 1.
(10)
End.It is proved in [1] that this algorithm is convergent.Theorem 3 (convergence of Algorithm2).
Let{λ(k)} be the sequence generated by Algorithm 2. Then, (i)
ifδ(λ(k))>0, then λ(k)≤λ(k+1),(ii)
ifδ(λ(k))<0, then λ(k)≥λ(k+1).In paper [2], the following two convex separable optimization problems were considered:(
C
=
)
(9)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
(10)
subject
to
∑
j
∈
J
‍
d
j
x
j
=
α
,
(11)
subject
to
a
j
≤
x
j
≤
b
j
,
j
∈
J
,
and(
C
≥
)
(12)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
(13)
subject
to
∑
j
∈
J
‍
d
j
x
j
≥
α
(14)
subject
to
a
j
≤
x
j
≤
b
j
,
j
∈
J
,
where for both problems, cj(xj) are twice differentiable convex functions, defined on the open convex sets Xj in ℝ, j∈J, respectively, dj>0, for every j∈J, x=(xj)j∈J, and J={1,…,n}.Assumptions for problem(C=) are as follows.(I.2)
aj≤bj for each j∈J.(II.2)
∑j∈J‍djaj≤α≤∑j∈J‍djbj. Otherwise the constraints (10), (11) are inconsistent and XL=∅, where XL is defined by (10)-(11).Under these assumptions, the following characterization theorem (necessary and sufficient condition) for problem(C=) is proved in [2].Theorem 4 (characterization of the optimal solution to problem(C=)).
A feasible solutionx*=(xj*)j∈J∈XL is an optimal solution to problem (C=) if and only if there exists a λ∈ℝ1 such that
(15)xj*=aj,j∈Jaλ≝{j∈J:λ≥-cj′(aj)dj},(16)xj*=bj,j∈Jbλ≝{j∈J:λ≤-cj′(bj)dj},(17)xj*:λdj=-cj′(xj*),j∈Jλ≝{j∈J:-cj′(bj)dj<λ<-cj′(aj)dj}.Assumptions for problem(C≥) are as follows.(I.3)
aj≤bj for all j∈J.(II.3)
α≤∑j∈J‍djbj. Otherwise the constraints (13), (14) are inconsistent and X≥=∅, where X≥ is defined by (13)-(14).Under these assumptions, the following theorem (sufficient condition) for problem(C≥) is proved in [2].Theorem 5 (sufficient condition for optimal solution to problem(C≥)).
Letxj*, j∈Jbe components of the optimal solution to problem C=. Then:(i)
Ifλ=-cj′(xj*)/dj≤0, then xj*,j∈J, solve problem (C≥) as well.(ii)
Ifλ=-cj′(xj*)/dj>0, then xj≥,j∈J defined as follows:xj≥=bj,j∈Jbλ,xj≥=min{bj,hj≥},j∈Jλ,xj≥=min{bj,hj≥}for all j∈Jaλ such that cj′(aj)<0,xj≥=aj  for all  j∈Jaλ, such that cj′(aj)≥0
solve problem(C≥).The following polynomial algorithm for solving problem(C=) with strictly convex differentiable functions cj(xj) was suggested in [2].Algorithm 6.
(1)
Initialization:J:={1,…,n},  k:=0,  α(0):=α,  n(0):=n,J(0):=J,  Jaλ:=∅,  Jbλ:=∅, initialize hj=,j∈J.
If∑j∈J‍djaj≤α≤∑j∈J‍djbj go to Step (2), else go to Step (9).
(2)
J
λ
(
k
)
:
=
J
(
k
). Calculate λ(k) by using the explicit expression of λ, calculated from the equality constraint ∑j∈Jλ(k)‍djxj=α(k), where xj,j∈Jλ(k), are given by (17). Go to Step (3).
(3)
Construct the setsJaλ(k),Jbλ(k),Jλ(k) through (15), (16), (17) (with J(k) instead of J) and find their cardinalities |Jaλ(k)|,|Jbλ(k)|,|Jλ(k)|, respectively. Go to Step (4).
(4)
Calculate(18)δ(λ(k))∶=∑j∈Jaλ(k)‍djaj+∑j∈Jbλ(k)‍djbj+∑j∈Jλ(k)‍djxj*-α(k),
wherexj*,j∈Jλ(k), are calculated from (17) with λ=λ(k). Go to Step (5).
(5)
Ifδ(λ(k))=0 or Jλ(k)=∅ then λ:=λ(k),  Jaλ:=Jaλ∪Jaλ(k),Jbλ∶=Jbλ∪Jbλ(k),  Jλ:=Jλ(k), go to Step (8)
else ifδ(λ(k))>0 go to Step (6)
else ifδ(λ(k))<0 go to Step (7).
(6)
x
j
*
:
=
a
j for j∈Jaλ(k),  α(k+1):=α(k)-∑j∈Jaλ(k)‍djaj,  J(k+1):=J(k)∖Jaλ(k),
n
(
k
+
1
)
:
=
n
(
k
)
-
|
J
a
λ
(
k
)
|,  Jaλ:=Jaλ∪Jaλ(k),  k:=k+1. Go to Step (2).
(7)
x
j
*
:
=
b
j for j∈Jbλ(k),  α(k+1):=α(k)-∑j∈Jbλ(k)djbj,  J(k+1):=J(k)∖Jbλ(k),
n
(
k
+
1
)
:
=
n
(
k
)
-
|
J
b
λ
(
k
)
|,  Jbλ:=Jbλ∪Jbλ(k),  k:=k+1. Go to Step (2).
(8)
x
j
*
:
=
a
j for j∈Jaλ;xj*:=bj for j∈Jbλ; assign xj* the value, calculated from (17) for j∈Jλ. Go to Step (10).
(9)
The problem has no optimal solution becauseXL=∅.
(10)
End.It is proved in [2] that this algorithm is convergent.Theorem 7 (convergence of Algorithm6).
Let{λ(k)} be the sequence generated by Algorithm 6. Then,(i)
ifδ(λ(k))>0, then λ(k)≤λ(k+1),(ii)
ifδ(λ(k))<0, then λ(k)≥λ(k+1).The following algorithm for solving problem(C≥) with strictly convex differentiable functions cj(xj) is suggested in [2].Algorithm 8.
(1)
Initialization:J:={1,…,n},  k:=0,  α(0):=α,  n(0):=n,J(0):=J,  Jaλ:=∅,  Jbλ:=∅,   initialize hj≥,j∈J.
If∑j∈J‍djaj≤α≤∑j∈J‍djbj then go to Step (2), else go to Step (9).
Steps (2)–(7) are the same as Steps (2)–(7) of Algorithm6, respectively.
(8)
Ifλ≤0 then xj≥:=aj for j∈Jaλ;  xj≥:=bj for j∈Jbλ;
assignxj≥ the value, calculated through (17) for j∈Jλ, go to Step (10)
else ifλ>0 then
x
j
≥
:
=
b
j for j∈Jbλ,
x
j
≥
:
=
min
{
b
j
,
h
j
≥
} for j∈Jλ,
ifj∈Jaλ and cj′(aj)<0 then xj≥:=min{bj,hj≥}
else ifj∈Jaλ and cj′(aj)≥0 then xj≥:=aj,
go to Step (10).
(9)
Problem(C≥) has no optimal solution because X≥=∅
or there do not existxj*∈[aj,bj],j∈J, such that ∑j∈J‍djxj*=α.
(10)
End.Since Algorithm8 is based on Theorem 5 and Algorithm 6, and since the “iterative” Steps (2)–(7) of Algorithms 6 and 8 are the same, then the “convergence” of Algorithm 8 follows from Theorem 7 as well.


## 1.2. Organization of the Paper

The rest of the paper is organized as follows. In Section2, the concepts of well-posedness of optimization problems in the sense of Tychonov, Hadamard, and in a generalized sense, as well as calmness in the sense of Clarke, are discussed. It is shown in Section 2.3 that the convex separable optimization problems under consideration are calm in the sense of Clarke. In Section 3, the concept of stability of the set of saddle points of the Lagrangian in the sense of Gol’shtein is also discussed and it is shown that this set is not stable for the “classical” Lagrangian. However, it is explained that despite this instability, due to the specificity of the approach, suggested by the author in previous papers for solving problems under consideration, it is not necessary to use modified Lagrangians but only the “classical” Lagrangians. In Section 4, primal-dual analysis of the problems under consideration in view of methods for solving them is presented. Main results of well-posedness and primal-dual analysis are included in Section 2.3 and in Sections 3 and 4.


## 2. Well-Posedness of Optimization Problems

Questions of existence of solutions and how they depend on problem’s parameters are usually important for many problems of mathematics, not only in optimization. The termwell-posedness refers to the existence and uniqueness of a solution and its continuous behavior with respect to data perturbations, which is referred to as stability. In general, a problem is said to be stable if
(19)ε(δ)⟶0whenδ⟶0,
where δ is a given tolerance of the problem’s data, ε(δ) is the accuracy with which the solution can be determined, and ε(δ) is a continuous function of δ. Besides these conditions, accompanying robustness properties in the convergence of sequence of approximate solutions are also required.Problems which are not well-posed are calledill-posed, or, sometimes, improperly posed.


### 2.1. Tychonov and Hadamard Well-Posedness: Well-Posedness in the Generalized Sense

Recall thatf is a proper function if f(x)<∞ for at least one x∈ℝn and f(x)>-∞ for all x∈ℝn, or, in other words, if
(20)domf≝{x∈ℝn:f(x)<∞}
is a nonempty set on which f(x)>-∞, where dom f is the effective domain of f. Otherwise, f is improper.Definition 9.
LetX be a space with either a topology or a convergence structure associated and let f:X→ℝ¯≡ℝ∪{+∞} be a proper extended real-valued function. Consider the problem
(21)minf(x)subjecttox∈X.
The problem (21) is Tychonov well-posed if and only if f has a unique global minimum point on X towards which every minimizing sequence converges.An equivalent definition is as follows: problem (21) is Tychonov well-posed if and only if there exists a unique x0∈X such that f(x0)≤f(x) for all x∈X and
(22)f(xn)⟶f(x0)impliesxn⟶x0.There are two ways to cope with ill-posedness.The first one is to change the statement of the problem.The second one is the so-calledTychonov regularization. A parametric functional is constructed such that if it approaches 0, the solution of the “regularized” problem converges to the exact solution of the original problem.Consider the problem(23)minx∈X⊂ℝnf(x)=f(x*).Associate the following problem with (23):
(24)minx∈X[f(x)+nk(x)]=zk(x*(nk(x))),
where nk(x) is perturbation in the input data and x*(nk(x)) is an optimal solution to the perturbed problem.Let(25)∫ℝnnk2(x)dx≤ck2<∞.If(26)|zk(x*(nk(x)))-f(x*)|⟶0,
when ck→0, then problem (23) is stable with respect to perturbation nk(x).A parametric functionF(x,Δ,f(x)) with a parameter Δ is called a regularizing function for problem (23) with respect to perturbation nk(x) if the following conditions are satisfied.(1)F(x,Δ,f(x)) is defined for all x∈X and Δ>0.(2) Ifx*(nk(x),Δ) is an optimal solution to problem
(27)minx∈XF(x,Δ,zk(x))=F(x*(nk(x),Δ),Δ,zk(x)),
then there exists a function Δk=Δk(ck) such that
(28)F(x*(nk(x),Δk),Δk,zk(x))⟶f(x*),
when ck→0.Following Tychonov, an ill-posed problem is said to beregularizable if there exists at least one regularizing function for it.The concept of Tychonov well-posedness can be extended to problems without the uniqueness of the optimal solution.Definition 10.
LetX be a space with either a topology or a convergence structure associated, and f:X→ℝ¯≡ℝ∪{+∞} be a proper real-valued function. Problem (21) is said to be well-posed in the generalized sense if and only if argminx∈Xf(x)≠∅ and every sequence {un}⊂X such that f(un)→inf{f(x):x∈X} has some subsequence {vn}→u with u∈ arg minx∈Xf(x).Problem (21) is Tychonov well-posed if and only if it is well-posed in the generalized sense and arg minx∈Xf(x) is a singleton.Hadamard well-posedness is primarily connected with problems of mathematical physics (boundary value problems for partial differential equations) and can be extended to mathematical programming problems. We do not discuss this topic here.As recent studies in the calculus of variations, optimal control, and numerical methods of optimization show, uniqueness and continuity are often too restrictive to be adopted as the standards of well-posedness. It turns out that practical concepts concerning well-posedness are some forms of semicontinuity in the problem’s data and solution mapping, along with potential multivaluedness in this mapping.


### 2.2. Calmness in the Sense of Clarke

LetX be a Banach space.Definition 11.
LetY be a subset of X. A function f:Y→ℝ is said to satisfy a Lipschitz condition on Y provided that, for some nonnegative scalar K, the following inequality holds true:
(29)|f(y)-f(y′)|≤K∥y-y′∥,
for all points y,y′∈Y; this is also referred to as a Lipschitz condition of rankK. We say that f is Lipschitz (of rank K) nearx if for some ε>0, f satisfies a Lipschitz condition (of rank K) on the set x+εB (i.e., within an ε-neighborhood of x), where B is the open unit ball around 0.
A functionf, which satisfies a Lipschitz condition, sometimes is said to be Lipschitz continuous.Consider the following general mathematical programming problem:(
P
)
(30)
min
f
(
x
)
subject
to
g
i
(
x
)
≤
0
,
i
=
1
,
…
,
t
,
subject
to
h
j
(
x
)
=
0
,
j
=
1
,
…
,
m
,
subject
to
x
∈
C
,
C
⊂
X
,
where gi,hj are real-valued functions on X.Letg and h be the functions g=[g1,…,gt]:X→ℝt,  h=[h1,…,hm]:X→ℝm.Let(P) be imbedded in a parametrized family P(p,q) of mathematical programs, where p∈ℝt,  q∈ℝm:P
(
p
,
q
)
(31)
min
f
(
x
)
subject
to
g
(
x
)
+
p
≤
0
subject
to
h
(
x
)
+
q
=
0
subject
to
x
∈
C
.Denote byA the feasible region of problem P(p,q).Definition 12 (Clarke [3]).
Thevalue functionV:ℝt×ℝm→ℝ∪{±∞} is defined via V(p,q)=inf{P(p,q)} (i.e., the value of the problem P(p,q)). If there are no feasible points for P(p,q), then the infimum is over the empty set and V(p,q) is assigned the value +∞.Definition 13 (Clarke [3]).
Letx solve (P). The problem (P) is calm at x provided that there exist positive ε and M such that for all (p,q)∈εB, for all x′∈x+εB which are feasible for P(p,q), one has
(32)f(x′)-f(x)+M∥(p,q)∥≥0,
where B is the open unit ball in X and ∥(p,q)∥ is the Euclidean norm of (p,q).LetU be an open convex subset of X.Theorem 14 (Roberts and Varberg [4], Clarke [3]; Lipschitz condition from boundedness of a convex function).
Letf be a convex function, bounded above on a neighborhood of some point of U. Then, for any x in U, f is Lipschitz near x.Recall thatlimit superior of a bounded sequence {xn} in ℝ, denoted limsup{xn} or lim¯{xn}, equals the infimum of all numbers q∈ℝ for which at most a finite number of elements of {xn} (strictly) exceed q. Similarly, limit inferior of {xn} is given by liminf{xn}≡lim_{xn}≡sup{q: at most a finite number of elements of {xn} are (strictly) less than q}.A bounded sequence always has a unique limit superior and limit inferior.Theorem 15 (Clarke [3], Calmness).
LetV(0,0) be finite and suppose that
(33)liminf(p,q)→(0,0)V(p,q)-V(0,0)∥(p,q)∥>-∞(this is true in particular if V is Lipschitz near (0,0)). Then, for any solution x to (P), problem (P) is calm at x.Sometimes problem(P) is said to be calm provided V satisfies the hypothesis of Theorem 15.Slater-Type Conditions.  Suppose that (P) has no equality constraints (i.e., m=0), that the functions gi,  i=1,…,t, are convex, and that C is a convex set. Recall that Slater’s condition (Slater’s constraint qualification), then is: there exists a point x¯ in C such that gi(x¯)<0,  i=1,…,t (x¯ is called a strictly feasible point).Forp∈ℝt, let V(p) be the infimum in the problem P(p) in which the constraints gi(x)≤0 of problem (P) are replaced by gi(x)+pi≤0.Theorem 16 (Clarke [3]; Lipschitz property of the value function from Slater’s condition).
IfC is bounded and f is Lipschitz on C, then Slater’s condition (i.e., the existence of a strictly feasible point) implies that V is Lipschitz near 0.Theorems15 and 16 mean that Slater’s constraint qualification implies calmness of problem P(p) in this case.Theorem 17 (Clarke [3]; Calmness of a problem subject to inequality constraints).
LetP incorporate only inequality constraints gi(x)≤0 and the abstract constraint x∈C and suppose that the value function V(p) is finite for p near 0. Then, for almost all p in a neighborhood of 0, the problem P(p) is calm.Remark 18.
In the case of problem(P), in which equality constraints exist, it is a consequence of Ekeland’s theorem that P(p,q) is calm for all (p,q) in a dense subset of any open set upon which V is bounded and lower semicontinuous.Consider the following way of perturbing problem(P):P
(
α
)
(34)
min
{
f
(
x
,
α
)
:
g
(
x
,
α
)
≤
0
,
h
(
x
,
α
)
=
0
,
(
x
,
α
)
∈
D
}
,
where αis a vector of k real components. The value function V then would be a function of α:V(α)=infP(α).This is a special case of problemP(p,q) with k=t+m,  α=(p,q),  f(x,α)=f(x),  g(x,α)=g(x)+p,h(x,α)=h(x)+q,D=C×ℝt+m. At least when the dependence of f,g, and h on α is locally Lipschitz, we can consider problem P(p,q) with k=t+m,  α=(p,q),f(x,α)=f(x),g(x,α)=g(x)+p,h(x,α)=h(x)+q, and D=C×ℝt+m rather than problem P(α). Hence, the methods and results, considered above, can be applied to perturbed family P(α) as well.Constraint qualifications (regularity conditions) can be classified into two categories: on the one hand, Mangasarian-Fromowitz and Slater-type conditions and their extensions, and, on the other hand, constraint qualifications calledcalmness. It turns out that calmness is the weakest of these conditions, since it is implied by all the others (see, e.g., Theorem 16).


### 2.3. Well-Posedness of Problems(C), (C=), and (C≥)

#### 2.3.1. Existence of Solutions

The question of existence of solutions to problems(C), (C=), and (C≥) has been discussed in Theorems 1, 4, and 5, respectively. Steps (0), (1), and (9) of Algorithm 2 and Steps (1) and (9) of Algorithms 6 and 8, respectively, refer to these results.


#### 2.3.2. Uniqueness of Solution

The question of uniqueness of the optimal solution to problems under consideration is also important.Ifc(x)≡∑j∈J‍cj(xj) defined by (1) (by (9), (12), resp.) is a strictly convex function, then problem (C) (problem (C=) or problem (C≥), resp.) has a unique optimal solution in the feasible region X  (XL,X≥, resp.) in case problem (C) (problem (C=) or problem (C≥), resp.) has feasible solutions; that is, xj*,j∈Jλ, are uniquely determined from (6) [(17)] in the interval [aj,bj] in this case. If the parameters aj,bj, and so forth of particular problems of the form (C)  ((C=) and (C≥), resp.) are generated in intervals where the functions cj(xj) are strictly convex, then problem (C)  (problem (C=) or problem (C≥), resp.), if it has feasible solutions, has a unique optimal solution.In the general case, if functionscj(xj) are convex but not necessarily strictly convex, then, as it is known, a convex programming problem has more than one optimal solution and the set of optimal solutions to such a problem is convex. Further, the optimal value of the objective function is the same for all optimal solutions to problem (C) (problem (C=) or problem (C≥), resp.) if it has more than one optimal solution. If, for example, (6) ((17), resp.) is a linear equation of xj*, then xj*,j∈Jλ, are also uniquely determined from (6) (from (17), resp.).


#### 2.3.3. Calmness of the Problems (of the Optimal Solutions)

Let(C(p)),(C=(p,q)), and (C≥(p)) be the parametrized families of mathematical programs associated with problems (C),(C=), and (C≥), respectively.Feasible regions of problems(C) and (C≥) are nonempty by the assumption; this is satisfied when ∑j∈J‍dj(aj)≤α and ∑j∈J‍djbj≥α, respectively. Without loss of generality, feasible regionsX
(
p
):
(35)∑j∈J‍dj(xj)+p0≤αaj≤xj+pj≤bj,j∈J,
and X≥(p):
(36)∑j∈J‍djxj+p0≥αaj≤xj+pj≤bj,j∈J,
of problems (C(p)) and (C≥(p)), respectively, are also nonempty in a neighborhood of p=0.Since the value functionV(p), associated with problems (C(p)) and (C≥(p)), is finite near 0 (according to Definition 12 and the assumption that the corresponding feasible set is nonempty) then both problems are calm according to Theorem 17.An alternative proof of calmness of problem (C) is the following.The objective functionc(x) of problem (C) (1)–(3) is convex (and, therefore, Lipschitz in accordance with Theorem 14), and Slater’s constraint qualification is satisfied by the assumption. From Theorem 16, it follows that the value function V(p) is Lipschitz, and problem (C) is calm at any solution x* of problem (C) according to Theorem 15.Consider the parametrized family(C=(p,q)) in which problem (C=) is imbedded as follows:(
C
=
(
p
,
q
)
)
(37)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
subject
to
x
∈
X
L
(
p
,
q
)
,
where XL(p,q) is defined as follows:
(38)∑j∈J‍djxj+q=αaj≤xj+pj≤bj,j∈J.As it has been pointed out,XL≠∅ if
(39)∑j∈J‍djaj≤α≤∑j∈J‍djbj,
whereas XL(p,q)≠∅ if
(40)∑j∈J‍dj(aj-pj)≤α-q≤∑j∈J‍dj(bj-pj).Without loss of generality, assume that there exists a(p,q) such that XL(p,q)≠∅. This is satisfied, for example, when ∑j∈J‍djpj=q in addition to the requirement XL≠∅. Then the value function V(p,q), associated with (C=(p,q)), is finite by Definition 12.Theorem 19 (Convexity of the infimum of a convex function subject to linear equality constraints).
Letf be a convex function and S be a convex set in ℝn. Then, function
(41)h(y)≝infx{f(x):Ax=y,Am×n,x∈S,y∈ℝm}
is convex.Proof.
Letx=λx1+(1-λ)x2,λ∈[0,1],x1,x2∈S,y1,y2∈ℝm. Therefore x∈S as a convex combination of elements of the convex set S. Then,
(42)h(λy1+(1-λ)y2)=infx{f(x):Ax=λy1+(1-λ)y2}=infx1,x2{f(λx1+(1-λ)x2):A(λx1+(1-λ)x2)=λy1+(1-λ)y2}≤infx1,x2{f(λx1+(1-λ)x2):Ax1=y1,Ax2=y2}≤infx1,x2{λf(x1)+(1-λ)f(x2):Ax1=y1,Ax2=y2}=infx1{λf(x1):Ax1=y1}+infx2{(1-λ)f(x2):Ax2=y2}=λh(y1)+(1-λ)h(y2).
We have used that f is a convex function, the property that
(43){x1,x2∈S:Ax1=y1,Ax2=y2}⊂{x1,x2∈S:λAx1+(1-λ)Ax2=λy1+(1-λ)y2}
and the fact that X⊂Y implies infx∈Yf(x)≤infx∈Xf(x).
Therefore,h(y) is a convex function by definition.For problem(C=(p,q)), matrix A of Theorem 19 consists of a single row, that is, m=1, and convex set S is the n-dimensional parallelepiped
(44)S={x∈ℝn:aj≤xj≤bj,j∈J}.
The value function associated with problem (C=(p,q)) is
(45)V(p,q)=infx∈XL(p,q)f(x).From Theorem19 and the assumption that XL(p,q)≠∅, it follows that V(p,q) is convex and finite, respectively, and from Theorem 14 it follows that it is Lipschitz. Then, problem (C=(p,q)) is calm according to Theorem 15.In the general case, if the mathematical program is not convex and equality constraints exist, we can use the approach of the Remark18.


## 2.1. Tychonov and Hadamard Well-Posedness: Well-Posedness in the Generalized Sense

Recall thatf is a proper function if f(x)<∞ for at least one x∈ℝn and f(x)>-∞ for all x∈ℝn, or, in other words, if
(20)domf≝{x∈ℝn:f(x)<∞}
is a nonempty set on which f(x)>-∞, where dom f is the effective domain of f. Otherwise, f is improper.Definition 9.
LetX be a space with either a topology or a convergence structure associated and let f:X→ℝ¯≡ℝ∪{+∞} be a proper extended real-valued function. Consider the problem
(21)minf(x)subjecttox∈X.
The problem (21) is Tychonov well-posed if and only if f has a unique global minimum point on X towards which every minimizing sequence converges.An equivalent definition is as follows: problem (21) is Tychonov well-posed if and only if there exists a unique x0∈X such that f(x0)≤f(x) for all x∈X and
(22)f(xn)⟶f(x0)impliesxn⟶x0.There are two ways to cope with ill-posedness.The first one is to change the statement of the problem.The second one is the so-calledTychonov regularization. A parametric functional is constructed such that if it approaches 0, the solution of the “regularized” problem converges to the exact solution of the original problem.Consider the problem(23)minx∈X⊂ℝnf(x)=f(x*).Associate the following problem with (23):
(24)minx∈X[f(x)+nk(x)]=zk(x*(nk(x))),
where nk(x) is perturbation in the input data and x*(nk(x)) is an optimal solution to the perturbed problem.Let(25)∫ℝnnk2(x)dx≤ck2<∞.If(26)|zk(x*(nk(x)))-f(x*)|⟶0,
when ck→0, then problem (23) is stable with respect to perturbation nk(x).A parametric functionF(x,Δ,f(x)) with a parameter Δ is called a regularizing function for problem (23) with respect to perturbation nk(x) if the following conditions are satisfied.(1)F(x,Δ,f(x)) is defined for all x∈X and Δ>0.(2) Ifx*(nk(x),Δ) is an optimal solution to problem
(27)minx∈XF(x,Δ,zk(x))=F(x*(nk(x),Δ),Δ,zk(x)),
then there exists a function Δk=Δk(ck) such that
(28)F(x*(nk(x),Δk),Δk,zk(x))⟶f(x*),
when ck→0.Following Tychonov, an ill-posed problem is said to beregularizable if there exists at least one regularizing function for it.The concept of Tychonov well-posedness can be extended to problems without the uniqueness of the optimal solution.Definition 10.
LetX be a space with either a topology or a convergence structure associated, and f:X→ℝ¯≡ℝ∪{+∞} be a proper real-valued function. Problem (21) is said to be well-posed in the generalized sense if and only if argminx∈Xf(x)≠∅ and every sequence {un}⊂X such that f(un)→inf{f(x):x∈X} has some subsequence {vn}→u with u∈ arg minx∈Xf(x).Problem (21) is Tychonov well-posed if and only if it is well-posed in the generalized sense and arg minx∈Xf(x) is a singleton.Hadamard well-posedness is primarily connected with problems of mathematical physics (boundary value problems for partial differential equations) and can be extended to mathematical programming problems. We do not discuss this topic here.As recent studies in the calculus of variations, optimal control, and numerical methods of optimization show, uniqueness and continuity are often too restrictive to be adopted as the standards of well-posedness. It turns out that practical concepts concerning well-posedness are some forms of semicontinuity in the problem’s data and solution mapping, along with potential multivaluedness in this mapping.


## 2.2. Calmness in the Sense of Clarke

LetX be a Banach space.Definition 11.
LetY be a subset of X. A function f:Y→ℝ is said to satisfy a Lipschitz condition on Y provided that, for some nonnegative scalar K, the following inequality holds true:
(29)|f(y)-f(y′)|≤K∥y-y′∥,
for all points y,y′∈Y; this is also referred to as a Lipschitz condition of rankK. We say that f is Lipschitz (of rank K) nearx if for some ε>0, f satisfies a Lipschitz condition (of rank K) on the set x+εB (i.e., within an ε-neighborhood of x), where B is the open unit ball around 0.
A functionf, which satisfies a Lipschitz condition, sometimes is said to be Lipschitz continuous.Consider the following general mathematical programming problem:(
P
)
(30)
min
f
(
x
)
subject
to
g
i
(
x
)
≤
0
,
i
=
1
,
…
,
t
,
subject
to
h
j
(
x
)
=
0
,
j
=
1
,
…
,
m
,
subject
to
x
∈
C
,
C
⊂
X
,
where gi,hj are real-valued functions on X.Letg and h be the functions g=[g1,…,gt]:X→ℝt,  h=[h1,…,hm]:X→ℝm.Let(P) be imbedded in a parametrized family P(p,q) of mathematical programs, where p∈ℝt,  q∈ℝm:P
(
p
,
q
)
(31)
min
f
(
x
)
subject
to
g
(
x
)
+
p
≤
0
subject
to
h
(
x
)
+
q
=
0
subject
to
x
∈
C
.Denote byA the feasible region of problem P(p,q).Definition 12 (Clarke [3]).
Thevalue functionV:ℝt×ℝm→ℝ∪{±∞} is defined via V(p,q)=inf{P(p,q)} (i.e., the value of the problem P(p,q)). If there are no feasible points for P(p,q), then the infimum is over the empty set and V(p,q) is assigned the value +∞.Definition 13 (Clarke [3]).
Letx solve (P). The problem (P) is calm at x provided that there exist positive ε and M such that for all (p,q)∈εB, for all x′∈x+εB which are feasible for P(p,q), one has
(32)f(x′)-f(x)+M∥(p,q)∥≥0,
where B is the open unit ball in X and ∥(p,q)∥ is the Euclidean norm of (p,q).LetU be an open convex subset of X.Theorem 14 (Roberts and Varberg [4], Clarke [3]; Lipschitz condition from boundedness of a convex function).
Letf be a convex function, bounded above on a neighborhood of some point of U. Then, for any x in U, f is Lipschitz near x.Recall thatlimit superior of a bounded sequence {xn} in ℝ, denoted limsup{xn} or lim¯{xn}, equals the infimum of all numbers q∈ℝ for which at most a finite number of elements of {xn} (strictly) exceed q. Similarly, limit inferior of {xn} is given by liminf{xn}≡lim_{xn}≡sup{q: at most a finite number of elements of {xn} are (strictly) less than q}.A bounded sequence always has a unique limit superior and limit inferior.Theorem 15 (Clarke [3], Calmness).
LetV(0,0) be finite and suppose that
(33)liminf(p,q)→(0,0)V(p,q)-V(0,0)∥(p,q)∥>-∞(this is true in particular if V is Lipschitz near (0,0)). Then, for any solution x to (P), problem (P) is calm at x.Sometimes problem(P) is said to be calm provided V satisfies the hypothesis of Theorem 15.Slater-Type Conditions.  Suppose that (P) has no equality constraints (i.e., m=0), that the functions gi,  i=1,…,t, are convex, and that C is a convex set. Recall that Slater’s condition (Slater’s constraint qualification), then is: there exists a point x¯ in C such that gi(x¯)<0,  i=1,…,t (x¯ is called a strictly feasible point).Forp∈ℝt, let V(p) be the infimum in the problem P(p) in which the constraints gi(x)≤0 of problem (P) are replaced by gi(x)+pi≤0.Theorem 16 (Clarke [3]; Lipschitz property of the value function from Slater’s condition).
IfC is bounded and f is Lipschitz on C, then Slater’s condition (i.e., the existence of a strictly feasible point) implies that V is Lipschitz near 0.Theorems15 and 16 mean that Slater’s constraint qualification implies calmness of problem P(p) in this case.Theorem 17 (Clarke [3]; Calmness of a problem subject to inequality constraints).
LetP incorporate only inequality constraints gi(x)≤0 and the abstract constraint x∈C and suppose that the value function V(p) is finite for p near 0. Then, for almost all p in a neighborhood of 0, the problem P(p) is calm.Remark 18.
In the case of problem(P), in which equality constraints exist, it is a consequence of Ekeland’s theorem that P(p,q) is calm for all (p,q) in a dense subset of any open set upon which V is bounded and lower semicontinuous.Consider the following way of perturbing problem(P):P
(
α
)
(34)
min
{
f
(
x
,
α
)
:
g
(
x
,
α
)
≤
0
,
h
(
x
,
α
)
=
0
,
(
x
,
α
)
∈
D
}
,
where αis a vector of k real components. The value function V then would be a function of α:V(α)=infP(α).This is a special case of problemP(p,q) with k=t+m,  α=(p,q),  f(x,α)=f(x),  g(x,α)=g(x)+p,h(x,α)=h(x)+q,D=C×ℝt+m. At least when the dependence of f,g, and h on α is locally Lipschitz, we can consider problem P(p,q) with k=t+m,  α=(p,q),f(x,α)=f(x),g(x,α)=g(x)+p,h(x,α)=h(x)+q, and D=C×ℝt+m rather than problem P(α). Hence, the methods and results, considered above, can be applied to perturbed family P(α) as well.Constraint qualifications (regularity conditions) can be classified into two categories: on the one hand, Mangasarian-Fromowitz and Slater-type conditions and their extensions, and, on the other hand, constraint qualifications calledcalmness. It turns out that calmness is the weakest of these conditions, since it is implied by all the others (see, e.g., Theorem 16).


## 2.3. Well-Posedness of Problems(C), (C=), and (C≥)

### 2.3.1. Existence of Solutions

The question of existence of solutions to problems(C), (C=), and (C≥) has been discussed in Theorems 1, 4, and 5, respectively. Steps (0), (1), and (9) of Algorithm 2 and Steps (1) and (9) of Algorithms 6 and 8, respectively, refer to these results.


### 2.3.2. Uniqueness of Solution

The question of uniqueness of the optimal solution to problems under consideration is also important.Ifc(x)≡∑j∈J‍cj(xj) defined by (1) (by (9), (12), resp.) is a strictly convex function, then problem (C) (problem (C=) or problem (C≥), resp.) has a unique optimal solution in the feasible region X  (XL,X≥, resp.) in case problem (C) (problem (C=) or problem (C≥), resp.) has feasible solutions; that is, xj*,j∈Jλ, are uniquely determined from (6) [(17)] in the interval [aj,bj] in this case. If the parameters aj,bj, and so forth of particular problems of the form (C)  ((C=) and (C≥), resp.) are generated in intervals where the functions cj(xj) are strictly convex, then problem (C)  (problem (C=) or problem (C≥), resp.), if it has feasible solutions, has a unique optimal solution.In the general case, if functionscj(xj) are convex but not necessarily strictly convex, then, as it is known, a convex programming problem has more than one optimal solution and the set of optimal solutions to such a problem is convex. Further, the optimal value of the objective function is the same for all optimal solutions to problem (C) (problem (C=) or problem (C≥), resp.) if it has more than one optimal solution. If, for example, (6) ((17), resp.) is a linear equation of xj*, then xj*,j∈Jλ, are also uniquely determined from (6) (from (17), resp.).


### 2.3.3. Calmness of the Problems (of the Optimal Solutions)

Let(C(p)),(C=(p,q)), and (C≥(p)) be the parametrized families of mathematical programs associated with problems (C),(C=), and (C≥), respectively.Feasible regions of problems(C) and (C≥) are nonempty by the assumption; this is satisfied when ∑j∈J‍dj(aj)≤α and ∑j∈J‍djbj≥α, respectively. Without loss of generality, feasible regionsX
(
p
):
(35)∑j∈J‍dj(xj)+p0≤αaj≤xj+pj≤bj,j∈J,
and X≥(p):
(36)∑j∈J‍djxj+p0≥αaj≤xj+pj≤bj,j∈J,
of problems (C(p)) and (C≥(p)), respectively, are also nonempty in a neighborhood of p=0.Since the value functionV(p), associated with problems (C(p)) and (C≥(p)), is finite near 0 (according to Definition 12 and the assumption that the corresponding feasible set is nonempty) then both problems are calm according to Theorem 17.An alternative proof of calmness of problem (C) is the following.The objective functionc(x) of problem (C) (1)–(3) is convex (and, therefore, Lipschitz in accordance with Theorem 14), and Slater’s constraint qualification is satisfied by the assumption. From Theorem 16, it follows that the value function V(p) is Lipschitz, and problem (C) is calm at any solution x* of problem (C) according to Theorem 15.Consider the parametrized family(C=(p,q)) in which problem (C=) is imbedded as follows:(
C
=
(
p
,
q
)
)
(37)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
subject
to
x
∈
X
L
(
p
,
q
)
,
where XL(p,q) is defined as follows:
(38)∑j∈J‍djxj+q=αaj≤xj+pj≤bj,j∈J.As it has been pointed out,XL≠∅ if
(39)∑j∈J‍djaj≤α≤∑j∈J‍djbj,
whereas XL(p,q)≠∅ if
(40)∑j∈J‍dj(aj-pj)≤α-q≤∑j∈J‍dj(bj-pj).Without loss of generality, assume that there exists a(p,q) such that XL(p,q)≠∅. This is satisfied, for example, when ∑j∈J‍djpj=q in addition to the requirement XL≠∅. Then the value function V(p,q), associated with (C=(p,q)), is finite by Definition 12.Theorem 19 (Convexity of the infimum of a convex function subject to linear equality constraints).
Letf be a convex function and S be a convex set in ℝn. Then, function
(41)h(y)≝infx{f(x):Ax=y,Am×n,x∈S,y∈ℝm}
is convex.Proof.
Letx=λx1+(1-λ)x2,λ∈[0,1],x1,x2∈S,y1,y2∈ℝm. Therefore x∈S as a convex combination of elements of the convex set S. Then,
(42)h(λy1+(1-λ)y2)=infx{f(x):Ax=λy1+(1-λ)y2}=infx1,x2{f(λx1+(1-λ)x2):A(λx1+(1-λ)x2)=λy1+(1-λ)y2}≤infx1,x2{f(λx1+(1-λ)x2):Ax1=y1,Ax2=y2}≤infx1,x2{λf(x1)+(1-λ)f(x2):Ax1=y1,Ax2=y2}=infx1{λf(x1):Ax1=y1}+infx2{(1-λ)f(x2):Ax2=y2}=λh(y1)+(1-λ)h(y2).
We have used that f is a convex function, the property that
(43){x1,x2∈S:Ax1=y1,Ax2=y2}⊂{x1,x2∈S:λAx1+(1-λ)Ax2=λy1+(1-λ)y2}
and the fact that X⊂Y implies infx∈Yf(x)≤infx∈Xf(x).
Therefore,h(y) is a convex function by definition.For problem(C=(p,q)), matrix A of Theorem 19 consists of a single row, that is, m=1, and convex set S is the n-dimensional parallelepiped
(44)S={x∈ℝn:aj≤xj≤bj,j∈J}.
The value function associated with problem (C=(p,q)) is
(45)V(p,q)=infx∈XL(p,q)f(x).From Theorem19 and the assumption that XL(p,q)≠∅, it follows that V(p,q) is convex and finite, respectively, and from Theorem 14 it follows that it is Lipschitz. Then, problem (C=(p,q)) is calm according to Theorem 15.In the general case, if the mathematical program is not convex and equality constraints exist, we can use the approach of the Remark18.


## 2.3.1. Existence of Solutions

The question of existence of solutions to problems(C), (C=), and (C≥) has been discussed in Theorems 1, 4, and 5, respectively. Steps (0), (1), and (9) of Algorithm 2 and Steps (1) and (9) of Algorithms 6 and 8, respectively, refer to these results.


## 2.3.2. Uniqueness of Solution

The question of uniqueness of the optimal solution to problems under consideration is also important.Ifc(x)≡∑j∈J‍cj(xj) defined by (1) (by (9), (12), resp.) is a strictly convex function, then problem (C) (problem (C=) or problem (C≥), resp.) has a unique optimal solution in the feasible region X  (XL,X≥, resp.) in case problem (C) (problem (C=) or problem (C≥), resp.) has feasible solutions; that is, xj*,j∈Jλ, are uniquely determined from (6) [(17)] in the interval [aj,bj] in this case. If the parameters aj,bj, and so forth of particular problems of the form (C)  ((C=) and (C≥), resp.) are generated in intervals where the functions cj(xj) are strictly convex, then problem (C)  (problem (C=) or problem (C≥), resp.), if it has feasible solutions, has a unique optimal solution.In the general case, if functionscj(xj) are convex but not necessarily strictly convex, then, as it is known, a convex programming problem has more than one optimal solution and the set of optimal solutions to such a problem is convex. Further, the optimal value of the objective function is the same for all optimal solutions to problem (C) (problem (C=) or problem (C≥), resp.) if it has more than one optimal solution. If, for example, (6) ((17), resp.) is a linear equation of xj*, then xj*,j∈Jλ, are also uniquely determined from (6) (from (17), resp.).


## 2.3.3. Calmness of the Problems (of the Optimal Solutions)

Let(C(p)),(C=(p,q)), and (C≥(p)) be the parametrized families of mathematical programs associated with problems (C),(C=), and (C≥), respectively.Feasible regions of problems(C) and (C≥) are nonempty by the assumption; this is satisfied when ∑j∈J‍dj(aj)≤α and ∑j∈J‍djbj≥α, respectively. Without loss of generality, feasible regionsX
(
p
):
(35)∑j∈J‍dj(xj)+p0≤αaj≤xj+pj≤bj,j∈J,
and X≥(p):
(36)∑j∈J‍djxj+p0≥αaj≤xj+pj≤bj,j∈J,
of problems (C(p)) and (C≥(p)), respectively, are also nonempty in a neighborhood of p=0.Since the value functionV(p), associated with problems (C(p)) and (C≥(p)), is finite near 0 (according to Definition 12 and the assumption that the corresponding feasible set is nonempty) then both problems are calm according to Theorem 17.An alternative proof of calmness of problem (C) is the following.The objective functionc(x) of problem (C) (1)–(3) is convex (and, therefore, Lipschitz in accordance with Theorem 14), and Slater’s constraint qualification is satisfied by the assumption. From Theorem 16, it follows that the value function V(p) is Lipschitz, and problem (C) is calm at any solution x* of problem (C) according to Theorem 15.Consider the parametrized family(C=(p,q)) in which problem (C=) is imbedded as follows:(
C
=
(
p
,
q
)
)
(37)
min
{
c
(
x
)
=
∑
j
∈
J
‍
c
j
(
x
j
)
}
subject
to
x
∈
X
L
(
p
,
q
)
,
where XL(p,q) is defined as follows:
(38)∑j∈J‍djxj+q=αaj≤xj+pj≤bj,j∈J.As it has been pointed out,XL≠∅ if
(39)∑j∈J‍djaj≤α≤∑j∈J‍djbj,
whereas XL(p,q)≠∅ if
(40)∑j∈J‍dj(aj-pj)≤α-q≤∑j∈J‍dj(bj-pj).Without loss of generality, assume that there exists a(p,q) such that XL(p,q)≠∅. This is satisfied, for example, when ∑j∈J‍djpj=q in addition to the requirement XL≠∅. Then the value function V(p,q), associated with (C=(p,q)), is finite by Definition 12.Theorem 19 (Convexity of the infimum of a convex function subject to linear equality constraints).
Letf be a convex function and S be a convex set in ℝn. Then, function
(41)h(y)≝infx{f(x):Ax=y,Am×n,x∈S,y∈ℝm}
is convex.Proof.
Letx=λx1+(1-λ)x2,λ∈[0,1],x1,x2∈S,y1,y2∈ℝm. Therefore x∈S as a convex combination of elements of the convex set S. Then,
(42)h(λy1+(1-λ)y2)=infx{f(x):Ax=λy1+(1-λ)y2}=infx1,x2{f(λx1+(1-λ)x2):A(λx1+(1-λ)x2)=λy1+(1-λ)y2}≤infx1,x2{f(λx1+(1-λ)x2):Ax1=y1,Ax2=y2}≤infx1,x2{λf(x1)+(1-λ)f(x2):Ax1=y1,Ax2=y2}=infx1{λf(x1):Ax1=y1}+infx2{(1-λ)f(x2):Ax2=y2}=λh(y1)+(1-λ)h(y2).
We have used that f is a convex function, the property that
(43){x1,x2∈S:Ax1=y1,Ax2=y2}⊂{x1,x2∈S:λAx1+(1-λ)Ax2=λy1+(1-λ)y2}
and the fact that X⊂Y implies infx∈Yf(x)≤infx∈Xf(x).
Therefore,h(y) is a convex function by definition.For problem(C=(p,q)), matrix A of Theorem 19 consists of a single row, that is, m=1, and convex set S is the n-dimensional parallelepiped
(44)S={x∈ℝn:aj≤xj≤bj,j∈J}.
The value function associated with problem (C=(p,q)) is
(45)V(p,q)=infx∈XL(p,q)f(x).From Theorem19 and the assumption that XL(p,q)≠∅, it follows that V(p,q) is convex and finite, respectively, and from Theorem 14 it follows that it is Lipschitz. Then, problem (C=(p,q)) is calm according to Theorem 15.In the general case, if the mathematical program is not convex and equality constraints exist, we can use the approach of the Remark18.


## 3. On the Stability of the Set of Saddle Points of the Lagrangian

### 3.1. The Concept of Stability of Saddle Points of the Lagrangian

Besides well-posedness of the optimization problems, stability of methods for solving these problems is also important.LetΦ(x,y) be a convex function of x∈X and a concave function of y∈Y, where X and Y are convex and closed sets.Recall the definition of a saddle point.A point(x^,y^) is said to be a saddle point of function Φ(x,y),  x∈X,  y∈Y, if the following inequalities hold:
(46)Φ(x^,y)≤Φ(x^,y^)≤Φ(x,y^)
for all x∈X,y∈Y, that is, if
(47)Φ(x^,y^)=minx∈Xmaxy∈YΦ(x,y)=maxy∈Yminx∈XΦ(x,y).This means thatΦ(x,y) attains at the saddle point (x^,y^) its maximum with respect to y for fixed x^ and Φ(x,y) attains at (x^,y^) its minimum with respect to x for fixed y^.Set(48)χ(x)=maxy∈YΦ(x,y),ψ(y)=minx∈XΦ(x,y).Denote byX* and Y* the sets of optimal solutions to the optimization problems
(49)minx∈Xχ(x),maxy∈Yψ(y),
respectively, that is,
(50)X*≝{x:χ(x)=minx∈Xmaxy∈YΦ(x,y)}≡{x:maxy∈YΦ(x,y)=Φ(x^,y^)},Y*≝{y:ψ(y)=maxy∈Yminx∈XΦ(x,y)}≡{y:minx∈XΦ(x,y)=Φ(x^,y^)}.
Let X*,Y* be bounded sets. Then,
(51)χ(x*)=ψ(y*),x*∈X*,y*∈Y*,that is,(52)χ(x*)≝maxy∈YΦ(x*,y)=ψ(y*)≝minx∈XΦ(x,y*)=Φ(x^,y^).
This means that X*×Y* is the set of saddle points of Φ(x,y) and
(53)Φ(x^,y^)=Φ(x*,y*).
Consider the sets
(54)Xy*≝{x:Φ(x,y*)=Φ(x*,y*)},Yx*≝{y:Φ(x*,y)=Φ(x*,y*)},
that is, Xy* and Yx* denote the sets of arguments of Φ(x,y) with y=y* and x=x*, respectively, for which the value of Φ(x,y) is equal to its value at the saddle point.In the general case,X*⊂Xy*,  Y*⊂Yx*; that is, the sets Xy*,  Yx* contain sets X*,  Y*, respectively.Definition 20.
IfX*=Xy* and Y*=Yx*, then the set of saddle points of Φ(x,y) is said to be stable.If the set of saddle points ofΦ(x,y) is stable, then from
(55)limk→∞Φ(x(k),y*(k))=Φ(x*,y*),x(k)∈X,y*(k)∈Y
it follows that
(56)δ(x(k),X*)⟶0,k⟶∞,
and from
(57)limk→∞Φ(x*(k),y(k))=Φ(x*,y*),x*(k)∈X,y(k)∈Y
it follows that
(58)δ(y(k),Y*)⟶0,k⟶∞,
where δ(x,X)≝minz∈X∥x-z∥ is the distance from x to the set X. The implications written above mean that convergence of Φ(x,y*) to Φ(x*,y*) with respect to x(k) and convergence of Φ(x*,y) to Φ(x*,y*) with respect to y(k) implies convergence of sequence ({x(k)},{y(k)}) to the set X*×Y* of saddle points of Φ(x,y).The concept of stability, introduced by Definition20, is important for constructing iterative gradient algorithms for finding saddle points of the Lagrangian associated with an optimization problem.The set of saddle points of the Lagrangian associated with the problem(59)minx∈Sf(x),(60)S={x∈ℝn:φi(x)≤0,i=1,…,m,x∈X}is not stable according to Definition 20. Concerning the dual variables this can be proved as follows.Letrth constraint of (60) be satisfied as an equality at x*, that is,
(61)φr(x*)=0
for some r,  1≤r≤m. Then, the Lagrangian L(x*,λ) of problem (59)-(60) does not depend on λr and therefore L(x*,λ*)=L(x*,λ) is satisfied for every λr. Hence, it is impossible to determine λr by using the relation L(x*,λ*)=L(x*,λ).In order to avoid this difficulty, so-calledmodified Lagrangians are used instead of the “classical” Lagrangian. Modified Lagrangians are usually nonlinear functions of λ and the set of their saddle points is stable and it coincides, under some assumptions, with the set of saddle points of the “classical” Lagrangian for the same problem. This is important to ensure convergence of iterative gradient algorithms (see, e.g., Gol’shtein [5]).


### 3.2. About the Stability of the Set of Saddle Points for the Approach Considered in this Paper

Consider problem(C) (problem (C=) and problem (C≥), resp.). Obviously, the Lagrange multiplier λ, associated with the constraint (2) ((10) and (13), resp.), is not involved in the equality
(62)L(x*,u*,v*,λ*)=L(x*,u,v,λ)
when δ(λ*)=0, that is, when ∑j∈J‍dj(xj)=α. For problem (C),  λ*(>0) is either determined uniquely from δ(λ*)=0 when δ(0)>0 or we set λ*:=0 when δ(0)≤0 (Algorithm 2). Although the set of saddle points of the Lagrangian L(x,u,v,λ), associated with problem (C) (problem (C=) and problem (C≥), resp.) is not stable in the sense of Gol’shtein, the specificity of the approach suggested (the algorithms are not of gradient type and λ* is determined uniquely in all cases for the three problems under consideration) overcomes this “weakness” of the classical Lagrangian. That is why it is not necessary to use modified Lagrangians for problems (C), (C=), and (C≥).On the one hand, we need a closed form expression ofλ at Step (2) of the algorithms suggested. However, it is this feature of the algorithms that allows us to use classical Lagrangians instead of modified Lagrangians in the approach suggested. Moreover, the method for finding λ, and, therefore, for finding xj*,j∈J, in the corresponding problem (C), (C=), and (C≥), is exact although it is an iterative method.As it usually happens, the disadvantage in one aspect turns out to be an advantage in another aspect and vice versa.All conclusions in this section have been drawn under the assumption that the objective functionc(x) and the constraint function(s) di(x) of the three problems under consideration (C), (C=), (C≥) are nondegenerate, that is, c′(x*)≢0,  di′(x*)≢0; otherwise, the application of the Karush-Kuhn-Tucker theorem with differentiability is void of meaning.Some optimality criteria for degenerate mathematical programs are given, for example, in the book of Karmanov [6].


## 3.1. The Concept of Stability of Saddle Points of the Lagrangian

Besides well-posedness of the optimization problems, stability of methods for solving these problems is also important.LetΦ(x,y) be a convex function of x∈X and a concave function of y∈Y, where X and Y are convex and closed sets.Recall the definition of a saddle point.A point(x^,y^) is said to be a saddle point of function Φ(x,y),  x∈X,  y∈Y, if the following inequalities hold:
(46)Φ(x^,y)≤Φ(x^,y^)≤Φ(x,y^)
for all x∈X,y∈Y, that is, if
(47)Φ(x^,y^)=minx∈Xmaxy∈YΦ(x,y)=maxy∈Yminx∈XΦ(x,y).This means thatΦ(x,y) attains at the saddle point (x^,y^) its maximum with respect to y for fixed x^ and Φ(x,y) attains at (x^,y^) its minimum with respect to x for fixed y^.Set(48)χ(x)=maxy∈YΦ(x,y),ψ(y)=minx∈XΦ(x,y).Denote byX* and Y* the sets of optimal solutions to the optimization problems
(49)minx∈Xχ(x),maxy∈Yψ(y),
respectively, that is,
(50)X*≝{x:χ(x)=minx∈Xmaxy∈YΦ(x,y)}≡{x:maxy∈YΦ(x,y)=Φ(x^,y^)},Y*≝{y:ψ(y)=maxy∈Yminx∈XΦ(x,y)}≡{y:minx∈XΦ(x,y)=Φ(x^,y^)}.
Let X*,Y* be bounded sets. Then,
(51)χ(x*)=ψ(y*),x*∈X*,y*∈Y*,that is,(52)χ(x*)≝maxy∈YΦ(x*,y)=ψ(y*)≝minx∈XΦ(x,y*)=Φ(x^,y^).
This means that X*×Y* is the set of saddle points of Φ(x,y) and
(53)Φ(x^,y^)=Φ(x*,y*).
Consider the sets
(54)Xy*≝{x:Φ(x,y*)=Φ(x*,y*)},Yx*≝{y:Φ(x*,y)=Φ(x*,y*)},
that is, Xy* and Yx* denote the sets of arguments of Φ(x,y) with y=y* and x=x*, respectively, for which the value of Φ(x,y) is equal to its value at the saddle point.In the general case,X*⊂Xy*,  Y*⊂Yx*; that is, the sets Xy*,  Yx* contain sets X*,  Y*, respectively.Definition 20.
IfX*=Xy* and Y*=Yx*, then the set of saddle points of Φ(x,y) is said to be stable.If the set of saddle points ofΦ(x,y) is stable, then from
(55)limk→∞Φ(x(k),y*(k))=Φ(x*,y*),x(k)∈X,y*(k)∈Y
it follows that
(56)δ(x(k),X*)⟶0,k⟶∞,
and from
(57)limk→∞Φ(x*(k),y(k))=Φ(x*,y*),x*(k)∈X,y(k)∈Y
it follows that
(58)δ(y(k),Y*)⟶0,k⟶∞,
where δ(x,X)≝minz∈X∥x-z∥ is the distance from x to the set X. The implications written above mean that convergence of Φ(x,y*) to Φ(x*,y*) with respect to x(k) and convergence of Φ(x*,y) to Φ(x*,y*) with respect to y(k) implies convergence of sequence ({x(k)},{y(k)}) to the set X*×Y* of saddle points of Φ(x,y).The concept of stability, introduced by Definition20, is important for constructing iterative gradient algorithms for finding saddle points of the Lagrangian associated with an optimization problem.The set of saddle points of the Lagrangian associated with the problem(59)minx∈Sf(x),(60)S={x∈ℝn:φi(x)≤0,i=1,…,m,x∈X}is not stable according to Definition 20. Concerning the dual variables this can be proved as follows.Letrth constraint of (60) be satisfied as an equality at x*, that is,
(61)φr(x*)=0
for some r,  1≤r≤m. Then, the Lagrangian L(x*,λ) of problem (59)-(60) does not depend on λr and therefore L(x*,λ*)=L(x*,λ) is satisfied for every λr. Hence, it is impossible to determine λr by using the relation L(x*,λ*)=L(x*,λ).In order to avoid this difficulty, so-calledmodified Lagrangians are used instead of the “classical” Lagrangian. Modified Lagrangians are usually nonlinear functions of λ and the set of their saddle points is stable and it coincides, under some assumptions, with the set of saddle points of the “classical” Lagrangian for the same problem. This is important to ensure convergence of iterative gradient algorithms (see, e.g., Gol’shtein [5]).


## 3.2. About the Stability of the Set of Saddle Points for the Approach Considered in this Paper

Consider problem(C) (problem (C=) and problem (C≥), resp.). Obviously, the Lagrange multiplier λ, associated with the constraint (2) ((10) and (13), resp.), is not involved in the equality
(62)L(x*,u*,v*,λ*)=L(x*,u,v,λ)
when δ(λ*)=0, that is, when ∑j∈J‍dj(xj)=α. For problem (C),  λ*(>0) is either determined uniquely from δ(λ*)=0 when δ(0)>0 or we set λ*:=0 when δ(0)≤0 (Algorithm 2). Although the set of saddle points of the Lagrangian L(x,u,v,λ), associated with problem (C) (problem (C=) and problem (C≥), resp.) is not stable in the sense of Gol’shtein, the specificity of the approach suggested (the algorithms are not of gradient type and λ* is determined uniquely in all cases for the three problems under consideration) overcomes this “weakness” of the classical Lagrangian. That is why it is not necessary to use modified Lagrangians for problems (C), (C=), and (C≥).On the one hand, we need a closed form expression ofλ at Step (2) of the algorithms suggested. However, it is this feature of the algorithms that allows us to use classical Lagrangians instead of modified Lagrangians in the approach suggested. Moreover, the method for finding λ, and, therefore, for finding xj*,j∈J, in the corresponding problem (C), (C=), and (C≥), is exact although it is an iterative method.As it usually happens, the disadvantage in one aspect turns out to be an advantage in another aspect and vice versa.All conclusions in this section have been drawn under the assumption that the objective functionc(x) and the constraint function(s) di(x) of the three problems under consideration (C), (C=), (C≥) are nondegenerate, that is, c′(x*)≢0,  di′(x*)≢0; otherwise, the application of the Karush-Kuhn-Tucker theorem with differentiability is void of meaning.Some optimality criteria for degenerate mathematical programs are given, for example, in the book of Karmanov [6].


## 4. Primal-Dual Analysis

Some of the main characteristics of the approach, suggested for solving problems(C), (C=), and (C≥), are following.Since the method, proposed for problem(C), uses values of the first derivatives of functions cj(xj),j∈J, we can consider it as a first-order method. Also, this method is a saddle point method or, more precisely, a dual variables saddle point method because it is based on convergence with respect to the Lagrange multiplier (dual variable) λ associated with the single constraint (2).At Step (2) of Algorithm2, we use the expression of λ(k), calculated from the equality δ(λ(k))=0, where xj* are determined from (6), j∈Jλ(k)=J(k). As it was proved, under the assumptions for problem (C), we can always determine λ=λ(x*) from δ(λ)=0 as an implicit function of x*. For example, when dj(xj),j∈J, are linear functions, the explicit expression of λ is always available for Algorithm 2. There are also many other examples of functions, for which it is possible to obtain closed form expressions of λ, and therefore, the suggested approach is applicable and gives good results.Analogous commentary is valid for the method suggested for solving problem(C=).When the (optimal) Lagrange multiplierλ* associated with (2) is known, then problem (C) (1)–(3) can be replaced by the following separable convex optimization problem
(63)min{∑j∈J‍[cj(xj)+λ*dj(xj)]-λ*α}subjecttox∈A≝{x∈ℝn:aj≤xj≤bj,j∈J}.The problem, dual to problem(C), is
(64)maxΨ(λ)subjecttoλ∈ℝ+1,
where
(65)Ψ(λ)=minx∈A{∑j∈J‍[cj(xj)+λdj(xj)]-λα}.Problem(C=) can be considered similarly; dj(xj)=djxj and λ∈ℝ1 for it.Thus, using the Lagrangian duality and Theorem1 for problem (C) (Theorem 4 for problem (C=)) we have replaced the multivariate problem (C) (problem (C=)) of x∈ℝn by the single-variable optimization problem for finding λ∈ℝ+1 (λ∈ℝ1, resp.).Since Algorithm8 is based on Theorem 5 and Algorithm 6, and since the “iterative” Steps (2)–(7) of Algorithms 6 and 8 are the same, then primal-dual analysis for problem (C≥) is similar to that for problems (C) and (C=).


## 5. Bibliographical Notes

The definition of Tychonov well-posedness is given by Tychonov in [7]. Tychonov and Hadamard well-posedness and well-posedness in the generalized sense are considered, for example, in the work of Cavazzuti and Morgan [8], in the book of Dontchev and Zolezzi [9], in works of Hadamard [10, 11], and so forth. Other questions regarding stability, ill-posed problems, and Tychonov regularization can be found in [12–19], and so forth. Sometimes Tychonov is written as Tykhonov, Tikhonov or Tychonoff in references. Well-posedness is also discussed in the book of Rockafellar and Wets [20].Calmness in the sense of Clarke is proposed and studied in the works of Clarke [3, 21, 22]. Concerning Theorem 14, see also the paper of Roberts and Varberg [4].Stability of the set of saddle points of Lagrangians is considered in the papers of Gol’shtein [5], Gol’shtein and Tret’iakov [23], and so forth.Various convex separable optimization problems are considered and convergent polynomial algorithms for solving them are proposed in Stefanov [1, 2, 24–29].



---

*Source: 279030-2013-04-15.xml*