In recent decades, semi infinite programming (SIP) attracted the attention and favor of many scholars at home and abroad, and the research results were abundant [1-4]. A simple form of SIP is given as follows:
where $f: R^n\rightarrow R$ is continuously differentiable and $g: R^n\times [a, b]\rightarrow R$ is continuously differentiable with respect to $x$.
Discretization method is a common method, and local reduction method is an intrinsic method for solving SIP. Refs. [1-3] made a analysis in detail. In view of the wide application of discretization method in engineering, many scholars studied the discretized problem from SIP [5-11]. The discretized problem has the following form
where ${\it\Omega}_q=\{\omega\in {\it\Omega}|\ \omega=a+i\cdot\frac{b-a}{q}, i=0, 1, 2, \cdots, q\}, $ and $q$ indicates the level of discretization. The interpretation of $q$ can be seen in [10].
For better analysis of how to solve SIP through solving ${\rm SIP}_q$, we attempt to present two algorithm frameworks based on discretization method and local reduction method, respectively. Of course, the two algorithm frameworks can be considered to be designed for the algorithms for ${\rm SIP}_q$ in [8-11]. In addition, under some necessary assumptions, the global convergence of the previous algorithm framework is proved. Finally, some preliminary numerical results are reported.
In this section, inspired by the idea of discretization method [2], we present an algorithm framework for SIP on this basis of the algorithms for ${\rm SIP}_q$ in [8-11].
For clarity, we denote the algorithm for ${\rm SIP}_q$ in [8-11] as "Algorithm A", which is taken as an inner iteration of Algorithm below. Define the distance of Hausdorff between $\Omega$ and $\Omega_q$ as ${\rm dist}(\Omega_q, {\Omega})=\max\limits_{\omega\in {\Omega}}\min\limits_{\hat{\omega}\in {\Omega}_q}\|\hat{\omega}-\omega\|$. As to discretization method, the sequence of discretized set $\{\Omega_{q_i}\}_{i\in N_0}$ satisfies the following conditions:
Our algorithm framework based on discretization method is described as follows.
Algorithm 2.1 An algorithm framework based on discretization method for SIP.
Parameters $\{\tau_i\}_{i\in N_0}$ such that $0 < \tau_{i+1} < \tau_i, \forall i\in N_0$ and $\lim\limits_{i\rightarrow \infty}\tau_i=0$, $q_0\in N_0\backslash\{0\}, $ and initialized parameters of Algorithm A.
Data $x_0=\bar{x}_{q_{-1}}\in R^n$, choose discretized set $\Omega_{q_0}\subset\Omega$ such that $|\Omega_{q_0}| < \infty$ and ${\rm dist}(\Omega_{q_0}, \Omega)\leq\tau_0$.
Step 0 Set $i=0$.
Step 1 Solve SIP($\Omega_{q_i}$) (i.e., ${\rm SIP}_{q_i}$) by applying Algorithm A to obtain a KKT point $\bar{x}_{q_i}$.
Step 2 Choose discretized set $\Omega_{q_{i+1}}\subset\Omega$ such that $\Omega_{q_0}\subset\Omega_{q_{i+1}}$, $|\Omega_{q_{i+1}}| < \infty$ and ${\rm dist}(\Omega_{q_{i+1}}, \Omega)\leq \tau_{i+1}$.
Step 3 Set $i=i+1$, and go back to Step 1.
Discretization method is actually an outer approximation algorithm. The real solution is approximated by the exterior approximation of the feasible region of SIP. From a numerical viewpoint, only the conceptual discretization method is useful. The latest research on discretization method can be seen in refs. [12, 13].
In this part, we will discuss the global convergence of Algorithm 2.1 under mild assumptions. For the sake of convenience, we denote
Definition 2.1 For $x_0\in R^n$ and discretized set $\Omega_{q_i}\subset\Omega, i\in N_0$ in Algorithm 2.1, the level set is defined as
Assumption 2.1 Level set $LV(x^0, \Omega_{q_0}, \Omega)$ is bounded, thus is compact.
Remark 1 The assumption that $\{x^k\}$ is bounded in refs. [8-11] can be replaced by Assumption 2.1.
Assumption 2.2 Functions $g(\cdot, \cdot)$ are Lipschitz continuous in the bounded set, i.e., there exist Lipschitz constants $L_{g_x}$ and $L_{g_\omega}$ such that
Assumption 2.3 Suppose that linearly independent constraint qualification (LICQ) is satisfied by problem SIP at any $\bar{x}\in \Omega_{act}$, i.e., the vectors $\{\nabla_x g(\bar{x}, \omega), \omega\in \Omega_{act}(\bar{x})\}$ are linearly independent.
Lemma 2.1 (see [3]) Suppose that Assumption 2.3 holds, then the number of indices of $\Omega_{act}(\bar{x})$ is finite.
Definition 2.2 (see [3]) Suppose that $\bar{x}\in X, 0\neq |\Omega_{act}(\bar{x})| < \infty$, then $\bar{x}$ is the KKT point of SIP, if there exist $\bar{u}_1, \cdots, $ $\bar{u}_\omega\geq 0, \omega\in\Omega_{act}(\bar{x})$ such that
Lemma 2.2 Suppose that iteration point sequence$\{\bar{x}_{q_i}\}_{i\in N_0}$ is yielded by Algorithm 2.1, then there exists an accumulation point $\bar{x}$ of $\{\bar{x}_{q_i}\}_{i\in N_0}$.
Proof If $x\in LV(x_0, \Omega_{q_i}, \Omega)$, according to $\Omega_{q_0}\subset \Omega_{q_i}, \forall i\in N_0\backslash\{0\}$, one can see that $\varphi_{q_0}(x)\leq \varphi_{q_i}(x_0)\leq \psi(x_0)$. Thus, it follows that $LV(x_0, \Omega_{q_i})\subset LV(x_0, \Omega_{q_0}, \Omega)$. Further, we can conclude that set $LV(x_0, \Omega_{q_i}, \Omega)$ is a closed subset of compact set $LV(x_0, \Omega_{q_0}, \Omega)$, and so it is compact. For iteration point sequence $\{\bar{x}_{q_i}\}_{i\in N_0}$, one has $\bar{x}_{q_i}\in LV(x_0, \Omega_{q_i}, \Omega)$, thus, there exists an accumulation point $\bar{x}$ of $\{\bar{x}_{q_i}\}_{i\in N_0}$, and the proof is finished.
Lemma 2.3 Suppose that iteration point sequence $\{\bar{x}_{q_i}\}_{i\in N_0}$ is generated by Algorithm 2.1, and the subset $\{\bar{x}_{q_i}\}_{i\in I}, I\subseteq N_0, |I|=\infty$ converges to $\bar{x}$. Then $\{\varphi_{q_i}(\bar{x}_{q_i})\}_{i\in I}$ is convergent, and $\lim\limits_{i\rightarrow\infty, i\in I}\varphi_{q_i}(\bar{x}_{q_i})=\psi(\bar{x})$.
Proof First, we prove that $0\leq\psi(x)-\varphi_{q_i}(x)\leq L_{g_\omega}{\hbox{dist}}(\Omega_{q_i}, \Omega), \forall x\in LV(x^0, \Omega_{q_0}, \Omega), i\in N_0$.
If $\psi(x)=0$, then the formula above hold obviously.
If $\psi(x) > 0$, choosing $\omega_g\in\Omega_g(x)$, then there exists $\omega_{q_i}\in\Omega_{q_i}$ such that $\|\omega_g-\omega_{q_i}\|\leq L_{g_\omega}{\hbox{dist}}(\Omega_{q_i}, \Omega)$. Furthermore, it follows that
Next, we prove that $\{\varphi_{q_i}(\bar{x}_{q_i})\}_{i\in I}$ is convergent.
From (2.3), one has $\varphi_{q_i}(\bar{x}_{q_i})\leq \psi(\bar{x}_{q_i})$. Further,
By Algorithm 2.1, one can see that $\lim\limits_{i\rightarrow\infty}\tau_i=0$. Applying (2.3), we can conclude that $\lim\limits_{i\rightarrow\infty, i\in I}\varphi(\bar{x}_{q_i})=\psi(\bar{x})$. Thus, the proof of this lemma is finished.
Lemma 2.4 Suppose that the stated assumption of Lemma 2.3 holds. Then, for $\bar{\omega}\in\Omega_{act}(\bar{x})$, there exists an iteration point sequence $\{\omega_{q_i}\}_{i\in I}$ such that $\omega_{q_i}\in\Omega_{act, q_i}(\bar{x}_{q_i})$, and $\omega_{q_i}\rightarrow \bar{\omega}$ holds for $i\in I$ large enough.
Proof From Lemma 2.1, we have $|\Omega_{act}(\bar{x})| < \infty$. For any $\bar{\omega}\in\Omega_{act}(\bar{x})$, one obtains $g(\bar{x}, \bar{\omega})=0$. Let $\omega_{q_i}\in\Omega_{q_i}$, we can conclude that
In view of $\lim\limits_{i\rightarrow\infty}\tau_i=0$ and $\lim\limits_{i\rightarrow\infty, i\in I}\bar{x}_{q_i}\rightarrow \bar{x}$, one can conclude that $\lim\limits_{i\rightarrow\infty, i\in I}g(\bar{x}_{q_i}, \omega_{q_i})=0$. Thus, the conclusion is at hand.
Theorem 2.1 Suppose that Assumptions 2.1-2.3 hold, and $\{\bar{x}_{q_i}\}_{i\in N_0}$ is yielded by Algorithm 2.1, there exists an accumulation point $\bar{x}$ of $\{\bar{x}_{q_i}\}_{i\in N_0}$ which is a KKT point for SIP (1.1). In such sense, Algorithm 2.1 is said to possess weak global convergence.
Proof By Lemma 2.2, one knows that there exists an accumulation point $\bar{x}$ of $\{\bar{x}_{q_i}\}_{i\in N_0}$. Choose an subset $\{\bar{x}_{q_i}\}_{i\in I}, I\subseteq N_0, |I|=\infty$ that converges to $\bar{x}$. From the structure of Algorithm 2.1, we can see that $\bar{x}_{q_i}$ is the KKT point of ${\rm SIP}_{q_i}$. Further, taking into account the theorem of Caratheodory, for $s=n+1, i\in I$ and $\omega_{q_i}\in\Omega_{act, q_i}(\bar{x}_{q_i})$, one can conclude that
In view of [10, Lemma 3.4] and [11, Lemma 3.5], we can conclude that $\{\lambda_i^j\}_{i\in I}, j=1, 2, \cdots, s$ are bounded. Thus, there exists a subset that converges to $\bar{\lambda}^j, j=1, 2, \cdots, s$. Without loss of generality, we regard the subset as original sequence. Denote $J_{act}(\bar{x})$ as an index set of $\Omega_{act}(\bar{x})$. By Lemma 2.4, one knows that, for $\bar{\omega}^j\in\Omega_{act}(\bar{x}), j\in J_{act}(\bar{x})$, there exists a sequence $\{\omega_{q_i}^j\}_{i\in I}$ such that $\omega_{q_i}^j\in\Omega_{act, q_i}(\bar{x}_{q_i})$, and $\omega_{q_i}^j\rightarrow \bar{\omega}^j, j\in J_{act}(\bar{x})$ for $i\in I$ large enough. Furthermore, through putting in order, one can get that, the first $l (=|J_{act}(\bar{x})|)$ indices of $S (={1, 2, \cdots, s})$ correspond to $\omega_{q_i}^j$ of $\Omega_{act, q_i}(\bar{x}_{q_i})$, and $\omega_{q_i}^j\rightarrow \bar{\omega}^j, j=1, 2, \cdots, l$. Moreover, note that $|S| < \infty$ and $\Omega$ are compact, we know that sequence or its subsequence $\{\omega_{q_i}^j\}_{i\in I}, j=l+1, \cdots, s$ converges to $\bar{\omega}^j\in\Omega, j=l+1, \cdots, s$. So, passing to the limit for $i\in I$ and $i\rightarrow\infty$ in (2.4)-(2.7), combining with Lemma 2.3, we have
From (2.11), one knows that $\bar{x}\in X$. Further, combining with Definition 2.2, according to (2.8)-(2.10), we can conclude that $\bar{x}$ is the KKT point of SIP, and the proof is finished.
Local reduction method originates from ref. [14], which studies how to convert SIP local reduction to optimization problem with finite constraints. Conditions for the establishment of local reduction lemma and related conclusions can be seen in [1, 15]. The essence of local reduction lemma is that, under certain conditions, the original SIP problem is locally equivalent to an implicit finite constrained programming in the optimal solution.
Note that the algorithms for ${\rm SIP}_q$ [8-11] can obtain an approximate solution of SIP. Inspired by local reduction method [1, 15], we present a two phase algorithm framework for SIP. In the first phase, we apply algorithms for ${\rm SIP}_q$ to obtain an approximate solution of SIP. Then, taking the approximate solution as a initial point, we switch to the second stage, i.e., solve the local reduction problem of SIP, which is based on the idea of local reduction. As to the iterative method solving for SIP, a sufficient condition for the local reduction is given below.
Assumption 3.1 (see [15]) Suppose that iteration point sequence $\{x^k\}_{k\in N_0}$ is yielded by some iteration method for SIP. For any iteration point $x^k, \ k\in N_0$, problem
is regular, i.e.,
(ⅰ) any critical point of problem $P(x^k)$ is non-degenerative;
(ⅱ) LICQ is satisfied by problem $P(x^k)$ at any $\omega\in\Omega$.
Remark 2 Originally, local reduction lemma (see [1]) and the assumptions need to solve global maximum points of $P(x^k)$. However, it is difficult to solve the global solution. In practice, we would like to solve local maximum points of $P(x^k)$. Some scholars improve the assumptions of local reduction lemma, in which we need to solve the local maximum points. Assumption 3.1 implies the updated assumptions hold [15], i.e., it is a sufficient condition for the local reduction lemma. Moreover, it is also the basis of Lemma 3.1 below.
Lemma 3.1 (see [15]) Suppose that Assumption 3.1 holds. Then there exists an neighborhood $U(x^k)$ of $x^k$ such that, for any $x\in U(x^k)$, problem SIP (1.1) is equivalent to the following local reduction problem
The lemma above is the corollary of local reduction lemma, which is the basis of Algorithm 3.1 below.
Algorithm 3.1 A two phase algorithm framework based on local reduction method for SIP
Phase 1 (Approximate phase) Choose a proper positive integer $q$ (depending on the length of $[a, b]$), and discretize $\Omega$ into $\Omega_q$. For any $x\in R^n$, applying Algorithm A (see [8-11]) to solve ${\rm SIP}_q$ and obtain an approximate solution $\bar{x}_q$.
Phase 2 (see [1, 15]) (Global phase)
Step 0 $x^0=\bar{x}_q$. Set $k=0$;
Step 1 Solve $ P(x^k)$ to obtain all local maximum points $\omega_l^j, j\in J_l(x^k)$;
Step 2 Set $i=0, X^k_i=x^k$;
Step 3 Applying some iterative methods such as SQP to solve ${\rm SIP}_{red}^l(x^k)$. Suppose the $i_k$ iterations are performed, and let initial point be $X^k_0$, then the inner iteration points are in turn $X^k_i, i=1, 2, \cdots, i_k$. If $i\in\{1, 2, \cdots, i_{k-1}\}$, then local maximum points of $P(X^k_i)$ are made local correction, and yield $\omega_{l, k_i}^j$, $j\in J_l(X^k_i)$;
Step 4 Set $x^{k+1}=X^k_{i_k}, k=k+1$, and go back to Step 1.
Although the hypothesis of local reduction method is strong, local reduction is intrinsic method for SIP. In recent years, it is still concerned and studied, such as ref. [16].
In this section, some preliminary numerical results are reported. All the numerical experiments are implemented on MATLAB 2016a on a 64-bit PC with an Intel Core i7-4790 CPU and 32GB of RAM. The tested problem $\verb"P1"$ from [17], and $\verb"P2"$ through $\verb"P3"$ are taken from [18], which have the following form
with $g$ and $\Omega$ as follows:
$\verb"P1":\ g(x, \omega)=(1-\omega^2)-(0.5x^2-2x\omega), \ \Omega=[-1, 1], \ x^0=1, \ f(x^*)=1.$
$\verb"P2":\ g(x, \omega)=\omega^2-(x_1\omega+x_2\exp(\omega)), \ \Omega=[0, 2], \ x^0=(1, 1), \ f(x^*)=0.53825.$
$\verb"P3":\ g(x, \omega)=\frac{1}{1+\omega}-(x_1\omega+x_2\exp(\omega)), \ \Omega=[-0.5, 0.5], \ x^0=(1, 1), \ f(x^*)=0.08716.$
For the record, $x^0$ is the initial point used the same as that of algorithms [6, 7], and $f(x^*)$ is the objective function value given in refs. [15, 17, 18]. Moreover, the tested problems above can be equivalent to inequality constrained SIP such as (1.1), and can be solved by our algorithm framework.
From the viewpoint of discretization method, for the closed interval $\Omega=[a, b]$ of variation $\omega$, it can be discretized into the following set by
where $q$ reflects the discretization level of SIP (1.1).
During the test experiments, the following parameters are used for all tested problems:
In addition, for a given discretization level $q$, the stopping criterion is $\|d^k\|\leq 1\times10^{-4}$ or $|z_k|\leq10^{-4}$, which is the same as of refs. [7, 8].
To test the validity of Algorithm 2.1, in view of the equivalence of $\lim\limits_{i\rightarrow \infty}\tau_i=0$ and $\lim\limits_{i\rightarrow \infty} q_i=\infty$, without loss of generality, we can assume that $q_{i+1}=2q_i$. The algorithm [8] is selected as Algorithm A, and the partial iterative results of Algorithm 2.1 for $\verb"P1"-\verb"P3"$ are reported in Table 1.
In Table 1, the column $i$ is $i$th iteration; $q_i$ indicates the discretization level at $i$th iteration. At $i$th iteration, ${\rm SIP}_{q_i}$ is solved, which is an inner loop. Assume that $k$ iterations are executed in the inner loop. The columns Ni (=$k$) and Nf are the number of iterations and objective function evaluations, respectively; Ng is the number of constraint function $g(x, \omega)$ evaluations for a given $x$ and $\omega$; $\Sigma|\Omega_k|$ is the sum over all iterations of the size of $\Omega_k$; $|\bar\Omega|$ means the average size of $\Omega_k$, i.e., $|\bar\Omega|=\Sigma|\Omega_k|/{\hbox{Ni}}$; $|\Omega_*|$ is the size of $\Omega_k$ at the end of $i$th iteration; $\bar{z}_{q_i}$ is the value of $z_k$ at the end of the $i$th iteration. Finally, $f(\bar{x}_{q_i})$ is the objective function value at the end of $i$th iteration. From the column of $|\bar\Omega|$, we find that the average number of constraints per iteration is small, which can reduce the computational cost of Algorithm 2.1. Compared with previous numerical results, our algorithm framework based on discretization method is effective.
In addition, in view of ref. [15] reported the theory and the numerical experimentation in detail on Phase 2 of Algorithm 3.1, we just need to further illustrate the efficiency of Algorithm A in Phase 1 of Algorithm 3.1. For this purpose, we select $q=10, 20, 50, 100, 200, 500, 1000$, $2000, 5000, 10000$, respectively. For a given discretization level $q$, we apply Algorithm A (may as well take Algorithm A of [8] as an example) to solve ${\rm SIP}_q$. The computational results are reported in Table 2.
In Table 2, the column $q$ indicates the given discretization level. The meanings of Ni, Nf, Ng, $\Sigma|\Omega_k|$, $|\bar\Omega|$, $|\Omega_*|$ are similar to those above, but all of them are generated by solving ${\rm SIP}_q$. Moreover, $z_*$ is the value of $z_k$ at the final iterate, and $f(x^*)$ is the objective function value at the final iterate point.
Comparing the results of Table 2 with previous numerical results [6, 7, 15, 17, 18], we find that choosing an appropriately large $q$ can reduce calculation cost greatly, and the solution of ${\rm SIP}_q$ is usually a good approximate solution of SIP, which is exactly required in Phase 1 of Algorithm 3.1. Thus, Phase 1 of Algorithm 3.1 can be better implemented.
In this paper, based on discretization method and local reduction, we present two algorithm frameworks for SIP, and solve problem how to solve SIP by the proposed algorithm in [8-11]. The two algorithm frameworks not only improve the theory of algorithms for [8-11], but also play an important role to achieve the real solution of SIP. Finally, some preliminary numerical results are reported, which show the proposed two algorithm frameworks are effective.
2018, Vol. 38 Issue (5): 851-860
PDF
2018, Vol. 38 Issue (5): 851-860 PDF