A Three‐Dimensional Filter‐Based SSDP Method for Nonlinear Semidefinite Programming With Its Applications

Abstract

Recently, there has been significant interest in filter methods for solving nonlinear problems. Extensions of these methods to nonlinear semidefinite programming (NLSDP) problems are described. A three‐dimensional filter sequential semidefinite programming (SSDP) algorithm with a feasible restoration phase is presented to efficiently solve NLSDPs with equality and matrix inequality constraints. In such an algorithm, the search direction is generated by solving a quadratic semidefinite subproblem. Reductions in the nonlinear objective function and constraint violation measure are ensured through a backtracking line search technique, three‐dimensional filter acceptance criteria, and a nonmonotonically sufficient descent condition. Under appropriate conditions, the global convergence of the proposed algorithm is established. Furthermore, we apply this algorithm to solve several applications, including the Rosen–Suzuki problem, the basic static output feedback problem, the Gaussian channel capacity problem, and the minimal eigenvalue problem. The experimental results demonstrate that it is both efficient and robust.

Full text

Translate

Turn on search term navigation

1. Introduction

In the past decade, nonlinear semidefinite programming (NLSDP) has become a focal point in optimization research and has emerged in many application fields such as feedback control [1], truss design problems [2], machine learning [3], and robust control [4]. Therefore, in this paper, we consider the following NLSDP problems: 1 $\begin{matrix} \min f (x), \\ s . t . c_{i} (x) = 0, i \in \{12,, \dots, p\}, \\ G (x) ⪯ 0, \end{matrix}$ where x ∈ Rⁿ, $c (x) = {(c_{1} (x), c_{2} (x), \dots, c_{p} (x))}^{T}$ , the functions f : Rⁿ⟶R, c : Rⁿ⟶R^p, and G : Rⁿ⟶S^m are smooth, with one or more of them being nonlinear. Here, S^m denotes the set of m × m real symmetric matrices. ⪯ denotes the negative semidefinite order, that is, A⪯B if and only if A − B is a negative semidefinite matrix. Similarly, the order relations ⪯, ≻, and ≺ can be defined.

Recently, there have been numerous studies on the theoretical properties and numerical methods for NLSDP (1). Inspired by the classical sequentially quadratic programming (SQP) method, the sequential semidefinite quadratic programming (SSDP) local method was modified in [5] by using the Han penalty function combined with a line search strategy. Based on generalized shifted barrier Karush–Kuhn–Tucker (KKT) conditions, a primal-dual interior point method for solving NLSDP (1) was proposed in [6]. A successive linearization method with a trust region type globalization for NLSDP (1) was presented in [7], where the subproblem can be converted to a linear semidefinite program with a second-order cone constraint. The work in [8] described interior point trust region algorithms for solving a class of NLSDP (1) and analyzed their global convergence properties. Based on a natural extension of its consolidated counterpart in nonlinear programming (NLP), an augmented Lagrangian method for NLSDP (1) was proposed in [9]. The common feature of these methods is their use of penalty functions to achieve global convergence, classifying them as penalty function-type algorithms (e.g., [10–14]).

Nevertheless, selecting or updating the penalty parameter for penalty function methods can be challenging. To avoid choosing the penalty parameter, a filter approach, which has demonstrated promising numerical performance, was first proposed in [15]. A multidimensional filter SQP method for solving general NLP problems was introduced using the classical filter idea and a nonmonotonic line search in [16], and its global and superlinear convergence were proven. Additionally, a three-dimensional filter SQP algorithm with a line search for NLP was presented in [17], implying that the criteria of the three-dimensional filter more readily accept a reasonable trial step compared to the traditional filter. Consequently, these methods can be classified as filter-type algorithms (e.g., [18–21]).

In this paper, motivated by the three-dimensional filter technique in [17] and combining with the SSDP method, which is one of the more effective methods for solving NLSDP problems, we propose a globally convergent SSDP algorithm with the three-dimensional filter. The three-dimensional filter consists of three components: the value of the equality constraint function, the semidefinite matrix constraint function, and the objective function. Under reasonable assumptions, we prove the global convergence of the new algorithm. Preliminary experimental results demonstrate the effectiveness of the new algorithm.

The remainder of this paper is organized as follows. In Section 2, we introduce some notations and preliminary results and present the new algorithm in detail. In Section 3, we illustrate some auxiliary results and analyze the global convergence of the algorithm. Section 4 reports the experimental results of the algorithm. Finally, Section 5 provides some conclusions.

2. Preliminaries and Algorithm

Throughout this paper, the following notations are introduced. The inner product in the set S^m is defined as 2 $\begin{matrix} ⟨A, B⟩ = t r (A B) = \sum_{i, j = 1}^{m} A_{i j} B_{i j}, \forall A, B \in S^{m} . \end{matrix}$

We use ∇f(x) and ∇²f(x) to denote the gradient and the Hessian matrix of the objective function f(x), respectively. The Jacobian matrix of $c (x) = {(c_{1} (x), \dots, c_{p} (x))}^{T}$ is defined as $D c (x) = {(\nabla c_{1} (x), \dots, \nabla c_{p} (x))}^{T} \in R^{p \times n}$ . We give a linear operator DG(x) for the function G(x) as follows: 3 $\begin{matrix} D G (x) = (\frac{\partial G (x)}{\partial x_{1}}, \frac{\partial G (x)}{\partial x_{2}}, \dots, \frac{\partial G (x)}{\partial x_{n}}), \end{matrix}$ where x_i is the i-th element of the vector x. For any vector d ∈ Rⁿ, we have 4 $\begin{matrix} D G (x) d = \sum_{i = 1}^{n} d_{i} \frac{\partial G (x)}{\partial x_{i}} . \end{matrix}$

Furthermore, for any matrix Z ∈ S^m, the formula for the adjoint operator DG(x)^∗ is 5 $\begin{matrix} D G {(x)}^{*} Z = {(⟨\frac{\partial G (x)}{\partial x_{1}}, Z⟩, ⟨\frac{\partial G (x)}{\partial x_{2}}, Z⟩, \dots, ⟨\frac{\partial G (x)}{\partial x_{n}}, Z⟩)}^{T} . \end{matrix}$

The operator D²G(x) : Rⁿ × Rⁿ⟶S^m, derived from the second derivative of G(x), is given by 6 $\begin{matrix} d^{T} D^{2} G (x) \tilde{d} = \sum_{i, j = 1}^{m} d_{i} {\tilde{d}}_{i} \frac{\partial^{2} G (x)}{\partial x_{i} \partial x_{j}} . \end{matrix}$

Additionally, we have 7 $\begin{matrix} {‖D G (x)‖}_{F} = \sqrt{{\sum_{i = 1}^{n} ‖\frac{\partial G (x)}{\partial x_{i}}‖}_{F}^{2}}, {‖D^{2} G (x)‖}_{F} = \sqrt{{\sum_{i, j = 1}^{n} ‖\frac{\partial^{2} G (x)}{\partial x_{i} \partial x_{j}}‖}_{F}^{2}}, \end{matrix}$ where ‖·‖_F denotes the Frobenius norm. It is easy to prove that 8 $\begin{matrix} {‖D G (x) d‖}_{F} \leq {‖d ‖D G (x)‖}_{F}, {‖d^{T} D^{2} G (x) \tilde{d}‖}_{F} \leq {‖d ‖\tilde{d} ‖D^{2} G (x)‖}_{F}, \end{matrix}$ where ‖·‖ denotes the Euclidean norm of a vector or a matrix.

We denote a Lagrangian function of NLSDP (1) as 9 $\begin{matrix} L (x, λ, Y) = f (x) + λ^{T} c (x) + ⟨Y, G (x)⟩, \end{matrix}$ where x ∈ Rⁿ, λ ∈ R^p, and Y ∈ S^m.

Statement

Definition 1.

Suppose that x^∗ ∈ Rⁿ is a feasible point of NLSDP (1), and there exists a vector λ^∗ ∈ R^p and a matrix Y_∗ ∈ S^m such that the following conditions are satisfied: 10 $\begin{matrix} \nabla_{x} L (x^{*}, λ^{*}, Y_{*}) = \nabla f (x^{*}) + D c {(x^{*})}^{T} λ^{*} + D G {(x^{*})}^{*} Y_{*} = 0, \\ c (x^{*}) = 00, G (x^{*}) ⪯, \\ Y_{*} ≽ 00, ⟨G (x^{*}), Y_{*}⟩ =, \end{matrix}$ then the pair (x^∗, λ^∗, Y_∗) is a KKT point of NLSDP (1), where the pair (λ^∗, Y_∗) is called a Lagrange multiplier associated with x^∗.

Statement

Definition 2.

Let x^∗ ∈ Rⁿ be a feasible point of NLSDP (1). If ${\{\nabla c_{i} (x^{*})\}}_{i = 1}^{p}$ is linearly independent and there exists a vector d ∈ Rⁿ such that 11 $\begin{matrix} D c (x^{*}) d = 00, G (x^{*}) + D G (x^{*}) d ≺, \end{matrix}$ then NLSDP (1) is said to satisfy Mangasarian–Fromovitz constraint qualification (MFCQ) at x^∗.

Given a current iterate point x^k ∈ Rⁿ, a search direction can be generated by solving the following quadratic semidefinite subproblem, denoting as QSD(x^k, H_k): 12 $\begin{matrix} \min \nabla f {(x^{k})}^{T} d + \frac{1}{2} d^{T} H_{k} d, \\ s . t . c (x^{k}) + D c (x^{k}) d = 0, \\ G (x^{k}) + D G (x^{k}) d ⪯ 0, \end{matrix}$ where H_k ∈ R^n×n is a symmetric positive matrix that includes the second-order information of NLSDP (1) at x^k. If a solution for the subproblem QSD(x^k, H_k) (12) exists, the solution is denoted by the search direction d^k. The corresponding Lagrange multipliers of QSD(x^k, H_k) (12) are denoted as (λ^k, Y_k). A step size t ∈ (0, 1] is then determined by a certain line search method. The trial point is subsequently given by $\overset{\land}{x} = x^{k} + t d^{k}$ .

To quantify the feasibility of NLSDP (1), we define the equality and semidefinite matrix constraint violations as follows: 13 $\begin{matrix} h_{c} (x) = ‖c (x)‖, h_{G} (x) = λ_{1} {(G (x))}_{+}, \end{matrix}$ where λ₁(A) is the largest eigenvalue value of a matrix A, (α)₊ = max{0, α}, and (λ₁(G(x))₊ abbreviates λ₁(G(x))₊. Hence, we denote the measure of all constraint violations of NLSDP (1) as 14 $\begin{matrix} h (x) = h_{c} (x) + h_{G} (x) . \end{matrix}$

Obviously, x is a feasible point in NLSDP (1) if h(x) = 0. The definition of dominance in [22] can be presented as follows.

Statement

Definition 3.

Let w = (w₁, w₂, w₃) ∈ R³ and $\overset{\land}{w} = ({\overset{\land}{w}}_{1}, {\overset{\land}{w}}_{2}, {\overset{\land}{w}}_{3}) \in R^{3}$ . We say that $w_{i} \leq {\overset{\land}{w}}_{i}, i = 123,,$ and $w \neq \overset{\land}{w}$ if and only if w dominates $\overset{\land}{w}$ , written $w ≺ \overset{\land}{w}$ .

Similarly, we can utilize $w ⪯ \overset{\land}{w}$ to indicate that either $w ≺ \overset{\land}{w}$ or $w = \overset{\land}{w}$ . Specially, for our problem, we define $\bar{x} ≺_{(h_{c}, h_{G}, f)} \overset{\land}{x}$ if and only if $(h_{c} (\bar{x}), h_{G} (\bar{x}), f (\bar{x})) ≺ (h_{c} (\overset{\land}{x}), h_{G} (\overset{\land}{x}), f (\overset{\land}{x}))$ for any $\bar{x}$ and $\overset{\land}{x}$ . Therefore, a filter is defined as follows.

Statement

Definition 4.

A filter $F$ is a set of points in Rⁿ such that $\bar{x} ≺_{(h_{c}, h_{G}, f)} \overset{\land}{x}$ does not hold for any $\bar{x}, \overset{\land}{x} \in F$ .

The aim of this paper is to reduce the objective function f(x), the equality constraint violation h_c(x), and the semidefinite matrix constraint violation h_G(x). The acceptance criteria of the three-dimensional filter differ from that of traditional filter in [23]. We define the acceptance criteria of the three-dimensional filter below.

Statement

Definition 5.

A trial point $\overset{\land}{x}$ is said to be accepted by the filter $F_{k}$ if one of the following relation holds for all $\bar{x} \in F_{k}$ : 15 $\begin{matrix} h_{c} (\overset{\land}{x}) \leq β_{c} h_{c} (\bar{x}), or h_{G} (\overset{\land}{x}) \leq β_{G} h_{G} (\bar{x}), or f (\overset{\land}{x}) + γ_{f} h (\overset{\land}{x}) \leq f (\bar{x}), \end{matrix}$ where β_c, β_G, γ_f ∈ (0, 1) are three fixed parameters, and $F_{k}$ is the filter at the k-th iteration.

Now, some notations are introduced as follows: 16 $\begin{matrix} \bar{f} (x^{k}) = \{\begin{cases} f (x^{0}), & k = 0, \\ \sum_{i = 0}^{m_{k} - 1} α_{k, i} f (x^{k - i}), & k > 0, \end{cases} \\ \bar{h} (x^{k}) = \{\begin{cases} h (x^{0}), & k = 0, \\ \sum_{i = 0}^{m_{k} - 1} α_{k, i} h (x^{k - i}), & k > 0, \end{cases} \end{matrix}$ where m₀ = 0, m_k = min{m_k−1 + 1, M}, k > 0, and M > 0 is a constant. If k > 0, then $\sum_{i = 0}^{m_{k} - 1} α_{k, i} = 1$ and $\bar{α} \leq α_{k, i} \leq 1$ for any $\bar{α} \in (012, /)$ .

Next, the acceptance criteria of our algorithm are discussed below. First, the nonmonotonically actual reduction of f(x) is defined by 17 $\begin{matrix} nared (x^{k}) = \max \{f (x^{k}), \bar{f} (x^{k})\} - f (\overset{\land}{x}), \end{matrix}$ which is different from the monotonically actual reduction: $ared (x^{k}) = f (x^{k}) - f (\overset{\land}{x})$ . The predicted reduction of f(x) is defined by 18 $\begin{matrix} pred (x^{k}) = - \nabla f {(x^{k})}^{T} d^{k} . \end{matrix}$

Thus, we denote the nonmonotonically sufficient descent condition for the objective function as 19 $\begin{matrix} nared (x^{k}) \geq t σ pred (x^{k}), \end{matrix}$ where σ ∈ (0, 1). Furthermore, if the algorithm does not stop at x^k, then the trial point $\overset{\land}{x}$ generated by the algorithm will improve the value of the objective function or the feasibility of the iterate point. In other words, if 20 $\begin{matrix} pred (x^{k}) \geq ξ {(d^{k})}^{T} H_{k} d^{k} and tpred (x^{k}) > h {(x^{k})}^{s_{h}}, \end{matrix}$ with s_h, ξ ∈ (0, 1) and the nonmonotonically sufficient descent condition (19) hold, then the trial point $\overset{\land}{x}$ is accepted, and we set $x^{k + 1} = \overset{\land}{x}$ and $F_{k + 1} = F_{k}$ . Otherwise, if the trial point $\overset{\land}{x}$ satisfies one of the following relations: 21 $\begin{matrix} h_{c} (\overset{\land}{x}) \leq β_{c} \max \{h (x^{k}), \bar{h} (x^{k})\}, h_{G} (\overset{\land}{x}) \leq β_{G} \max \{h (x^{k}), \bar{h} (x^{k})\}, \\ or nared (x^{k}) \geq γ_{f} h (x^{k}), \end{matrix}$ then the trial point $\overset{\land}{x}$ is accepted, and we set $x^{k + 1} = \overset{\land}{x}$ , $D_{k} ≔ \{\bar{x} ∣ x^{k} ⪯_{(h_{c}, h_{G}, f)} \bar{x}, \bar{x} \in F_{k}\}$ . If the trial point $\overset{\land}{x}$ is accepted, the filter $F_{k + 1}$ should be updated according to the following rule: 22 $\begin{matrix} F_{k + 1} = \frac{F_{k} \cup \{x^{k}\}}{D_{k}} . \end{matrix}$

To inspect whether no admissible step size can be found and the feasible restoration phase has to be invoked, a lower bound $t_{k}^{\min}$ for the step size t needs to be given that is defined as follows: 23 $\begin{matrix} t_{k}^{\min} = γ_{t} \{\begin{cases} Θ_{k}, & if pred (x^{k}) \geq ξ {(d^{k})}^{T} H_{k} d^{k}, \\ Θ_{k}^{1}, & otherwise, \end{cases} \end{matrix}$ where $Θ_{k} = \min \{Θ_{k}^{1}, Θ_{k}^{2}, Θ_{k}^{3}, Θ_{k}^{4}\}$ , $Θ_{k}^{1} = (1 - β_{c} \max \{h (x^{k}), \bar{h} (x^{k})\}) / h (x^{k})$ , $Θ_{k}^{2} = 1 - (β_{G} \max \{h (x^{k}), \bar{h} (x^{k})\}) / h (x^{k})$ , $Θ_{k}^{3} = (h {(x^{k})}^{s_{h}}) / pred (x^{k})$ , $Θ_{k}^{4} = (\max \{\bar{f} (x^{k}), f (x^{k})\} - f (x^{k}) - γ_{f} h (x^{k})) / - pred (x^{k})$ , and γ_t ∈ (0, 1].

When the subproblem QSD(x^k, H_k) (12) becomes incompatible or $t_{k}^{\min} > t$ , the feasibility restoration phase should be invoked to seek a trial point $\overset{\land}{x}$ such that the following conditions hold:

(A1) subproblem $QSD (\overset{\land}{x}, H_{k})$ (12) is compatible,
(A2) $h_{c} (\overset{\land}{x}) \leq β_{c} h_{c} (x^{k})$ or $h_{G} (\overset{\land}{x}) \leq β_{G} h_{G} (x^{k})$ .

The details of the feasibility restoration phase can be found in [24]. Finally, we present an algorithm (see Algorithm 1) to solve NLSDP (1) based on the discussion above.

Algorithm 1: A three-dimensional filter-based SSDP algorithm.

Step 0. (initialization) Given an initial point x⁰ ∈ Rⁿ, a symmetrically positive definite matrix B₀ = I_n (identity matrix), parameters β_c, β_G, γ_f, ρ, σ ∈ (0, 1), γ_t ∈ (0, 1], s_h, ξ ∈ (0, 1), M > 0, a sufficiently large constant u > 0, and filter $F_{0} = \{(u, u, \inf)\}$ . Set k = 0.
Steps 1. Set flag = 0 and solve the subproblem QSD(x^k, H_k) (12). If QSD(x^k, H_k) (12) is incompatible, then enter the feasibility restoration phase and go to step 6. Otherwise, denote its solution as d^k. If d^k = 0, then stop.
Step 2. Calculate a lower bound step size $t_{k}^{\min}$ using (23).
Step 3. (backtracking line search)
Step 3.1 Set t = 1.
Step 3.2 If $t < t_{k}^{\min}$ , then go to Step 6. Otherwise, set the trial point $\overset{\land}{x} = x^{k} + t d^{k}$ .
Step 3.3 If the trial point $\overset{\land}{x}$ is rejected by the filter $F_{k}$ , then go to Step 3.5.
Step 3.4 If conditions (19) and (20) are satisfied, then go to Step 4. If (20) is not satisfied but (21) is, then set flag = 1, and go to step 4.
Step 3.5 Set t = ρt, go to Step 3.2.
Step 4. Set t_k = t, x^k+1 = x^k + t_kd^k, and update $F_{k + 1}, m_{k + 1}$ using the following equations:
$F_{k + 1} = \{\begin{cases} F_{k} \cup \{x^{k}\} ∖ D_{k}, & flag = 1, \\ F_{k}, & flag = 0, \end{cases}$
m_k+1 = min{m_k + 1, M}.
Step 5. Utilize a specific technique to update a symmetric, positive definite matrix H_k+1 from H_k. Set k = k + 1, go to step 1.
Step 6. (Feasibility Restoration Phase) Generate trial points $\overset{\land}{x}$ that satisfy (A1) and (A2) in the feasibility restoration phase. Set $x^{k + 1} = \overset{\land}{x}$ , update $F_{k + 1}$ by (22), and set m_k+1 = min{m_k + 1, M}. Set k = k + 1, go to step 1.

3. Global Convergence

In the reminder of this paper, we need to establish the global convergence of Algorithm 1 for NSLDP (1). We should make the following general assumptions.

Assumption B

(B1) The functions f(x), c(x), and G(x) are twice continuous differentiable on an open set containing $X$ .
(B2) The sequence {x^k} generated by Algorithm 1 lies in a nonempty compact set $X \subset R^{n}$ .
(B3) The matrix H_k is uniformly positive definite; that is, there exists constants a, b > 0 such that 24 $\begin{matrix} a {‖d‖}^{2} \leq d^{T} H_{k} d \leq b {‖d‖}^{2}, \end{matrix}$
for any $< i > d < / i > \in R^{< i > n < / i >}$ .
(B4) The feasible points in NLSDP (1) satisfy the MFCQ condition.

Statement

Remark 1.

Without loss of generality, we assume ‖∇²f(x)‖ ≤ b, ‖D²h(x)‖ ≤ b, ${‖D^{2} G (x)‖}_{F} \leq b$ for any $x \in X$ from Assumption B.

To describe the proof of the following lemmas and theorems, we need to introduce a set: 25 $\begin{matrix} Λ = \{k ∣ F_{k + 1} \neq F_{k}\} . \end{matrix}$

Statement

Lemma 1.

Considering the sequence {x^k} generated by the algorithm, if $F_{k}$ is updated finitely, that is, ∣Λ | <∞ and {f(x^k)} has a lower bound, then 26 $\begin{matrix} \lim_{k ⟶ \infty} h (x^{k}) = 0 . \end{matrix}$

Statement

Proof 1.

It follows from ∣Λ | <∞ that there exists an index k₁ such that the filter $F_{k}$ will not be updated for any k > k₁. In view of the algorithm mechanism, the fact is that the point x^k+1 = x^k + t_kd^k satisfies (20) and (19). In addition, it follows from (19) that 27 $\begin{matrix} \max \{f (x^{k}), \sum_{i = 0}^{m_{k} - 1} α_{k, i} f (x^{k - i})\} - f (x^{k + 1}) \geq σ t_{k} pred (x^{k}) . \end{matrix}$

First, we show that the following inequality holds by induction for any k ≥ k₁ + 1: 28 $\begin{matrix} f (x^{k}) < \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{i = k_{1}}^{k - 2} θ_{i} + σ θ_{k - 1} < \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{i = k_{1}}^{k - 1} θ_{i}, \end{matrix}$ where $\overset{\land}{f} (x^{k_{1}}) = \max \{f (x^{k_{1}}), \sum_{i = 0}^{m_{k_{1}} - 1} α_{k_{1}, i} f (x^{k_{1} - i})\}, θ_{*} = t_{*} \nabla f {(x^{*})}^{T} d^{*}$ , and ∗ is the corresponding indicator. Furthermore, we know that θ_∗ < 0 from (20). Assume k = k₁ + 1, then (27) and $01 < \bar{α} <$ imply that 29 $\begin{matrix} f (x^{k_{1} + 1}) \leq \overset{\land}{f} (x^{k_{1}}) + σ θ_{k_{1}} < \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ θ_{k_{1}}, \end{matrix}$ which shows that (28) holds. Assume k = j(>k₁ + 1), and (28) holds. We then have the following inequality: 30 $\begin{matrix} f (x^{j}) < \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{i = k_{1}}^{j - 2} θ_{i} + σ θ_{j - 1} < \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{i = k_{1}}^{j - 1} θ_{i} . \end{matrix}$ Assume k = j + 1, we need to show that (28) holds. According to (27), we get 31 $\begin{matrix} f (x^{j + 1}) \leq \max \{f (x^{j}), \sum_{i = 0}^{m_{j} - 1} α_{j, i} f (x^{j - i})\} + σ θ_{j} . \end{matrix}$

When $f (x^{j}) \geq \sum_{i = 0}^{m_{j} - 1} α_{j, i} f (x^{j - i})$ holds, together with (30) and (31) and $01 < \bar{α} <$ , we get 32 $\begin{matrix} f (x^{j + 1}) \leq f (x^{j}) + σ θ_{j} < \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{i = k_{1}}^{j - 1} θ_{i} + σ θ_{j} < \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{i = k_{1}}^{j - 1} θ_{i} + \bar{α} σ θ_{j} = \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{i = k_{1}}^{j} θ_{i}, \end{matrix}$ which implies that (28) holds. When $f (x^{j}) < \sum_{i = 0}^{m_{j} - 1} α_{j, i} f (x^{j - i})$ holds, together with $\sum_{i = 0}^{r} α_{j, i} = 101, < \bar{α} \leq α_{j, i} <$ , r = m_j − 1, (30) and (31), we obtain 33 $\begin{matrix} f (x^{j + 1}) \leq \sum_{i = 0}^{r} α_{j, i} f (x^{j - i}) + σ θ_{j} \leq \sum_{i = 0}^{r} α_{j, i} (\overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{l = k_{1}}^{j - i - 2} θ_{l} + σ θ_{j - i - 1}) + σ θ_{j} \\ = α_{j, 0} (\overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{l = k_{1}}^{j - r - 2} θ_{l} + \bar{α} σ \sum_{l = j - r - 1}^{j - 2} θ_{l} + σ θ_{j - 1}) \\ + α_{j, 1} (\overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{l = k_{1}}^{j - r - 2} θ_{l} + \bar{α} σ \sum_{l = j - r - 1}^{j - 3} θ_{l} + σ θ_{j - 2}) \\ ⋮ \\ + α_{j, r} (\overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{l = k_{1}}^{j - r - 2} θ_{l} + σ θ_{j - r - 1}) + σ \bar{α} θ_{j} \\ < \sum_{i = 0}^{r} α_{j, i} (\overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{l = k_{1}}^{j - r - 2} θ_{l}) + \bar{α} σ \sum_{l = j - r - 1}^{j - 2} θ_{l} + \bar{α} σ θ_{j - 1} + σ \bar{α} θ_{j} = \overset{\land}{f} (x^{k_{1}}) + \bar{α} σ \sum_{l = k_{1}}^{j} θ_{l}, \end{matrix}$ which implies that (28) holds. From this fact, the lower bound of {f(x^k)}, and (28), it follows that $\sum_{i = k_{1}}^{k - 1} t_{i} \nabla f {(x^{i})}^{T} d^{i} < \infty$ for sufficiently large k, which indicates that 34 $\begin{matrix} \lim_{k ⟶ \infty} t_{k} \nabla f {(x^{k})}^{T} d^{k} = 0 . \end{matrix}$

Thus, this equation and $t_{k} pred (x^{k}) > h {(x^{k})}^{s_{h}}$ deduce that lim_k⟶∞h(x^k) = 0.

Statement

Lemma 2.

Considering the sequence {x^k} generated by the algorithm and $F_{k}$ be updated infinitely, that is, ∣∧∣ = +∞, then lim_k⟶∞h(x^k) = 0.

Statement

Proof 2.

The proof is by contradiction. Assume that this result is not true, which means that there exits an infinite index set $K \subset \land$ and 35 $\begin{matrix} h (x^{k}) \geq ϵ, \end{matrix}$ holds for some ϵ > 0. Considering the point x^k or (h_c(x^k), h_G(x^k), f(x^k)) is added to the filter at each iterate $k \in K$ , which implies that no other point can be added to the filter at a later stage within the cube: 36 $\begin{matrix} Φ = [h_{c} (x^{k}) - (1 - β_{c}) ϵ, h_{c} (x^{k})] \times [h_{G} (x^{k}) - (1 - β_{G}) ϵ, h_{G} (x^{k})] \times [f (x^{k}) - (1 - γ_{f}) ϵ, f (x^{k})] . \end{matrix}$

The volume of each of these cubes is at least (1 − β_c)(1 − β_G)(1 − γ_f)ϵ³. Therefore, we know that Φ is completely covered by at most a finite number of such cubes, which contradicts the fact that the index of the infinite set $K$ satisfies (35).

Statement

Lemma 3.

Let Assumption B hold, if the relation pred(x^k) ≥ ϵ₁ holds, there exists a constant $\bar{t} \in (01,]$ such that the nonmonotonically sufficient descent condition holds, that is, nared(x^k) ≥ σtpred(x^k) for all $t \in (0, \bar{t}]$ .

Statement

Proof 3.

By Taylor’s expansion theorem, we deduce that 37 $\begin{matrix} f (x^{k} + t d^{k}) = f (x^{k}) + t \nabla f {(x^{k})}^{T} d^{k} + \frac{1}{2} {(d^{k})}^{T} \nabla^{2} f (ζ) d^{k}, \end{matrix}$ where ζ is between x^k and x^k + td^k. Let $\bar{t} = \min \{(2 (1 - σ) ϵ_{1}) / (b {‖d^{k}‖}^{2}), 1\}$ , for all $t \in (0, \bar{t}]$ , the above equation, together with and (17) and (18), gives 38 $\begin{matrix} nared (x^{k}) - σ t pred (x^{k}) = \max \{f (x^{k}), \bar{f} (x^{k})\} - f (x^{k} + t d^{k}) - σ t pred (x^{k}) \\ \geq t pred (x^{k}) - σ t pred (x^{k}) - \frac{1}{2} {(d^{k})}^{T} \nabla^{2} f (ζ) d^{k} \\ \geq (1 - σ) t ϵ_{1} - \frac{1}{2} t^{2} b {‖d^{k}‖}^{2} \geq 0 . \end{matrix}$

The proof is completed.

Statement

Lemma 4.

Let x^k be a feasible point of NLSDP (1), i.e., h(x^k) = 0, and d^k be an optimal solution of subproblem QSD (x^k, H_k) (12). Then, $pred (x^{k}) \geq ξ {(d^{k})}^{T} H_{k} d^{k}$ holds.

Statement

Proof 4.

We give the KKT conditions of subproblem QSD (x^k, H_k) (12): 39 $\begin{matrix} \nabla f (x^{k}) + H_{k} d^{k} + D c {(x^{k})}^{T} λ^{k} + D G {(x^{k})}^{*} Y_{k} = 0, \\ c (x^{k}) + D c (x^{k}) d^{k} = 0, \\ G (x^{k}) + D G (x^{k}) d^{k} ⪯ 0, \\ Y_{k} ⪰ 0, \\ tr (Y_{k} (G (x^{k}) + D G (x^{k}) d^{k}) = 0 . \end{matrix}$

Thus, from (39), we get 40 $\begin{matrix} \nabla f {(x^{k})}^{T} d^{k} = - {(d^{k})}^{T} H_{k} d^{k} - {(λ^{k})}^{T} D c (x^{k}) d^{k} - ⟨D G (x^{k}) d^{k}, Y_{k}⟩ \\ = - {(d^{k})}^{T} H_{k} d^{k} + c {(x^{k})}^{T} λ^{k} + ⟨G (x^{k}), Y_{k}⟩, \end{matrix}$ which, together with h(x^k) = 0 and ξ ∈ (0, 1], yields $p r e d (x^{k}) \geq {(d^{k})}^{T} H_{k} d^{k} \geq ξ {(d^{k})}^{T} H_{k} d^{k}$ .

Statement

Lemma 5.

Let Assumption B hold, for any k, we have $τ_{k} = \min \{h (\bar{x}) ∣ \bar{x} \in F_{k}\} > 0$ .

Statement

Proof 5.

We prove this result by induction. Assume that k = 0, we have τ₀ = 2u > 0 in Step 0 of Algorithm 1. Assume that k = j, τ_j > 0 holds. Now, we want to show that τ_j+1 > 0 for k = j + 1. We consider the following two cases. (1) h(x^j) > 0. If x^j is added to $F_{j}$ , then τ_j+1 > 0 holds from (22). Otherwise, τ_j+1 = τ_j > 0 holds because the filter is not updated. (12) h(x^j) = 0. From Lemma 3.4, we get $pred (x^{j}) \geq ξ {(d^{j})}^{T} H_{j} d^{j}$ , which implies that $t_{j} pred (x^{j}) > h {(x^{j})}^{s_{h}}$ holds. Combining Lemma 3.3, the nonmonotonically sufficient descent condition holds, i.e., (19). Therefore, from Steps 3.4 and 4 of the algorithm, the filter cannot be updated, i.e., $F_{j + 1} = F_{j}$ , so we get τ_j+1 = τ_j > 0.

Statement

Lemma 6.

Let Assumption B holds, the line search at Step 3 of the algorithm is well defined.

Statement

Proof 6.

The algorithm stops from the mechanism of the algorithm if d^k = 0, so we discuss the conclusion based on the fact that subproblem QSD (x^k, H_k) is compatible.

We proceed by contradiction and assume that the line search does not terminate in finite steps. Thus, we get t⟶0 from the mechanism of the algorithm. Suppose that h(x^k) = 0, using Taylor’s expansion theorem, we have 41 $\begin{matrix} h_{c} (x^{k} + t d^{k}) = ‖c (x^{k}) + t D c (x^{k}) d^{k} + \frac{1}{2} t^{2} {(d^{k})}^{T} D^{2} c (ζ_{1}) d^{k}‖ \\ \leq (1 - t) {‖c (x^{k}) ‖+ \frac{1}{2} t^{2} b‖ d^{k}‖}^{2} \\ = \frac{1}{2} t^{2} b {‖d^{k}‖}^{2}, \end{matrix}$ where ζ₁ is between x^k and x^k + td^k. If $t^{2} \leq (2 τ_{k}) / (b {‖d^{k}‖}^{2})$ , then h(x^k + td^k) ≤ τ_k, so x^k + td^k is accepted by the filter $F_{k}$ . By Lemma 3.4, $pred (x^{k}) \geq ξ {(d^{k})}^{T} H_{k} d^{k}$ holds, which yields $t pred (x^{k}) > h {(x^{k})}^{s_{h}}$ . By Lemma 3.3, the nonmonotonically sufficient descent condition holds, so from Step 3.4, the algorithm exits the line search. Thus, this is a contradict. Suppose also that h(x^k) > 0. We have the fact that $t < t_{k}^{\min}$ because t⟶0, which means that the feasible restoration phase invoked. This is also a contradiction.

Statement

Theorem 1.

Let Assumption B holds, there is one of the following conclusions holds:

(C1) The feasible restoration phase does not find a trial point $\overset{\land}{x}$ satisfying (A1) and (A2).
(C2) The algorithm terminates at a finite step, i.e., there exists an iterate x^k that is a KKT point of NLSDP (1).
(C3) The sequence {x^k} generated by the algorithm converges to an accumulation point x^∗, which is a feasible point of NLSDP (1), and x^∗ is a KKT point.

Statement

Proof 7.

Assume that neither (C1) nor (C2) occurs. We need to prove that (C3) holds below. Now, considering the following two cases:

Case 1: ∣Λ | <∞. By Lemma 3.1, we know that lim_k⟶∞h(x^k) = 0 = h(x^∗), i.e., x^∗ is a feasible point. In addition, by Lemma 3.3, there exists a constant $\bar{t} > 0$ , implying $t_{k} \geq ρ \bar{t}$ . This, together with (20), yields 42 $\begin{matrix} t_{k} \nabla f {(x^{k})}^{T} d^{k} \leq - t_{k} ξ {(d^{k})}^{T} H_{k} d^{k} \leq - ρ \bar{t} ξ a {‖d^{k}‖}^{2} . \end{matrix}$

Furthermore, lim_k⟶0‖d^k‖ = 0 holds from the above equality and (34), so x^∗ is a KKT point.

Case 2: ∣Λ | = ∞. By Lemma 3.2, lim_k⟶∞h(x^k) = 0 = h(x^∗), that is, x^∗ is a feasible point. Suppose there exists an infinite set of index $K_{2}$ and a constant ϵ₂ > 0 such that ‖d^k‖ ≥ ϵ₂ for any $k \in K_{2}$ . This, together with Assumption B (39), gives 43 $\begin{matrix} pred (x^{k}) - ξ {(d^{k})}^{T} H_{k} d^{k} = {(d^{k})}^{T} H_{k} d^{k} - c {(x^{k})}^{T} λ^{k} - ⟨Y_{k}, G (x^{k})⟩ - ξ {(d^{k})}^{T} H_{k} d^{k} \\ \geq (1 - ξ) a {‖d^{k}‖}^{2} - \max \{‖λ^{k}‖, t r (Y_{k})\} h (x^{k}) \\ \geq (1 - ξ) a ϵ_{2}^{2} - \max \{‖λ^{k}‖, t r (Y_{k})\} h (x^{k}) . \end{matrix}$

When k is sufficiently large, together with ξ ∈ (0, 1) and h(x^k)⟶0, we have $pred (x^{k}) \geq ξ {(d^{k})}^{T} H_{k} d^{k}$ .

Similarly, by Assumptions B (39), we have 44 $\begin{matrix} t_{k} pred (x^{k}) - h {(x^{k})}^{s_{h}} = t_{k} {(d^{k})}^{T} H_{k} d^{k} - t_{k} c {(x^{k})}^{T} λ^{k} - t_{k} ⟨Y_{k}, G (x^{k})⟩ - h {(x^{k})}^{s_{h}} \\ \geq t_{k} a {‖d^{k}‖}^{2} - t_{k} \max \{‖λ^{k}‖, t r (Y_{k})\} h (x^{k}) - h {(x^{k})}^{s_{h}} \\ > ρ \bar{t} a ϵ_{2}^{2} - \max \{‖λ^{k}‖, t r (Y_{k})\} h (x^{k}) - h {(x^{k})}^{s_{h}} . \end{matrix}$

When k is sufficiently large and h(x^k)⟶0, we have 45 $\begin{matrix} t_{k} pred (x^{k}) > h {(x^{k})}^{s_{h}}, \end{matrix}$ which implies nared(x^k) ≥ t_kσpred(x^k) from Lemma 3.3. Thus, from Steps 3.4 and 4 in the algorithm, we know that the filter cannot be updated. This is a contradiction. Therefore, lim_k⟶0‖d^k‖ = 0 and x^∗ is a KKT point.

4. Numerical Experiments

In this section, to test the performance of the proposed algorithm in Section 2, a Matlab(2014a) code was written. The subproblem QSD(x^k, H_k) (12) was implemented using SDPT3 solver as described in [25]. The running environment was set as Windows 10 (64 bits), RAM: 8G, CPU 3.60 GHz. At each iteration, the matrix H_k is updated using the following modified BFGS formula [10]: 46 $\begin{matrix} H_{k + 1} = H_{k} - \frac{H_{k} Δ x^{k} {(Δ x^{k})}^{T} H_{k}}{{(Δ x^{k})}^{T} H_{k} Δ x^{k}} + \frac{y^{k} {(y^{k})}^{T}}{{(Δ x^{k})}^{T} y^{k}}, \end{matrix}$ where Δx^k = x^k+1 − x^k, y^k = ψ_kΔL^k + (1 − ψ_k)H_kΔx^k, Δ_xL^k = ∇_xL(x^k+1, λ^k, Y_k) − ∇_xL(x^k, λ^k, Y_k), and 47 $\begin{matrix} ψ_{k} ≔ \{\begin{cases} 1, & if {(Δ x^{k})}^{T} Δ L^{k} \geq 0.2 {(Δ x^{k})}^{T} H_{k} Δ x^{k}, \\ \frac{{(0.8 Δ x^{k})}^{T} H_{k} Δ x^{k}}{{(Δ x^{k})}^{T} (H_{k} Δ x^{k} - Δ L^{k})}, & Otherwise . \end{cases} \end{matrix}$

For the numerical experiment, the following parameters in the algorithm are set as 48 $\begin{matrix} β_{c} = 0.990.990.010.010.30.10.30.53, β_{G} =, γ_{f} =, γ_{t} =, ξ =, σ =, s_{h} =, ρ =, M = . \end{matrix}$

Furthermore, Algorithm 1 stops if ‖d^k‖ ≤ 10⁻⁴ or if the upper bound of iterations is exceeded.

Now, we consider the following problem.

Statement

Problem 1.

The Rosen–Suzuki problem, as presented in [12], is 49 $\begin{matrix} \min x_{1}^{2} + x_{2}^{2} + 255217 x_{3}^{2} + x_{4}^{2} - x_{1} - x_{2} - x_{3} + x_{4}, \\ s . t . (\begin{array}{l} x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2} + x_{1} - x_{2} + x_{3} - x_{4} - 8 \\ x_{1}^{2} + 229 x_{2}^{2} + x_{3}^{2} + x_{4}^{2} - x_{1} - x_{4} - \\ 225 x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{1} - x_{2} - x_{4} - \end{array}) = 0, \\ (\begin{array}{c} - x_{2} - x_{3} & 0 & 0 & 0 \\ 0 & 2 x_{4} & - x_{1} & 0 \\ 0 & - x_{1} & - x_{1} & 0 \\ 0 & 0 & 0 & - x_{2} - x_{3} \end{array}) ⪯ 0 . \end{matrix}$

The optimal solution is x^∗ = (0, 1, 2, −1)^T. The experiment results for Problem 1 are shown in Table 1. $x_{0}^{T}$ stands for the initial points. Nf, Ndf, ri, and Iter are the numbers of evaluation of f(x), ∇f(x), the feasibility restoration phase, and iterations, respectively. h^∗ and f^∗ are the optimal value of the measure of constraint violation and objective function, respectively. Time stands for the time of calculation in seconds.

Table 1 Numerical results for Rosen–Suzuki problem.

$x_{0}^{T}$	Nf	Ndf	Ri	Iter	h^∗	f^∗	Time
(0, 0, 0, 0)	9	8	0	7	1.835e − 06	−4.400e + 01	1.212e + 00
(1, 1, 1, 1)	8	7	0	6	7.483e − 07	−4.400e + 01	1.025e + 00
(−1, −1, −1, −1)	10	10	1	9	1.047e − 09	−4.400e + 01	1.410e + 01
(2, 2, 2, 2)	10	8	0	7	2.143e − 07	−4.400e + 01	1.111e + 00
(−2, −2, −2, −2)	10	9	1	8	1.082e − 05	−4.400e + 01	2.465e + 00
(3, 3, 3, 3)	10	9	0	8	8.265e − 08	−4.400e + 01	1.285e + 00
(−3, −3, −3, −3)	14	13	2	12	6.624e − 06	−4.400e + 01	3.945e + 00
(4, 4, 4, 4)	12	10	0	9	4.979e − 07	−4.400e + 01	1.416e + 00
(−4, −4, −4, −4)	9	9	1	8	1.561e − 05	−4.400e + 01	2.695e + 00
(5, 5, 5, 5)	9	9	0	8	6.052e − 07	−4.400e + 01	1.273e + 00
(−5, −5, −5, −5)	12	12	1	11	5.704e − 07	−4.400e + 01	1.917e + 00
(10, 10, 10, 10)	10	10	0	9	5.960e − 06	−4.400e + 01	1.381e + 00
(−10, −10, −10, −10)	14	11	1	10	4.013e − 07	−4.400e + 01	2.664e + 00
(20, 20, 20, 20)	12	12	0	11	6.180e − 09	−4.400e + 01	1.705e + 00
(−20, −20, −20, −20)	15	13	1	12	8.048e − 08	−4.400e + 01	3.375e + 00
(30, 30, 30, 30)	12	12	0	11	1.863e − 08	−4.400e + 01	1.696e + 00
(−30, −30, −30, −30)	10	9	1	8	4.344e − 06	−4.400e + 01	4.093e + 00
(40, 40, 40, 40)	12	12	0	11	3.186e − 07	−4.400e + 01	1.763e + 00
(−40, −40, −40, −40)	15	12	1	11	4.264e − 08	−4.400e + 01	4.335e + 00
(50, 50, 50, 50)	12	12	0	11	4.661e − 08	−4.400e + 01	1.739e + 00
(−50, −50, −50, −50)	14	13	1	12	2.339e − 05	−4.400e + 01	4.208e + 00

Statement

Problem 2.

The basic static output feedback problem (SOFP), as presented in [23, 26], is 50 $\begin{matrix} \min_{F, L} t r (L Q_{F}), \\ s . t . A_{F} L + L A_{F}^{T} + I = 0, \\ A_{F} L + L A_{F}^{T} ⪯ 00, L ≻, \end{matrix}$ where A_F = A + BFC, Q_F = C^TF^TFC + I, and the data A, B, C are extracted from COMPl_eib [26]. In the problem SOFP, the variables are F and L, where L is symmetric and real, but F, associated with SOF control law, is generally not square. The initial points are set as $L = I \in R^{n_{x} \times n_{x}}$ and $F = O \in R^{n_{u} \times n_{y}}$ , where n_x, n_u, and n_y are given integers extrated from COMPl_eib [26]. The experiment results for Problem 2 are listed in Table 2, where “problem” refers to the name of the example in COMPl_eib.

Table 2 Numerical results for SOFP.

problem	n	p	m	Nf	Ndf	ri	Iter	h^∗	f^∗	Time
AC1	24	15	5	36	36	0	35	1.136e − 08	2.002e + 01	6.407e + 00
AC2	24	15	5	36	36	0	35	1.136e − 08	2.002e + 01	6.546e + 00
AC3	23	15	5	32	32	0	31	2.219e − 09	2.184e + 01	4.824e + 00
AC4	12	10	4	70	67	6	66	1.048e − 06	1.198e + 01	1.883e + 01
AC6	36	28	7	24	24	0	23	7.480e − 08	1.090e + 01	5.079e + 00
AC7	47	45	9	40	32	1	31	4.689e − 06	1.559e + 02	1.774e + 01
AC8	50	45	9	32	32	1	31	1.898e − 09	1.536e + 01	1.066e + 01
AC9	75	55	10	155	130	1	129	2.366e − 09	2.140e + 01	4.584e + 01
AC15	16	10	4	55	53	0	52	1.095e − 09	1.590e + 02	8.706e + 00
AC16	18	10	4	38	34	0	33	5.247e − 09	1.512e + 02	5.612e + 00
AC17	12	10	4	23	23	0	22	1.391e − 07	1.462e + 01	3.796e + 00
HE2	14	10	4	17	17	0	16	3.685e − 08	1.187e + 01	3.028e + 00
HE3	60	36	8	152	144	0	143	2.604e − 10	8.519e + 02	3.094e + 01
REA1	16	10	4	43	43	0	42	5.084e − 08	3.483e + 00	6.964e + 00
REA2	14	10	4	37	37	1	36	2.756e − 09	3.773e + 00	6.464e + 00
REA3	81	78	12	41	41	2	40	1.486e − 10	1.504e + 02	1.341e + 01
DIS1	52	36	8	29	29	0	28	1.374e − 08	1.535e + 01	5.830e + 00
DIS2	10	6	3	30	30	0	29	6.697e − 09	8.595e + 00	4.568e + 00
DIS3	37	21	6	39	39	0	38	2.606e − 09	5.986e + 00	7.532e + 00
DIS4	45	21	6	72	70	0	69	5.427e − 09	3.957e + 00	1.490e + 01
TG1	59	55	10	60	59	2	58	4.359e − 09	4.948e + 02	1.697e + 01
AGS	82	78	12	12	12	0	11	7.153e − 08	4.942e + 01	4.336e + 00
BDT1	75	66	11	67	39	0	38	1.180e − 11	8.831e + 02	1.091e + 01
UWV	40	36	8	14	14	0	13	2.542e − 06	2.093e + 00	3.067e + 00
IH	341	231	21	31	31	0	30	3.648e − 09	4.229e + 01	1.044e + 02
CSE1	230	210	20	20	20	1	19	5.968e − 10	7.669e + 01	3.781e + 01
EB1	56	55	10	18	18	0	17	1.041e − 10	8.713e + 02	4.312e + 00
EB2	56	55	10	18	18	0	17	1.041e − 10	8.713e + 02	4.405e + 00
EB3	56	55	10	18	17	1	16	7.468e − 11	1.549e + 03	8.402e + 00
EB4	211	210	20	21	21	1	20	1.381e − 11	8.892e + 04	5.739e + 01
TF1	36	28	7	82	70	1	69	1.653e − 09	2.937e + 02	1.467e + 01
PSM	34	28	7	27	27	0	26	9.085e − 08	3.236e + 00	5.223e + 00
NN2	4	3	2	12	12	0	11	2.521e − 07	3.464e + 00	1.511e + 00
NN4	16	10	4	38	38	0	37	1.115e − 08	5.407e + 00	5.926e + 00
NN8	10	6	3	23	23	0	22	9.158e − 08	4.438e + 00	3.103e + 00
NN11	151	136	16	15	15	0	14	1.519e − 08	2.758e + 02	1.349e + 01
NN15	10	6	3	38	26	0	25	2.258e − 08	4.695e + 02	3.952e + 00
NN16	52	36	8	51	47	0	46	3.581e − 08	1.536e + 01	1.068e + 01
HF2D10	21	15	5	129	129	0	128	4.070e − 11	2.212e + 00	2.237e + 01
HF2D11	21	15	5	94	94	0	93	1.193e − 11	6.163e − 01	1.524e + 01
HF2D12	23	15	5	188	188	0	187	1.540e − 13	1.561e + 00	3.256e + 01
HF2D13	23	15	5	61	61	0	60	6.163e − 09	5.109e − 01	1.076e + 01
HF2D14	23	15	5	97	97	0	96	1.430e − 08	4.556e + 00	1.653e + 01
HF2D15	23	15	5	62	62	0	61	8.160e − 08	1.493e + 00	1.156e + 01
HF2D18	19	15	5	70	70	0	69	5.408e − 09	1.309e + 01	1.180e + 01
CM1	212	210	20	75	60	1	59	3.509e − 12	1.723e + 04	1.892e + 02
TMD	29	21	6	90	86	0	85	1.165e − 08	4.798e + 01	1.491e + 01
DLR1	59	55	10	37	26	0	25	5.094e − 09	2.981e + 03	6.228e + 00
ROC7	21	15	5	94	86	2	85	9.906e − 10	4.877e + 01	1.405e + 01

Statement

Problem 3.

The Gaussian channel capacity problem, as presented in [27], is 51 $\begin{matrix} \min \frac{1}{2} \sum_{i = 1}^{n} \log (1 + \frac{x_{i}}{r_{i} + a_{i} x_{i}}) \\ s . t . \frac{1}{n} \sum_{i = 1}^{n} \leq P, x_{i} \geq 012, =,, \dots, n . \end{matrix}$

In this experiment, P is set to 1. The values r_i and a_i are set to uniform random numbers between 0 and 1. This problem is solved with n = 5, 10, 15, 20, …, 40. We take the initial point as x_i = 10, fro i = 1, 2, …, n. The numerical results are shown in Table 3.

Table 3 Numerical results for Gaussian channel capacity problem.

n	m	Nf	Ndf	ri	Iter	h^∗	f^∗	Time
5	6	5	5	0	4	0	8.394e − 09	1.108e + 00
10	11	4	4	0	3	0	2.256e − 08	1.747e + 00
15	16	8	8	0	7	0	7.531e − 09	8.158e + 00
20	21	5	5	0	4	0	3.405e − 08	9.317e + 00
25	26	5	5	0	4	0	2.286e − 09	1.707e + 01
30	31	5	5	0	4	0	1.640e − 08	3.369e + 01
35	36	4	4	0	3	0	4.153e − 08	4.024e + 01
40	41	5	5	0	4	0	2.614e − 10	8.168e + 01

Statement

Problem 4.

The minimization of the minimal eigenvalue problem, as presented in [27], is 52 $\begin{matrix} \min λ_{\min} (M (q)), \\ s . t . q \in Q, \end{matrix}$ where q ∈ Rⁿ, Q ⊂ Rⁿ, and M ∈ S^l are a function of q, which can be formulated as the following problem: 53 $\begin{matrix} \min t r (\prod M (q)), \\ s . t . t r (\prod) = 1, \\ \prod ⪰ 0, \\ q \in Q . \end{matrix}$ where ∏∈S^l is an additional matrix variable. In this experiment, we set q = (x, y)^T and M = xyA + xB + yC with given A, B, C ∈ S^l. The elements of matrix A, B, C ∈ S^l are set from uniform random numbers in [−5, 5], and the variable q is set to [−1, 1] × [−1, 1]. This problem is solved with l = 10, 20, …, 80. We take the initial point as ∏ = I ∈ S^l, x = y = 0. The numerical results are shown in Table 4, where n = ((1 + l)l/2) + 2, p = 1, and m = l + 4.

Table 4 Numerical results for the minimal eigenvalue problem.

l	n	p	m	Nf	Ndf	ri	Iter	h^∗	f^∗	Time
10	57	1	14	7	6	0	5	1.110223e − 16	−2.661e + 01	1.319e + 00
20	212	1	24	8	7	0	6	1.110e − 16	−4.089e + 01	4.381e + 00
30	467	1	34	10	9	0	8	1.354e − 14	−5.087e + 01	3.020e + 01
40	822	1	44	10	9	0	8	1.790e − 13	−5.531e + 01	1.190e + 02
50	1277	1	54	7	6	0	5	2.131e − 14	−6.783e + 01	2.330e + 02
60	1832	1	64	10	9	0	8	1.100e − 13	−7.049e + 01	1.089e + 03
70	2487	1	74	5	5	0	4	3.530e − 14	−7.754e + 01	1.389e + 03
80	3242	1	84	8	7	0	6	2.737e − 13	−8.494e + 01	4.803e + 03

5. Conclusion

In this paper, we develop a three-dimensional filter SSDP algorithm with a feasible restoration phase for solving NLSDP problems, expanding on the SQP method well-known in nonlinear optimization. The new algorithm incorporates acceptance criteria for the three-dimensional filter and nonmonotonically sufficient descent condition, making it easy to adopt reasonable trial points. Additionally, the backtracking line search technique in the new algorithm ensures the descent of the objective function or the improvement of constraint violations. Furthermore, under certain assumptions, we prove that the new algorithm is well defined and converges globally. Finally, preliminary numerical results show that it is effective.

Data Availability Statement

The data that support the findings of this study are available from the corresponding author upon reasonable request.

Disclosure

Although we have received funding from the Natural Science Foundation in Guangxi Province, P.R. China (grant number 2024GXNSFAA010478), and Guangdong Province Philosophy and Social Science Planning Project (grant number GD24XGL029), given that our research pertains only to the fundamental theories in mathematics, we confirm that the results of this study have not been influenced by the funding bodies in any way.

Conflicts of Interest

The authors declare no conflicts of interest.

Funding

This research was funded by the Natural Science Foundation in Guangxi Province, P.R. China (grant number 2024GXNSFAA010478), and Guangdong Province Philosophy and Social Science Planning Project (grant number GD24XGL029).

Acknowledgments

References

1 Apkarian P., Noll D., and Tuan H. D., Fixed-Order H_∞ Control Design via a Partially Augmented Lagrangian Method, International Journal of Robust and Nonlinear Control. (2003) 13, 1137–1148.

2 Roche J. R., Herskovits J., Bazán E., and Zúñiga A., A Feasible Direction Algorithm for General Nonlinear Semidefinite Programming, Structural and Multidisciplinary Optimization. (2017) 55, no. 4, 1261–1279, https://doi.org/10.1007/s00158-016-1564-5, 2-s2.0-84983731347.

3 Konno H., Kawadai N., and Wu D., Estimation of Failure Probability Using Semi-Definite Logit Model, Computational Management Science. (2003) 1, 59–73, https://doi.org/10.1007/s10287-003-0001-6.

4 Fares B., Noll D., and Apkarian P., Robust Control via Sequential Semidefinite Programming, Proceedings of the 36th IEEE Conference on Decision and Control, 2002, Las Vegas, NV, USA.

5 Correa R. and Ramirez H. C., A Global Algorithm for Nonlinear Semidefinite Programming, SIAM Journal on Optimization. (2004) 15, 303–318.

6 Yamakawa Y. and Yamashita N., A Two-Step Primal-Dual Interior Point Method for Nonlinear Semidefinite Programming Problmes and Its Superlinear Convergence, Journal of the Operations Research Society of Japan. (2014) 57, no. 3-4, 105–127, https://doi.org/10.15807/jorsj.57.105, 2-s2.0-85028726199.

7 Christian K., Christian N., Hirokazu K., and Masao F., Successive Linearization Methods for Nonlinear Semidefinite Programs, Computational Optimization and Applications. (2005) 31, no. 3, 251–273, https://doi.org/10.1007/s10589-005-3231-4, 2-s2.0-23944460017.

8 Leibfritz F. and Mostafa E. M. E., An Interior Point Constrained Trust Region Method for a Special Class of Nonlinear Semidefinite Programming Problems, SIAM Journal on Optimization. (2002) 12, no. 4, 1048–1074, https://doi.org/10.1137/s1052623400375865, 2-s2.0-0036434767.

9 Ernesto G. et al., An Augmented Lagrangian Algorithm for Nonlinear Semidefinite Programming Applied to the Covering Problem, Computational and Applied Mathematics. (2019) 39, 1–21.

10 Zhao Q. and Chen Z., An SQP-Type Method With Superlinear Convergence for Nonlinear Semidefinite Programming, Asia Pacific Journal of Operational Research. (2018) 35, no. 03, https://doi.org/10.1142/s0217595918500094, 2-s2.0-85040662894.

11 Li J. L. and Zhang H., A Superlinearly Convergent SSDP Algorithm for Nonlinear Semidefinite Programming, Journal of Inequalities and Applications. (2019) 2019, 1–21, https://doi.org/10.1186/s13660-019-2171-y, 2-s2.0-85070817446.

12 Zhao Q., Chen Z., and Hager W. W., A Line Search Exact Penalty Method for Nonlinear Semidefinite Programming, Computational Optimization and Applications. (2020) 75, no. 2, 467–491, https://doi.org/10.1007/s10589-019-00158-x.

13 Fu W. and Chen Z., A Line Search SQP-Type Method With Bi-Object Strategy for Nonlinear Semidefinite Programming, Acta Mathematicae Applicatae Sinica, English Series. (2022) 38, no. 2, 388–409, https://doi.org/10.1007/s10255-022-1081-9.

14 Fu W. and Chen Z., A Globally Convergent SQP-Type Method With Least Constraint Violation for Nonlinear Semidefinite Programming, Optimization. (2024) 74, no. 10, 1–35, https://doi.org/10.1080/02331934.2024.2345397.

15 Fletcher R. and Leyffer S., Nonlinear Programming Without a Penalty Function, Mathematical Programming: Series A. (2002) 91, no. 2, 239–269, https://doi.org/10.1007/s101070100244, 2-s2.0-0001556338.

16 Gu C. and Zhu D., A Non-Monotone Line Search Multidimensional Filter-SQP Method for General Nonlinear Programming, Numerical Algorithms. (2011) 56, no. 4, 537–559, https://doi.org/10.1007/s11075-010-9403-z, 2-s2.0-79952281384.

17 Shen C., Xue W., and Pu D., Global Convergence of a Tri-Dimensional Filter SQP Algorithm Based on the Line Search Method, Applied Numerical Mathematics. (2009) 59, no. 2, 235–250, https://doi.org/10.1016/j.apnum.2008.01.005, 2-s2.0-56249098697.

18 Huang A., A Filter-Type Method for Solving Nonlinear Semidefinite Programming, Applied Numerical Mathematics. (2020) 158, 415–424, https://doi.org/10.1016/j.apnum.2020.08.012.

19 Zhu Z. B. and Zhu H. L., A Filter Method for Nonlinear Semidefinite Programming With Global Convergence, Acta Mathematica Sinica. (2014) 30, no. 10, 1810–1826, https://doi.org/10.1007/s10114-014-3241-1, 2-s2.0-84907638298.

20 Liu Z. and Sun W., A Globally Convergent Primal-Dual Interior-Point Three-Dimensional Filter Method for Nonlinear Semidefinite Programming, SIAM Journal on Optimization. (2008) .

21 Li D., Wang S., and Li Y., A Backtracking Line Search Method for Nonlinear Semidefinite Programming, Journal of South China Normal University (Social Science Edition). (2022) 7, 61–71.

22 Nie P. Y., Sequential Penalty Quadratic Programming Filter Methods for Nonlinear Programming, Nonlinear Analysis: Real World Applications. (2007) 8, no. 1, 118–129, https://doi.org/10.1016/j.nonrwa.2005.06.003, 2-s2.0-33750060318.

23 Gomez W. and Ramirez H., A Filter Algorithm for Nonlinear Semidefinite Programming, Computational and Applied Mathematics. (2010) 29, 297–328.

24 Wu J. Q., Two Filter Algorihtms for Nonlinear Semidefinte Programmding, 2019.

25 Toh K. C., Tutuncu R. H., and Todd M. J., On the Implementation of SDPT3 (Version 3.1): A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Proceedings of the IEEE International Symposium on Computer Aided Control System Design. (2004) 290–296.

26 Leibfritz F., Compleib: Constrained Matrix–Optimization Problem Library: A Collection of Test Examples for Nonlinear Semidefinite Programs, Control System Design and Related Problems, Department of Mathematics at the University of Trier (Universität Trier), Technical Reports. (2004) .

27 Yamashita H., Yabe H., and Harada K., A Primal Dual Interior Point Method for Nonlinear Semidefinite Programming, Mathematical Programming. (2012) 135, no. 1-2, 89–121, https://doi.org/10.1007/s10107-011-0449-z, 2-s2.0-84866264482.

Word count: 6192

Show less

© 2026. This work is published under http://creativecommons.org/licenses/by/4.0/ (the "License"). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

A Three‐Dimensional Filter‐Based SSDP Method for Nonlinear Semidefinite Programming With Its Applications

Content area

Abstract

Full text