Primal-dual path following method for nonlinear semi-infinite programs with semi-definite constraints

In this paper, we propose a primal-dual path following method for nonlinear semi-infinite semi-definite programs with infinitely many convex inequality constraints, called SISDP for short. A straightforward approach to the SISDP is to use classical methods for semi-infinite programs such as discretization and exchange methods and solve a sequence of (nonlinear) semi-definite programs (SDPs). However, it is often too demanding to find exact solutions of SDPs. In contrast, our approach does not rely on solving SDPs accurately but approximately following a path leading to a solution, which is formed on the intersection of the semi-infinite feasible region and the interior of the semi-definite feasible region. Specifically, we first present a prototype path-following method and show its global weak* convergence to a Karush-Kuhn-Tucker point of the SISDP under some mild assumptions. Next, to achieve fast local convergence, we integrate a two-step sequential quadratic programming method equipped with the Monteiro-Zhang scaling technique into the prototype method. We prove two-step superlinear convergence of the resulting algorithm using Alizadeh-Hareberly-Overton-like, Nesterov-Todd, and Helmberg-Rendle-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro scaling directions. Finally, we conduct some numerical experiments to demonstrate the efficiency of the proposed method through comparison with a discretization method that solves SDPs obtained by finite relaxation of the SISDP.

1. Actually, Jiang et al.  [12] solved linear SDPs with finitely many inequality constraints, which are obtained by discretizing the SISDP.

2. Here, the metric topology in \(\mathcal {R}^n\times S^m\times \mathcal {R}^M\times T^M\) is the one which is naturally induced from the norm topology in \(\mathcal {R}^n\times S^m\times \mathcal {R}^m\) and the metric topology in \(T^M\).

3. For each k, by definition, \(\tau _i^k\ne \tau _j^k\) if \(i\ne j\). But, at the limit, \(\tau _i^{*}= \tau _j^{*}\) possibly occurs, since two distinct sequences may converge to the identical point.

4. We say that \(z^{*}\) is a KKT point of NSDP (3.1) with \(\bar{x}=x^{*}\) if \(\nabla f(x^{*})+\sum _{i=1}^{p(x^{*})} \nabla \hat{g}_i(x^{*})\zeta _i^{*} -(F_j\bullet V_{*})_{j=1}^n=0\), \(0\le \zeta ^{*}\perp \hat{g}(x^{*})\le 0\), and condition (2.2) holds with \(V=V_{*}\).

5. For \(X\in S^{m}_{++},Y\in S^m\), the eigenvalues of \(X^{-1}Y\) are all real numbers.

6. If \(x^k\) and \(x^{k+\frac{1}{2}}\) are sufficiently close to \(\delta \)-nondegenerate \(x^{*}\) as supposed in Algorithm 2, such j exists for each i.

7. There is no theoretical guarantee for global optimality of \(\tau \) thus found. In practice, however, we may expect to have a global optimum by setting N large enough.

We would like to thank two anonymous reviewers and the associated editor for their valuable comments and suggestions.

Authors and Affiliations

1. Faculty of Science and Technology Department of Science and Technology, Seikei University, 3-3-1, Kita, Kichijoji, Musashino, Tokyo, 180-8633, Japan

   Takayuki Okuno

2. Center for Advanced Intelligence Project, RIKEN, Nihonbashi 1-chome Mitsui Building, 15th floor, 1-4-1 Nihonbashi, Chuo-ku, Tokyo, 103-0027, Japan

   Takayuki Okuno

3. The Kyoto College of Graduate Studies for Informatics, Kyoto, 606-8225, Japan

   Masao Fukushima

Corresponding author

Correspondence to Takayuki Okuno.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The work was supported by JSPS KAKENHI Grant Number [15K15943, 20K19748, 20H04145].

Appendix

1.1 A.1 Proof of Theorem 2.1

Firstly, note that \(F(x^{*})\bullet V=0,\ F(x^{*})\in S^m_+\) and \(V\in S^m_+\) hold if and only if \(F(x^{*})\circ V=O,\ F(x^{*})\in S^m_+\), and \(V\in S^m_+\).

To show the theorem, we utilize [21, Theorem 2.4] related to the KKT conditions for semi-infinite programs with infinitely many conic constraints. To apply this theorem, we let \(\mathcal {W}:=S^m\times \mathcal {R}\), \(C:=S^m_{+}\times \mathcal {R}_+\), and \(H(x,\tau ):=(F(x),g(x,\tau ))\in \mathcal {W}\). Furthermore, we define the inner product \(\langle \cdot ,\cdot \rangle \) by \(\langle (Y_1,y_1),(Y_2,y_2)\rangle := Y_1\bullet Y_2+y_1y_2\) for any \((Y_1,y_1),(Y_2,y_2)\in \mathcal {W}\). Then, SISDP (1.1) is rewritten as the following semi-infinite program with infinitely many conic constrains:

In fact, the SCQ for the SISDP implies the RCQ [21, Definition 2.2], that is, for a given feasible point x, there exists \(d\in \mathcal {R}^n\) such that \(H(x,\tau )+\nabla _xH(x,\tau )^{\top }d\in \mathrm{int}\,C\), which is rewritten as \(F(x+d)\in S^m_{++}\) and \(g(x,\tau )+\nabla _xg(x,\tau )^{\top }d<0\ (\tau \in T)\). This can be ensured by letting \(d:=\bar{x}-x\) with a Slater point \(\bar{x}\) and using the fact that \(F(\bar{x})\in S^m_{++}\) and \(g(x,\tau )+\nabla _xg(x,\tau )^{\top }d\le g(\bar{x},\tau )<0\ (\tau \in T)\) from the convexity of \(g(\cdot ,\tau )\) for any \(\tau \in T\). Hence, by applying [21, Theorem 2.4] to problem (A.1), under the presence of the SCQ, there exist \(p(\le n)\) Lagrange multipliers \(Z_j:=(V_j,y_j)\in \mathcal {W} \ (1\le j\le p)\) and \(\tau _1,\tau _2,\ldots ,\tau _p\in T\) such that

where \(C^{*}\) stands for the dual cone of C and

Then, by letting \(V:=\sum _{j=1}^pV_j\in S^m_{+}\), we have

By noting this fact together with \(C^{*}=C\), the conditions (A.2)-(A.3) yields

Finally, define \(y\in \mathcal {M}_+(T)\) as follows: For any \(\tau \in T\), \(y(\tau ):=y_j\) if \(\tau =\tau _j\) with \(1\le j\le p\) and, otherwise, \(y(\tau ):=0\). Then, by \(\sum _{j=1}^pg(x^{*},\tau _j)y_j=\int _{T}g(x^{*},\tau )dy(\tau )\) and \(\sum _{j=1}^p\nabla _xg(x^{*},\tau _j)y_j=\int _T\nabla _xg(x^{*},\tau )dy(\tau )\), conditions (A.4)-(A.6) are rewritten as the desired KKT conditions (2.1)-(2.3). By definition, \(|\mathrm{supp}(y)|\le p\le n\) holds.

The last assertion can be shown in a manner similar to the the one in the standard convex optimization theory. The proof is complete.

1.2 Proof of Proposition 3.1

Since \(x^{*}\) is \(\delta \)-nondegenerate and feasible for the SISDP, \(\max _{\tau \in T}g(x^{*},\tau )\le 0\) and the number of global maximizers of \(\max _{\tau \in T}g(x^{*},\tau )\) is finite. Denote the set of these global maximizers by \(\mathcal {S}\). As \(w^{*}\) is a KKT point of the SISDP, the KKT conditions (2.1)-(2.3) hold. In particular, by the complementarity condition (2.3), for each \(A\in \mathcal {B}\), we have the implication that \(y^{*}(A)>0\Rightarrow g(x^{*},\tau )=0\ (\tau \in A)\). Hereafter, suppose \(\mathrm{supp}(y^{*})\ne \emptyset \). Then, by definition, for arbitrarily chosen \(s\in \mathrm{supp}(y^{*})\), \(y^{*}(N_{s})>0\) holds for any open neighborhood \(N_s\) of s, which together with the above implication implies that \(g(x^{*},\tau )=0\ (\tau \in N_{s})\). Then, notice that \(\max _{\tau \in T}g(x^{*},\tau )\le 0\) since \(x^{*}\) is feasible to the SISDP. Thus, \(s\in N_s\subseteq \mathcal {S}\) holds for any \(s\in \mathrm{supp}(y^{*})\). This means \(\mathrm{supp}(y^{*})\subseteq \mathcal {S}\), which together with the fact that \(\mathcal {S}\) is a finite discrete set yields that \(\mathrm{supp}(y^{*})\) must be a finite discrete set. From this fact, we conclude that \(y^{*}\) is a discrete measure with finite support. Then, (3.3) readily follows from \(\mathrm{supp}(y^{*})\subseteq \mathcal {S}\subseteq \{\tau _{x^{*}}^1(x^{*}),\tau _{x^{*}}^2(x^{*}),\ldots ,\tau _{x^{*}}^{p(x^{*})}(x^{*})\}\).

Lastly, we show that \(z^{*}\) is a KKT point of the NSDP. Noting (3.3) and the fact that \(y^{*}\) is a discrete measure, we have \(\int _T\nabla _xg(x^{*},\tau )dy^{*}(\tau )=\sum _{i=1}^{p(x^{*})}\nabla _xg(x^{*},\tau _{x^{*}}^i(x^{*}))\zeta ^{*}_i\) and \(\int _Tg(x^{*},\tau )d\zeta ^{*}(\tau )=\sum _{i=1}^{p(x^{*})}g(x^{*},\tau _{x^{*}}^i(x^{*}))\zeta ^{*}_i\). Using this fact together with the KKT conditions (2.1)–(2.3) with \(w^{*}\) replaced by \(\bar{w}\), we obtain

This means that \(z^{*}\) is a KKT point of the NSDP. \(\square \)

1.3 A.2 Proof of Proposition 3.3

We begin with giving some lemmas that help to show Proposition 3.3.

Lemma A.1

Let \(X\in S^m_+\), \(Y\in S^m\) and \(\mu \ge 0\). Then,

1. 1.

   \(\Vert XY-YX\Vert _F\le 2\Vert X\circ Y-\mu I\Vert _F\) and

2. 2.

   \(\Vert \mathcal {L}_X\mathcal {L}_Y-\mathcal {L}_Y\mathcal {L}_X\Vert _2\le \Vert X\circ Y-\mu I\Vert _F.\)

Proof

Using some orthogonal matrix \(\mathcal {O}\in \mathcal {R}^{m\times m}\), we make an eigenvalue decomposition of X: \(\mathcal {O}^{\top }X\mathcal {O}=D\) with \(D\in \mathcal {R}^{m\times m}\) being a diagonal matrix. Denote the i-th diagonal entry of D by \(d_i\ge 0\) for \(i=1,2,\ldots ,m\). Let \({\tilde{Y}}:=\mathcal {O}^{\top }Y\mathcal {O}\) with the (i, j)-th entry \({\tilde{y}}_{ij}\) for \(1\le i,j\le m\).

1. 1.

   We have the desired result from

   $$\begin{aligned} \Vert XY-YX\Vert _F^2&=\Vert \mathcal {O}^{\top }X\mathcal {O}\mathcal {O}^{\top }Y\mathcal {O}-\mathcal {O}^{\top }Y\mathcal {O}\mathcal {O}^{\top }X\mathcal {O}\Vert _F^2\\&=\Vert D{\tilde{Y}}-{\tilde{Y}}D\Vert _F^2\\&=\sum _{1\le i,j\le m}(d_{i}-d_{j})^2{\tilde{y}}_{ij}^2\\&\le \sum _{1\le i\ne j\le m}(d_{i}+d_{j})^2{\tilde{y}}_{ij}^2\\&\le \sum _{1\le i\ne j\le m}(d_{i}+d_{j})^2{\tilde{y}}_{ij}^2+\sum _{i=1}^m(2d_{i}{\tilde{y}}_{ii}-2\mu )^2\\&=\Vert D{\tilde{Y}}+{\tilde{Y}}D-2\mu I\Vert _F^2\\&=\Vert XY+YX-2\mu I\Vert _F^2\\&=4\Vert X\circ Y-\mu I\Vert _F^2, \end{aligned}$$

   where the first inequality follows from \(d_{i}\ge 0\) for \(i=1,2,\ldots ,m\).

2. 2.

   By direct calculation, we have

   $$\begin{aligned} \Vert \mathcal {L}_X\mathcal {L}_Y-\mathcal {L}_Y\mathcal {L}_X\Vert _2&=\max _{\Vert Z\Vert _F=1}\Vert \mathcal {L}_X\mathcal {L}_YZ-\mathcal {L}_Y\mathcal {L}_XZ\Vert _F\\&=\max _{\Vert Z\Vert _F=1}\frac{\Vert (XY-YX)Z-Z(XY-YX)\Vert _F}{4}\\&\le \frac{\Vert XY-YX\Vert _F}{2}\\&\le \Vert X\circ Y-\mu I\Vert _F, \end{aligned}$$

   where the second inequality follows from item 1.

\(\square \)

Lemma A.2

Let \((X_{*},Y_{*})\in S^m_+\times S^m_+\) satisfy the strict complementarity condition that \(X_{*}{\circ }Y_{*}=O\) and \(X_{*}+Y_{*}\in S^m_{++}\). Let \(\{\mu _r\}\subseteq \mathcal {R}_{++}\) and \(\{(X_r,Y_r)\}\subseteq S^m_{++}\times S^m_{++}\) be sequences such that \(\lim _{r\rightarrow \infty }\mu _r=0\) and \(\lim _{r\rightarrow \infty }(X_r,Y_r)=(X_{*},Y_{*})\). Let spectral decompositions of \(X_{*}\) and \(Y_{*}\) be

using some orthogonal matrix \(\mathcal {O}_{*}\in \mathcal {R}^{m\times m}\) and positive diagonal matrices \(D_{X_{*}}\in S^p_{++}\) and \(D_{Y_{*}}\in S^q_{++}\) with \(p+q=m\). Furthermore, suppose \(p,q>0\) and choose a sequence of orthogonal matrices \(\{\mathcal {O}_{r}\}\subseteq \mathcal {R}^{m\times m}\) such that

with \(D_{X_r}\in \mathcal {R}^{p\times p}\) and \(E_{X_r}\in \mathcal {R}^{q\times q}\) being positive diagonal matrices for \(r\ge 1\). (Notice that \(\lim _{r\rightarrow \infty }E_{X_r}\)=O.) If \(\Vert X_r\circ Y_r-\mu _r I\Vert =o(\mu _r)\), then

Proof

Let \({\tilde{Y}}_r:=\mathcal {O}_r^{\top }Y_r\mathcal {O}_r\) and \({\tilde{y}}^r_{ii}\) and \(e^r_i\) be the i-th diagonal entry of \({\tilde{Y}}_r\) and \(E_{X_r}\), respectively for any \(i=p+1,p+2,\ldots ,m\). Since \(\Vert X_r\circ Y_r-\mu _rI\Vert _F=o(\mu _r)\) and

we have

which yields \(\lim _{r\rightarrow \infty }\frac{e^r_i}{\mu _r}{\tilde{y}}^r_{ii}=1\) for any \(i=p+1,\ldots ,m\). Notice that, for \(i\ge p+1\), \(\{{\tilde{y}}^r_{ii}\}\) converges to the i-th positive diagonal entry of \(D_{Y_{*}}\). In view of these facts, we obtain (A.7). \(\square \)

Now, we are ready to show Proposition 3.3. For the case where \(X_{*}\in S^m_{++}\), it is easy to prove the desired result. So, we consider the case of \(X_{*}\in S^m_+\setminus S^m_{++}\). Let \(\lambda _r>0\) be the smallest eigenvalue of \(X_r\). Notice that \(\lambda _r\rightarrow 0\ (r\rightarrow \infty )\) and, by Lemma A.2, \(\lim _{r\rightarrow \infty }\frac{\lambda _r}{\mu _r}\) exists and is positive. Thus, we also have

Note that, for any \(X\in S^m\) having m eigenvalues \(\alpha _1\le \alpha _2\le \cdots \le \alpha _m\), the corresponding symmetric linear operator \(\mathcal {L}_X\) has \(m(m+1)/2\) eigenvalues \( \alpha _1,\alpha _2,\ldots ,\alpha _m,\{(\alpha _i+\alpha _j)/2\}_{i\ne j}. \) This fact yields that the maximum eigenvalue of the operator \(\mathcal {L}_{X_r}^{-1}\) is \(\lambda _r^{-1}\). Therefore, we have \(\Vert \mathcal {L}_{X_r}^{-1}\Vert _2=\lambda _r^{-1}\) for any \(r\ge 0\). It then follows that

where the second inequality follows from Lemma A.1. This relation together with (A.8) and \(\Vert X_r\circ Y_r-\mu _rI\Vert _F=O(\mu _r^{1+{\theta }})\) implies \( \Vert \mathcal {L}_{X_r}\mathcal {L}_{Y_r}\mathcal {L}_{X_r}^{-1}-\mathcal {L}_{Y_r} \Vert _2=O(\mu _r^{\theta }).\)

\(\square \)

1.4 A.4 Proof of Proposition 3.4

Define \(U_r(s):=\left( X_r+s\varDelta X_r\right) \circ \left( Y_r+s\varDelta Y_r\right) \) for \(s\in [0,1]\) and each r. By using the fact that \(\Vert X\Vert _F\ge |\lambda _{\min }(X)|\) for any \(X\in S^m\), conditions (3.25)–(3.27) yield that there exists some \(K>0\) such that

Then, it holds that

for any r sufficiently large and \(s\in [0,1]\), where the first inequality follows from the fact that \(\lambda _{\min }(A+B)\ge \lambda _{\min }(A)+\lambda _{\min }(B)\) for \(A, B\in S^m\) and the second inequality is due to (A.9)–(A.11) and \(s\in [0,1]\). Notice that \(u_r(s)\) is concave and quadratic. Then, for any r sufficiently large, we have \(u_r(s)>0\ (s\in [0,1])\) since \(0<\theta ,\widehat{\theta }<1\), \(\lim _{r\rightarrow \infty }(\mu _r,\hat{\mu }_r)=(0,0)\), and (3.28) imply that \(u_r(0)=\mu _r-K\mu _r^{1+\theta }>0\) and \(u_r(1)=\hat{\mu }_r-K\hat{\mu }_r^{1+\widehat{\theta }}-K\mu _r^2>0\) for sufficiently large r. This means that \(\lambda _{\min }(U_r(s))\ge u_r(s)>0\ (s\in [0,1])\) and therefore

from which we can derive \(X_r+\varDelta X_r\in S^m_{++}\) and \(Y_r+\varDelta Y_r\in S^m_{++}\). Actually, for contradiction, suppose that either one of these two conditions is not true. We can assume \(X_r+\varDelta X_r\notin S^m_{++}\) without loss of generality. Recall that \(X_r\in S^m_{++}\). Then, there exists some \(\bar{s}\in (0,1]\) such that \(X_r+\bar{s}\varDelta X_r\in S^m_{+}\setminus S^m_{++}\). Therefore, we can find some nonzero vector \(d\in \mathcal {R}^n\) such that \((X_r+\bar{s}\varDelta X_r)d=0\). From this fact, we readily have

which contradicts (A.12). Hence, we conclude that \(X_r+\varDelta X_r\in S^m_{++}\) and \(Y_r+\varDelta Y_r\in S^m_{++}\) for all r sufficiently large. The proof is complete. \(\square \)

1.5 A.5 Proof of Lemma 3.1

To begin with, notice that Assumptions B-, C-, and C- yield that for sufficiently large k,

Furthermore, by (3.10), we have

which together with \(\zeta _i^{*}=0\ (i\in \{1,2,\ldots ,p(x^{*})\}\setminus I_a(x^{*}))\) implies \(\Vert \tilde{z}^k-\tilde{z}^{*}\Vert =\Vert z^k-z^{*}\Vert \) for all k sufficiently large. Next, by (A.14), \(z^k\in \widehat{\mathcal {N}}_{\mu _{k-1}}^{\varepsilon _{k-1}}\), and \(\varepsilon _{k-1}=\gamma _1\mu _{k-1}^{1+\alpha }\), it follows that

Noting \(a=2(a)_+-|a|\) for \(a\in \mathcal {R}\), we have

which together with (A.13) and (A.16) yields \(|\hat{g}_i(x^k)|=o(\mu _{k-1})\ (i\in I_a(x^{*}))\). From this fact and (A.15), we obtain \(\Vert \varPhi _0(\tilde{z}^k)\Vert =\varTheta (\mu _{k-1})\) and thus \(\mu _{k-1}=\varTheta (\Vert \varPhi _{0}(\tilde{z}^k)\Vert )\).

We next prove \(\mu _{k-1}=\varTheta (\Vert z^k-z^{*}\Vert )\) by showing \(\Vert \varPhi _{0}({\tilde{z}}^k)\Vert =\varTheta (\Vert \tilde{z}^k-\tilde{z}^{*}\Vert )\). It suffices to show that the sequence \(\{\eta _k\}:=\{{\Vert \varPhi _{0}(\tilde{z}^k)\Vert }/{\Vert \tilde{z}^k-\tilde{z}^{*}\Vert }\}\) is bounded above and away from zero. Note that by \(\varPhi _{0}(\tilde{z}^{*})=0\) and Assumption B-,

Obviously, \(\{\eta _k\}\) is bounded from above. To show \(\{\eta _k\}\) is bounded away from zero, suppose to the contrary. Then, without loss of generality, we can assume that \(\lim _{k\rightarrow \infty }\eta _k=0\), and hence there exists some \(d^{*}\) with \(\Vert d^{*}\Vert =1\) such that \(\lim _{k\rightarrow \infty }\frac{\tilde{z}^k-\tilde{z}^{*}}{\Vert \tilde{z}^k-\tilde{z}^{*}\Vert }=d^{*}\) and \(\mathcal {J}\varPhi _0(\tilde{z}^{*})d^{*}=0\). However, this contradicts the nonsingularity of \(\mathcal {J}\varPhi _{0}(\tilde{z}^{*})\) from Assumption B-. We have the desired conclusion. \(\square \)

Reprints and permissions