A Nonconvex Proximal Bundle Method for Nonsmooth Constrained Optimization

Abstract

An implementable algorithm for solving nonsmooth nonconvex constrained optimization is proposed by combining bundle ideas, proximity control, and the exact penalty function. We construct two kinds of approximations to nonconvex objective function; these two approximations correspond to the convex and concave behaviors of the objective function at the current point, which captures precisely the characteristic of the objective function. The penalty coefficients are increased only a finite number of times under the conditions of Slater constraint qualification and the boundedness of the constrained set, which limit the unnecessary penalty growth. The given algorithm converges to an approximate stationary point of the exact penalty function for constrained nonconvex optimization with weakly semismooth objective function. We also provide the results of some preliminary numerical testing to show the validity and efficiency of the proposed method.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction and Motivation

Nonsmooth optimization problems (NSO) arise from many fields of applications in engineering [1], economics [2], mechanics [3], and optimal control [4]. For example, multiobjective nonsmooth optimization has also been applied in many fields of engineering where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives [5]. There exist several approaches to solving NSO, see [6–10]. Bundle methods are currently among the most efficient optimization methods; they can be used to study the engineering problem of the safe evaluation technology for concrete dams by applying nonsmooth bundle ideas to hydrostructure antiseismic fields [11–14]. These methods are based on the cutting plane method [15, 16], where the convexity of the objective function is the fundamental assumption. If the objective function $f$ is convex, the model functions are lower approximations to the objective function. This feature is crucial to prove the convergence of most bundle methods. There exist lots of bundle methods [7, 17–19] for solving convex constrained optimization problems. In [7], the author presents a version of proximal bundle method for convex constrained optimization, where $l_1$ and $l_{\infty }$ exact penalty functions are employed and a new penalty update is used to limit unnecessary penalty growth; the global convergence of the method is established. In [17], an infeasible bundle method for convex constrained optimization is proposed, which does not use either a penalty function or a filter, and in fact the method can be viewed as an unconstrained proximal bundle method applied directly to the improvement function, and it should be noted that the serious steps need neither be monotone nor feasible. The algorithm presented in [18] inherits attractive features from the proximal bundle methods and the filter strategy, which makes the criterion for accepting a candidate point as a serious step easier to satisfy.

However, for nonconvex cases, the corresponding model function does not stay below the objective function $f$ and may even cut off a region containing a minimizer. There are few systematic studies for extending convex bundle methods to nonconvex cases. Most authors have considered forcing linearization errors to be positive by replacing negative values with a quadratic term or with the absolute value of the linearization errors; the piecewise affine models embedding possible downward shifting of the affine pieces are also considered [20, 21]. In [22], the author presents a substitute for the cutting plane without convexity assumption and proves that every accumulation point of the sequence of serious steps is critical. Based on cutting plane models, a local convexification model of the objective function is constructed in [23]; it opens a new way to create nonconvex algorithms; Fuduli et al. [24] partitioned the bundle information into two subsets to capture convex and concave behaviors of the objective function around the current point. Other literatures about bundle methods for nonsmooth nonconvex optimization can be found in [25–28].

In this paper, we propose a new algorithm for constrained nonconvex optimization. The algorithm is based on the construction of two kinds of approximations to the objective function, and these two kinds of approximations correspond to the convex and concave behaviors of the objective function at the current point. If the linearization error is positive, we build a local lower approximation to the objective function, otherwise a local upper approximation is constructed. Besides that, the method employs $l_1$ exact penalty functions with a new penalty update rule that limits unnecessary penalty growth. Our method extends the exact penalty function algorithms for constrained convex minimization to nonconvex optimization. The following is the main difference of our paper in many respects from the existing ones [6, 7, 19, 29]. The proposed algorithm in this paper is quite different from the ones in [7, 17–19] since the objective function in our paper is nonconvex although the constraint function is convex, while both the objective function and the constraint function are convex in [7, 17–19]. In [7, 19], the $l_1$ and $l_{\infty }$ exact penalty functions are employed to consider convex constraint optimization problems by combining with proximal bundle method. In this paper, we also use the similar exact penalty functions for solving nonconvex optimization problems, but we have to adjust suitably the construction of quadratic programming subproblems since the presence of nonconvexity can make the linearization errors negative, which enhances the difficulty to solve the problem. To solve this problem, we divide the bundle index set into two sets according to the signs of linearization errors and use the partitioned bundles during the process of the construction of the objective function model. Therefore, the direction finding subproblem is quite different from the existing ones, which leads to the overall changes for the design of the algorithm. The algorithms in [17, 18] use neither penalty functions nor relatively complex filters; they build on the theory of the well-developed unconstrained bundle methods by introducing the improvement function, which is essential for the convergence of the proposed algorithm. It is another approach proposed in recent years for solving nonsmooth convex constrained optimization problems. It should be noted that the descent condition in our method used to decide when the candidate point can be accepted as the next serious step is different from the ones in [17, 18], where the improvement function involving the objective function is employed to form the descent criterion, but in our method, the penalty function is used to serve the same role.

This paper is organized as follows: in Section 2, the model for constrained nonconvex optimization is established by using the exact penalty function. The nonconvex bundle algorithm is presented in Section 3. In Section 4, we prove that the sequence of serious steps generated by the proposed algorithm converges to an approximate stationary point of exact penalty function with weakly semismooth objective functions. Preliminary numerical experiments are provided in Section 5. Finally, some conclusions are given in Section 6.

2. Derivation of the Model

Consider the following constrained nonconvex optimization problem:$$\begin{array}{c}\text{(1)}& \underset{x\in {\mathbf{R}}^n}{\min } fx,\mathrm{s}.\mathrm{t}.Fx\le 0,\end{array}$$where $f:R^n⟶R$ is a real-valued locally Lipschitz function and $F:R^n⟶R$ is a real-valued convex function. It is well known that for a locally Lipschitz function $f$, the generalized subdifferential (Clarke’s subdifferential) at each point $x$ is defined by$$\begin{array}{}\text{(2)}& {\partial }_{C}fx=\text{conv}g|g\in R^n,\nabla f{x}^k⟶g,x^k⟶x,x^k\notin {\Omega }_f,\end{array}$$where “conv” denotes the convex hull of a set and ${\Omega }_f$ is the set where $f$ is not differentiable. The set ${\partial }_{C}fx$ is locally bounded [30]. An extension of the generalized subdifferential is the Goldstein $\epsilon$-subdifferential ${\partial }_{\epsilon }^{G}fx$ defined as$$\begin{array}{}\text{(3)}& {\partial }_{\epsilon }^{G}fx=\text{conv}{\partial }_{C}fy|y-x\le \epsilon .\end{array}$$

For convex function $F$, the subdifferential of $F$ at $x$ is defined by$$\begin{array}{}\text{(4)}& \partial Fx=g|g\in R^n,Fy\ge Fx+g,y-x,\forall y\in R^n,\end{array}$$which is locally bounded. Assume that we are able to compute at each point $x$ both the function values $fx,Fx$ and subgradients $g_{f}x\in {\partial }_{C}fx,g_{F}x\in \partial Fx$. We denote the current iteration point (stability center) and the trial point by $x^i$ and $y^j$, respectively. The bundles of available information are the sets $B_{fi}$ and $B_{Fi}$ of elements$$\begin{array}{}\text{(5)}& y^j,f{y}^j,g_f^j,{\alpha }_f^j,a_f^j,j\in B_{fi},y^j,F{y}^j,g_F^j,{\alpha }_F^j,j\in B_{Fi},\end{array}$$where $g_f^j\in {\partial }_{C}f{y}^j$, $g_F^j\in \partial F{y}^j$, ${\alpha }_f^j=f{x}^i-f{y}^j-g_f^j,x^i-y^j$, $a_f^j=x^i-y^j$, ${\alpha }_F^j=F{x^i}_{+}-F{y}^j-g_F^j,x^i-y^j$, and $F{x^i}_{+}=\max F{x}^i,0$.

If $f$ and $F$ are real-valued convex functions on $R^n$, under Slater constraint qualification, problem (1) can be solved by minimizing the following $l_1$ exact penalty function$$\begin{array}{}\text{(6)}& ex,c=fx+cF{x}_{+},\end{array}$$where $c$ is the penalty parameter which is greater than the Lagrange multiplier of problem (1), see [7]. For real-valued locally Lipschitz function $f:R^n⟶R$ and real-valued convex function $F:R^n⟶R$, we try to combine the ideas of bundle methods, proximity control, and exact penalty functions to solve problem (1). We define the cutting plane approximations of $f$, $F$, and $ex,c$ by their linearizations:$$\begin{array}{c}\text{(7)}& {\widehat{f}}^{i}x=\underset{j\in B_{fi}}{\max }f{y}^j+g_f^j,x-y^j,{\widehat{F}}^{i}x=\underset{j\in B_{Fi}}{\max }F{y}^j+g_F^j,x-y^j,\\ {\widehat{e}}^{i}x,c_i={\widehat{f}}^{i}x+c_i{\widehat{F}}^i{x}_{+},\end{array}$$where $B_{fi},B_{Fi}\subset 1,2,\dots ,i$, $c_i$ is the corresponding penalty parameter. The next trial point $y^{j+1}$ is obtained by solving the following problem:$$\begin{array}{}\text{(8)}& \underset{x\in R^n}{\min }{\widehat{e}}^{i}x,c_i+\frac{u_i}{2}{x-x^i}^2,\end{array}$$where $u_i>0$ is the proximal parameter. Note that if $x$ is feasible, $F{x}_{+}=0$. Therefore, we introduce additionally a trial point $y^0$, the subgradient $g_F^0=0$, and the linearization error ${\alpha }_F^0=F{x^i}_{+}=0$ with respect to $y^0$, and then we define $B_{Fi0}=B_{Fi}\cup 0$. Hence, problem (8) can be written in equivalent form$$\begin{array}{}\text{(9)}& \begin{array}{c}\min v_f+c_i{v}_F+\frac{u_i}{2}{d}^2,\\ \mathrm{s}.\mathrm{t}.-{\alpha }_f^j+{g_f^j}^{\top }d\le v_f,j\in B_{fi},\\ -{\alpha }_F^j+{g_F^j}^{\top }d\le v_F,j\in B_{Fi0},\end{array}\end{array}$$where $d=x-x^i$. The introduction of index set $0$ into $B_{F_{i0}}$ can make sure $v_F\ge 0$ in (9) for $j=0$.

It should be noted that ${\alpha }_f^j$ may be negative since $f$ is nonconvex; we divide $B_{fi}$ into two sets $B_{fi}^{+}$ and $B_{fi}^{-}$ defined by$$\begin{array}{}\text{(10)}& B_{fi}^{+}=j\in B_{fi}|{\alpha }_f^j\ge 0,B_{fi}^{-}=j\in B_{fi}|{\alpha }_f^j<0,\end{array}$$where $B_{fi}^{+}$ is nonempty since $i\in B_{fi}^{+}$. We define the following two piecewise affine functions:$$\begin{array}{}\text{(11)}& H^{+}d=\underset{j\in B_{fi}^{+}}{\max }{g_f^j}^{\top }d-{\alpha }_f^j,H^{-}d=\underset{j\in B_{fi}^{-}}{\min }{g_f^j}^{\top }d-{\alpha }_f^j.\end{array}$$

Let $hd=f{x}^i+d-f{x}^i$, the affine function $H^{+}d$, be considered as the approximation of $hd$ since $hd=f{x}^i+d-f{x}^i=fx-f{x}^i$ and $H^{+}d={\max }_{j\in B_{fi}^{+}}{g_f^j}^{\top }d-{\alpha }_f^j={\max }_{j\in B_{fi}^{+}}f{y}^j+{g_f^j}^{\top }x-y^j-f{x}^i$. Because $H^{+}0<0$, $H^{-}0>0$ if $B_{fi}^{-}\ne \varnothing$, therefore $H^{+}0<H^{-}0$. Summing up, around $d=0$ (around the stability center $x^i$), it appears that the set $S_f=d\in R^n|H^{+}d\le H^{-}d$ is more important and reliable.

Let $v_{f_{u_i}},v_{F_{u_i}},d_{u_i}$ be the optimal solution to the following problem:$$\begin{array}{}\text{(12)}& Q{P}_{u_i}\begin{array}{c}{z}_{u_i}=\min v_f+c_i{v}_F+\frac{u_i}{2}{d}^2,\\ \mathrm{s}.\mathrm{t}.-{\alpha }_f^j+{g_f^j}^{\top }d\le v_f,j\in B_{fi}^{+},\\ -{\alpha }_f^j+{g_f^j}^{\top }d\ge v_f,j\in B_{fi}^{-},\\ -{\alpha }_F^j+{g_F^j}^{\top }d\le v_F,j\in B_{Fi0}.\end{array}\end{array}$$

Let $y^{j+1}=x^i+d_{u_i}$. Since $v_{F{u}_i}$ is the optimal solution of problem (12), $v_{F{u}_i}={\widehat{F}}^i{y^{j+1}}_{+}-F{x^i}_{+}$, similarly, $v_{f{u}_i}={\widehat{f}}^i{y}^{j+1}-f{x}^i$. We define the predicted descent $v_{u_i}={\widehat{e}}^i{y}^{j+1},c_i-e{x}^i,c_i$, it is not difficult to find that $v_{u_i}=v_{f{u}_i}+c_i{v}_{F{u}_i}$. We notice that $z_{u_i}\le 0$ (therefore, $v_{u_i}\le 0$) since $v_f,v_F,d=0,0,0$ is a feasible point of problem (12). Set$$\begin{array}{c}\text{(13)}& L{v}_f,v_F,d,\lambda ,\mu ,\gamma =v_f+c_i{v}_F+\frac{u_i}{2}{d}^2-{\displaystyle \sum }_{j\in B_{fi}^{+}}{\lambda }_j{v}_f-{g_f^j}^{\top }d+{\alpha }_f^j-{\displaystyle \sum }_{j\in B_{fi}^{-}}{\mu }_j{g_f^j}^{\top }d-{\alpha }_f^j-v_f-{\displaystyle \sum }_{j\in B_{Fi0}}{\gamma }_j{v}_F-{g_F^j}^{\top }d+{\alpha }_F^j.\end{array}$$

Let ${\nabla }_{d}L=0$; we obtain$$\begin{array}{}\text{(14)}& d=\frac{1}{u_i}-G_{+}^f\lambda +G_{-}^f\mu -G^F\gamma ,\end{array}$$where $G_{+}^f,G_{-}^f$ and $G^F$ are matrices whose columns are the vectors $g_f^j,j\in B_{fi}^{+},g_f^j,j\in B_{fi}^{-}$ and $g_F^j,j\in B_{Fi0}$. $\lambda ,\mu$ and $\gamma$ are the vectors with components ${\lambda }_j,j\in B_{fi}^{+},{\mu }_j,j\in B_{fi}^{-}$ and ${\gamma }_j,j\in B_{Fi0}$, respectively. Let ${\nabla }_{v_f}L=0$; we obtain$$\begin{array}{}\text{(15)}& {\displaystyle \sum }_{j\in B_{fi}^{+}}{\lambda }_j-{\displaystyle \sum }_{j\in B_{fi}^{-}}{\mu }_j=1,\end{array}$$i.e., ${\stackrel{\sim }{e}}^{\top }\lambda -{\stackrel{\sim }{e}}^{\top }\mu =1$, where $\stackrel{\sim }{e}={1,1,\dots ,1}^T$. Let ${\nabla }_{v_F}L=0$; we obtain$$\begin{array}{}\text{(16)}& c_i={\stackrel{\sim }{c}}_i+{\gamma }_0,{\stackrel{\sim }{c}}_i={\displaystyle \sum }_{j\in B_{Fi}}{\gamma }_j\ge 0.\end{array}$$

Substituting (14)–(16) into $L$, we have$$\begin{array}{}\text{(17)}& L{v}_f,v_F,d,\lambda ,\mu ,\gamma =-\frac{1}{2u_i}{G_{+}^f\lambda -G_{-}^f\mu +G^F\gamma }^2-{\alpha }_{f+}^{\top }\lambda +{\alpha }_{f-}^{\top }\mu -{\alpha }_F^{\top }\gamma ,\end{array}$$where ${\alpha }_{f+},{\alpha }_{f-}$ and ${\alpha }_F$ are vectors whose components are ${\alpha }_f^j,j\in B_{fi}^{+};{\alpha }_f^j,j\in B_{fi}^{-}$ and ${\alpha }_F^j,j\in B_{Fi0}$, respectively. Then, the duality problem of $Q{P}_{u_i}$ is the following minimization problem:$$\begin{array}{}\text{(18)}& D{P}_{u_i}\begin{array}{c}\min \frac{1}{2u_i}{G_{+}^f\lambda -G_{-}^f\mu +G^F\gamma }^2+{\alpha }_{f+}^{\top }\lambda -{\alpha }_{f-}^{\top }\mu +{\alpha }_F^{\top }\gamma ,\\ \mathrm{s}.\mathrm{t}.\lambda ,\mu ,\gamma \ge 0,\\ {\stackrel{\sim }{e}}^{\top }\lambda -{\stackrel{\sim }{e}}^{\top }\mu =1,\end{array}\end{array}$$and the primal optimal solution $v_{f_{u_i}},v_{F_{u_i}},d_{u_i}$ is related to the dual optimal solution $\lambda ,\mu ,\gamma$ by the following formulae:$$\begin{array}{}\text{(19)}& d_{u_i}=\frac{1}{u_i}-G_{+}^f\lambda +G_{-}^f\mu -G^F\gamma ,\text{(20)}& v_{u_i}=v_{f{u}_i}+c_i{v}_{F{u}_i}=-u_i{d_{u_i}}^2-{\alpha }_{f+}^{\top }{\lambda }_{u_i}+{\alpha }_{f-}^{\top }{\mu }_{u_i}-{\alpha }_F^{\top }{\gamma }_{u_i}.\end{array}$$

3. Algorithm

In this section, we present a nonconvex bundle algorithm for constrained nonconvex optimization problem (1). Our method is based on repeatedly solving problem (12).

A few comments on Algorithm 1 are in order.

Algorithm 1: A proximal bundle algorithm for nonconvex functions.

  Step 0 (Initialization):

   Choose $x^1$ such that $F{x}^1\le 0$. Choose the stationarity tolerance $\delta >0$, the proximity measure $\epsilon \ge 0$, the improvement parameter $m\in 0,1$, the cut parameter $\rho \in m,1$, the reduction parameter $r\in 0,1$, the increase parameter $R>1$, the infeasibility contraction bound $k_{\max }\in$ [0,1), the initial penalty coefficient $c_1>0$, and the maximal number of stored subgradients $M\ge n+2$. Set $y^1=x^1,B_{f1}^{+}=1,B_{f1}^{-}=\varnothing ,B_{F1}=1$. Set the outer iteration counter $i=1$, the inner iteration counter $j=1$.

  Step 1 (Safeguard parameters setting):

   If $g_f^i+c_i{g}_F^i\le \delta$, terminate; otherwise set $u_{\max }=g_f^i+c_i{g}_F^i/r\epsilon$, $u_{\min }=u_{\max }/R$, $\theta =r\delta /u_{\max }$.

  Step 2 (Direction finding):

   Solve $Q{P}_{u_i}$ repeatedly by choosing decreasing value of $u_i\in u_{\min },u_{\max }$ (for the first time choose $u_i=u_{\max }$) and find the solution $v_{f_{u_i}}^j,v_{F_{u_i}}^j,d_{u_i}^j$ of problem (12) for $u=u_i$ until $e{x}^i+d_{u_i}^j,c_i>e{x}^i,c_i+m{v}_{u_i}^j,$

   where $v_{u_i}^j=v_{f_{u_i}}^j+c_i{v}_{F_{u_i}}^j$. If such $u_i$ does exist, let $\widehat{u}$ equals the maximum value of $u_i\in u_{\min },u_{\max }$; otherwise set $\widehat{u}=u_{\min }$. Denote the optimal solution of $Q{P}_{\widehat{u}}$ by $v_{f\widehat{u}}^j,v_{F\widehat{u}}^j,d_{\widehat{u}}^j$, and set $y^{j+1}=x^i+d_{\widehat{u}}^j$. If $d_{\widehat{u}}^j>\theta$, go to Step 5.

  Step 3 (Penalty updating):

   If ${\widehat{F}}^i{y}^{j+1}>{\kappa }_{i}F{x^i}_{+}$, choose ${\kappa }_i\in 0,{\kappa }_{\max }$ and replace $c_i$ by $2c_i$, go to Step 2.

  Step 4 (Stationarity test):

   Set

    $B_{fi}^{+}=B_{fi}^{+}\backslash j\in B_{fi}^{+}|a_f^j>\epsilon ,B_{fi}^{-}=B_{fi}^{-}\backslash j\in B_{fi}^{-}|a_f^j>\epsilon .$

   Calculate

    $g^{\ast }=\min g|g\in \text{conv}{g}_f^j+c_i{g}_F^j,g_f^j,j\in B_{fi}^{+};g_F^j,j\in B_{Fi}$

   If $g^{\ast }\le \delta$, terminate; else set $u_{\min }$ := $u_{\min }{u}_{\max }/1-r{u}_{\max }+r{u}_{\min }$, go to Step 2.

  Step 5 (Trial point calculating):

   Compute $g_f^{j+1}\in {\partial }_{C}f{y}^{j+1}$, $g_F^{j+1}\in \partial F{y}^{j+1}$ and set ${\alpha }_f^{j+1}=f{x}^i-f{y}^{j+1}+{g_f^{j+1}}^T{d}_{\widehat{u}}^j$, ${\alpha }_F^{j+1}=F{x^i}_{+}-F{y}^{j+1}+{g_F^{j+1}}^T{d}_{\widehat{u}}^j$.

  Step 6 (Insertion of index):

   (a) If ${\alpha }_f^{j+1}<0$ and $d_{\widehat{u}}^j>\epsilon$, insert the element $y^{j+1},f{y}^{j+1},g_f^{j+1},{\alpha }_f^{j+1},d_{\widehat{u}}^j$ into the bundle for an appropriate value of $j\in B_{fi}^{-}$ and set $\widehat{u}$ := $\widehat{u}{u}_{\max }/1-r{u}_{\max }+r\widehat{u}$.

   (b) Else, if ${g_f^{j+1}+c_i{g}_F^{j+1}}^T{d}_{\widehat{u}}^j\ge \rho v_{\widehat{u}}^j$, insert the element $y^{j+1},f{y}^{j+1},g_f^{j+1}$, $\max 0,{\alpha }_f^{j+1},d_{\widehat{u}}^j$ into the bundle for an appropriate value of $j\in B_{fi}^{+}$.

   (c) Else find a scalar $t\in 0,1$ such that $g_{1}t+c_i{g}_{2}t\in \partial e{x}^i+t{d}_{\widehat{u}}^j,c_i$ satisfies the condition ${g_{1}t+c_i{g}_{2}t}^T{d}_{\widehat{u}}^j\ge \rho v_{\widehat{u}}^j$, where $g_{1}t\in {\partial }_{C}f{x}^i+t{d}_{\widehat{u}}^j$, $g_{2}t\in \partial F{x}^i+t{d}_{\widehat{u}}^j$, and insert the element $x^i+t{d}_{\widehat{u}}^j,f{x}^i+t{d}_{\widehat{u}}^j,g_{1}t$, $\max 0,{\alpha }_t,t{d}_{\widehat{u}}^j$ into the bundle for an appropriate value of $j\in B_{fi}^{+}$, where ${\alpha }_t=f{x}^i-f{x}^i+t{d}_{\widehat{u}}^j+t{g}_1{t}^T{d}_{\widehat{u}}^j$.

   (d) Insert the element $y^{j+1},F{y}^{j+1},g_F^{j+1},{\alpha }_F^{j+1}$ into the bundle $B_{Fi}$.

  Step 7 (Descent test):

   If

    $e{x}^i+d_{\widehat{u}}^j,c_i\le e{x}^i,c_i+m{v}_{\widehat{u}}^j,$

   set $u_i=\widehat{u}$, $d_{u_i}^i=d_{\widehat{u}}^j$, the new stability center $x^{i+1}=x^i+d_{u_i}^i$ (serious step); otherwise set $x^{i+1}=x^i$ (null step).

  Step 8 (Bundle updating):

   Select sets ${\tilde{B}}_{fi},{\tilde{B}}_{Fi}$ such that ${\widehat{B}}_{fi}\subset {\tilde{B}}_{fi}\subset B_{fi}$, ${\widehat{B}}_{Fi}\subset {\tilde{B}}_{Fi}\subset B_{Fi}$ and ${\tilde{B}}_{fi}+{\tilde{B}}_{Fi}\le M-2$, where ${\widehat{B}}_{fi}\subset B_{fi},{\widehat{B}}_{Fi}\subset B_{Fi}$ corresponding to nonzero multipliers satisfy ${\widehat{B}}_{fi}+{\widehat{B}}_{Fi}\le n+2$. Set $B_{fi+1}={\tilde{B}}_{fi}\cup i+1$, $B_{Fi+1}={\tilde{B}}_{Fi}\cup i+1$. Set $c_{i+1}=c_i$. If a serious step is taken, increase $i$ by 1 and go to Step 1, otherwise increase $j$ by 1 and go to Step 2.

  End of Algorithm1

The stopping criterion in Step 1 is used to assess the stationarity of current stability center. If it is satisfied, the approximate stationarity of exact penalty function is achieved, Algorithm 1 stops, and the approximate solution is obtained.

The solution $d_{\widehat{u}}^j,v_{f\widehat{u}}^j,v_{F\widehat{u}}^j$ of $Q{P}_{\widehat{u}}$ at Step 2 may be obtained by using the dual quadratic programming method of [29] or [31], which can efficiently solve sequences of subproblems $Q{P}_{u_i}$ with varying $u_i$ and $c_i$.

The result $d_{\widehat{u}}^j\le \theta$ is never a consequence of the choice of too big $\widehat{u}$. In fact, we note that if $g_f^i+c_i{g}_F^i>\delta$, it holds that$$\begin{array}{}\text{(21)}& d_{u_{\max }}\le \frac{2}{u_{\max }}{g}_f^i+c_i{g}_F^i=\frac{2\theta g_f^i+c_i{g}_F^i}{r\delta }.\end{array}$$

The right-hand side of the above inequality is more than $\theta$, so too big $\widehat{u}$ may not lead to $d_{\widehat{u}}^j\le \theta$, therefore we intend to decrease the value of $u$ in Step 2.

Large $c_i$ may force the iterate points generated by Algorithm 1 to approach closely to the boundary of the feasible set $S_F=x\in R^n|Fx\le 0$ and may damage the fast convergence of Algorithm 1. Our rule increases $c_i$ (from $c_{i-1}$) only to ensure a significant predicted decrease in constraint violation of the form ${\widehat{F}}^i{y}^{i+1}\le {\kappa }_{i}F{x^i}_{+}$, where ${\kappa }_i\in$ [0,1) is a contraction factor, see Step 3.

Finally, note that the insertion of a bundle index into $B_{fi}^{+}$ or $B_{fi}^{-}$ at Step 6 is not simply based on the sign of ${\alpha }_f^j$, see [15].

4. Convergence Results

The presented work in this section follows a line of investigation initiated in [6, 7], where nonconvex bundle algorithm is used to solve unconstrained minimization problem and the idea of exact penalty function is employed in proximal bundle method for constrained convex minimization problem. Here, we expand and generalize the central idea [6] to constrained nonconvex minimization problems; some techniques have to be adjusted to the new situations for the presence of constraints and nonconvexity.

Throughout the section, we make the following assumptions:

  (A1) $f$ and $F$ are weakly semismooth ($f$ is said to be weakly semismooth if the directional derivative $f^{\prime }x;d={\lim }_{t\downarrow 0}{t}^{-1}fx+td-fx$ exists for all $x$ and $d$, and $f^{\prime }x;d={\lim }_{t\downarrow 0}g{x+td}^{T}d$ where $gx+td\in \partial fx+td$).

  (A2) The set $S_1=x\in R^n|fx\le f{x}^1$ is compact, where $x^1$ is the initial point provided by the user in Algorithm 1.

  (A3) The feasible set $S_F=x\in R^n|Fx\le 0$ is bounded.

  (A4) The Slater constraint qualification holds, i.e., there exists $\stackrel{\sim }{x}\in R^n$ such that $F\stackrel{\sim }{x}<0$.

The assumption that the feasible set of problem (1) is bounded is usual and reasonable; it was also assumed in [7, 32–34]. In [27], the boundedness of the feasible set was assumed in order to guarantee the existence of the supremum of the range of a set-valued mapping on the feasible set. In [32], the authors assumed the feasible sets were bounded closed convex for finding the saddle point of the objective function.

Lemma 1.

Let $d_{\widehat{u}}^j,v_{\widehat{u}}^j$ be the sequence generated within an inner iteration such that $d_{\widehat{u}}^j>\theta$ and$$\begin{array}{}\text{(22)}& e{x}^i+d_{\widehat{u}}^j,c_i>e{x}^i,c_i+m{v}_{\widehat{u}}^j,\end{array}$$with Algorithm 1 looping between Step 2 and Step 8. Then, the following conclusions hold:

(i) There is an index $\widehat{j}$ such that for each $j\ge \widehat{j}$, every new bundle index with respect to $f$ is inserted into $B_{fi}^{+}$ and $\widehat{u}$ remains unchanged.

(ii) Step 6(c) is appropriate, feasible, and not difficult to realize.

(iii) Whenever a new bundle index is inserted into ${\mathrm{B}}_{\text{fi}}^{+}$, the condition ${g_f^{j+1}+c_i{g}_F^{j+1}}^{\top }{d}_{\widehat{u}}^j\ge \rho v_{\widehat{u}}^j$ holds, where $g_f^{j+1},g_F^{j+1}$ are the subgradients of $f$ and $F$ at $y^{j+1}$, respectively.

Proof.

(i) Since $\widehat{u}$ increases at Step 6(a) of Algorithm 1, the situation that infinite bundle indices are inserted into $B_{fi}^{-}$ can not happen. Hence, once $\widehat{u}$ exceeds ${\epsilon /2g_f^i+c_i{g}_F^i}^{-1}$, no bundle index with respect to $f$ can be inserted into $B_{fi}^{+}$.

(ii) According to Assumption (A1), $ex,c$ is weakly semismooth, the directional derivative $e^{\prime }{x}^i+t_i{d}_{\widehat{u}}^j,c_i;d_{\widehat{u}}^j$ exists for any $t_i>0$. It follows from the mean value theorem that $e{x}^i+d_{\widehat{u}}^j,c_i-e{x}^i,c_i=c$ for some $c\in e_{\inf }^{\prime },e_{\sup }^{\prime }$, where$$\begin{array}{}\text{(23)}& e_{\inf }^{\prime }=\underset{0\le t_i\le 1}{\inf }{e}^{\prime }{x}^i+t_i{d}_{\widehat{u}}^j,c_i;d_{\widehat{u}}^j,e_{\sup }^{\prime }=\underset{0\le t_i\le 1}{\sup }{e}^{\prime }{x}^i+t_i{d}_{\widehat{u}}^j,c_i;d_{\widehat{u}}^j.\end{array}$$

  Since the sufficient decrease condition Algorithm 1 is not satisfied, we have$$\begin{array}{}\text{(24)}& \rho v_{\widehat{u}}^j<m{v}_{\widehat{u}}^j<e{x}^i+d_{\widehat{u}}^j,c_i-e{x}^i,c_i,\end{array}$$

  there exists a scalar $\overline{t_i}\in 0,1$ such that $\rho v_{\widehat{u}}^j<e^{\prime }{x}^i+\overline{t_i}{d}_{\widehat{u}}^j,c_i;d_{\widehat{u}}^j.$ By weak semismoothness of $ex,c$, it is not difficult to find a scalar $t\in 0,1$ such that $g_{1}t+c_i{g}_{2}t\in \partial e{x}^i+t{d}_{\widehat{u}}^j,c_i$ satisfies the condition ${g_{1}t+c_i{g}_{2}t}^T{d}_{\widehat{u}}^j\ge \rho v_{\widehat{u}}^j$, where $g_{1}t\in {\partial }_{C}f{x}^i+t{d}_{\widehat{u}}^j$, $g_{2}t\in \partial F{x}^i+t{d}_{\widehat{u}}^j$.

(iii) By construction of Algorithm 1, we have ${g_f^{j+1}+c_i{g}_F^{j+1}}^{\top }{d}_{\widehat{u}}^j\ge \rho v_{\widehat{u}}^j$. If ${\alpha }_f^{j+1}-c_i{\alpha }_F^{j+1}\ge 0$ (the next Lemma 4 shows that $c_i$ can not be increased for infinitely many times, therefore, ${\alpha }_f^{j+1}-c_i{\alpha }_F^{j+1}\ge 0$ is possible), we also have$$\begin{array}{}\text{(25)}& {g_f^{j+1}+c_i{g}_F^{j+1}}^{\top }{d}_{\widehat{u}}^j\ge {g_f^{j+1}+c_i{g}_F^{j+1}}^{\top }{d}_{\widehat{u}}^j-{\alpha }_f^{j+1}+c_i{\alpha }_F^{j+1}=e{x}^i+d_{\widehat{u}}^j,c_i-e{x}^i,c_i>m{v}_{\widehat{u}}^j>\rho v_{\widehat{u}}^j,\end{array}$$

  the condition ${g_f^{j+1}+c_i{g}_F^{j+1}}^{\top }{d}_{\widehat{u}}^j\ge \rho v_{\widehat{u}}^j$ also holds.

The next lemma shows the finite termination of the inner iteration.

Lemma 2.

The inner iteration terminates after a finite number of steps.

Proof.

It is enough to demonstrate that, in a finite number of steps, either the condition of the stop at Step 1 or the exit at Step 4 is satisfied. Firstly, we prove Algorithm 1 cannot pass through Step 4 infinitely many times. Assume that such a case occurs, since at each iteration, the algorithm enters Step 4, then we have $d_{\widehat{u}}^j\le \theta$ and $g^{\ast }>\delta$. Observe that $\widehat{u}\ge u_{\min }$ and $u_{\min }$ will exceed the threshold $2g_f^i+c_i{g}_F^i/\epsilon$ in a finite number of steps. It follows that $d_{u_i}^j\le 2/u_i{g}_f^j+c_{i}g{f}_F^j$, therefore we obtain $d_{\widehat{u}}^j\le \epsilon$, which means that the indices of the new bundle elements are inserted into $B_{fi}^{+}$ and are never removed.

According to Step 6, we insert an index into $B_{fi}^{-}$ only if $d_{\widehat{u}}^j>\epsilon$, which implies that whenever entering Step 4, all the elements in $i\in B_{fi}^{-}$ are removed. Taking into account (15), (16), (19), and (20), there is an index $\stackrel{\sim }{j}$ such that for all $j\ge \stackrel{\sim }{j}$,$$\begin{array}{}\text{(26)}& d_{\widehat{u}}^j=-\frac{1}{\widehat{u}}{G}_{+}^f\lambda +G^F\gamma =-\frac{1}{\widehat{u}}{g}_{cf}^i+c_i{g}_{cF}^i,\end{array}$$where $g_{cf}^i=\text{conv}{g}_f^j|j\in B_{fi}^{+},g_{cF}^i=\text{conv}{g}_F^j|j\in B_{Fi}$. But since $d_{\widehat{u}}^j\le \theta$ and $g^{\ast }>\delta$, we have$$\begin{array}{}\text{(27)}& \theta \ge d_{\widehat{u}}^j=\frac{1}{\widehat{u}}{g}_{cf}^i+c_i{g}_{cF}^i\ge \frac{1}{u_{\max }}{g}^{\ast }>\frac{\theta }{r\delta }\delta >\theta ,\end{array}$$which leads to a contradiction.

Next, we show that it is impossible to have $d_{\widehat{u}}^j>\theta$ for infinitely many times and the descent condition Algorithm 1 is not satisfied with the algorithm looping between Step 4 and Step 8. Indexing by $j\in B_{Fi}\cup B_{fi}$, the jth passage through such a loop, we observe that, by Lemma 1(i), there exists an index $\overline{j}$ such that for every $j\ge \overline{j}$, the index of each new bundle element is put into $B_{fi}^{+}$ with $\widehat{u}$ remaining unchanged. Therefore, for $j\ge \overline{j}$, the sequence $z_{\widehat{u}}^j$ is nondecreasing and bounded and hence convergent. Since $d_{\widehat{u}}^j$ is bounded, suppose ${d_{\widehat{u}}^j}_{j\in B_{Fi}\cup B_{fi}}$ is its convergent subsequence. The sequence ${v_{\widehat{u}}^j}_{j\in B_{Fi}\cup B_{fi}}$ also converges to a nonpositive limit $\overline{v}$. Now assume that $\overline{v}<0$. Let $s$ and $t$ be two successive indices in $B_{Fi}\cup B_{fi}$ and let ${\beta }_f^s=\max 0,{\alpha }_f^s$ with ${\alpha }_f^s=e{x}^i,c_i-e{x}^i+d_{\widehat{u}}^s,c_i+{g_f^s+c_i{g}_F^s}^T{d}_{\widehat{u}}^s$ and $g_f^s\in {\partial }_{C}f{x}^i+d_{\widehat{u}}^s$, $g_F^s\in \partial F{x}^i+d_{\widehat{u}}^s$; we have$$\begin{array}{}\text{(28)}& v_{\widehat{u}}^t\ge {g_f^s+c_i{g}_F^s}^{\top }{d}_{\widehat{u}}^t-{\beta }_f^s,\end{array}$$$e{x}^i+d_{\widehat{u}}^s,c_i-e{x}^i,c_i>m{v}_{\widehat{u}}^s,$ and ${g_f^s+c_i{g}_F^s}^T{d}_{\widehat{u}}^s\ge \rho v_{\widehat{u}}^s$. If ${\beta }_f^s=0$; we have$$\begin{array}{}\text{(29)}& {g_f^s+c_i{g}_F^s}^{\top }{d}_{\widehat{u}}^t-{\beta }_f^s\ge \rho v_{\widehat{u}}^s,\end{array}$$if ${\beta }_f^s={\alpha }_f^s$, it holds that$$\begin{array}{}\text{(30)}& {g_f^s+c_i{g}_F^s}^{\top }{d}_{\widehat{u}}^s-{\beta }_f^s=e{x}^i+d_{\widehat{u}}^s,c_i-e{x}^i,c_i>m{v}_{\widehat{u}}^s>\rho v_{\widehat{u}}^s.\end{array}$$

Combing (28) and (29), we obtain $v_{\widehat{u}}^t-\rho v_{\widehat{u}}^s\ge {g_f^s+c_i{g}_F^s}^{\top }{d}_{\widehat{u}}^t-d_{\widehat{u}}^s$, hence by taking the limits $1-\rho \overline{v}\ge 0$, it contradicts $\overline{v}<0$, hence $\overline{v}=0$. It follows from $z_{\widehat{u}}^j\le 0$ that $v_{\widehat{u}}^j\ge \widehat{u}/2{d_{\widehat{u}}^j}^2$, which contradicts the fact that $d_{\widehat{u}}^j>\theta$.

The next lemma shows that the penalty coefficients are increased finitely many times under the conditions of Slater constraint qualification and the boundedness of $S_F$.

Lemma 3.

There exists $\overline{c}<\infty$such that${\widehat{F}}^i{y}^{j+1}\le 0$if$c_i\ge \overline{c}$.

Proof.

Denote the Lagrangian of $Q{P}_{u_i}$ by$$\begin{array}{c}\text{(31)}& L{v}_f,v_F,d,\lambda ,\mu ,\gamma =v_f+c_i{v}_F+\frac{u_i}{2}{d}^2-{\displaystyle \sum }_{j\in B_{fi}^{+}}{\lambda }_j{v}_f-{g_f^j}^{\top }d+{\alpha }_f^j-{\displaystyle \sum }_{j\in B_{fi}^{-}}{\mu }_j{g_f^j}^{\top }d-{\alpha }_f^j-v_f-{\displaystyle \sum }_{j\in B_{Fi0}}{\gamma }_j{v}_F-{g_F^j}^{\top }d+{\alpha }_F^j.\end{array}$$

The Lagrange multipliers satisfy the usual saddle-point condition:$$\begin{array}{}\text{(32)}& L{v}_{f{u}_i},v_{F{u}_i},d_{u_i},{\lambda }_i,{\mu }_i,{\gamma }_i\le L{v}_f,v_F,d,{\lambda }_i,{\mu }_i,{\gamma }_i,\end{array}$$for all $d,v_f,v_F$. For the above inequality, we take $d={\stackrel{\sim }{d}}_{u_i}=\stackrel{\sim }{x}-x^i$, where $\stackrel{\sim }{x}$ is the one in Assumption (A4), and then by using (15) and (16), we obtain$$\begin{array}{c}\text{(33)}& \frac{u_i}{2}{d_{u_i}}^2+{p_f^i}^T{d}_{u_i}-{\displaystyle \sum }_{j\in B_{f_i}^{+}}{\lambda }_j{\alpha }_f^j+{\displaystyle \sum }_{j\in B_{f_i}^{-}}{\mu }_j{\alpha }_f^j+c_i{g_F^j}^T{d}_{u_i}-{\alpha }_F^j\le \frac{u_i}{2}{{\stackrel{\sim }{d}}_{u_i}}^2+{p_f^i}^T{\stackrel{\sim }{d}}_{u_i}-{\displaystyle \sum }_{j\in B_{f_i}^{+}}{\lambda }_j{\alpha }_f^j+{\displaystyle \sum }_{j\in B_{f_i}^{-}}{\mu }_j{\alpha }_f^j+c_i{g_F^j}^T{\stackrel{\sim }{d}}_{u_i}-{\alpha }_F^j,\end{array}$$where $p_f^i={{\displaystyle \sum }}_{j\in B_{fi}^{+}}{\lambda }_j{g}_f^j-{{\displaystyle \sum }}_{j\in B_{fi}^{-}}{\mu }_j{g}_f^j$. Remove the same terms from both sides of (33) and note that ${g_F^j}^T{d}_{u_i}-{\alpha }_F^j=v_{F_{u_i}}={\widehat{F}}^i{y^{j+1}}_{+}-F{x^i}_{+}$, ${g_F^j}^T{\stackrel{\sim }{d}}_{u_i}-{\alpha }_F^j={g_F^j}^T{\stackrel{\sim }{d}}_{u_i}-F{x^i}_{+}+F{y}^j+g_F^j,x^i-y^j$, and the subgradient inequality of convex function $F{y}^j+g_F^j,x^i-y^j+g_F^j,\stackrel{\sim }{x}-x^i\le F\stackrel{\sim }{x}$; we have$$\begin{array}{}\text{(34)}& \frac{1}{2}{u}_i{d_{u_i}}^2+{p_f^i}^T{d}_{u_i}+c_i{\widehat{F}}^i{y^{j+1}}_{+}\le \frac{1}{2}{u}_i{{\stackrel{\sim }{d}}_{u_i}}^2+{p_f^i}^T{\stackrel{\sim }{d}}_{u_i}+c_{i}F\stackrel{\sim }{x}.\end{array}$$

Since $c_i={\stackrel{\sim }{c}}_i+{\gamma }_0$, ${\gamma }_0\ge 0$, and Assumption (A4) tells us that $F\stackrel{\sim }{x}<0$, the following inequality holds:$$\begin{array}{}\text{(35)}& \frac{1}{2}{u}_i{d_{u_i}}^2+{p_f^i}^T{d}_{u_i}+c_i{\widehat{F}}^i{y^{j+1}}_{+}\le \frac{1}{2}{u}_i{{\stackrel{\sim }{d}}_{u_i}}^2+{p_f^i}^T{\stackrel{\sim }{d}}_{u_i}+{\stackrel{\sim }{c}}_{i}F\stackrel{\sim }{x}.\end{array}$$

Recalling that $g_f^j$ is locally bounded, let $D=\sup x-y|x,y\in S_F$ and $C_g=\sup g_f^j|j\in I_{fi}$. The existence of $C_g$ can be guaranteed by the aggregate technique of bundle methods. Then,$$\begin{array}{}\text{(36)}& {\stackrel{\sim }{c}}_i-F\stackrel{\sim }{x}+c_i{\widehat{F}}^i{y^{j+1}}_{+}\le \frac{1}{2}\overline{u}{D}^2+D{C}_g≕L,\end{array}$$where $\overline{u}$ is the upper bound of $u_i$. Now, if we take $\overline{c}=-L/F\stackrel{\sim }{x}$, the conclusion can be obtained.

Lemma 4.

There exist an index$\overline{i}$and$\overline{c}>0$such that$c_i=\overline{c}$for all$i\ge \overline{i}$.

Proof.

According to the result of Lemma 3, there exists one $\overline{c}>0$ such that ${\widehat{F}}^i{y}^{j+1}>{\kappa }_{i}F{x}^i$ does not hold for $c_i\ge \overline{c}$. Therefore, Step 3 in Algorithm 1 will not be executed once $c_i\ge \overline{c}$. The penalty coefficient $c_i$ remains constant $\overline{c}$.

Note that Lemmas 3 and 4 ensure the number of iterations between Step 2 and Step 3 is finite, and the penalty coefficients stay unchanged after finitely many iterations.

Now, we are ready to prove the overall finiteness of Algorithm 1.

Theorem 5.

Suppose Assumptions (A1)–(A4) hold, then for any $\epsilon >0$ and $\delta >0$, Algorithm 1 stops at a point satisfying the approximate stationarity condition$$\begin{array}{}\text{(37)}& g^{\ast }\le \delta ,\end{array}$$with $g^{\ast }\in {\partial }_{\epsilon }^{G}f{x}^i+c_i{\partial }_{\epsilon }^{G}F{x}^i$.

Proof.

For contradiction, assume that the approximate stationarity condition (37) cannot be satisfied for an infinite number of iterations. In other words, the termination condition $g^{\ast }\le \delta$ in Step 4 is not satisfied for each iteration. Therefore, Algorithm 1 is executed for infinitely many times. It follows from Lemma 2 that the descent condition Algorithm 1 is satisfied for each iteration. Let $x^i$ be the stability center at the jth iteration through inner iteration, then $d_{\widehat{u}}^j>\theta$ and $e{x}^{i+1},c_{i+1}\le e{x}^i,c_i+m{v}_{\widehat{u}}^j$, hence$$\begin{array}{}\text{(38)}& e{x}^{i+1},c_{i+1}-e{x}^1,c_1\le m{\displaystyle \sum }_{s=1}^j{v}_{\widehat{u}}^s.\end{array}$$

Since $u_{\max }=2g_f^i+c_i{g}_F^i/r\epsilon$ and $\theta =r\delta 1/u_{\max }$, it follows that, if $i$ is big enough,$$\begin{array}{}\text{(39)}& \theta =\frac{r^2\epsilon \delta }{2g_f^i+c_i{g}_F^i}\ge \frac{r^2\epsilon \delta }{2L_f+c_i{L}_F}\ge \frac{r^2\epsilon \delta }{2L_f+\overline{c}{L}_F},\end{array}$$where $\overline{c}$ is the constant appeared in Lemma 3 and $L_f$ and $L_F$ are the locally Lipschitz constants of $f$ and $F$ on $S_1$. Therefore, $d_{\widehat{u}}^j$ is bounded away from zero. It follows from $z_{\widehat{u}}^j\le 0$ that $v_{\widehat{u}}^j\ge \widehat{u}/2{d_{\widehat{u}}^j}^2$. Hence, $v_{\widehat{u}}^j$ is bounded away from zero as well. Therefore, by passing to the limit, we obtain$$\begin{array}{}\text{(40)}& \underset{i⟶\infty }{\lim }e{x}^{i+1},c_{i+1}-e{x}^1,c_1\le -\infty .\end{array}$$

Note that $f$ is bounded from below as a consequence of the semismoothness of $f$ and the compactness of the level set $S_1$ of $f$. By combining the fact $f{x}^{i+1}\le e{x}^{i+1},c_{i+1}$ and (40), we obtain ${\lim }_{i⟶\infty }f{x}^{i+1}=-\infty$, and $f$ is unbounded, which leads to a contradiction. Hence, Algorithm 1 cannot be executed for infinitely many times; it stops at a point satisfying condition (37).

5. Numerical Experiments

To assess practical performance of the presented method, we coded Algorithm 1 in MATLAB and ran it on a PC with 1.80 GHz CPU.

5.1. Examples for Nonconvex Optimization Problems

In this subsection, we first introduce the nonconvex test problems. We prefer a series of polynomial functions developed in [35], also see [23, 36]. For each $i=1,2,\dots ,n$, the function $h_i:R^n⟶R$ is defined by$$\begin{array}{}\text{(41)}& h_{i}x={\displaystyle \sum }_{j=1}^n{x}_j+i{x}_i^2-2x_i.\end{array}$$

There are four classes of test functions defined by $h_i$ in [36] as objective functions. It has been proved in [23, 36] that they are nonconvex, globally lower $-C^1$, level coercive, and bounded on compact $\mathcal{X}=B_{15}0$. We use one of these test functions to verify the validity and efficiency of the proposed method.

Example 1.

Consider problem (1):$$\begin{array}{c}\text{(42)}& \underset{x\in {\mathbf{R}}^n}{\min } fx,\mathrm{s}.\mathrm{t}.Fx\le 0.\end{array}$$

For objective function, we define the nonconvex function$$\begin{array}{}\text{(43)}& fx≔{\displaystyle \sum }_{i=1}^n{h}_{i}x+\frac{1}{2}{x}_2,n=4.\end{array}$$

For constraint function, we consider the pointwise maximum of a finite collection of quadratic functions:$$\begin{array}{c}\text{(44)}& Fx=\max F_{1}x,F_{2}x,F_{3}x,F_{4}x,F_{1}x=-x_1^2-27\ast x_1-2\ast x_4^2-22\ast x_4-23\ast x_2-21\ast x_3-x_2\ast x_2+x_3-9;\\ F_{2}x=-x_1^2-28\ast x_1-2\ast x_2^2-29\ast x_2-x_4^2-21\ast x_4-21\ast x_3-3;\\ F_{3}x=-27\ast x_1-22\ast x_2-21\ast x_3-24\ast x_4-x_3\ast x_2+2\ast x_3-x_2^2-5;\\ F_{4}x=-22\ast x_1-23\ast x_2-31\ast x_3-22\ast x_4-x_1\ast x_1+x_3-x_1\ast x_2-x_3^2-x_4^2-3.\end{array}$$

For problem (1) with (43) and (44), we can obtain that $0=\underset{Fx\le 0}{\min }fx$ and $0\subseteq \underset{Fx\le 0}{\mathrm{argmin}}fx$. The results of numerical experiment are as follows:

  The initial point: $x_0=3,3,3,3$;

  Optimal solution: $x_{\text{final}}=1.0e-03\times 0.63,0.50,0.74,0.36$;

  The final objective function value: $f_{\text{final}}=0.0056$;

  The final constraint function value: $F_{\text{final}}=-3.0051$;

  The CPU time: 0.25 seconds.

Example 2.

Consider problem (1):$$\begin{array}{c}\text{(45)}& \underset{x\in {\mathbf{R}}^n}{\min } fx,\mathrm{s}.\mathrm{t}.Fx\le 0.\end{array}$$

For objective function, we define the nonconvex function$$\begin{array}{}\text{(46)}& fx≔{\displaystyle \sum }_{i=1}^n{h}_{i}x+\frac{1}{2}{x}_2,n=6.\end{array}$$

For constraint function, we consider the pointwise maximum of a finite collection of quadratic functions:$$\begin{array}{c}\text{(47)}& Fx=\max F_{1}x,F_{2}x,F_{1}x=-37\ast x_1-33\ast x_2-41\ast x_3-32\ast x_4-33\ast x_5-36\ast x_6-x_2\ast x_4-x_5\ast x_6\\ -x_1\ast x_1+2\ast x_5-x_6\ast 3\ast x_2+x_5-x_4\ast x_1+x_3+x_4\\ -x_3\ast x_2+x_5+x_6-19;\\ F_{2}x=-39\ast x_1-52\ast x_2-27\ast x_3-32\ast x_4-26\ast x_5-32\ast x_6-x_3\ast x_4+x_6\\ -x_2\ast x_2-x_3+3\ast x_5-x_4\ast 2\ast x_2+2\ast x_5+x_6-x_1\ast x_1-x_6\\ -x_5\ast 2\ast x_1+x_3+x_4-11.\end{array}$$

For problem (1) with (46) and (47), we can obtain that $0={\min }_{Fx\le 0}fx$ and $0\subseteq {\mathrm{argmin}}_{Fx\le 0}fx$. The results of the numerical experiment are as follows:

  The initial point: $x_0=1,1,1,1,1,1$;

  Optimal solution: $x_{\text{final}}=1.0e-05\times 0.12,-0.07,0.09,-0.02,0.00,-0.02$;

  The final objective function value: $f_{\text{final}}=9.78e-06$;

  The final constraint function value: $F_{\text{final}}=-11.00$;

  The CPU time: 15.47 seconds.

The above two examples show that the proposed Algorithm 1 does perform not badly since the optimal solutions $1.0e-03\times 0.63,0.50,0.74,0.36$ and $1.0e-05\times 0.12,-0.07,0.09,-0.02,0.00,-0.02$ computed, respectively, by Algorithm 1 are not far away from the true optimal solution to problem (1).

6. Conclusion

For constrained nonconvex optimization problem, we propose an implementable algorithm by combining bundle ideas, proximal control, and exact penalty functions. The results extend the ideas of cutting plane and proximity control to the constrained nonconvex case. We present some techniques for choosing penalty coefficients which ensures the limitation of penalty growth. The penalty parameters are increased only a finite number of times which prevents the algorithm from following closely the curvature boundary of the constrained set. For weakly semismooth functions, the convergence of the presented algorithm to an approximate stationary point of the exact penalty function is proved without any additional assumptions except for the conditions of Slater constraint qualification and the boundedness of the constrained set.

Acknowledgments

This work was supported by the National Nature Science Foundation of China (grant numbers 61877032 and 11601061) and Basic Scientific Research Project of Educational Department of Liaoning Province (grant number JYTMS20231042).

References

[1] E. S. Mistakidis, G. E. Stavroulakis, Nonconvex Optimization in Mechanics. Smooth and Nonsmooth Algorithms, Heuristics and Engineering Applications, 1998.

[2] J. Outrata, M. Kocvara, J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Theory, Applications and Numerical Results, 1998.

[3] J. J. Moreau, P. D. Panagiotopoulos, G. Strang, Topics in Nonsmooth Mechanics, 1988.

[4] F. H. Clarke, Y. S. Ledyaev, R. J. Stern, P. R. Wolenski, Nonsmooth Analysis and Control Theory, 1998.

[5] K. Miettinen, Nonlinear Multiobjective Optimization, 1999.

[6] A. Fuduli, M. Gaudioso, G. Giallombardo, "Minimizing nonconvex nonsmooth functions via cutting planes and proximity control," SIAM Journal on Optimization, vol. 14 no. 3, pp. 743-756, DOI: 10.1137/s1052623402411459, 2004.

[7] K. C. Kiwiel, "Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization," Mathematical Programming, vol. 52 no. 1-3, pp. 285-302, DOI: 10.1007/bf01582892, 1991.

[8] L. P. Pang, Z. Q. Xia, "A PVT-type algorithm for minimizing a nonsmooth convex function," Serdica Mathematical Journal, vol. 29 no. 1, pp. 11-32, 2003.

[9] L. P. Pang, Z. Q. Xia, L. W. Zhang, "On a second order parallel variable transformation approach," Journal of Applied Mathematics and Computing, vol. 11 no. 1-2, pp. 201-213, DOI: 10.1007/bf02935732, 2003.

[10] M. Gaudioso, E. Gorgone, "Gradient set splitting in nonconvex nonsmooth numerical optimization," Optimization Methods and Software, vol. 25 no. 1, pp. 59-74, DOI: 10.1080/10556780903236911, 2010.

[11] C. Lemarechal, "Lagrangian relaxation," Computational combinatorial optimization: optimal or provably near-optimal solutions, pp. 112-156, 2001.

[12] D. Noll, "Bundle method for non-convex minimization with inexact subgradients and function values," Computational and Analytical Mathematics, Volume 50 of Springer Proceedings in Mathematics and Statistics, pp. 555-592, 2013.

[13] W. Hare, C. Sagastizabal, M. Solodov, "A proximal bundle method for nonsmooth nonconvex functions with inexact information," Computational Optimization and Applications, vol. 63 no. 1,DOI: 10.1007/s10589-015-9762-4, 2016.

[14] Y. Yang, L. Pang, X. Ma, J. Shen, "Constrained nonconvex nonsmooth optimization via proximal bundle method," Journal of Optimization Theory and Applications, vol. 163 no. 3, pp. 900-925, DOI: 10.1007/s10957-014-0523-9, 2014.

[15] E. W. Cheney, A. A. Goldstein, "Newton’s method for convex programming and Tchebycheff approximation," Numerical Mathematics, vol. 1, pp. 253-268, DOI: 10.1007/bf01386389, 1959.

[16] J. E. Kelley Jr., "The cutting-plane method for solving convex programs," Journal of the Society for Industrial and Applied Mathematics, vol. 8 no. 4, pp. 703-712, DOI: 10.1137/0108053, 1960.

[17] C. A. Sagastizabal, M. V. Solodov, "An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter," SIAM Journal on Optimization, vol. 16 no. 1, pp. 146-169, DOI: 10.1137/040603875, 2005.

[18] E. Karas, A. Ribeiro, C. A. Sagastizabal, M. V. Solodov, "A bundle-filter method for nonsmooth convex constrained optimization," Mathematical Programming, vol. 116 no. 1-2, pp. 297-320, DOI: 10.1007/s10107-007-0123-7, 2009.

[19] K. C. Kiwiel, "An exact penalty function algorithm for nonsmooth convex constrained minimization problems," IMA Journal of Numerical Analysis, vol. 5 no. 1, pp. 111-119, DOI: 10.1093/imanum/5.1.111, 1985.

[20] H. Schramm, J. Zowe, "A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results," SIAM Journal on Optimization, vol. 2 no. 1, pp. 121-152, DOI: 10.1137/0802008, 1992.

[21] K. C. Kiwiel, "Restricted step and Levenberg-Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization," SIAM Journal on Optimization, vol. 6 no. 1, pp. 227-249, DOI: 10.1137/0806013, 1996.

[22] D. Noll, "Cutting plane oracles to minimize non-smooth non-convex functions," Set-Valued and Variational Analysis, vol. 18 no. 3-4, pp. 531-568, DOI: 10.1007/s11228-010-0159-3, 2010.

[23] W. Hare, C. Sagastizabal, "A redistributed proximal bundle method for nonconvex optimization," SIAM Journal on Optimization, vol. 20 no. 5, pp. 2442-2473, DOI: 10.1137/090754595, 2010.

[24] A. Fuduli, M. Gaudioso, E. A. Nurminski, "A splitting bundle approach for non-smooth non-convex minimization," Optimization, vol. 64 no. 5, pp. 1131-1151, DOI: 10.1080/02331934.2013.840625, 2015.

[25] A. Fuduli, M. Gaudioso, G. Giallombardo, "A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization," Optimization Methods and Software, vol. 19 no. 1, pp. 89-102, DOI: 10.1080/10556780410001648112, 2004.

[26] J. V. Burke, A. S. Lewis, M. L. Overton, "A robust gradient sampling algorithm for nonsmooth, nonconvex optimization," SIAM Journal on Optimization, vol. 15 no. 3, pp. 751-779, DOI: 10.1137/030601296, 2005.

[27] K. C. Kiwiel, "Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization," SIAM Journal on Optimization, vol. 18 no. 2, pp. 379-388, DOI: 10.1137/050639673, 2007.

[28] W. Hare, C. Sagastizabal, "Computing proximal points of nonconvex functions," Mathematical Programming, vol. 116 no. 1-2, pp. 221-258, DOI: 10.1007/s10107-007-0124-6, 2009.

[29] K. C. Kiwiel, "A dual method for certain positive semidefinite quadratic programming problems," SIAM Journal on Scientific and Statistical Computing, vol. 10 no. 1, pp. 175-186, DOI: 10.1137/0910013, 1989.

[30] F. H. Clarke, Optimization and Nonsmooth Analysis, 1983.

[31] A. Fuduli, M. Gaudioso, "The proximal trajectory algorithm for convex minimization," 1998. Technical Report 7/98

[32] C. Lemarechal, A. Nemirovskii, Y. Nesterov, "New variants of bundle methods," Mathematical Programming, vol. 69 no. 1-3, pp. 111-147, DOI: 10.1007/bf01585555, 1995.

[33] R. Mifflin, "An algorithm for constrained optimization with semismooth functions," Mathematics of Operations Research, vol. 2, pp. 191-207, DOI: 10.1287/moor.2.2.191, 1977.

[34] R. Fletcher, S. Leyffer, "A bundle filter method for nonsmooth nonlinear optimization," 1999. Numerical Analysis Report NA/195

[35] C. Ferrier, "Bornes Duales de Problemes d’Optimisation Polynomiaux," 1997. Ph.D. thesis

[36] C. Ferrier, "Computation of the distance to semi-algebraic sets," ESAIM: Control, Optimisation and Calculus of Variations, vol. 5, pp. 139-156, DOI: 10.1051/cocv:2000104, 2000.