Optimality Conditions for Sparse Bilinear Least Squares Problems†

This work was partially supported by the National Natural Science Foundation of China under Grants 12371309, 12471295 and 12426306, Guangdong Basic and Applied Basic Research Foundation (2024A1515011566), and Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project (HZQSWS-KCCYB-2024016).

Zixin Deng School of Mathematics, Tianjin University, Tianjin 300072, China. Email: dengzx@tju.edu.cn.

Zheng-Hai Huang Corresponding author. School of Mathematics, Tianjin University, Tianjin 300072, China. Email: huangzhenghai@tju.edu.cn.

Yun-Bin Zhao Shenzhen International Center for Industrial and Applied Mathematics, SRIBD, The Chinese University of Hong Kong, Shenzhen 518172, China. Email: yunbinzhao@cuhk.edu.cn.

Abstract

The first-order optimality conditions of sparse bilinear least squares problems are studied. The so-called T-type and N-type stationary points for this problem are characterized in terms of tangent cone and normal cone in Bouligand and Clarke senses, and another stationarity concept called the coordinate-wise minima is introduced and discussed. Moreover, the L-like stationary point for this problem is introduced and analyzed through the newly introduced concept of like-projection, and the M-stationary point is also investigated via a complementarity-type reformulation of the problem. The relationship between these stationary points is discussed as well. It turns out that all stationary points discussed in this work satisfy the necessary optimality conditions for the sparse bilinear least squares problem.

Key words:  Bilinear least squares problem, sparsity constraint, first-order optimality condition, tangent cone, normal cone, like-projection

AMS subject classifications:  90C30, 90C26, 90C46, 94A12

1 Introduction

Sparse optimization involves the restriction on the cardinality of the support of variables in either constraints or the objective of an optimization problem (see, e.g., [3, 11, 12, 13, 38, 43]). Sparse optimization was largely motivated by the sparse signal recovery which has been extensively studied over the past decades (see, e.g., [18, 17, 22, 23, 24]). The problem for sparse signal recovery can be cast as

min_x∈ R ^n ‖ Ax-b‖ ^2:‖ x‖ _0≤ s ,

(1.1)

which can be referred to as the sparse least squares problem. In this model, A∈ℝˡ× n is a matrix with l≪n, b∈ Rˡ is a given vector (denoting the measurements of the signal to recover), and s (≪n) is a given positive integer. Throughout the paper, ‖ ·‖ denotes the 2-norm of a vector and ‖ ·‖ ₀ is called the ‘ℓ₀-norm’ denoting the number of nonzero components of a vector. The model (1.1) is a special case of the following optimization problem with a sparsity constraint:

min f(x): ‖ x‖ _0≤ s ,

(1.2)

where f:ℝⁿ →ℝ is a continuously differentiable function. The global sufficient and/or necessary optimality conditions for the problem (1.1) can be characterized in terms of such properties as the null space property (see, e.g., [20, 26]), restricted isometry property [18], range space propery of transposed matrices [44, 45], and the mutual coherence and related properties [23, 43]. For instance, under the above-mentioned null or range space property, it is known that the problem (1.1) can be equivalent to an ℓ₁-norm-based convex optimization problem (e.g., the LASSO problem or ℓ₁-minimization). This implies that the optimal solution of (1.1) can actually be characterized via the optimality condition of its equivalent convex counterpart under such matrix properties.

Due to the generality of f in (1.2), it is generally more difficult to characterize the optimality conditions for the solution of this problem. However, some recent progress has been made. Some work focuses on developing the necessary optimality conditions for (1.2), and the others on certain sufficient optimality conditions for the problem. For instance, Beck and Eldar [7] investigated the first-order necessary optimality conditions for the problem, including L-stationarity, basic feasibility and coordinate-wise minimality. They also developed certain numerical methods for (1.2) to locate a point satisfying their optimality conditions. Pan et al. [36] studied the so-called N-stationarity and T-stationarity conditions for (1.2) and pointed out that such stationarities are the necessary optimality conditions for this problem. They also developed a second-order sufficient optimality condition for (1.2). Similar studies of optimality conditions for this problem can be found in [34, 28, 32] and numerical methods in [47, 46, 42, 10, 6, 21, 3, 4].

However, the model (1.2) is far from being broad enough to cover all application scenarios. Motivated by structured signal recovery and other applications, the optimization problems with more complex constraints than (1.2) have also been studied in the literature. Such problems can be formulated as

(min, f(x); s.t., g(x)≤0, h(x)=0,; ·, ‖ x‖ ₀≤s,)

(1.6)

where g and h are two continuously differentiable functions. Compared to (1.2), it becomes more difficult to develop an optimality condition for the problem (1.6). One way to achieve this is to borrow the analysis tool from the traditional optimization problems. Burdakov, Kanzow and Schwartz [13] proposed a complementarity-type reformulated model and thus established the M (Mordukhovich)-stationarity condition for (1.6). They also proposed a regularization method which turns out to be globally convergent to an M-stationary point of the problem. Based on such a reformulation, Bucher and Schwartz [12] introduced a second-order optimality condition that can guarantee the local uniqueness of a M-stationary point. More studies on the optimality conditions of (1.6) can be found in [33, 35, 11, 27].

In this paper, we study a sparse optimization problem which is also more general than (1.1) but does not fall into the framework of (1.6) . The model considered here is referred to as the sparse bilinear least squares problem for which we develop certain necessary optimality conditions in this paper. Specifically, let A=(a_ijk)∈ R ^l× m× n be a given 3-rd order tensor, b∈ℝˡ be a given vector and s,t be two fixed positive integers with s<m and t<n. For x∈ℝᵐ and y∈ℝⁿ, denote _1:= supp (x)= i:x_i=0 and define γₓ as the first index of Γ₁. We consider the following model:

(min, f(x,y)=(1)/(2)‖ Axy-b‖ ²; s.t., eᵧₓ^→ p x=1,; ·, ‖ x‖ ₀≤s, ‖ y‖ ₀≤t,)

(1.10)

where e_γₓ∈ℝᵐ is an m-dimensional identity column vector whose γₓ-th entry is 1 and the others are 0. In this model, Axy is short for A×_2x×_3y, where ×ₖ (k=2,3) is the mod-k product of 3-rd order tensor. Precisely, for any x∈ℝᵐ and y∈ℝⁿ, the entries of A×_2x∈ R ^l× n, A×_3y∈ R ^l× m and A×_2x×_3y∈ R ^l are given as

(A×_2x)_ij=Σ_i_2∈ 1,2,…,m a_ii_2jx_i_2, ∀ i∈ 1,2,…,l ,∀ j∈ 1,2,…,n ,

(A×_3y)_ij=Σ_i_3∈ 1,2,…,n a_iji_3y_i_3, ∀ i∈ 1,2,…,l ,∀ j∈ 1,2,…,m ,

(A×_2x×_3y)_i=Σ_i_2∈ 1,2,…,m ,i_3∈ 1,2,…,n a_ii_2i_3x_i_2y_i_3, ∀ i∈ 1,2,…,l .

The constraint e_γₓ^→ p x=1 is used to eliminate the multiplicity of the solution to the problem and thus to guarantee the well-definedness of the bilinear model [25, 39]. In fact, without the constraint e_γₓ^→ p x=1, we see that for any α∈ℝ, if (α x,y) solves the problem (1.10), so does the point (x,α y). Clearly, the well-definedness of the bilinear model can also ensured if e_γₓ^→ p x=1 is replaced by e_γ_y^→ p y=1, where γ_y is the first index of supp(y). The constraint e_γₓ^→ p x=1 makes it more difficult to develop an optimality condition for the problem (1.10) than (1.2) and (1.6).

Problem (1.10) arises in many scenarios, including blind deconvolution [2, 9, 8, 16, 29, 15], Hammerstein identification [39, 25], self-calibration [40, 31] and matrix sensing [1, 30]. Let us take a look at two examples.

Example 1.1 (Blind deconvolution) Generally, the mathematical model of blind deconvolution can be described as

(Hx)⊙ (Gy)=b,

(1.11)

where H=(hᵢⱼ)∈ℝˡ× m and G=(gᵢₖ)∈ℝˡ× n are two known dictionaries, b∈ℝˡ is an observation vector, x∈ℝᵐ and y∈ℝⁿ are two unknown vectors, and ‘⊙’ denotes the Hadamard product (i.e., for any u,v∈ℝˡ, w=u⊙ v means wᵢ=uᵢ vᵢ for i=1,…,l). In such scenarios as random mask imaging [8], compressed sensing with unknown sensor gains [16, 15] and blind channel estimation [29, 2, 31], the sparse structure of x,y needs to be considered separately. Thus the cardinality constraints ‖ x‖ ₀≤s and ‖ y‖ ₀≤t for certain integers s<m and t<n would come into play. In this case, (1.11) can be modeled as (1.10) where A=(a_ijk)∈ R ^l× m× n with aᵢⱼₖ=gᵢⱼ hᵢₖ for i∈{1,…,l}, j∈{1,…,m} and k∈{1,…,n}.

Example 1.2 (Matrix sensing)

Lee, Wu and Bresler [30] solved rank-one matrix equations by using the sparse power factorization method when the row sparsity and column sparsity are both involved. Specifically, let A:ℝᵐ× n →ℝˡ be a linear operator defined by A(X)=(⟨M₁,X⟩,…,⟨Mₗ,X⟩)^→ p for X∈ℝᵐ× n, where Mᵢ ∈ℝᵐ× n are known measurements for i∈{1,…,m}, and let b∈ℝˡ be the measurement vector and

S:={X∈ℝᵐ× n: X has s nonzero rows and t nonzero columns} .

The sparse least squares problem for a matrix equation can be described as

min_X∈ S ‖ A X-b‖ ^2.

(1.12)

Since X is rank-one, there exist λ∈ℝ,x∈ℝᵐ and y∈ℝⁿ such that X=λ xy^→ p. Thus (1.12) can be reformulated as the sparse bilinear problem

min_x∈ S_1,y∈ S_2 ‖ λ A (xy^→ p)-b‖ ^2,

(1.13)

where S₁:={x∈ℝᵐ: ‖ x‖ ₀≤s} and S₂:={y∈ℝⁿ: ‖ y‖ ₀≤t}. So the problem above can be formulated as (1.10), where the tensor A=(a_ijk)∈ R ^l× m× n is defined by aᵢⱼₖ=(Mᵢ)ⱼₖ for i∈{1,…,l} ,j∈{1,…,m} and k∈{1,…,n} .

The optimality conditions for (1.10) have not been systematically studied at present. This paper is devoted to this study and the main contributions of this work include:

• The exact expressions of Bouligand (Clarke) tangent and normal cones for the problem (1.10) at some feasible point are given. Based on this, we characterize the so-called N^B(N^C)-stationary point and T^B(T^C)-stationary point of (1.10). We show that an optimal solution of (1.10) must be an N^B(N^C)-stationary point and be an T^B(T^C)-stationary point for this problem.
• The concept of coordinate-wise minima is given in accordance with the structure of the feasible set of (1.10). We show that an optimal solution of (1.10) is necessarily a CW-minimum.
• Using the newly defined concept of like-projection, L-like stationarity is introduced and characterized. In particular, we establish the first-order necessary condition for an optimal solution of (1.10) to be an L-like stationary point.
• Based on a complementarity-type reformulation of (1.10), we introduce and characterize the M-stationary point of (1.10). In particular, we also show that an optimal solution of (1.10) must be an M-stationary point.
• We also discuss the relationship of the above-mentioned stationary points.

The rest of the paper is organized as follows. In Section 2, we introduce the notations, concepts and basic results that will be used in the subsequent analysis. In Section 3, we study the N^B(N^C)-stationary points, T^B(T^C)-stationary points, coordinate-wise minima, L-like stationary points and M-stationary points as well as the related optimality conditions. The conclusions are given in Section 4.

2 Preliminaries

Let ℕ denote the set {1,2,…,}. For fixed positive integers m and n, we denote

I:={1,…,m+n} ,I₁:={1,…,m} ,I₂:={m+1,…,m+n} .

Denote by e_I:=(1,…,1)^→ p ∈ℝᵐ⁺ⁿ, e_I₁:=(1,…,1)^→ p ∈ℝᵐ and e_I₂:=(1,…,1)^→ p ∈ℝⁿ. For any i∈ I, let eᵢ denote the (m+n)-dimensional column vector with the i-th entry being 1 and the others being 0. For fixed integer l, we denote A=(a_i_1i_2i_3)∈ R ^l× m× n as a 3-rd order tensor with i₁ ∈{1,…,l}, i₂ ∈{1,…,m} and i₃ ∈{1,…,n}.

For any x∈ℝᵐ, ‖ x‖ denotes the l₂-norm of x, ‖ x‖ _∞ denotes the infinite norm of x, supp(x):={i∈ I₁: xᵢ≠0} denotes the support of x, and |x| denotes the absolute vector of x, i.e., |x|:=(|x₁|,…,|xₘ|)^→ p. We use Mᵢ(x) to denote the value of the i-th largest entries of x for any i∈ I₁. For any z:=(x^→ p,y^→ p)^→ p ∈ℝᵐ⁺ⁿ, we use (x,y) to denote (x^→ p,y^→ p)^→ p for convenience, and we use Γ,Γ₁,Γ₂ to denote respectively the following support sets:

Γ:=supp(z), Γ₁:=supp(x), Γ₂:=supp(y).

(2.1)

Let γₓ be the index of the first nonzero entry of x∈ℝᵐ, i.e., γ_x:= i∈ I_1:x_i≠ 0. Moreover, denote by

F₁ :={x∈ℝᵐ: ‖ x‖ ₀≤s, e^→ p_γₓx=1} , F₂ :={y∈ℝⁿ: ‖ y‖ ₀≤t} , F :=F₁ × F₂={z=(x,y): x∈ F₁, y∈ F₂} .

(2.2) (2.3) (2.4)

Clearly, F is the feasible set of (1.10).

For a symmetric matrix A∈ℝᵐ× m, λₘₐₓ(A) is the spectrum value of A, i.e.,

λₘₐₓ(A):={max|λ|: λ∈ℝis an eigenvalue of A} .

For an index set Λ⊆ I, |Λ| means the cardinality of Λ. For a subset S⊆ℝᵐ, let δ_S denote the indicator function of S. That is,

δ_S(x)={(0, if x∈ S,; ∞, if x∉S.).

Tangent and normal cones of the feasible set of optimization problems are important tools for the study of optimization problems (see, e.g., [19, 37]). The following concepts of tangent and normal cones are defined in the sense of Bouligand and Clarke, respectively.

Definition 2.1

For any nonempty set S⊆ℝⁿ, d∈ℝⁿ is called a Bouligand tangent vector of S at x∈ S if there exist {xᵏ} ⊂ S with limₖ→∞ xᵏ=x and λₖ≥0 for k∈ℕ such that limₖ→∞ λₖ(xᵏ-x)=d. The set containing all Bouligand tangent vectors of S at x∈ S is a cone, which is called the Bouligand tangent cone of S at x, denote by T^B_S(x). Moreover, the polar cone of T^B_S(x) is called the Bouligand normal cone of S at x, denote by N^B_S(x), i.e.,

N^B_S(x)={d∈ℝⁿ:<d,u>≤0, ∀ u∈ T^B_S(x)} .

Definition 2.2

For any nonempty set S⊆ℝⁿ, d∈ℝⁿ is called a Clarke tangent vector of S at x∈ S if for any {xᵏ} ⊂ S with limₖ→∞ xᵏ=x and {λₖ} ⊂ℝ₊ with limₖ→∞ λₖ=0, there exists {yᵏ} with limₖ→∞ yᵏ=d such that xᵏ+λₖ yᵏ ∈ S for any k∈ℕ. The set containing all Clarke tangent vectors of S at x∈ S is called the Clarke tangent cone of S at x, denote by T^C_S(x). Correspondingly, the polar cone of the Clarke tangent cone of S at x is called the Clarke normal cone of S at x, denote by N^C_S(x), i.e,

N^C_S(x)={d∈ℝⁿ:<d,u>≤0, ∀ u∈ T^C_S(x)} .

Throughout the remainder of the paper, we use f:ℝᵐ⁺ⁿ →ℝ to denote the objective function of (1.10), ∇ f(z) the gradient of f at z:=(x,y)∈ℝᵐ⁺ⁿ, and ∇ᵢ f(z) the i-th component of ∇ f(z) for i∈ I. And for S⊂ I, we use ∇_S f(z) to denote the sub-vector of ∇ f(z) with only components ∇ᵢ f(z) for i∈ S.

3 First-order optimality conditions

In this section, we investigate several classes of stationary points and the related optimality conditions for the problem (1.10).

3.1 N-type and T-type stationary points

We first introduce the concepts of N-type stationary point and T-type stationary point via the tangent and normal cones described in Definitions 2.1 and 2.2. Then we characterize these stationary points and establish the optimality conditions for problem (1.10).

3.1.1 Basic concepts and lemma

The definition of N-type stationary point of (1.10) is an extension of the definition of critical point in [5].

Definition 3.1

Let F be defined by (2.4). z∗:=(x∗,y∗)∈ℝᵐ⁺ⁿ is called an N^#-stationary point of (1.10) if

-∇ f(z∗)∈ N^#_F(z∗),

where #∈{B,C} means the Bouligand sense and Clarke sense, respectively.

Next, the T-type stationary point of (1.10) is extended from [14].

Definition 3.2

Let F be defined by (2.4). z∗:=(x∗,y∗)∈ℝᵐ⁺ⁿ is called a T^#-stationary point of (1.10) if

‖ ∇^#_F f(z∗)‖=0,

where ∇^#_F f(z∗):=argmin{‖ ∇ f(z∗)+d‖ : d∈ T^#_F(z∗)} and #∈{B,C} means the Bouligand sense and Clarke sense, respectively.

The following lemma will be frequently used in subsequent analyses.

Lemma 3.1

For any x∈ F₁ defined in (2.2) and {xᵏ} ⊂ F₁ satisfying limₖ→∞ xᵏ=x, there must exist k₀ ∈ℕ such that the index for the first nonzero element of xᵏ is equal to γₓ for all k>k₀.

Proof. Since the sequence {xᵏ} converges to x, it follows that for any ε<1, there exists k₀ ∈ℕ such that ‖ xᵏ-x‖ _∞<ε. Choose k>k₀ arbitrarily and denote the first element of supp(xᵏ) by i∗.

• If i∗<γₓ, then we have xᵏ_i∗=1 and x_i∗=0 by the definition of F₁ since x∈ F₁ and {xᵏ} ⊂ F₁. Thus ‖ xᵏ-x‖ _∞≥|xᵏ_i∗-x_i∗|=1>ε, which contradicts the result ‖ xᵏ-x‖ _∞<ε.
• If i∗>γₓ, then we have xᵏ_γₓ=0 and x_γₓ=1, and hence, ‖ xᵏ-x‖ _∞≥|xᵏ_γₓ-x_γₓ|=1>ε, which also leads to a contradiction.

Thus, i∗=γₓ. By the arbitrariness of k, we conclude that the index for the first nonzero element of xᵏ is equal to γₓ for any k>k₀. $\Box$

3.1.2 First-order optimality conditions by Bouligand tangent and normal cones

Firstly, we describe the precise forms of the tangent and normal cones of F at a point in F in the sense of Bouligand. The following two lemmas are useful for proving the desired result.

Lemma 3.2

([37, Proposition 6.41]) Assume that C₁ ⊆ℝᵐ and C₂ ⊆ℝⁿ, then for any z=(x,y)∈ C₁ × C₂ ⊆ℝᵐ⁺ⁿ, we have

T_C₁ × C₂^B(z)=T_C₁^B(x)× T_C₂^B(y) and N_C₁ × C₂^B(z)=N_C₁^B(x)× N_C₂^B(y).

The above lemma indicates that the Bouligand tangent and normal cones are separable under the Cartesian product of sets. In fact, denote C:=C₁ × C₂, by the definition of Bouligand tangent cone at some point z=(x,y)∈ C, we have

T^B_C(z)={d∈ℝᵐ⁺ⁿ: d=limₖ→∞ λₖ(zᵏ-z) where zᵏ→z,{λₖ}≥0} .

Since C=C₁ × C₂, we have d=(d₁,d₂)∈ T^B_C(z) if and only if for {λₖ}≥0,

d_1=lim_k→∞λ_k(x^k-x) where x^kC_1→x and d_2=lim_k→∞λ_k(y^k-y) where y^kC_2→y.

That is d₁ ∈ T^B_C₁(x) and d₂ ∈ T^B_C₂(y). The result for the normal cone follows directly from the polarity relation. This lemma provides an approach to characterize the Bouligand tangent and normal cones of the set F, that is, by first characterizing those of F₁ and F₂ separately and then taking their Cartesian product. Fortunately, the characterization of F₂ has already been established in the existing literature, which is given in the following lemma.

Lemma 3.3

([36, Theorem 2.1]) For any y∈ F₂ with F₂ being defined by (2.3), the Bouligand tangent cone and corresponding normal cone of F₂ at y are

T^B_F_2(y) = d∈ R ^n: ‖ d‖ _0≤ t, ‖ y+μ d‖ _0≤ t, ∀μ∈ R = _ span e_i,i∈_2,||≤ t ,

(3.1) (3.2)

N^B_F₂(y)={(d∈ℝⁿ: dᵢ=0, i∈Γ₂, ·, if |Γ₂|=t,; 0, ·, if |Γ₂|<t,).

(3.3)

respectively.

Theorem 3.1

For any x∈ F₁ with F₁ being defined by (2.2), then the Bouligand tangent cone and normal cone of F₁ at x can be written as

T^B_F_1(x) = d∈ R ^m: ‖ d‖ _0≤ s-1; d_j=0, ∀ j≤γ_x; x+μ d∈ F_1, ∀μ∈ R = _ span e_i: i∈_1∖ γ_x ; j, ∀ j≤γ_x; ||≤ s-1 ,

(3.4) (3.5)

N^B_F₁(x)={(d∈ℝᵐ: dᵢ=0, i∈Γ₁ ∖γₓ, ·, if |Γ₁|=s,; d∈ℝᵐ: dᵢ=0, i>γₓ, ·, if |Γ₁|<s,).

(3.6)

respectively.

Proof. Let D denote the set on the right-hand side of (3.4). Thus it is sufficient to show that T^B_F₁(x)=D. On one hand, for any d∈ T^B_F₁(x), it follows from Definition 2.1 that there exist {xᵏ} ⊂ F₁ satisfying limₖ→∞ xᵏ=x and λₖ≥0 for k∈ℕ such that limₖ→∞ λₖ(xᵏ-x)=d. Then there exists k₀ ∈ℕ such that supp(x)⊆supp(xᵏ) and supp(d)⊆supp(xᵏ-x)⊆supp(xᵏ) for any k>k₀, and hence,

supp(d)⊆supp(xᵏ), supp(d)∪supp(x)⊆supp(xᵏ).

(3.7)

These imply that

‖ x+μ d‖ ₀≤s, ∀μ∈ℝ.

(3.8)

In addition, by Lemma 3.1, there exists k₁ ∈ℕ such that xᵏ_γₓ=1 for any k>k₁. Thus,

d_γₓ=limₖ→∞ λₖ(xᵏ_γₓ-x_γₓ)=0.

(3.9)

Note that for any j∈ I₁ with j<γₓ,

dⱼ=limₖ→∞ λₖ(xᵏⱼ-xⱼ)=limₖ→∞ λₖ(0-0)=0.

(3.10)

Thus, for any μ∈ℝ, one has

=x_γₓ+μ d_γₓ=1,=xⱼ+μ dⱼ=0, ∀ j<γₓ.

(3.11) (3.12)

Combining (3.7)-(3.12), we can obtain that z+μ d∈ F for any μ∈ℝ, ‖ d‖ ₀≤s-1 and dⱼ=0 for any j∈ I₁ with j<γₓ. This means d∈ D, and thus T^B_F₁(x)⊆ D. On the other hand, for any d∈ D, we take {λₖ} such that limₖ→∞ λₖ=∞, and define

xᵏ:=x+(1)/(λₖ)d, ∀ k∈ℕ.

Then, we have xᵏ ∈ F₁ for any k∈ℕ, limₖ→∞ xᵏ=x and d=limₖ→∞ λₖ(xᵏ-x). It follows that d∈ T^B_F₁(x). Thus D T^B_F_1(x). So (3.4) holds, we now further show that (3.5) holds.

Let P denote the set on the right-hand side of (3.5). We now prove (3.5), i.e., D=P. On one hand, for any d∈ D, we define Λᵈ:=supp(d)∪(Γ₁ ∖{γₓ}). It is easy to see that

d∈span{eᵢ: i∈Λᵈ} , Γ₁ ∖{γₓ} ⊆Λᵈ, γₓ∉Λᵈ

and j∉Λᵈ for any j∈ I₁ with j<γₓ. In addition, since ‖ x+μ d‖ ₀≤s for any μ∈ℝ, one has

|supp(d)∪supp(x)|≤s,

which together with γₓ ∈supp(x) imply that |Λᵈ|≤s-1. Thus it follows from (3.5) that span{eᵢ: i∈Λᵈ} ⊆ P, and thus d∈ P. So D⊆ P. On the other hand, for any d∈ P, it follows from (3.5) that there exists Λ̅ᵈ with |Λ̅ᵈ|≤s-1, Γ₁ ∖{γₓ} ⊆Λ̅ᵈ and j∉Λ̅ᵈ for any j∈ I₁ with j<γₓ such that supp(d)⊆Λ̅ᵈ. Therefore, |supp(d)|≤s-1 and dⱼ=0 for any j∈ I₁ with j<γₓ. Moreover, supp(x+μ d)⊆Γ₁ ∪supp(d)⊆Λ̅ᵈ ∪{γₓ} for any μ∈ℝ. Thus, ‖ x+μ d‖ ₀≤s, (x+μ d)_γₓ=1 and (x+μ d)ⱼ=0 for any j∈ I₁ with j<γₓ. That is, x+μ d∈ F₁ for any μ∈ℝ. This, together with |supp(d)|≤s-1 and dⱼ=0 for any j∈ I₁ with j<γₓ, implies that d∈ D. Thus, P⊆ D. So D=P, and thus (3.5) holds.

Now, we show (3.6), which holds trivially when s=1. Specifically, one must have Γ₁={γₓ} for any x∈ F₁ with s=1. Then at this point x, the tangent cone T^B_F₁(x) reduces to {0}. It follows from the definition of normal cone that N^B_F₁(x)=ℝᵐ, which implies that (3.6) holds due to Γ₁={γₓ}. Now, we turn to the case s>1. In this situation, (3.6) can be verified by considering two separate cases.

Case 1: |Γ₁|=s. On one hand, for any h∈ T^B_F₁(x), it follows from (3.4) that hⱼ=0 for any j∉Γ₁ ∖{γₓ}. Thus, for any d∈{d∈ℝᵐ: dᵢ=0,∀ i∈Γ₁ ∖{γₓ}}, we have <d,h>=0≤0, and hence d∈ N^B_F₁(x) by the definition of N^B_F₁(x). So in this case

{d∈ℝᵐ: dᵢ=0,∀ i∈Γ₁ ∖{γₓ}} ⊆ N^B_F₁(x).

On the other hand, for any d∈ N^B_F₁(x), it follows from (3.4) that d∈ D. If

d∉{d∈ℝᵐ: dᵢ=0,∀ i∈Γ₁ ∖{γₓ}} ,

then there exists i₀ ∈Γ₁ ∖{γₓ} such that d_i₀≠0. Define h∈ℝᵐ such that h_i₀=d_i₀ and other entries are zero. Then, it is easy to see that ‖ h‖ ₀≤s-1 and x+μ h∈ F₁ due to i₀ ∈Γ₁ ∖{γₓ}, and that hⱼ=0 for all j∈ I₁ with j≤γₓ by the definition of γₓ. Thus, h∈ D, i.e., h∈ T^B_F₁(x). However, <d,h>=d_i₀²>0, which contradicts d∈ N^B_F₁(x) and h∈ T^B_F₁(x). Thus, d∈{d∈ℝᵐ: dᵢ=0,∀ i∈Γ₁ ∖{γₓ}}. So

N^B_F₁(z)⊆{d∈ℝᵐ: dᵢ=0,∀ i∈Γ₁ ∖{γₓ}} .

Therefore, (3.6) holds in this case.

Case 2: |Γ₁|<s. On one hand, for any

d∈D:= d∈ R ^m: d_i=0,∀ i> γ_x ,

one has dᵢ=0 for any i∈{i∈ I₁:i>γₓ}. Since for any h∈ T^B_F₁(x), it follows from (3.4) that hⱼ=0 for all j∈ I₁ with j≤γₓ, we have <d,h>=0≤0 for any h∈ T^B_F₁(x). Then we have d∈ N^B_F₁(x). So D̂⊆ N^B_F₁(x). On the other hand, suppose there exists d∈ N^B_F₁(x) but dD. Then there exists i₀ ∈{i∈ I₁:i>γₓ} such that d_i₀≠0. We define h same as Case 1. Similar to the analysis in Case 1, we obtain a contradiction as well. Thus, d∈D. So D N^B_F_1(x). Therefore, D̂=N^B_F₁(x). It means (3.6) still holds in this case. The proof of the theorem is complete. $\Box$

Theorem 3.2

For any z=(x,y)∈ F with F being defined by (2.4), the Bouligand tangent cone and corresponding normal cone of F at z are given by

T^B_F(z) = d=(d_1,d_2)∈ R ^m+n: ‖ d_1‖ _0≤ s-1, ‖ d_2‖ 0≤ t; z+μ d∈ F, d_j=0 for all j≤γ_x = span e_i:i∈ : ∖ γ_x ,j for all j≤γ_x, |∩ I_1|≤ s-1, |∩ I_2|≤ t

,

(3.15) (3.18)

N^B_F(z)={(d∈ℝᵐ⁺ⁿ: dᵢ=0,∀ i∈Γ∖γₓ, if |Γ₁|=s and |Γ₂|=t,; d∈ℝᵐ⁺ⁿ: dᵢ=0,∀ i∈(Γ₁ ∖γₓ)∪ I₂, if |Γ₁|=s and |Γ₂|<t,; d∈ℝᵐ⁺ⁿ: dᵢ=0,∀ i∈γₓ+1,…,m ∪Γ₂, if |Γ₁|<s and |Γ₂|=t,; d∈ℝᵐ⁺ⁿ: dᵢ=0,∀ i∈i∈ I:i>γₓ, if |Γ₁|<s and |Γ₂|<t,).

(3.19)

respectively, where Γ,Γ₁ and Γ₂ are defined by (2.1).

The results are directly from Lemma 3.2, Lemma 3.3 and Theorem 3.1. Next, we present a sufficient and necessary condition for N^B- and T^B-stationary points, respectively. The first one below can be obtained directly from (3.19).

Theorem 3.3

Let z∗=(x∗,y∗)∈ F, where F is defined by (2.4). Then z∗ is an N^B-stationary point of (1.10) if and only if ∇ f(z∗)∈ℝᵐ⁺ⁿ with

{(∇ᵢ f(z∗)=0,∀ i∈Γ∗ ∖γₓ∗, if |Γ∗₁|=s and |Γ∗₂|=t,; ∇ᵢ f(z∗)=0,∀ i∈(Γ∗₁ ∖γₓ∗)∪ I₂, if |Γ∗₁|=s and |Γ∗₂|<t,; ∇ᵢ f(z∗)=0,∀ i∈γₓ∗+1,…,m ∪Γ∗₂, if |Γ∗₁|<s and |Γ∗₂|=t,; ∇ᵢ f(z∗)=0,∀ i∈i∈ I:i>γₓ∗, if |Γ∗₁|<s and |Γ∗₂|<t,).

(3.24)

where Γ∗,Γ∗₁,Γ∗₂ are defined by

Γ∗:=supp(z∗), Γ∗₁:=supp(x∗), Γ∗₂:=supp(y∗).

(3.25)

Theorem 3.4

Let z∗=(x∗,y∗)∈ F, where F is defined by (2.4). Then z∗ is a T^B-stationary point if and only if (3.24) holds.

Proof. Define Γ∗,Γ∗₁,Γ∗₂ as (3.25). We consider the following four cases.

Case 1: |Γ∗₁|=s and |Γ∗₂|=t. For this case, we prove that ∇^B_F f(z∗)=0 if and only if ∇ᵢ f(z∗)=0 for all i∈Γ∗ ∖{γ_x∗}.

(⇒) Suppose there exists i₀ ∈Γ∗ ∖{γ_x∗} such that ∇_i₀f(z∗)≠0. Pick d̅=(d̅₁,d̅₂)∈ℝᵐ⁺ⁿ such that d̅_i₀=-∇_i₀f(z∗) and other entries of d̅ are zero. Since ‖ d̅₁ ‖ ₀≤s-1 (note that d is well-defined here: when s=1, since i₀ ∈Γ∗ ∖{γₓ}, we have d₁=0 i.e., ‖ d₁ ‖ ₀=0), ‖ d̅₂ ‖ ₀≤t, z^ +μd∈ F for all μ∈ℝ and d̅ⱼ=0 for all j∈ I₁ with j≤γ_x∗, it follows from (3.15) that d̅∈ T^B_F(z∗). Then, by Definition 3.2, one has

‖ ∇^B_F f(z∗)+∇ f(z∗)‖ ²≤‖ d̅+∇ f(z∗)‖ ².

(3.26)

Since ∇^B_F f(z∗)=0, (3.26) is equivalent to

Σ₁≤i≤m+n(∇ᵢ f(z∗))²≤Σ_1≤i≤m+n,i≠i₀(∇ᵢ f(z∗))².

(3.27)

This implies that (∇_i₀f(z∗))²≤0, a contradiction.

($\Leftarrow$) Suppose there exists d̅∈ T^B_F(z∗) and d̅≠0 such that

‖ d̅+∇ f(z∗)‖ ²≤‖ 0+∇ f(z∗)‖ ².

(3.28)

It follows from (3.15) that supp(d̅)⊆Γ∗ ∖{γ_x∗}. Thus (3.28) is equivalent to

Σ_i∈Γ∗ ∖{γ_x∗} (d̅ᵢ+∇ᵢ f(z∗))²≤Σ_i∈Γ∗ ∖{γ_x∗} (∇ᵢ f(z∗))².

Since ∇ᵢ f(z∗)=0 for all i∈Γ∗ ∖{γ_x∗}, the inequality above implies that Σ_i∈Γ∗ ∖{γ_x∗} (d̅ᵢ)²≤0, which leads to a contradiction.

Case 2: |Γ∗₁|=s and |Γ∗₂|<t. In this case, we prove that ∇^B_F f(z∗)=0 if and only if ∇ᵢ f(z∗)=0 for all i∈(Γ∗₁ ∖{γ_x∗})∪ I₂.

(⇒) Suppose there exists i₀ ∈(Γ∗₁ ∖{γ_x∗})∪ I₂ such that ∇_i₀f(z∗)≠0. Pick d̅=(d̅₁,d̅₂)∈ℝᵐ⁺ⁿ same as Case 1, we also have d̅∈ T^B_F(z∗). Then, by Definition 3.2, the inequality (3.26) holds. Since ∇^B_F f(z∗)=0, (3.26) is equivalent to (3.27), which implies that (∇_i₀f(z∗))²≤0. This is a contradiction.

($\Leftarrow$) Suppose there exists d̅∈ T^B_F(z∗) and d̅≠0 such that (3.28) holds. It follows from (3.15) that supp(d̅)⊆(Γ∗₁ ∖{γ_x∗})∪ I₂. Thus (3.28) is equivalent to

Σ_i∈(Γ∗₁ ∖{γ_x∗})∪ I₂(d̅ᵢ+∇ᵢ f(z∗))²≤Σ_i∈(Γ∗₁ ∖{γ_x∗})∪ I₂(∇ᵢ f(z∗))²,

which implies Σ_i∈(Γ∗₁ ∖{γ_x∗})∪ I₂(d̅ᵢ)²≤0, a contradiction.

Case 3: |Γ∗₁|<s and |Γ∗₂|=t. In this case, we prove that ∇^B_F(z∗)=0 if and only if ∇ᵢ f(z∗)=0 for all i∈{γ_x∗+1,…,m} ∪Γ∗₂.

(⇒) Suppose there exists i₀ ∈{γ_x∗+1,…,m} ∪Γ∗₂ such that ∇_i₀f(z∗)≠0. Pick d̅=(d̅₁,d̅₂)∈ℝᵐ⁺ⁿ same as Case 1, we also have d̅∈ T^B_F(z∗). Then, by Definition 3.2, one must have (3.26) holds. Similar to the analysis in Case 1, it follows from ∇^B_F f(z∗)=0 that (∇_i₀f(z∗))²≤0. This is a contradiction.

($\Leftarrow$) Suppose there exists d̅∈ T^B_F(z∗) and d̅≠0 such that (3.28) holds. It follows from (3.15) that supp(d̅)⊆{γ_x∗+1,…,m+n}. Thus (3.28) implies Σ_i=γ_x∗+1ᵐ⁺ⁿ(d̅ᵢ)²≤0, a contradiction.

Case 4: |Γ∗₁|<s and Γ∗₂<t. In this case, we prove that ∇^B_F(z∗)=0 if and only if ∇ᵢ f(z∗)=0 for all i∈{i∈ I:i>γ_x∗}.

(⇒) Suppose there exists i₀ ∈{i∈ I:i>γ_x∗} such that ∇_i₀f(z∗)≠0. Pick d̅=(d̅₁,d̅₂)∈ℝᵐ⁺ⁿ same as Case 1, we also have d̅∈ T^B_F(z∗). Then, by the same analysis as in Case 1, one can also obtain that (∇_i₀f(z∗))²≤0, a contradiction.

($\Leftarrow$) Suppose there exists d̅∈ T^B_F(z∗) and d̅≠0 such that (3.28) holds. It follows from (3.15) that supp(d̅)⊆{i∈ I:i>γ_x∗}. Thus (3.28) implies Σ_i∈{i∈ I:i>γ_x∗} (d̅ᵢ)²≤0, a contradiction again. Therefore the proof of the theorem is complete. $\Box$

According to Theorems 3.3 and 3.4, the next result follows immediately.

Corollary 3.1

z∗ ∈ℝᵐ⁺ⁿ is an N^B-stationary point of (1.10) if and only if z∗ is a T^B-stationary point of (1.10).

Finally, we discuss the relation between N^B-stationary point (T^B-stationary point) of (1.10) and the optimal solution of (1.10).

Theorem 3.5

If z∗=(x∗,y∗) is an optimal solution of (1.10), then z∗ is an N^B-stationary point, and z∗ is also a T^B-stationary point.

Proof. By Corollary 3.1, we only need to show that z∗ is an N^B-stationary point. We will use Theorem 3.3 to show this result. Since z∗=(x∗,y∗) is an optimal solution of (1.10), it follows that z∗ ∈ F. Define Γ∗,Γ∗₁,Γ∗₂ by (3.25). We now show the desired result by using (3.24).

Let gᵢ(u):=f(z∗+ueᵢ) for any i∈ I and u∈ℝ, where f is defined by (1.10). Then, for any i∈ I, we have

gᵢ(u)={(‖ A(x^ +ueᵢ)y^ -b‖ ², if i∈ I₁,; ‖ Ax^ (y^ +ueᵢ)-b‖ ², if i∈ I₂,).

which is a strictly convex function for any i∈ I. Thus gᵢ(·) has a unique minimizer that satisfies g′ᵢ(u)=0. In what follows, we divide the proof into four cases.

Case 1: ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀=t. For any i∈Γ∗ ∖{γ_x∗}, we have argmin{gᵢ(u): u∈ℝ}=0. Otherwise, there exists u₀≠0 such that z∗+u₀ eᵢ ∈ F and f(z∗+u₀ eᵢ)<f(z∗) which yields a contradiction. Thus g′ᵢ(0)=0 for any i∈Γ∗ ∖{γ_x∗}. Moreover,

g′ᵢ(0)=limᵤ→ 0(f(z∗+ueᵢ)-f(z∗))/(u)=∇ᵢ f(z∗), ∀ i∈ I.

Thus ∇ᵢ f(z∗)=g′ᵢ(0)=0 for any i∈Γ∗ ∖{γ_x∗}. This, together with Theorem 3.3, implies that z∗ is an N^B-stationary point when ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀=t.

Case 2: ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀<t. For any i∈(Γ∗₁ ∖{γ_x∗})∪ I₂, we have z∗+ueᵢ ∈ F for any u∈ℝ. If g′ᵢ(0)≠0 for any i∈Γ∗₁ ∪ I₂ ∖{γ_x∗}, there exists u₀≠0 such that f(z∗+u₀ eᵢ)<f(z∗), which togehter with z∗+u₀ eᵢ ∈ F contradicts the optimality of z∗. Similar to the analysis in Case 1, we can obtain that ∇ᵢ f(z∗)=g′ᵢ(0)=0 for any i∈(Γ∗₁ ∖{γ_x∗})∪ I₂. Thus, by Theorem 3.3 we deduce that z∗ is an N^B-stationary point when ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀<t.

Case 3: ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀=t. For any i∈{γ_x∗+1,…,m} ∪Γ∗₂, we have z∗+ueᵢ ∈ F for any u∈ℝ. If g′ᵢ(0)≠0 for any i∈{γₓ+1,…,m} ∪Γ∗₂, there exists u₀≠0 such that f(z∗+u₀ eᵢ)<f(z∗), which together with z∗+u₀ eᵢ ∈ F contradicts the optimality of z∗. Similar to Case 1, we can obtain that ∇ᵢ f(z∗)=g′ᵢ(0)=0 for any i∈{γ_x∗+1,…,m} ∪Γ∗₂. Thus, by Theorem 3.3 we deduce that z∗ is an N^B-stationary point when ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀=t.

Case 4: ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀<t. For any i∈{i∈ I:i>γ_x∗}, we have z∗+ueᵢ ∈ F for any u∈ℝ. If g′ᵢ(0)≠0 for any i∈{i∈ I:i>γ_x∗}, there exists u₀≠0 such that f(z∗+u₀ eᵢ)<f(z∗), which together with z∗+u₀ eᵢ ∈ F contradicts the optimality of z∗. Similar to Case 1, we can obtain that ∇ᵢ f(z∗)=g′ᵢ(0)=0 for any i∈{i∈ I:i>γ_x∗}. Thus, by Theorem 3.3 we conclude that z∗ is an N^B-stationary point when ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀<t.

Combining Case 1 with Case 2, we complete the proof of this theorem. $\Box$

3.1.3 First-order optimality conditions by Clarke tangent and normal cones

Firstly, we need to find out the precise form of Clarke tangent and normal cones of F at a point in F. The following two lemmas can be used to achieve our goal.

Lemma 3.4

[19, Theorem 2.4.5] Let Z=X× Y where X,Y are Banach spaces, and let z=(x,y)∈ C₁ × C₂, where C₁ ⊆ X, C₂ ⊆ Y. Then

T_C₁ × C₂(z)=T_C₁(x)× T_C₂(y) and N_C₁ × C₂(z)=N_C₁(x)× N_C₂(y).

Lemma 3.5

[36, Theorem 2.2] For any y∈ F₂ with Γ₂:=supp(y), the Clarke tangent cone and corresponding normal cone of F₂ at y are given respectively as

T^C_F₂(y)={d∈ℝⁿ: supp(d)⊆Γ₂}=span{eᵢ, i∈Γ₂} , N^C_F₂(y)={d∈ℝⁿ: dᵢ=0, ∀ i∈Γ₂}=span{eᵢ, i∉Γ₂} .

(3.30) (3.31)

To express the Clarke tangent and normal cones of F at a point in F, by Lemmas 3.4 and 3.5, it is sufficient to represent the Clarke tangent and normal cones of F₁ at a point in F₁, which are given as follows.

Theorem 3.6

Let F₁ be defined by (2.2) and Γ₁ be defined by (2.1). Then the Clarke tangent cone and corresponding normal cone of F₁ at x∈ F₁ can be written respectively as

T^C_F₁(x)={d∈ℝᵐ: supp(d)⊆Γ₁ ∖{γₓ}} , N^C_F₁(x)={d∈ℝᵐ: dᵢ=0, ∀ i∈Γ₁ ∖{γₓ}} .

(3.32) (3.33)

Proof. If (3.32) holds, then by the definition of Clarke normal cone (see Definition 2.2), it is easy to see that (3.33) holds. Thus, it is enough to show that (3.32) holds. Firstly, we prove that

T^C_F₁(x)⊆{d∈ℝᵐ: supp(d)⊆Γ₁ ∖{γₓ}} .

(3.34)

For any d∈ T^C_F₁(x), we will show d∈{d∈ℝᵐ: supp(d)⊆Γ₁ ∖{γₓ}}. For this purpose, we only need to prove supp(d)⊆Γ₁ and d_γₓ=0. Since d∈ T^C_F₁(x), it follows from the definition of T^C_F₁(x) that for any {xᵏ} ⊂ F₁ with limₖ→∞ xᵏ=x and {λₖ} ⊂ℝ₊ with limₖ→∞ λₖ=0, there exists {dᵏ} with limₖ→∞ dᵏ=d such that xᵏ+λₖ dᵏ ∈ F₁ for any k∈ℕ.

• We prove supp(d)⊆Γ₁. Suppose that supp (d)⊆_1. Then there exists i₀ ∈supp(d) such that i₀∉Γ₁, i.e., x_i₀=0 and d_i₀≠0. Since limₖ→∞ dᵏ=d, one must have dᵏ_i₀→ d_i₀. Then there exists k₀ ∈ℕ such that d_i₀≠0 for all k≥k₀. Choose {xᵏ} ⊂ F₁ such that limₖ→∞ xᵏ=x and supp(xᵏ)=Γ₁ ∪Γ₁ᵏ with |Γ₁ ∪Γᵏ₁|=s, where Γ₁ᵏ ∩Γ₁=∅ and i₀∉Γ₁ᵏ. Trivially, Γ₁ᵏ=∅ if |Γ₁|=s. Let λₖ be selected as

λ_k=min_i∈_1∪_1^k|x^k_i||d^k_i|+k,

then one has λₖ>0 for any k∈ℕ and λₖ → 0. For any i∈Γ₁ ∪Γᵏ₁, we have

|xᵏᵢ+λₖ dᵏᵢ|≥|xᵏᵢ|-λₖ|dᵏᵢ|>0.

Since λₖ>0, xᵏ_i₀=0 and dᵏ_i₀≠0 for k≥k₀, one must have xᵏ_i₀+λₖ dᵏ_i₀≠0 for k≥k₀. This, together i₀∉Γ₁ ∪Γ₁ᵏ and |Γ₁ ∪Γᵏ₁|=s, implies that ‖ xᵏ+λₖ dᵏ ‖ ₀>s for k≥k₀. This contradicts xᵏ+λₖ dᵏ ∈ F₁. Thus supp(d)⊆Γ₁.

• We prove d_γₓ=0. Suppose that d_γₓ≠0. It follows that for any {dᵏ} with limₖ→∞ dᵏ=d, there exists k₁ ∈ℕ such that dᵏ_γₓ≠0 for any k>k₁. Set λₖ=(1)/(|dᵏ_γₓ|+k) for all k>k₁, then one has λₖ>0 for all k>k₁ and limₖ→∞ λₖ=0. For any j<γₓ, one must have j∉Γ₁. It follows that dⱼ=0 by supp(d)⊆Γ₁. Thus, limₖ→∞ dᵏⱼ=0. Then for ε<1, there exists k₂ ∈ℕ such that λₖ dᵏⱼ<ε for any k>k₁ and j<γₓ. By Lemma 3.1, there exists k₀ ∈ℕ such that xᵏⱼ=0 for any k>k₀ and j<γₓ and xᵏ_γₓ=1. Let K=max{k₀,k₁,k₂}, for any k>K,j<γₓ, one has (xᵏ+λₖ dᵏ)ⱼ<ε,

(xᵏ+λₖ dᵏ)_γₓ=1+(dᵏ_γₓ)/(|dᵏ_γₓ|+k)≠0 and(xᵏ+λₖ dᵏ)_γₓ=1+(dᵏ_γₓ)/(|dᵏ_γₓ|+k)≠1,

which contradicts xᵏ+λₖ dᵏ ∈ F₁. So d_γₓ=0.

Thus (3.34) holds. We now prove that

{d∈ℝᵐ: supp(d)⊆Γ₁ ∖{γₓ}} ⊆ T^C_F₁(x).

(3.35)

To this goal, for any d∈{d∈ℝᵐ: supp(d)⊆Γ₁ ∖{γₓ}}, we need to show d∈ T^C_F₁(x). For any {xᵏ} ⊂ F₁ such that limₖ→∞ xᵏ=x and any {λₖ} ⊂ℝ₊ such that limₖ→∞ λₖ=0, it follows that there exists k₀ ∈ℕ such that Γ₁ ⊆supp(xᵏ) and xᵏ_γₓ=1 for any k≥k₀. Moreover, we choose a sequence {dᵏ} defined as

dᵏ:={(0, if k=1,2,…,k₀,; xᵏ-x+d, if k=k₀+1,k₀+2,…,).

(3.36)

which satisfies that limₖ→∞ dᵏ=d by limₖ→∞ xᵏ=x. For k<k₀, we have

dᵏⱼ=xⱼᵏ-xⱼ+dⱼ=0-0+0, ∀ j<γₓ, dᵏ_γₓ=xᵏ_γₓ-x_γₓ+d_γₓ=1-1+0=0, supp(dᵏ) ⊆supp(xᵏ)∪supp(x)∪supp(d)=supp(xᵏ).

So we have ‖ xᵏ+λₖ dᵏ ‖ ₀≤s and xᵏ_γₓ+λₖ dᵏ_γₓ=1 for any k>k₀. These, together with xᵏ+λₖ dᵏ=xᵏ ∈ F₁ for any k≤k₀, imply that xᵏ+λₖ dᵏ ∈ F₁ for any k∈ℕ. Therefore, d∈ T^C_F₁(x), and hence (3.35) holds. Thus (3.32) holds. The proof is complete. $\Box$

Now, we provide the precise forms of the Clarke tangent cone and Clarke normal cone of F at a point in F.

Theorem 3.7

For any z=(x,y)∈ F with F being defined by (2.4), the Clarke tangent cone and corresponding normal cone of F at z can be written as

T^C_F(z)={d∈ℝᵐ⁺ⁿ: supp(d)⊆Γ∖{γₓ}} , N^C_F(z)={d∈ℝᵐ⁺ⁿ: dᵢ=0, ∀ i∈Γ∖{γₓ}} ,

(3.37) (3.38)

respectively, where Γ is defined by (2.1).

This result follows immediately from Theorem 3.6 and Lemmas 3.4 and 3.5. Next, we provide a sufficient and necessary condition for N^C-stationary and T^C-stationary points.

Theorem 3.8

Let z∗=(x∗,y∗)∈ F, where F is defined by (2.4), and let Γ∗ be defined by (3.25). Then (i) z∗ is an N^C-stationary point if and only if ∇ f(z∗)∈ℝᵐ⁺ⁿ satisfies

∇ᵢ f(z∗)=0, ∀ i∈Γ∗ ∖{γ_x∗} .

(3.39) (ii) z∗ is a T^C-stationary point if and only if (3.39) holds.

Proof. Item (i) follows directly from (3.38). We now show Item (ii). By Definition 3.2, we need to show that ∇^C_F f(z∗)=0 if and only if (3.39) holds.

(⇒) Suppose there exists i₀ ∈Γ∖{γ_x∗} such that ∇_i₀f(z∗)≠0. Pick d̅=(d̅₁,d̅₂)∈ℝᵐ⁺ⁿ such that d̅_i₀=-∇_i₀f(z∗) and other entries are zero. Since supp(d̅)⊆Γ∗ ∖{γ_x∗}, it follows from (3.37) that d̅∈ T^C_F(z∗). Then, by Definition 3.2, we have

‖ ∇_F^C f(z∗)+∇ f(z∗)‖ ²≤‖ d̅+∇ f(z∗)‖ ².

Since ∇^C_F f(z∗)=0, the above inequality is equivalent to (3.27), which further implies (∇_i₀f(z∗))²≤0. This contradicts the assumption ∇_i₀f(z∗)≠0.

($\Leftarrow$) Suppose there exists d̅∈ T^C_F(z∗) with d̅≠0 such that (3.28) holds. It follows from (3.37) that supp(d̅)⊆(Γ∗ ∖{γ_x∗}). Thus (3.28) is equivalent to

Σ_i∈Γ∗ ∖{γ_x∗} (d̅ᵢ+∇ᵢ f(z∗))²≤Σ_i∈Γ∗ ∖{γ_x∗} (∇ᵢ f(z∗))².

This, together with (3.39), implies that Σ_i∈Γ∗ ∖{γ_x∗} (d̅ᵢ)²≤0, a contradiction. $\Box$

By Theorems 3.3 and 3.4, we immediately obtain the following Corollary.

Corollary 3.2

Let z∗=(x∗,y∗)∈ F, where F is defined by (2.4). Then z∗ is an N^C-stationary point of (1.10) if and only if it is a T^C-stationary point of (1.10).

We now discuss the relation between N^B-stationary point and N^C-stationary point.

Theorem 3.9

Let z∗=(x∗,y∗)∈ F, where F is defined by (2.4). If z∗ is an N^B-stationary point of (1.10), then z∗ is also an N^C-stationary point.

Proof. Let Γ∗,Γ∗₁,Γ∗₂ be defined as in (3.25). It is sufficient to consider the following four cases:

• ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀=t. For this case, the result can be obtained directly from (3.24) and (3.39).
• ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀=t. Since Γ∗₁ ∖{γ_x∗} ⊆{γ_x∗+1,…,m}, it follows that ∇ᵢ f(z∗)=0 for any i∈Γ∗₁ ∖{γ_x∗} if ∇ᵢ f(z∗)=0 for any i∈{γ_x∗+1,…,m}. Thus it follows from (3.19) and (3.38) that z∗ is an N^C-stationary point if z∗ is an N^B-stationary point.
• ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀<t. Since Γ∗₁ ∖{γ_x∗} ⊆(Γ∗₁ ∪ I₂)∖{γ_x∗}, similar to the analysis of Case (ii), it follows from (3.19) and (3.38) that z∗ is an N^C-stationary point if z∗ is an N^B-stationary point.
• ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀<t. Since Γ∗₁ ∖{γ_x∗} ⊆{i∈ I: i>γ_x∗}, it follows from (3.19) and (3.38) that z∗ is an N^C-stationary point if z∗ is an N^B-stationary point.

Thus an NB-stationary point must be an NC-stationary point. $\Box$

Corollary 3.3

If |Γ∗₁|=s and |Γ∗₂|=t, then the N^B-stationary point and T^B-stationary point are equivalent to the N^C-stationary point and T^C-stationary point, respectively.

Finally, we discuss the relation between N^C-stationary point (T^C-stationary point) of (1.10) and the optimal solution of (1.10). The following result is implied directly from Theorems 3.5 and 3.9.

Theorem 3.10

z∗=(x∗,y∗) is an optimal solution of (1.10), then z∗ is an N^C-stationary point, and z∗ is also a T^C-stationary point.

3.2 Coordinate-Wise minimum

Motivated by the concept of coordinate-wise minimum (CW minimum) for the problem (1.2) proposed in [7], we extend this notion to the problem (1.10). Because of the equality constraint e^→ p_γₓx=1, the definition is appropriately modified to fit the current framework.

Definition 3.3

Let F be defined by (2.4), then z∗ is called a CW minimum of (1.10) if and only if one of the following conditions is satisfied:

• When ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀=t, for any index pair (i,j)∈ I₁ × I₁ or I₂ × I₂ with i∈Γ∗ ∖{γ_x∗} and j>γₓ, one has

f(z^ )=min_u∈ R f(z^ -z^ _ie_i+ue_j).

(3.40)

• When ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀<t, for any i>γ_x∗, one has

f(z^ )=min_u∈ R f(z^ +ue_i).

(3.41)

• When ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀<t, for any i∈ I₂, one has (3.41) holds, and for any (i,j)∈ I₁ × I₁ with i∈Γ∗₁ ∖{γ_x∗} and j>γ_x∗, one has (3.40) holds.
• When ‖ x∗ ‖ ₀<s and ‖ y*‖ ₀=t, for any i∈ I₁ with i>γ_x∗, one has (3.41) holds, and for any i∈Γ∗₂ and j∈ I₂, one has (3.40) holds.

Based on the above definition, it follows that any optimal solution of the problem must be a CW minimum, as stated in the following theorem.

Theorem 3.11

Let z∗ be an optimal solution of (1.10), then z∗ is a CW minimum of (1.10).

Proof. It follows directly from the optimality of z∗. $\Box$

It can be observed that a CW minimum is also an N^B-stationary point, which is stated in the following theorem.

Theorem 3.12

Let z∗=(x∗,y∗)∈ F, where F is defined by (2.4). If z∗ is a CW minimum of (1.10), then ∇ f(z∗)∈ℝᵐ⁺ⁿ satisfies (3.24), and hence, z∗ is an N^B-stationary point.

Proof. Assume that z∗ ∈ F is a CW minimum of (1.10). We first show that ∇ f(z∗)∈ℝᵐ⁺ⁿ satisfies (3.24), which is divided into the following four cases. (i) ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀=t. By Definition 3.3, it follows that (3.40) is satisfied for any index pair (i,j)∈ I₁ × I₁ or I₂ × I₂ with i∈Γ∗ ∖{γ_x∗} and j>γₓ, then we have

f(z^ )=min_u∈ R f(z^ -z^ _ie_i+ue_i),

which becomes

f(z^ )=min_v∈ R f(z^ +ve_i),

(3.42)

by denoting v:=u-z∗ᵢ. It follows from (3.42) that v=0 is an optimal solution of the problem min_v∈ R h_i(v)=f(z^ +ve_i). By the optimality condition hᵢ′(0)=0 for any i∈Γ∗ ∖{γ_x∗}, we conclude that for any CW minimum z∗ of (1.10) with ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀=t, we have

∇ᵢ f(z∗)=0, ∀ i∈Γ∗ ∖{γ_x∗} ,

which implies that case ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀=t in (3.24) is satisfied. That is, z∗ is an N^B-stationary point in this case. (ii) ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀<t. It follows from Definition 3.3 that (3.42) is already satisfied for any i>γ_x∗. By the same analysis in (i), we can obtain that

∇ᵢ f(z∗)=0, ∀ i>γ_x∗,

which implies that case ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀<t in (3.24) is satisfied. That is, z∗ is an N^B-stationary point in this case. (iii) ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀<t. By Definition 3.3, one has (3.40) holds for any (i,j)∈ I₁ × I₁ with i∈Γ∗₁ ∖{γ_x∗} and j>γ_x∗. By similar analysis in (i), we can obtain that

∇ᵢ f(z∗)=0, ∀ i∈Γ∗₁ ∖{γ_x∗} .

(3.43)

By Definition 3.3, one has (3.41) holds for any i∈ I₂. Then by similar analysis in (ii), we have ∇ᵢ f(z∗)=0 for any i∈ I₂, which implies that case ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀<t in (3.24) is satisfied. That is, z∗ is an N^B-stationary point in this case. (iv) ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀=t. Since for any i∈ I₁ with i>γ_x∗, one has (3.41) holds, and for any i∈Γ∗₂ and j∈ I₂, one has (3.40) holds. Analogous to (iii), we can conclude that ∇ᵢ f(z∗)=0 for any i∈{γ_x∗+1,…,m} ∪Γ∗₂, which implies that case ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀=t in (3.24) is satisfied. That is, z∗ is an N^B-stationary point in this case.

Combining the above cases (i)-(iv), we obtain that ∇ f(z∗)∈ℝᵐ⁺ⁿ satisfies (3.24). Furthermore, by Theorem 3.3 we obtain that z∗ is an N^B-stationary point. $\Box$

Note that an N^B-stationay point may not be a CW minimum, we present the following example to illustrate it.

Example 3.3

Consider the problem (1.10) with b=(5,0)^→ p, tensor A=(a_j_1j_2j_3)∈ R ^2× 3× 3, where a₁₁₁=1,a₁₁₂=1,a₁₁₃=3,a₁₂₁=1,a₁₂₂=1,a₁₃₃=1,a₂₁₁=1,a₂₁₃=-1,a₂₂₂=1,a₂₃₁=1 and all other entries are zero. Then for any z=(x,y)∈ℝ³ ×ℝ³, the objective function in (1.10) is defined by f(z):=(1)/(2)‖ Axy-b‖ ^2 with

Axy-b=[ x_1y_1+x_1y_2+3x_1y_3+x_2y_1+x_2y_2+x_3y_3-5 x_1y_1-x_1y_3+x_2y_2+x_3y_1 ].

Let s=t=2 and z̅=(1,1,0,1,1,0)^→ p. We have ‖ x̅‖ ₀=s, ‖ y̅‖ ₀=t, γₓ̅=1, Γ̅={1,2,4,5}, f(z̅)=5/2 and ∇ f(z̅)=(0,0,2,0,0,-5)^→ p. It is easy to see that ∇ᵢ f(z̅)=0 for i∈Γ̅∖{γₓ̅}. Thus, by Theorem 3.3 we obtain that that z̅ is an N^B-stationary point. However, if we define z∗:=z̅-e₅+e₆=(1,1,0,1,0,1)^→ p, then we have f(z∗)=0. Obviously, f(z̅)>f(z∗), which implies that (3.40) is not satisfied at z̅. In another word, z̅ is not a CW minimum.

3.3 L-like stationary point

Recall that for the single-block variable sparse optimization problem (1.2), a vector x∗ ∈ Cₛ:={x∈ℝᵐ: ‖ x‖ ₀≤s} is said to be an L-stationary point if and only if x∗ ∈P_Cₛ(x∗-∇ f(x∗)/L) for some L>0, where P_Cₛ(x):=argmin_u∈ Cₛ‖ u-x‖ (see, e.g., [7]). Since the problem (1.10) has a special constraint e_γₓ^→ p x=1, it is difficult for us to characterize the L-stationary point for this problem by using the projection operator P_F, where F is defined by (2.4). In this section, similar to the idea used in the L-stationary point, we introduce and discuss the concept of an L-like stationary point. For this purpose, we introduce the following concept of like-projection operator.

Before introducing this new concept, let us first give the definition below.

Definition 3.4

Let ψ_z:ℝᵐ⁺ⁿ →ℝᵐ⁺ⁿ be a mapping defined as follows: given z=(x,y)∈ℝᵐ⁺ⁿ, for any u∈ℝᵐ⁺ⁿ,

• if x=0, ψ_z(u):=u;
• if x≠0,

(ψ_z(u))ᵢ:={(xᵧᵤ^zuᵢ, if i∈ I₁,; (uᵢ)/(xᵧᵤ^z), if i∈ I₂,).

where γᵤ^z is given by

γ_u^z:=min i∈ I_1:u_i≠ 0,z_i≠ 0 .

(3.44)

By using the mapping ψ_z(u) above, we can now define the like-projection.

Definition 3.5

For any z=(x,y)∈ℝᵐ⁺ⁿ, let F be defined by (2.4). The like-projection of z onto F is defined by

P _F(z)=_u∈ F‖ _z(u)-z‖ ^2.

Remark 3.1

The like-projection operator P̅_F(·) introduced in Definition 3.5 is determined by the set F defined by (2.4), it is different from the classical projection operator P_F(·) (i.e., P_F(z):=argminᵤ∈ F ‖ u-z‖ for z∈ℝᵐ⁺ⁿ), but when z_γᵤ^z=1 or xᵢ=0 for all i∈ I₁, the like-projection of z onto F coincides with the projection of z onto F.

It is easy to find the projection of an arbitrary point x∈ℝᵐ onto the sparse set Cₛ={x∈ℝᵐ: ‖ x‖ ₀≤s}. A natural question is how to calculate the like-projection of a point z∈ℝᵐ⁺ⁿ onto the set F defined by (2.4). The following lemma addresses this question.

Lemma 3.6

For any z=(x,y)∈ℝᵐ⁺ⁿ, let q₁,q₂ be the smallest integers and r₁,r₂ be the largest integers such that

M_q₁(|x|)=M_q₁+1(|x|)=⋯=Mₛ(|x|)=⋯=M_r₁(|x|),

M_q₂(|y|)=M_q₂+1(|y|)=⋯=Mₜ(|y|)=⋯=M_r₂(|y|),

and Λ₁ and Λ₂ are defined as

Λ₁:={i∈ I₁:|xᵢ|=Mₛ(|x|)} , Λ₂:={i∈ I₂:|zᵢ|=Mₜ(|y|)} .

If u∗ ∈P̅_F(z), then there exist sets _1⊆_1 and _2⊆_2 with |_1|=s-q_1+1 and |_2|=t-q_2+1 such that one of the following holds:

• x≠0 and u∗ ∈ℝᵐ⁺ⁿ is defined by

uᵢ∗={(zᵢxᵧₘin^, if i∈₁:=i∈ I₁:|zᵢ|>Mₛ(|x|) ₁,; xᵧₘin^ zᵢ, if i∈₂:=i∈ I₂:|zᵢ|>Mₜ(|y|) ₂,; 0, otherwise,).

(3.45)

where γ_min^ =min i∈_1:x_i≠ 0.

• x=0 and u∗ ∈ℝᵐ⁺ⁿ is defined by

u_i_0^ = 1 for some i_0∈_1=I_1, u_i^ = 0 if i∈ I_1∖ i_0 , z_i if i∈_2:= i∈ I_2:|z_i|> M_t(|y|) _2, 0 if i∈ I_2∖_2. .

(3.51)

Conversely, for any _1⊆_1 with |_1|=s-q_1+1 and _2⊆_2 with |_2|=t-q_2+1, if u∗ is given by (3.45) for x≠0 or u∗ is given by (3.51) for x=0, then u^ ∈ P _F(z).

Proof. (⇒) We first show that either (3.45) or (3.51) holds if u∗ ∈P̅_F(z). It suffices to consider the following two cases.

Case 1: z∈ℝᵐ⁺ⁿ with x≠0. In this case, we show that (3.45) holds if u∗ ∈P̅_F(z). For any u=(u¹,u²)∈ F, it follows from the definition of F that ‖ u¹ ‖ ₀≤s and ‖ u² ‖ ₀≤t, and hence, there exist sets _1⊆_1 and _2⊆_2 with |_1|=s-q_1+1 and |_2|=t-q_2+1 such that

_1:= i∈ I_1:|z_i|> M_s(|x|) _1 and _2:= i∈ I_2:|z_i|> M_t(|y|) _2

satisfy supp(u¹)=supp({zᵢ:i∈Ω₁}) and supp(u²)=supp({zᵢ:i∈Ω₂}). It follows from Definition 3.4 that ψ_z(u)=(ψ_z¹(u),ψ_z²(u²)) with ψ_z¹(u)=x_γᵤ^zu¹ and ψ_z²(u)=(u²)/(x_γᵤ^z), where γᵤ^z is defined as (3.44). Thus,

‖ ψ_z(u)-z‖ ²=Σ_i∈ I₁|(ψ_z¹(u))ᵢ-zᵢ|²+Σ_j∈ I₂|(ψ_z²(u))ⱼ-zⱼ|²=Σ_i∈Ω₁|x_γᵤ^zu¹ᵢ-zᵢ|²+Σ_j∈Ω₂|u²ⱼ/x_γᵤ^z-zⱼ|² +Σ_i∈ I₁ ∖Ω₁|zᵢ|²+Σ_j∈ I₂ ∖Ω₂|zⱼ|².

(3.52)

Furthermore, we have

min_u∈ F‖ _z(u)-z‖ ^2=min_u∈ F Σ_i∈_1|x_γ_u^zu^1_i-z_i|^2+Σ_j∈_2|u^2_j/x_γ_u^z-z_j|^2 .

(3.53)

Since u∗ ∈P̅_F(z)=argminᵤ∈ F ‖ ψ_z(u)-z‖ ², it follows from (3.53) that

uᵢ∗={((zᵢ)/(xᵧᵤ∗^z), if i∈Ω₁,; xᵧᵤ∗^zzᵢ, if i∈Ω₂,; 0, otherwise.).

(3.54)

From (3.54), it is easy to see that for any i∈ I, uᵢ∗≠0 if zᵢ≠0, and hence, γ_min^ =γ_u^ ^z where γ_min^ =min i∈_1:x_i≠ 0. Thus, (3.54) is nothing but (3.45). So (3.45) holds for this case.

Case 2: z∈ℝᵐ⁺ⁿ with x=0. In this case, we show that (3.51) holds when u∗ ∈P̅_F(z). For any u=(u¹,u²)∈ F, it follows from the definition of F that there exist i_0∈_1=I_1 such that u_i₀¹=1 and a set _2⊆_2 with |_2|=t-q_2+1 such that _2:= i∈ I_2:|z_i|> M_t(|y|) ∪_2 satisfies supp(u²)=supp({zᵢ:i∈Ω₂}). It follows from Definition 3.4 that ψ_z(u)=u. Thus, in a manner similar to (3.52), one has

‖ ψ_z(u)-z‖ ²=1+Σ_i∈ I₁ ∖{i₀} |u¹ᵢ-zᵢ|²+Σ_j∈Ω₂|u²ⱼ-zⱼ|²+Σ_j∈ I₂ ∖Ω₂|zⱼ|².

Furthermore, we have

min_u∈ F‖ _z(u)-z‖ ^2=min_u∈ F Σ_i∈ I_1∖ i_0 |u^1_i-z_i|^2+Σ_j∈_2|u^2_j-z_j|^2 .

(3.55)

Since u∗ ∈P̅_F(z)=argminᵤ∈ F ‖ ψ_z(u)-z‖ ², it follows from (3.55) and u_i₀¹∗=1 that u_i₀∗=1 for some i_0∈_1=I_1, and

uᵢ∗={(0, if i∈ I₁ ∖i₀ ,; zᵢ, if i∈₂:=i∈ I₂:|zᵢ|>Mₜ(|y|) ₂,; 0, if i∈ I₂ ∖Ω₂.).

Thus (3.51) holds for this case.

($\Leftarrow$) We now show that u∗ ∈P̅_F(z) when (3.45) or (3.51) holds. It is also sufficient to consider two cases.

Case 1: z∈ℝᵐ⁺ⁿ with x≠0. In this case, let u∗=(u¹∗,u²∗)∈ℝᵐ ×ℝⁿ be defined by (3.45), then γ^z_u^ =min i∈_1: x_i≠ 0 =γ^ _min, where γ_u∗^z is defined as (3.44). It follows from Definition 3.4 that ψ_z(u∗)=(ψ_z¹(u∗),ψ_z²(u∗)) with _z^1(u^ )=x_γ_min^ u^1 and _z^2(u^ )=u^2 x_γ_min^. Thus,

‖ _z(u^ )-z‖ ^2 = Σ_i∈ I_1|u^ _ix_γ_min^ -z_i|^2+Σ_j∈ I_2|u^ _j/x_γ_min^ -z_j|^2 = Σ_i∈_1|u^ _ix_γ_min^ -z_i|^2+Σ_j∈_2|u^ _j/x_γ_min^ -z_j|^2+Σ_i∈ I_1∖_1|z_i|^2+Σ_j∈ I_2∖_2|z_j|^2 = Σ_i∈_1|z_i-z_i|^2+Σ_j∈_2|z_j-z_j|^2+Σ_i∈ I_1∖_1|z_i|^2+Σ_j∈ I_2∖_2|z_j|^2 = Σ_i∈ I_1∖_1|z_i|^2+Σ_j∈ I_2∖_2|z_j|^2

=Σᵢ₌₁ᵐ⁻ˢ (Mₛ₊ᵢ(|x|))²+Σⱼ₌₁ⁿ⁻ᵗ (Mₜ₊ⱼ(|y|))²,

(3.56)

where the third equality follows from (3.45). For any u=(u¹,u²)∈ F, we must have ‖ u¹ ‖ ₀≤s and ‖ u² ‖ ₀≤t, which imply that I₁ ∖supp(u¹)≥m-s and I₂ ∖supp(u²)≥n-t. Moreover, it follows from Definition 3.4 that ψ_z(u)=(ψ_z¹(u),ψ_z²(u)) with ψ_z¹(u)=x_γᵤ^zu¹ and ψ_z²(u)=(u²)/(x_γᵤ^z), where γᵤ^z is defined by (3.44). Thus,

‖ ψ_z(u)-z‖ ²=Σ_i∈ I₁|uᵢ x_γᵤ^z-zᵢ|²+Σ_j∈ I₂|uⱼ/x_γᵤ^z-zⱼ|²=Σ_i∈supp(u₁)|uᵢ x_γᵤ^z-zᵢ|²+Σ_j∈supp(u₂)|uⱼ/x_γᵤ^z-zᵢ|² +Σ_i∈ I₁ ∖supp(u₁)|zᵢ|²+Σ_j∈ I₂ ∖supp(u₂)|zⱼ|²≥Σ_i∈ I₁ ∖supp(u₁)|zᵢ|²+Σ_j∈ I₂ ∖supp(u₂)|zⱼ|²

≥Σᵢ₌₁ᵐ⁻ˢ (Mₛ₊ᵢ(|x|))²+Σⱼ₌₁ⁿ⁻ᵗ (Mₜ₊ⱼ(|y|))²=‖ ψ_z(u∗)-z‖ ²,

(3.57)

where the last equality follows from (3.56). Thus, by the definition of like-projection (i.e., Definition 3.5), we have u^ ∈ P _F(z).

Case 2: z∈ℝᵐ⁺ⁿ with x=0. In this case, let u∗=(u¹∗,u²∗) be defined by (3.51), then it follows from the definition of ψ_z that ψ_z(u∗)=(ψ_z¹(u∗),ψ_z²(u∗)) with ψ_z¹(u∗)=u¹∗ and ψ_z²(u∗)=u²∗. Thus, similar to (3.56), it follows that

‖ ψ_z(u∗)-z‖ ²=1+Σⱼ₌₁ⁿ⁻ᵗ (Mₜ₊ⱼ(|y|))².

For any u=(u¹,u²)∈ F, we must have ‖ u¹ ‖ ₀≤s and ‖ u² ‖ ₀≤t, which imply that I₁ ∖supp(u¹)≥n-s and I₂ ∖supp(u²)≥n-t. Moreover, it follows from Definition 3.4 that ψ_z(u)=(ψ_z¹(u),ψ_z²(u)) with ψ_z¹(u)=u¹ and ψ_z²(u)=u². Thus, in a manner analogous to (3.57), one obtains

$$\Vert \psi_{z}(u)-z\Vert ^{2} \geq |1-0|^{2}+\sum_{j\in I_{2}\setminus{\mathrm{supp}}(u_{2})}|z_{j}|^{2}\qquad {} \geq 1+\sum_{j=1}^{n-t}\left(M_{t+j}(|y|)\right)^{2}\qquad {} = \Vert \psi_{z}(u^{\ast })-z\Vert ^{2},$$

where the first inequality follows from u∈ F and x=0. Thus, by the definition of like-projection (i.e., Definition 3.5), we have u^ ∈ P _F(z). $\Box$

The following example reveals the difference between projection and like-projection.

Example 3.4

Suppose that F is defined by (2.4), where m=3, n=3, s=2, t=2.

• Given z=(0,0,3,3,-4,2)^→ p. Then x=(0,0,3)^→ p and y=(3,-4,2)^→ p. In this case, it is easy to check that

$$\mathbf{P}_{F}(z)=\left\lbrace (1,0,3,3,-4,0)^{\to p},(0,1,3,3,-4,0)^{\to p}\right\rbrace ,$$ $${\bar{\mathbf{P}}}_{F}(z)=\lbrace (0,0,1,9,-12,0)^{\to p}\rbrace .$$

• Given z=(0,0,1,3,-4,2)^→ p. Then x=(0,0,1)^→ p and y=(3,-4,2)^→ p. In this case, it is easy to check that

$$\mathbf{P}_{F}(z)={\bar{\mathbf{P}}}_{F}(z)=\lbrace (0,0,1,3,-4,0)^{\to p}\rbrace .$$

• Given z=(0,0,0,3,-4,2)^→ p. Then x=(0,0,0)^→ p and y=(3,-4,2)^→ p. In this case, it is easy to check that

$${\bar{\mathbf{P}}}_{F}(z)=\mathbf{P}_{F}(z)=\left\lbrace (1,0,0,0,3,-4,0)^{\to p},(0,1,0,0,3,-4,0)^{\to p},(0,0,1,0,3,-4,0)^{\to p}\right\rbrace .$$

Now, we introduce the definition of an L-like stationary point of (1.10).

Definition 3.6

Let F be defined by (2.4) and let L>0 be a given constant. z∗=(x∗,y∗)∈ F is an L-like stationary point of (1.10) if and only if

$$z^{\ast }\in{\bar{\mathbf{P}}}_{F}(z^{\ast }-\nabla f(z^{\ast })/L) and \nabla_{\gamma_{x^{\ast }}}f(z^{\ast })=0,$$

where γ_x∗ is the first index of the nonzero entries of z∗ and P̅_F is defined in Definition 3.5.

Remark 3.2

It is worth pointing out the difference between the L-stationary point and the L-like stationary point.

• An L-like stationary point of (1.10) must be an L-stationary point of (1.10). In fact, if z∗ is an L-like stationary point of (1.10), then it follows from Definition 3.6 that z∗ ∈ F and ∇_γ_x∗f(z∗)=0. Since z∗ ∈ F, we have z_γ_x∗∗=1. This together with ∇_γ_x∗f(z∗)=0 implies that (z∗-∇ f(z∗)/L)_γ_x∗=1. In this case, it follows from Remark 3.1 that P̅_F(z∗-∇ f(z∗)/L)=P_F(z∗-∇ f(z∗)/L). Thus z∗ is an L-stationary point of (1.10).
• An L-stationary point of (1.10) need not be an L-like stationary point of the problem. Such a result holds since the projection of a point z∈ℝᵐ⁺ⁿ onto F does not need to be a like-projection of z onto F. In addition, if z∗ is an L-stationary point of (1.10) and (z∗-∇ f(z∗)/L)_γ_x∗=1, then z∗ is an L-like stationary point of the problem. In fact, on one hand, it follows from Remark 3.1 that P̅_F(z∗-∇ f(z∗)/L)=P_F(z∗-∇ f(z∗)/L), and on the other hand, by (z∗-∇ f(z∗)/L)_γ_x∗=1 and z_γ_x∗∗=1, it follows that ∇_γ_x∗f(z∗)=0. Thus, by Definition 3.6, z∗ is an L-like stationary point of the problem.

Similar to the single-block variable case [7], if z∗ is an L-like stationary point of (1.10), then the entries of z∗ can provide upper bounds for entries of |∇ f(z∗)|. We discuss this fact in the next theorem.

Theorem 3.13

For z∗=(x∗,y∗)∈ F, let Γ∗,Γ₁∗,Γ₂∗ be given as (3.25) and denote γ_x∗ by the index of the first nonzero entry of z∗. Then z∗ is an L-like stationary point of (1.10) if and only if ∇ f(z∗)∈ℝᵐ⁺ⁿ is given by

$$|\nabla_{i}f(z^{\ast })|\left\lbrace \begin{array}{ll}=0& \mathrm{if} i\in\Gamma^{\ast },\\ \leq LM_{s}(|x^{\ast }|)& \mathrm{if} i\in I_{1}\setminus\Gamma_{1}^{\ast },\\ \leq LM_{t}(|y^{\ast }|)& \mathrm{if} i\in I_{2}\setminus\Gamma_{2}^{\ast },\end{array}\right.$$

(3.58)

where L is given as in Definition 3.6.

Proof. (⇒) Since z∗ is an L-like stationary point of (1.10), it follows from Definition 3.6 that z∗ ∈P̅_F(z∗-∇ f(z∗)/L) and ∇_γ_x∗f(z∗)=0. Next, we show that (3.58) holds. Denote

$$\Lambda_{1}^{\ast }:=\lbrace i\in I_{1}:|(z^{\ast }-\nabla f(z^{\ast })/L)_{i}|=M_{s}(|x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L|)\rbrace ,$$ $$\Lambda_{2}^{\ast }:=\lbrace i\in I_{2}:|(z^{\ast }-\nabla f(z^{\ast })/L)_{i}|=M_{t}(|y^{\ast }-\nabla_{I_{2}}f(z^{\ast })/L|)\rbrace .$$

Since z∗ ∈P̅_F(z∗-∇ f(z∗)/L), we have x∗≠0. Thus, it follows from (3.45) that there exist _1^ ⊆_1^ and _2^ ⊆_2^ such that

$$z_{i}^{\ast }=\left\lbrace \begin{array}{ll}\frac{(z^{\ast }-\nabla f(z^{\ast })/L)_{i}}{(z^{\ast }-\nabla f(z^{\ast })/L)_{\gamma_{\min}^{\ast }}}& \mathrm{if}\;i\in\Omega_{1}^{\ast },\\ (z^{\ast }-\nabla f(z^{\ast })/L)_{\gamma_{\min}^{\ast }}(z^{\ast }-\nabla f(z^{\ast })/L)_{i}& \mathrm{if}\;i\in\Omega_{2}^{\ast },\\ 0& \mathrm{otherwise},\end{array}\right.$$

(3.59)

where

$$\left\lbrace \begin{array}{rcl}\Omega_{1}^{\ast }&:=&\lbrace i\in I_{1}:|(z^{\ast }-\nabla f(z^{\ast })/L)_{i}|\gt M_{s}(|x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L|)\rbrace \bigcup\Upsilon_{1}^{\ast },\\ \\ \Omega_{2}^{\ast }&:=&\lbrace i\in I_{2}:|(z^{\ast }-\nabla f(z^{\ast })/L)_{i}|\gt M_{t}(|y^{\ast }-\nabla_{I_{2}}f(z^{\ast })/L|)\rbrace \bigcup\Upsilon_{2}^{\ast }\end{array}\right.$$

(3.60)

with |Ω∗₁|=s and |Ω₂∗|=t, and

$$\gamma_{\min}^{\ast }:=\min \mathrm{supp}(\lbrace (z^{\ast }-\nabla f(z^{\ast })/L)_{i}:i\in\Omega_{1}^{\ast }\rbrace ).$$

(3.61)

Note that (3.59) is well-defined. In fact, since z∗ ∈ F, we have z∗_γ_x∗=1, which together with ∇_γ_x∗f(z∗)=0 implies that (z∗-∇ f(z∗)/L)_γ_x∗=1. Thus supp({(z∗-∇ f(z∗)/L)ᵢ:i∈Ω₁∗}) is non-empty, and hence (z^ - f(z^ )/L)_γ_min^ ≠ 0. So (3.59) is well-defined. Moreover, it is easy to see from (3.59) and (3.60) that supp(x∗)=supp({(z∗-∇ f(z∗)/L)ᵢ:i∈Ω₁∗}) and supp(y∗)=supp({(z∗-∇ f(z∗)/L)ᵢ:i∈Ω₂∗}). Thus, γ_x^ =γ_min^.

• We show that ∇ᵢ f(z∗)=0 for any i∈Γ∗. In fact, for any i∈Γ∗, there are only two cases: i∈Γ∗₁ and i∈Γ∗₂. For the first case, i.e., i∈Γ₁∗, one has (P̅_F(z∗-∇ f(z∗)/L))ᵢ=z∗ᵢ≠0. This, together with (3.59), x∗_γ_x∗=1 and ∇_γ_x∗f(z∗)=0, implies that

$$z^{\ast }_{i}-\nabla_{i}f(z^{\ast })/L=z^{\ast }_{i}\left(x^{\ast }_{\gamma_{x^{\ast }}}-\nabla_{\gamma_{x}}f(z^{\ast })/L\right)=z^{\ast }_{i},\;\;\forall i\in\Gamma_{1}^{\ast }.$$

(3.62)

For the second case, i.e., i∈Γ₂∗, one has (P̅_F(z∗-∇ f(z∗)/L))ᵢ=z∗ᵢ≠0. This, together with (3.59), x∗_γ_x∗=1 and ∇_γ_x∗f(z∗)=0, implies that

$$z^{\ast }_{i}-\nabla_{i}f(z^{\ast })/L=z^{\ast }_{i}/\left(x^{\ast }_{\gamma_{x^{\ast }}}-\nabla_{\gamma_{x}}f(z^{\ast })/L\right)=z^{\ast }_{i},\;\;\forall i\in\Gamma_{2}^{\ast }.$$

(3.63)

Thus, by (3.62) and (3.63), we obtain that ∇ᵢ f(z∗)=0 for any i∈Γ∗.

• We show that |∇ᵢ f(z∗)|≤LMₛ(|x∗|) for any i∈ I₁ ∖Γ₁∗. There are only the following two cases.

  Case 1: |Γ∗₁|=s. In this case, it follows from supp(x∗)=supp({(z∗-∇ f(z∗)/L)ᵢ:i∈Ω₁∗}) that supp(x∗)⊆Ω∗₁. Since |Γ∗₁|=|Ω∗₁|=s, we have Γ∗₁=Ω∗₁. By the definition of Ω∗₁ in (3.60), we have that for any i∈ I₁ ∖Ω∗₁ and j∈Ω∗₁,

$$|(z^{\ast }-\nabla f(z^{\ast })/L)_{i}|\leq M_{s}(|x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L|)\leq|(z^{\ast }-\nabla f(z^{\ast })/L)_{j}|.$$

Moreover, it follows from (a) that ∇ᵢ f(z∗)=0 for any i∈Γ∗₁. Thus, combining with Γ∗₁=Ω∗₁, it implies that for any i∈ I₁ ∖Γ∗₁ and j∈Γ∗₁,

$$|-\nabla_{i}f(z^{\ast })/L|=|(z^{\ast }-\nabla f(z^{\ast })/L)_{i}|\leq|(z^{\ast }-\nabla f(z^{\ast })/L)_{j}|=|z^{\ast }_{j}|.$$

Furthermore, it follows that |-_if(z^ )/L|≤min_j∈^ _1|z^ _j|=M_s(|x^ |) for any i∈ I₁ ∖Γ∗₁. Thus, |∇ᵢ f(z∗)|≤LMₛ(|x∗|) for any i∈ I₁ ∖Γ∗₁.

Case 2: |Γ∗₁|<s. In this case, Mₛ(|x∗|)=0. We must have |∇ᵢ f(z∗)|=0≤LMₛ(|x∗|) for any i∈ I₁ ∖Γ₁∗. Denote

$$i_{0}:=\mathrm{arg}\max_{j\in I_{1}\setminus\Gamma^{\ast }_{1}}\left\lbrace |\nabla_{j}f(z^{\ast })|\right\rbrace .$$

(3.64)

Suppose |∇_i₀f(z∗)|≠0. Since |Γ∗₁|<s=|Ω∗₁|, we have Γ∗₁≠Ω∗₁. It follows from (3.64) that for any i∈ I₁ ∖Γ₁∗,

$$|(z^{\ast }-\nabla f(z^{\ast })/L)_{i_{0}}|=|\nabla_{i_{0}}f(z^{\ast })/L|\geq|\nabla_{i}f(z^{\ast })/L|=|(z^{\ast }-\nabla f(z^{\ast })/L)_{i}|.$$

Thus i₀ ∈Ω∗₁ by (3.60). For any u∈ P (z^ - f(z^ )/L), by (3.59) and γ_x^ =γ_min^, we have

$$u_{i_{0}}=\frac{(z^{\ast }-\nabla f(z^{\ast })/L)_{i_{0}}}{z^{\ast }_{\gamma_{x^{\ast }}}-\nabla_{\gamma_{x^{\ast }}}f(z^{\ast })/L}=(z^{\ast }-\nabla f(z^{\ast })/L)_{i_{0}}\neq z^{\ast }_{i_{0}},$$

which yields a contradiction. Thus, |∇ᵢ f(z∗)|=0 for any i∈ I₁ ∖Γ₁∗, which implies that |∇ᵢ f(z∗)|≤LMₛ(|x∗|) for any i∈ I₁ ∖Γ₁∗.

Combining the two cases above yileds |∇ᵢ f(z∗)|≤LMₛ(|x∗|) for any i∈ I₁ ∖Γ₁∗.

• We show that |∇ᵢ f(z∗)|≤LMₜ(|y∗|) for any i∈ I₂ ∖Γ₂∗. This can be proved similarly to (b), and thus the proof is omitted.

Merging the cases (a)-(c) above leads to (3.58).

($\Leftarrow$) Suppose that (3.58) holds. We show that z∗ is an L-like stationary point of (1.10). From (3.58), one has

$$(z^{\ast }-\nabla f(z^{\ast })/L)_{i}=\left\lbrace \begin{array}{ll}z^{\ast }_{i}& \mathrm{if}\;i\in\Gamma^{\ast },\\ -\nabla_{i}f(z^{\ast })/L& \mathrm{otherwise}.\end{array}\right.$$

| | (3.65) |

Since z∗ ∈ F, we have x_γ_x∗∗=1. This, together with the first equality in (3.65), implies that ∇_x_γ_x∗∗f(z∗)=0. By Definition 3.6, we need to show that z∗ ∈P̅_F(z∗-∇ f(z∗)/L). By Lemma 3.6, we only need to prove there exist Ω₁∗ and Ω₂∗ defined by (3.60) such that (3.59) holds. To this goal, we divide the remaining proof into two parts.

Part 1. We show that there exists Ω∗₁ defined as (3.60) such that

$$z^{\ast }_{i}=\left\lbrace \begin{array}{ll}\frac{(z^{\ast }-\nabla f(z^{\ast })/L)_{i}}{(z^{\ast }-\nabla f(z^{\ast })/L)_{\gamma_{\min}^{\ast }}}&\mathrm{if} i\in\Omega^{\ast }_{1},\\ 0&\mathrm{if} i\in I_{1}\setminus\Omega^{\ast }_{1},\end{array}\right.$$

(3.66)

where γ_min^ is defined by (3.61). It is sufficient to consider the following two cases.

Case 1: |Γ∗₁|=s. In this case, we define Ω∗₁=Γ∗₁. Firstly, we show that Ω∗₁ is just the one defined by (3.60). On one hand, it is obvious that |Ω∗₁|=s. On the other hand, since z∗ᵢ≥Mₛ(|x∗|) for i∈Γ∗₁, it follows from (3.58) that

$$|z^{\ast }_{i}|\geq|\nabla_{j}f(z^{\ast })/L|, \forall i\in\Gamma^{\ast }_{1}, j\in I_{1}\setminus\Gamma_{1}^{\ast }.$$

Thus, by (3.65) we have

$$|(z^{\ast }-\nabla f(z^{\ast })/L)_{i}|\geq|(z^{\ast }-\nabla f(z^{\ast })/L)_{j}|, \forall i\in\Gamma^{\ast }_{1}, j\in I_{1}\setminus\Gamma_{1}^{\ast }.$$

(3.67)

By |Γ∗₁|=s and (3.67), we have |(x∗-∇_I₁f(z∗)/L)ᵢ|≥Mₛ(|x∗-∇_I₁f(z∗)/L|) for any i∈Ω∗₁ and |(x∗-∇_I₁f(z∗)/L)ⱼ|≤Mₛ(|x∗-∇_I₁f(z∗)/L|) for any j∈ I₁ ∖Ω∗₁. Thus Ω∗₁ is just the one defined by (3.60) with _1^ =_1^ ∩_1^.

Secondly, we show that (3.66) holds. By |Ω∗₁|=s and (3.65), we have

$$\gamma_{\min}^{\ast }=\min \mathrm{supp}(\lbrace (z^{\ast }-\nabla f(z^{\ast })/L)_{i}:i\in\Omega_{1}^{\ast }\rbrace )=\min \mathrm{supp}(\lbrace z^{\ast }_{i}:i\in\Gamma_{1}^{\ast }\rbrace )=\gamma_{x^{\ast }}.$$

By ∇_γ_x∗f(z∗)=0, z∗_γ_x∗=1 and ∇ᵢ f(z∗)=0 for any i∈Ω₁∗, we see that (3.66) holds.

Case 2: |Γ∗₁|=q<s. In this case, we have Mₛ(|x∗|)=0. This, together with (3.58), implies that ∇ᵢ f(z∗)=0 for any i∈ I₁. Thus, x∗-∇_I₁f(z∗)/L=x∗. Choose _1⊆ I_1∖_1^ with |_1|=s-q and define _1^ :=_1^ ∪_1. Then, |Ω₁∗|=s. Since x∗-∇_I₁f(z∗)/L=x∗, we have

$$|(x^{\ast }-\nabla f(z^{\ast })/L)_{i}|=|x^{\ast }_{i}|\geq M_{s}(|x^{\ast }|)=M_{s}(|x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L|)$$

for any i∈Ω∗₁ and

$$|(x^{\ast }-\nabla f(z^{\ast })/L)_{j}|=|x^{\ast }_{j}|\leq M_{s}(|x^{\ast }|)=M_{s}(|x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L|)$$

for any j∈ I₁ ∖Ω∗₁. Thus Ω∗₁ is just the one defined by (3.60). Moreover, we have

$$\gamma_{\min}^{\ast }=\min \mathrm{supp}(\lbrace (z^{\ast }-\nabla f(z^{\ast })/L)_{i}:i\in\Omega_{1}^{\ast }\rbrace )=\min \mathrm{supp}(\lbrace z^{\ast }_{i}:i\in\Omega_{1}^{\ast }\rbrace )=\gamma_{x^{\ast }}.$$

Thus, by x∗_γ_x∗=1 and ∇ᵢ f(z∗)=0 for any i∈ I₁, we see that (3.66) holds.

Part 2. Similar to the proof in Part 1 for x-block, we can also show that there exists Ω∗₂ ⊆ I₂ with the same definition as (3.60) such that

$$z^{\ast }_{i}=\left\lbrace \begin{array}{ll}(z^{\ast }-\nabla f(z^{\ast })/L)_{\gamma_{\min}^{\ast }}(z^{\ast }-\nabla f(z^{\ast })/L)_{i}&\mathrm{if} i\in\Omega^{\ast }_{2},\\ 0&\mathrm{if} i\in I_{2}\setminus\Omega^{\ast }_{2}.\end{array}\right.$$

(3.68)

Combining (3.66) and (3.68) yields (3.59), and thus, by Lemma 3.6, we obtain that z∗ ∈P̅_F(z∗-∇ f(z∗)/L). Furthermore, by Definition 3.6, z∗ is an L-like stationary point of the problem (1.10). $\Box$

The relation between L-like stationarity and N-type stationarity is stated in the theorem below.

Theorem 3.14

If z∗=(x∗,y∗) is an L-like stationary point of (1.10), then z∗ is also an N^B-stationary point of (1.10).

Proof. Consider the following four cases:

• ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀=t. For this case, Mₛ(|x∗|)>0 and Mₜ(|y∗|)>0. Combining with (3.58), we see that ∇ᵢ f(z∗)=0 for any i∈Γ∗, which implies (3.24).
• ‖ x∗ ‖ ₀<s and ‖ y∗ ‖ ₀=t. In this case, Mₛ(|x∗|)=0 and Mₜ(|y∗|)>0. Combining with (3.58) leads to ∇ᵢ f(z∗)=0 for any i∈ I₁ ∪Γ₂∗, which implies (3.24).
• ‖ x∗ ‖ ₀=s and ‖ y∗ ‖ ₀<t. In this case, Mₛ(|x∗|)>0 and Mₜ(|y∗|)=0. Combining with (3.58), we have ∇ᵢ f(z∗)=0 for any i∈Γ∗₁ ∪ I₂, which implies (3.24).
• ‖ x‖ ₀<s and ‖ y‖ ₀<t. In this case, Mₛ(|x∗|)=0 and Mₜ(|y∗|)=0. Combining with (3.58) yields ∇ f(z∗)=0 for any i∈ I, which also implies (3.24) .

Thus, by Theorem 3.3, the desired result follows. $\Box$

The following two theorems provide necessary optimal conditions for (1.10) through the L-like stationary points.

Theorem 3.15

Let z∗=(x∗,y∗) be an optimal solution of (1.10) and A:=A×_3y^. If ∇_γₓf(z∗)=0 and

$$L\gt \max\left\lbrace \lambda_{max}\left(A^{\to p}A\right),\max_{i\in I_{2}\setminus\Gamma^{\ast }_{2}}\frac{|\nabla_{i}f(z^{\ast })|}{M_{t}(|y^{\ast }|)}\right\rbrace ,$$

then z∗ is an L- like stationary point of (1.10), and P̅_F(z∗-∇ f(z∗)/L) is a singleton. Thus

$$z^{\ast }=\bar{\mathbf{P}}_{F}\left(z^{\ast }-\nabla f(z^{\ast })/L\right).$$

(3.69)

Proof. Since z∗=(x∗,y∗) is an optimal solution of (1.10), it follows from Theorem 3.5 that z∗ is an N^B-stationary point of (1.10). Thus, by Theorem 3.3, we have that ∇ᵢ f(z∗)=0 for any i∈ I₂ if ‖ y∗ ‖ ₀<t, and that ∇ᵢ f(z∗)=0 for any i∈Γ₂∗ if ‖ y∗ ‖ ₀=t, where Γ₂∗ is defined as (3.25). Let z=(x,y)∈ P _F(z^ - f(z^ )/L). We show that z=z∗.

Part 1. We show y=y∗. Consider the following two cases.

Case 1: ‖ y∗ ‖ ₀=q<t. In this case, since ∇ᵢ f(z∗)=0 for any i∈ I₂, we have y∗-∇_I₂f(z∗)/L=y∗. Pick _2⊆ I_2∖_2^ with |_2|=t-q and denote _2=_2∪^ _2. Since ∇_I₂f(z∗)=0, we have |(z∗-∇ f(z∗)/L)ᵢ|=|y∗ᵢ| for any i∈Ω₂ and Mₜ(|y∗-∇_I₂f(z∗)/L|)=Mₜ(|y∗|). Then for any i∈Ω₂, it follows from |y∗ᵢ|≥Mₜ(|y∗|) that |(z∗-∇ f(z∗)/L)ᵢ|≥Mₜ(|y∗-∇_I₂f(z∗)/L|). Thus, Ω₂ satisfies (3.60) with _2 being chosen arbitrarily. Note that _2 is picked arbitrarily, which leads to the arbitrarity of Ω₂. It follows from z=(x,y)∈ P _F(z^ - f(z^ )/L) and (3.45) that

$$y_{j}=\left\lbrace \begin{array}{ll}\left(x^{\ast }_{\gamma_{x^{\ast }}}-\nabla_{\gamma_{x^{\ast }}}f(z^{\ast })/L\right)y^{\ast }_{j}&\mathrm{if} j\in\Omega_{2},\\ 0&\mathrm{if} j\in I_{2}\setminus\Omega_{2}.\end{array}\right.$$

(3.70)

Since x∗_γ_x∗=1,∇_γ_x∗f(z∗)=0, we have y=y∗.

Case 2: ‖ y∗ ‖ ₀=t. In this case, we have ∇ᵢ f(z∗)=0 for any i∈Γ₂∗. Then

$$(y^{\ast }-\nabla_{I_{2}}f(z^{\ast })/L)_{i}=\left\lbrace \begin{array}{ll}y^{\ast }_{i}&\mathrm{if} i\in\Gamma^{\ast }_{2},\\ -\nabla_{i}f(z^{\ast })/L&\mathrm{if} i\in I_{2}\setminus\Gamma^{\ast }_{2}.\end{array}\right.$$

As L>max_i∈ I₂ ∖Γ∗₂(|∇ᵢ f(z∗)|)/(Mₜ(|y∗|)), we have |∇ᵢ f(z∗)|/L<Mₜ(|y∗|) for any i∈ I₂ ∖Γ₂∗. Since |Γ₂∗|=t, we have |z∗ᵢ|≥Mₜ(y∗) for any i∈Γ₂∗. Thus

$$|(y^{\ast }-\nabla_{I_{2}}f(z^{\ast })/L)_{i_{1}}|\geq\cdots\geq|(y^{\ast }-\nabla_{I_{2}}f(z^{\ast })/L)_{i_{t}}|\qquad {} \gt |(y^{\ast }-\nabla_{I_{2}}f(z^{\ast })/L)_{j_{1}}|\geq\cdots\geq|(y^{\ast }-\nabla_{I_{2}}f(z^{\ast })/L)_{j_{n-t}}|,$$

where i₁,…,iₜ ∈Γ₂∗, j₁,…,jₙ₋ₜ ∈ I₂ ∖Γ₂∗ and i₁,…,iₜ,j₁,…,jₙ₋ₜ are not equal to each other. Then the only way to choose Ω₂ satisfying (3.60) is Ω₂=Γ∗₂. Since ∇ᵢ f(z∗)=0 for any i∈Ω₂, then we also obtain (3.70). Thus, we must have y=y∗.

Part 2. We show x=x∗. Suppose that there exists z=(x,y∗) with ‖ x-x∗ ‖>0 such that z∈ P _F(z^ - f(z^ )/L). Combining z∗_γₓ=1 with ∇_γₓf(z)=0, One has

$$\Vert z-\left(z^{\ast }-\nabla f(z^{\ast })/L\right)\Vert ^{2}\leq\Vert z^{\ast }-\left(z^{\ast }-\nabla f(z^{\ast })/L\right)\Vert ^{2},$$

which implies that

$$\left\lt z-\left(z^{\ast }-\nabla f(z^{\ast })/L\right),z-\left(z^{\ast }-\nabla f(z^{\ast })/L\right)\right\gt \leq\frac{1}{L^{2}}\Vert \nabla f(z^{\ast })\Vert ^{2},$$

and hence <z-z∗,∇ f(z∗)>≤-(L)/(2)‖ z-z∗ ‖ ² which is equivalent to

$$\left\lt x-x^{\ast },\nabla_{I_{1}}f(z^{\ast })\right\gt \leq-\frac{L}{2}\Vert x-x^{\ast }\Vert ^{2}.$$

(3.71)

Let ϕ_y∗(x)=1/2‖ Ax-b‖ ². By expanding ϕ_y∗ at x∗ and using (3.71) , one has

$$f(z) =\phi_{y^{\ast }}(x)\leq\phi_{y^{\ast }}(x^{\ast })+\left\lt x-x^{\ast },\nabla\phi_{y^{\ast }}(x^{\ast })\right\gt +\frac{\lambda_{max}(A^{\to p}A)}{2}\Vert x-x^{\ast }\Vert ^{2}\qquad {} \leq\phi_{y^{\ast }}(x^{\ast })-\frac{L}{2}\Vert x-x^{\ast }\Vert ^{2}+\frac{\lambda_{max}(A^{\to p}A)}{2}\Vert x-x^{\ast }\Vert ^{2}\qquad {} \lt \phi_{y^{\ast }}(x^{\ast })=f(z^{\ast }),$$

which contradicts the optimality of z∗. Combining Part 1 with Part 2 yields the equality (3.69). $\Box$

By a similar proof to the above, we can also show the next result. For completeness, we still give a full proof for this result.

Theorem 3.16

Let z∗=(x∗,y∗) be an optimal solution of (1.10) and B:=A×_2x^. If ∇_γₓf(z∗)=0 and

$$L\gt \max\left\lbrace \lambda_{max}\left(B^{\to p}B\right),\max_{i\in I_{1}\setminus\Gamma_{1}^{\ast }}\frac{|\nabla_{i}f(z^{\ast })|}{M_{s}(|x^{\ast }|)}\right\rbrace ,$$

then z∗ is an L-like stationary point of (1.10), and P̅_F(z∗-∇ f(z∗)/L) is a singleton. Thus (3.69) holds, i.e.,

$$z^{\ast }=\bar{\mathbf{P}}_{F}\left(z^{\ast }-\nabla f(z^{\ast })/L\right).$$

Proof. While the proof is similar to that of Theorem 3.15. We still provide the proof here for completeness. Since z∗=(x∗,y∗) is an optimal solution of (1.10), it follows from Theorem 3.5 that z∗ is an N^B-stationary point of (1.10). Thus, by Theorem 3.3, we have that ∇ᵢ f(z∗)=0 for any i∈ I₁ if ‖ x∗ ‖ ₀<s, and that ∇ᵢ f(z∗)=0 for any i∈Γ₁∗ if ‖ x∗ ‖ ₀=s, where Γ₁∗ is defined as (3.25). Let z=(x,y)∈ P _F(z^ - f(z^ )/L). We show that z=z∗.

Part 1. We show x=x∗. Consider the two cases below.

Case 1: ‖ x∗ ‖ ₀=q<s. In this case, since ∇ᵢ f(z∗)=0 for any i∈ I₁, we have x∗-∇_I₁f(z∗)/L=x∗. Pick _1⊆ I_1∖_1^ with |_1|=t-q and denote _1=_1∪^ _1. Since ∇_I₁f(z∗)=0, we have |(z∗-∇ f(z∗)/L)ᵢ|=|x∗ᵢ| for any i∈Ω₁ and Mₛ(|x∗-∇_I₁f(z∗)/L|)=Mₛ(|x∗|). Then for any i∈Ω₁, it follows from |x∗ᵢ|≥Mₛ(|x∗|) that |(z∗-∇ f(z∗)/L)ᵢ|≥Mₛ(|x∗-∇_I₁f(z∗)/L|). Thus, Ω₁ satisfies (3.60) with _1 being chosen arbitrarily. Note that _1 is picked arbitrarily, which leads to the arbitrarity of Ω₁. It follows from z=(x,y)∈ P _F(z^ - f(z^ )/L) and (3.45) that

$$x_{j}=\left\lbrace \begin{array}{ll}x^{\ast }_{j}/\left(x^{\ast }_{\gamma_{x^{\ast }}}-\nabla_{\gamma_{x^{\ast }}}f(z^{\ast })/L\right)&\mathrm{if} j\in\Omega_{1},\\ 0&\mathrm{if} j\in I_{1}\setminus\Omega_{1}.\end{array}\right.$$

(3.72)

Since x∗_γ_x∗=1,∇_γ_x∗f(z∗)=0, we have x=x∗.

Case 2: ‖ x∗ ‖ ₀=s. In this case, we have ∇ᵢ f(z∗)=0 for any i∈Γ₁∗. Then we have

$$(x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L)_{i}=\left\lbrace \begin{array}{ll}x^{\ast }_{i}&\mathrm{if} i\in\Gamma^{\ast }_{1},\\ -\nabla_{i}f(z^{\ast })/L&\mathrm{if} i\in I_{1}\setminus\Gamma^{\ast }_{1}.\end{array}\right.$$

Since L>max_i∈ I₁ ∖Γ∗₁(|∇ᵢ f(z∗)|)/(Mₛ(|x∗|)), we have |∇ᵢ f(z∗)|/L<Mₛ(|x∗|) for any i∈ I₁ ∖Γ₁∗. Since |Γ₁∗|=s, we have |z∗ᵢ|≥Mₛ(x∗) for any i∈Γ₁∗. We have

$$|(x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L)_{i_{1}}|\geq\cdots\geq|(x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L)_{i_{t}}|\qquad {} \gt |(x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L)_{j_{1}}|\geq\cdots\geq|(x^{\ast }-\nabla_{I_{1}}f(z^{\ast })/L)_{j_{n-t}}|,$$

where i₁,…,iₜ ∈Γ₁∗, j₁,…,jₙ₋ₜ ∈ I₁ ∖Γ₁∗ and i₁,…,iₜ,j₁,…,jₙ₋ₜ are not equal to each other. Then the only way to choose Ω₁ satisfying (3.60) is Ω₁=Γ∗₁. Since ∇ᵢ f(z∗)=0 for any i∈Ω₁, then we also have (3.72) holds. Thus, we must have x=x∗.

Part 2. We show y=y∗. Suppose that there exists z=(x∗,y) with ‖ y-y∗ ‖>0 such that z∈ P _F(z^ - f(z^ )/L). Combine z∗_γₓ=1 with ∇_γₓf(z)=0, we have

$$\Vert z-\left(z^{\ast }-\nabla f(z^{\ast })/L\right)\Vert ^{2}\leq\Vert z^{\ast }-\left(z^{\ast }-\nabla f(z^{\ast })/L\right)\Vert ^{2},$$

which implies that

$$\left\lt z-\left(z^{\ast }-\nabla f(z^{\ast })/L\right),z-\left(z^{\ast }-\nabla f(z^{\ast })/L\right)\right\gt \leq\frac{1}{L^{2}}\Vert \nabla f(z^{\ast })\Vert ^{2},$$

and thus <z-z∗,∇ f(z∗)>≤-(L)/(2)‖ z-z∗ ‖ ² which is equivalent to

$$\left\lt y-y^{\ast },\nabla_{I_{2}}f(z^{\ast })\right\gt \leq-\frac{L}{2}\Vert y-y^{\ast }\Vert ^{2}.$$

(3.73)

Let ϕ_x∗(y)=1/2‖ By-b‖ ². By expanding ϕ_x∗ at y∗ and (3.73), one has

$$f(z) =\phi_{x^{\ast }}(y)\leq\phi_{x^{\ast }}(y^{\ast })+\left\lt y-y^{\ast },\nabla\phi_{x^{\ast }}(y^{\ast })\right\gt +\frac{\lambda_{max}(B^{\to p}B)}{2}\Vert y-y^{\ast }\Vert ^{2}\qquad {} \leq\phi_{x^{\ast }}(y^{\ast })-\frac{L}{2}\Vert y-y^{\ast }\Vert ^{2}+\frac{\lambda_{max}(B^{\to p}B)}{2}\Vert y-y^{\ast }\Vert ^{2}\qquad {} \lt \phi_{x^{\ast }}(y^{\ast })=f(z^{\ast }),$$

which contradicts the optimality of z∗. Combining Part 1 with Part 2 leads to (3.69). $\Box$

For problem (1.10) and fixed z∗=(x∗,y∗)∈ℝᵐ⁺ⁿ, denote A:=A×_2x^ and B:=A×_3y^. Let ϕ_y∗(x)=1/2‖ Bx-b‖ ² and ϕ_x∗(y)=1/2‖ Ay-b‖ ² . Then we obtain the two subproblems below:

$$\min\lbrace \phi_{y^{\ast }}(x)=\frac{1}{2}\Vert Bx-b\Vert ^{2}:~\Vert x\Vert _{0}\leq s\rbrace .$$

(3.74)

$$\min\lbrace \phi_{x^{\ast }}(y)=\frac{1}{2}\Vert Ay-b\Vert ^{2}:~\Vert y\Vert _{0}\leq t\rbrace ,$$

(3.75)

Theorem 3.17

For some L>0, if z∗:=(x∗,y∗) is an L-like stationary point of (1.10), then x∗ and y∗ are the L-stationary points of (3.74) and (3.75), respectively. Conversely, if x∗ and y∗ are L-stationary points of (3.74) and (3.75), respectively, then z̅∗:=(z̅∗₁,z̅∗₂) is an N^C-stationary point of (1.10), where z̅∗₁:=x∗/x∗_γₓ and z̅∗₁:=x∗_γₓy∗.

Proof. Since z∗:=(x∗,y∗) is an L-like stationary point of (1.10), combining (3.58) with ∇ f(z∗)=(∇ϕ_y∗(x∗),∇ϕ_x∗(y∗)), we obtain that

$$|\nabla_{i}\phi_{y^{\ast }}(x^{\ast })|\left\lbrace \begin{array}{ll}=0&\mathrm{if} i\in\Gamma_{1}^{\ast },\\ \leq LM_{s}(|x^{\ast }|)&\mathrm{if} i\in I_{1}\setminus\Gamma_{1}^{\ast }\end{array}\right.$$

(3.76)

and

$$|\nabla_{i}\phi_{x^{\ast }}(y^{\ast })|\left\lbrace \begin{array}{ll}=0&\mathrm{if} i\in\Gamma_{2}^{\ast },\\ \leq LM_{t}(|y^{\ast }|)&\mathrm{if} i\in I_{2}\setminus\Gamma_{2}^{\ast },\end{array}\right.$$

(3.77)

respectively. It follows from Lemma 2.2 in [7] that x∗ and y∗ are L-stationary points of (3.74) and (3.75), respectively.

Conversely, since x∗ and y∗ are L-stationary points of (3.74) and (3.75), respectively, we see that (3.76) and (3.77) hold. Thus, ∇ᵢ ϕ_y∗(x∗)=0 for any i∈Γ∗₁ and ∇ⱼ ϕ_x∗(y∗)=0 for any j∈Γ∗₂. Furthermore, we have ∇ᵢ f(z̅∗)=∇ᵢ ϕ_z̅∗₂(z̅∗₁) for any i∈Γ∗₁, where

$$\phi_{\bar{z}^{\ast }_{2}}(\bar{z}^{\ast }_{1})=\frac{1}{2}\Vert (\mathscr{A}\times_{3}\bar{z}^{\ast }_{2})\bar{z}^{\ast }_{1}-b\Vert ^{2}=\frac{1}{2}\Vert \left(\mathscr{A}\times_{3}(x^{\ast }_{\gamma_{x^{\ast }}}y^{\ast })\right)(x^{\ast }/x^{\ast }_{\gamma_{x}})-b\Vert ^{2}.$$

So, for any i∈Γ∗₁, we have

$$\nabla_{i}f(\bar{z}^{\ast })=\left(\mathscr{A}\times_{3}(x^{\ast }_{\gamma_{x}}y^{\ast })^{\to p}(\mathscr{A}x^{\ast }y^{\ast }-b)\right)_{i}=x^{\ast }_{\gamma_{x}}\left(B^{\to p}(Bx^{\ast }-b)\right)_{i}=x^{\ast }_{\gamma_{x}}\nabla_{i}\phi_{y^{\ast }}(x^{\ast })=0.$$

Symmetrically, we have

$$\nabla_{j}f(z)=\nabla_{i}\phi_{x^{\ast }}(y^{\ast })/x^{\ast }_{\gamma_{x}}=0, \forall j\in\Gamma^{\ast }_{2}.$$

By Theorem 3.8, we conclude that z∗ is an N^C-stationary point of (1.10). $\Box$

Recall that for the sparsity constrained optimization (1.2), as shown in [36], the concepts of L-stationarity and N^B-stationarity are equivalent when the sparsity constraint is not active. However, similar result for L-like stationarity and N^B-stationarity does not hold. In fact, L-like stationarity remains stronger than N^B-stationarity for the problem (1.10) even when the sparsity constraint is not active. We present the following example to illustrate it.

Example 3.5

Consider the problem (1.10) with b=(1,7)^→ p, tensor A=(a_j_1j_2j_3)∈ R ^2× 4× 4, where a₁₁₁=1,a₁₂₂=1,a₁₂₃=1,a₁₃₁=1,a₁₃₄=1,a₂₁₁=1,a₂₁₃=2,a₂₂₁=1,a₂₂₂=2,a₂₃₂=4,a₂₄₄=1 and all other entries are zero. Then for any z=(x,y)∈ℝ⁸, the objective function in (1.10) is defined by f(z):=(1)/(2)‖ Axy-b‖ ^2 with

$$\mathscr{A}xy-b=\left[\begin{array}{l}x_{1}y_{1}+x_{2}y_{2}+x_{2}y_{3}+x_{3}y_{1}+x_{3}y_{4}-1\\ x_{1}y_{1}+2x_{1}y_{3}+x_{2}y_{1}+2x_{2}y_{2}+4x_{3}y_{2}+x_{4}y_{4}-7\end{array}\right].$$

Let s=t=3. For z∗=(1,1,0,0,2,1,0,0)^→ p, we have γ_x∗=1,z∗_γ_x∗=1,|Γ∗₁|=2<s,|Γ∗₂|=2<t, then z∗ ∈ F. It is straightforward to verify that ∇ f(z∗)=(2,0,0,0,0,0,0,0)^→ p, i.e., ∇ᵢ f(z∗)=0 for any i>γ_x∗, which implies that z∗ is an N^B-stationary point. However, for any L∈(0,+∞),

$$z^{\ast }-\nabla f(z^{\ast })/L=(1-2/L,1,0,0,2,2,0,0)^{\to p}$$

and

$${\bf\bar{P}}_{F}(z^{\ast }-\nabla f(z^{\ast })/L)=\lbrace (1,1/(1-2/L),0,0,2-4/L,2-4/L,0,0)\rbrace ,$$

which imply z^ P_F(z^ - f(z^ )/L). Thus, z∗ is not an L-like stationary point.

3.4 M-stationary point

Recall that Burdakov, Kanzow and Schwartz [13] reformulated and relaxed the single-block-variable optimization problem with sparse constraint as a smooth model with complementarity constraint. We also consider complementarity-type reformulation of (1.10), based on which we introduce the M-stationary point of (1.10). For this purpose, we introduce the auxiliary variable w=(u,v)∈ℝᵐ⁺ⁿ and consider the following mixed-integer model:

$$\begin{array}{cl}\min&f(x,y)=\frac{1}{2}\Vert \mathscr{A}xy-b\Vert ^{2}\\ \mathrm{s}.t.&e_{\gamma_{x}}^{\to p}x=1,\\ &z^{\to p}w=0, e_{I_{1}}^{\to p}u\geq m-s, e_{I_{2}}^{\to p}v\geq n-t,\\ &w_{i}\in\left\lbrace 0,1\right\rbrace ,\forall i\in I.\end{array}$$

(3.82)

The following theorem shows the relationship between the global minima of the problems (1.10) and (3.82).

Theorem 3.18

z∗ ∈ℝᵐ⁺ⁿ is an optimal solution of (1.10) if and only if there exists w∗ ∈ℝᵐ⁺ⁿ such that the pair (z∗,w∗) is an optimal solution of (3.82).

Proof. (⇒) Suppose that z∗ ∈ℝᵐ⁺ⁿ is an optimal solution of (1.10). Then, we have z∗ ∈ F. Let w∗=(w¹∗,w²∗)∈ℝᵐ⁺ⁿ be given as

$$w^{\ast }_{i}=\left\lbrace \begin{array}{ll}0&\mathrm{if} z^{\ast }_{i}\neq 0,\\ 1&\mathrm{if} z^{\ast }_{i}=0,\end{array}\;\;\forall i\in I.\right.$$

Then z∗^→ p w∗=0, e_I₁^→ p w¹∗≥n-s and e_I₂^→ p w²∗≥n-t. Thus (z∗,w∗) is a feasible point of (3.82). Suppose that (z∗,w∗) is not an optimal solution of (3.82), then there exists a feasible point (z̅,w̅) of (3.82) with z̅=(x̅,y̅) and w̅=(u̅,v̅) such that f(z̅)<f(z∗). Since z̅^→ p w̅=0, e_I₁^→ p u̅≥m-s, e_I₂^→ p v̅≥n-t and w̅ᵢ ∈{0,1} for all i∈ I, it follows that ‖ x̅‖ ₀≤s and ‖ y̅‖ ₀≤t. These together with e_γₓ̅^→ p x̅=1 imply that z̅∈ F. However, f(z̅)<f(z∗), which contradicts the assumption that z∗ is an optimal solution of (1.10).

($\Leftarrow$) Suppose that there exists w∗ ∈ℝᵐ⁺ⁿ such that (z∗,w∗) is an optimal solution of (3.82). Then one must have z∗ ∈ F. Suppose that z∗ is not an optimal solution of (1.10). Then there exists z̅∈ F such that f(z̅)<f(z∗). Choose w̅∈ℝᵐ⁺ⁿ such that

$$\bar{w}_{i}=\left\lbrace \begin{array}{ll}0&\mathrm{if} \bar{z}_{i}\neq 0,\\ 1&\mathrm{if} \bar{z}_{i}=0,\end{array}\;\;\forall i\in I.\right.$$

Then (z̅,w̅) is a feasible point of problem (3.82). However, f(z̅)<f(z∗). These contradict the assumption that (z∗,w∗) is an optimal solution to problem (3.82). $\Box$

In order to reduce the complexity of 0-1 constraints in problem (3.82), we consider the following relaxed model.

$$\begin{array}{cl}\min&f(x,y)=\frac{1}{2}\Vert \mathscr{A}xy-b\Vert ^{2}\\ \mathrm{s}.t.&e_{\gamma_{x}}^{\to p}x=1,\\ &z^{\to p}w=0,e_{I_{1}}^{\to p}u\geq m-s,e_{I_{2}}^{\to p}v\geq n-t,\\ &w_{i}\in[0,1],\forall i\in I.\end{array}$$

(3.87)

Problems (1.10) and (3.87) share common global minima, as indicated by the following theorem, to which the proof is similar to that of Theorem 3.18 and thus omitted.

Theorem 3.19

z∗ ∈ℝᵐ⁺ⁿ is an optimal solution of (1.10) if and only if there exists w∗ ∈ℝᵐ⁺ⁿ such that (z∗,w∗) is an optimal solution of (3.87).

Denote E:={z=(x,y)∈(ℝᵐ ∖{0})×ℝⁿ: x_γₓ=1} , and

$$g(w):=\left(\begin{array}{c}(m-s)-e_{I_{1}}^{\to p}u\\ (n-t)-e_{I_{2}}^{\to p}v\\ -w\\ w-e_{I}\end{array}\right).$$

Then, (3.87) can be rewritten as

$$\begin{array}{cl}\min&f(x,y)=\frac{1}{2}\Vert \mathscr{A}xy-b\Vert ^{2}\\ \mathrm{s}.t.&g(w)\leq 0, z^{\to p}w=0,\\ &z\in E.\end{array}$$

(3.91)

Denote the feasible set of (3.91) by F̅, and denote the normal cone of E at z∈ E by N^#_E(z), where #∈{B,C} means the Bouligand sense and Clarke sense, respectively. We provide the following lemma, which gives the formula for N^#_E(z).

Lemma 3.7

For any given z∈ E, the normal cone of E at z is

$$N^{\#}_{E}(z)=\left\lbrace d\in\mathbb{R}^{m+n}: d_{i}=0, \text{for any} i\gt \gamma_{x}\right\rbrace .$$

(3.92)

Proof. Denote Q:={d∈ℝᵐ⁺ⁿ: dᵢ=0, for any i≤γₓ}. Then, by Definitions 2.1 and 2.2, we need to show T^#_E(z)=Q, where T^#_E(z) denotes the tangent cone of E at z. (i) We prove that T^B_E(z)=Q. Firstly, we show T^B_E(z)⊆ Q. For any d∈ T^B_E(z), it follows from Definition 2.1 that there exist {zᵏ} ⊂ E satisfying limₖ→∞ zᵏ=z and λₖ ∈ℝ⁺ such that _k→∞λ_k(z^k-z)=d. By Lemma 3.1, there exists k₀ ∈ℕ such that zᵏᵢ=0 for any i<γₓ and zᵏ_γₓ=1 for all k≥k₀. Thus, one has

$$d_{i}=\lim_{k\to\infty}\lambda_{k}(z^{k}_{i}-z_{i})=0, \forall i\leq\gamma_{x}.$$

That is d∈ Q. Thus we have T_E(z)⊆ Q. Secondly, we show T_E(z) Q. For any d∈ Q, let zᵏ=z+(d)/(k) for all k∈ℕ. By z∈ E, one has zᵏᵢ=0 for any i<γₓ and zᵏ_γₓ=1 for all k∈ℕ. Thus {zᵏ} ⊂ E. Besides, we also have limₖ→∞ zᵏ=z and _k→∞(1)/(k)(z^k-z)=d. That is d∈ T^B_E(z). Thus we have T^B_E(z) Q. Thus T^B_E(z)=Q. (ii) We prove that T^C_E(z)=Q. Firstly, we show T^C_E(z)⊆ Q. Suppose there exits d∈ T^C_E(z) with dᵢ≠0 where i≤γₓ. Then for any {dᵏ} ⊆ E with limₖ→∞ dᵏ=d, there exists k₁>0 such that dᵏᵢ≠0 for all k>k₁. Without loss of generality, suppose i is the first index of nonzero entries of dᵏ. Pick λₖ:=(1)/(k|dᵏᵢ|) for all k∈ℕ. For any zᵏ → z, there exists k₂>0 such that zᵏⱼ=0 for all j<γₓ and zᵏ_γₓ=1 for all k>k₂. It follows that i is the first index of nonzero entries of zᵏ+λₖ dᵏ. Let K=max{k₁,k₂}, one has

$$z_{i}^{k}+\lambda_{k}d_{i}^{k}=\left\lbrace \begin{array}{ll}\mathrm{sgn}(d^{k}_{i})\frac{1}{k}\neq 1&\mathrm{if} i\lt \gamma_{x},\\ 1+\mathrm{sgn}(d^{k}_{i})\frac{1}{k}\neq 1&\mathrm{if} i=\gamma_{x},\end{array}\right.$$

for k>K, where sgn(·) denotes the symbolic function. This contradicts the result that xᵏ+λₖ dᵏ ∈ E. Thus, dᵢ=0 for any i≤γₓ. That is d∈ Q. Thus we have T^C_E(z)⊆ Q. Secondly, we show T^C_E(z) Q. For any d∈ Q, define dᵏ as (3.36). Then for any zᵏ → z and {λₖ} ⊂ E with λₖ → 0, one has zᵏ_γₓ+λₖ dᵏ_γₓ=1+0=1 and zᵏⱼ+λₖ dᵏⱼ=0 for any j<γₓ and for all k∈ℕ. Thus, zᵏ+λₖ dᵏ ∈ E for all k∈ℕ. So Q⊆ T^C_E(z). Therefore, T^C_E(z)=Q.

Based on the proofs of (i) and (ii) above, we conclude that (3.92) holds. $\Box$

The following definition of M-stationary point of (1.10) is in line with Definition 4.6 in [13], which is similar to the one in [41] for MPEC (mathematical programs with equilibrium constraints).

Definition 3.7

z∗ is an M-stationary point of (1.10) if there exists w∗ ∈ℝᵐ⁺ⁿ satisfying (z^ ,w^ )∈F and μ∈ℝᵐ⁺ⁿ such that the two conditions below hold:

• -∇ f(z∗)-μ∈ N^#_E(z∗).
• μᵢ=0, while z∗ᵢ≠0.

Theorem 3.20

Let z∗=(x∗,y∗)∈ F, where F is defined by (2.4), and let Γ be defined by (2.1). Then z∗ is an M-stationary point of (1.10) if and only if ∇ f(z∗)∈ℝᵐ⁺ⁿ satisfies

$$\nabla_{i}f(z^{\ast })=0, \forall i\in\Gamma^{\ast }\setminus\left\lbrace \gamma_{x^{\ast }}\right\rbrace .$$

(3.93)

Proof. Choose w∗:=(u∗,v∗)∈ℝᵐ⁺ⁿ such that

$$w^{\ast }\left\lbrace \begin{array}{ll}=0&\mathrm{if} i\in\Gamma^{\ast },\\ \in(0,1]&\mathrm{otherwise}.\end{array}\right.$$

Then z∗^→ p w∗=0. Clearly, (z^ ,w^ )∈F due to z∗ ∈ F. Thus, by Definition 3.7, z∗ is an M-stationary point if and only if there exists μ∈ℝᵐ⁺ⁿ such that μᵢ=0 for any i∈Γ∗ and

$$-\nabla f(z^{\ast })-\mu\in N_{E}(z^{\ast }).$$

By Lemma 3.7, this implies that z∗ is an M-stationary point if and only if (3.93) holds. $\Box$

The following corollary indicates the relation of M-stationarity and N^C-stationarity of (1.10) and also claims that the M-stationarity is a necessary first-order optimality condition for (1.10) .

Corollary 3.4 (i) z∗=(x∗,y∗) is an M-stationary point of (1.10) if and only if z∗ is an N^C-stationary point of (1.10). (ii) z∗=(x∗,y∗) is an optimal solution of (1.10), then z∗ is an M-stationary point.

Item (i) above follows directly from Theorems 3.8 and 3.20, and Item (ii) follows directly from Theorems 3.4 and 3.9. Finally, we summarize the relationship between the stationary points discussed in this work as follows.

Theorem 3.21

The stationary points of (1.10) satisfy the following relationship:

$$\begin{array}{ccccccc}&&\mathrm{CWminimum}&&&&\\ &&\Downarrow&&&&\\ L\text{-stationarity}&\Longrightarrow&{\mathrm{N}^{B}}\text{-stationarity}&\Longrightarrow&{\mathrm{N}^{C}}\text{-stationarity}&\Longleftrightarrow&\text{M-stationarity}\\ &&\Updownarrow&&\Updownarrow&&\\ &&{\mathrm{T}^{B}}\text{-stationarity}&\Longrightarrow&{\mathrm{T}^{C}}\text{-stationarity}&&\end{array}$$

4 Conclusion

In this paper, we investigated the first-order optimality conditions for the sparse bilinear least squares problems. Via some variational geometric tools, we characterized T-type and N-type stationary points of the problem in terms of tangent and normal cones in Bouligand sense and Clarke sense. We also showed that an optimal solution to a sparse bilinear least squares problem is necessarily a T-type and/or N-type stationary point in Bouligand sense and Clarke sense. In addition, the definition of coordinate-wise minima is modified and characterized according to the feasible set, and it is proved that any optimal solution of the considered problem must be a CW minimum. Moreover, we introduced the concept of L-like stationary point based on the so-called like-projection. Based on this concept, we established the first-order necessary optimality condition for the sparse bilinear least squares problem. By reformulating the problem as a complementarity-type model, we introduced and characterized the M-stationary point, and showed that M-stationarity is a necessary optimality condition for the problem. Furthermore, the relationship between the various stationary points is also discussed in this work. We believe that the theoretical results established here provide a fundamental basis for the development of certain numerical methods for the sparse bilinear least squares problems, which would be an interesting and worthwhile research topic in the near future.

References

• [1]

  M. Aharon, M. Elad, A. Bruckstein, K-SVD: An algorithm fro designing overcomplete dictionaries for sparse representation, IEEE Trans. Signal Process. 54(11) (2006) 4311-4322.

• [2]

  A. Ahmed, B. Recht, J. Romberg, Blind deconvolution using convex programming, IEEE Trans. Inf. Theory 60(3) (2014) 1711-1732.

• [3]

  F.S. Aktaç, M.Ç. Pinar, Separable Bregman framework for sparisity for sparisity constrained nonlinear optimization, arXiv:2409.12343v2, 2024.

• [4]

  J.H. Alcantara, C.-P. Lee, Accelerated projected gradient algorithms for sparsity constrained optimization problems, 36th Conference on Neural Information Processing Systems, NeurIPS 2022.

• [5]

  H. Attouch, J. Bolte, B. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods, Math. Program. 137 (2013) 91–129.

• [6]

  S. Bahmani, B. Raj, P.T. Boufounos, Greedy sparsity-constrained optimization, J. Mach. Learn. Res. 14 (2013) 807–841.

• [7]

  A. Beck, Y. Eldar, Sparsity constrained nonlinear optimization: optimality conditions and algorithms, SIAM J. Optim. 23 (2013) 1480-1509.

• [8]

  S. Bhmani, J. Romberg, Lifting for blind deconvolution in random mask imaging: identifiability and convex relaxation, SIAM J. Imaging Sci. 8(4) (2015) 2203-2238.

• [9]

  Ç. Bilen, G. Puy, R. Gribonval, L. Daudet, Convex optimization approaches for blind sensor calibration using sparsity, IEEE Trans. Signal Process. 62(18) (2014) 4847-4856.

• [10]

  T. Blumensath, Compressed sensing with nonlinear observations and related nonlinear optimization problems, IEEE Trans. Inf. Theory 59(6) (2013) 3466–3474.

• [11]

  M. Branda, M. Bucher, M. Cervinka, A. Schwartz, Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization, Comput. Optim. Appl. 70(2) (2018) 503–530.

• [12]

  M. Bucher, A. Schwartz, Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems, J. Optim. Theory Appl. 178 (2018) 383–410.

• [13]

  O. Burdakova, C. Kanzow, A. Schwartz, Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and regularization method, SIAM J. Optim. 26 (2016) 397–425.

• [14]

  P. Calamai, J. More, Projected gradient methods for linearly constrained problems, Math. Program. 39 (1987) 93–116.

• [15]

  V. Cambareri, L. Jacques, Through the haze: a non-convex approach to blind gain calibration for linear random sensing models, Inf. Inference 8 (2019) 205–271.

• [16]

  V. Cambareri, A. Moshtaghpour, L. Jacques, A greedy blind calibration method for compressed sensing with unknown sensor gains, IEEE Int. Symp. Inf. Theory (2017) 1132–1136.

• [17]

  E.J. Candès, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory 52(2) (2006) 489–509.

• [18]

  E.J. Candès, T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory 51(12) (2005) 4203–4215.

• [19]

  F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, NY, 1990.

• [20] A. Cohen, W. Dahmen, R. DeVore, Compressed sensing and best k-term approximation, J. Am. Math. Soc., 22(1) (2008) 211–231.

• [21]

  S. Damadi, J. Shen, Gradient properties of hard thresholding operator, arXiv:2209.08247v2, 2022.

• [22]

  D.L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52(4) (2006) 1289–1306.

• [23]

  M. Elad, Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing, Springer, NY, 2010.

• [24]

  Y. Eldar, G. Kutyniok, Compressed Sensing: Theory and Applications, Cambridge University Press, Cambridge, UK, 2012.

• [25]

  L. Elden, S. Ahmadi-Asl, Solving bilinear tensor least squares problems and application to Hammerstein identification, Numer. Linear Algebra Appl. 26(2) (2019) e2226.

• [26]

  S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Springer, NY, 2013.

• [27]

  C. Kanzow, A.B. Raharja, A. Schwartz, Sequential optimality conditions for cardinality-constrained optimization problems with applications, Comput. Optim. Appl. 80(1) (2021) 185–211.

• [28]

  S. Lämmel and V. Shikhman, On nondegenerate M-stationary points for sparsity constrained nonlinear optimization, J. Global Optim. 82(2) (2022) 219–242.

• [29]

  K. Lee, N. Tian and J. Romberg, Fast and guaranteed blind multichannel deconvolution under a bilinear system model, IEEE Trans. Inf. Theory 64(7) (2018) 4792–4818.

• [30]

  K. Lee, Y. Wu, Y. Bresler, Near optimal compressed sensing of sparse rank-one matrices via sparse power factorization, IEEE Trans. Inf. Theory 99 (2018) 1666–1698.

• [31]

  Y. Li, K. Lee, Y. Bresler, Identifiability in bilinear inverse problems with applications to subspace or sparsity-constrained blind gain and phase calibration, IEEE Trans. Inf. Theory 63(2) (2017) 822–842.

• [32]

  X. Li, W. Song, The first-order necessary conditions for sparsity constrained optimization, J. Oper. Res. Soc. China. 3 (2015) 521–535.

• [33]

  Z. Lu, Y. Zhang, Sparse approximation via penalty decomposition methods, SIAM J. Optim. 23(4) (2013) 2448–2478.

• [34]

  N. Movahedian, S. Nobakhtian, M. Sarabadan, Nonsmooth sparsity constrained optimization problems: optimality conditions, Optim. Lett. 13 (2019) 1027–1038.

• [35]

  L. Pan, N. Xiu, J. Fan, Optimality conditions for sparse nonlinear programming, Sci. China Math. 60(5) (2017) 759–776.

• [36]

  L. Pan, N. Xiu, S. Zhou, On solutions of sparsity constrained optimization, J. Oper. Res. Soc. China. 3 (2015) 421–439.

• [37]

  R. Rockafellar, R. Wets, Variational Analysis, Springer, Berlin, 1998.

• [38]

  A.M. Tillmann, D. Bienstock, A. Lodi, A. Schwartz, Cardinality minimization, constraints, and regularization: a survey, SIAM Rev. 66(3) (2024) 403–477.

• [39]

  J. Wang, Q. Zhang, L. Ljung, Revisiting Hammerstein system identification through the two-stage algorithm for bilinear parameter estimation, Automatica 45(11) (2009) 2627–2633.

• [40]

  G. Xu, H. Liu, L. Tong, T. Kailath, A least-squares approach to blind channel identification, IEEE Trans. Signal Process. 43(12) (1995) 2982–2993.

• [41]

  J. J. Ye, Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints, J. Math. Anal. Appl. 307(1) (2005) 350–369.

• [42]

  X.T. Yuan, P. Li, T. Zhang, Gradient hard thresholding pursuit, J. Mach. Learn. Res. 18 (2018) 1–43.

• [43]

  Y.-B. Zhao, Sparse Optimization Theory and Methods, CRC Press, Boca Raton, FL, 2018.

• [44] Y.-B. Zhao, RSP-based analysis for sparsest and least ℓ₁-norm solutions to underdetermined linear systems, IEEE Trans. Signal Process., 61 (22) (2013) 5777–5788.

• [45] Y.-B. Zhao, Equivalence and strong equivalence between the sparsest and least ℓ₁-norm nonnegative solutions of linear systems and their applications, J. Oper. Res. Soc. China 2 (2014) 171–193.

• [46]

  S.L. Zhou, Gradient projection Newton pursuit for sparsity constrained optimization, Appl. Comput. Harmon. Anal. 61 (2022) 75–100.

• [47]

  S.L. Zhou, N. Xiu, H.-D. Qi, Global and quadratic convergence of Newton hard-thresholding pursuit, J. Mach. Learn. Res. 22 (2021) 1–45.