# An Objective Penalty Function-Based Method for Inequality Constrained Minimization Problem

Authors: Shujun Lian; Sitong Meng; Yiju Wang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

For inequality constrained minimization problem, we first propose a new exact nonsmooth objective penalty function and then apply a smooth technique to the penalty function to make it smooth. It is shown that any minimizer of the smoothing objective penalty function is an approximated solution of the original problem. Based on this, we develop a solution method for the inequality constrained minimization problem and prove its global convergence. Numerical experiments are provided to show the efficiency of the proposed method.


---

## Body

## 1. Introduction

Consider the following inequality constrained minimization problem:Pminfxs.t.gix≤0,i∈I=1,2,…,mwhere f,gi:Rn→R,i∈I are continuously differentiable functions. Throughout this paper, we use X=x∈Rn∣gix≤0,i∈I to denote the feasible solution set.The problem finds applications in fields such as economics, mathematical programming, transportation, and regional science [1–5], and it has received much attention from researchers; see, e.g., [6–16].Due to the involvement of the inequality constraint in the problem, it is very hard to solve directly. Hence, some researchers turn to indirect methods such as the penalty function method, the SQP method, and the feasible direction method [17]. Among these methods, the penalty function method is a popular one. Its main idea is to combine the objective function and constraints into a penalty function and then attack problem P by solving a sequence of unconstrained problems. Generally, if the solution of the original problem is the solution of the penalty problem or the solution of the penalty problem is the solution of the original problem, then the penalty function is called exact [17]. For this, Zangwill [18] proposed the following classical l1 exact penalty function: (1)Fx,ρ=fx+ρ∑i∈Igi+x,where ρ>0 is a penalty parameter and gi+(x)=maxgix,0,i∈I.Obviously, the penalty function given above is not smooth and the researchers considered its smoothing version [19–25]. In [26], the lower-order penalty function, (2)φρ,kx=fx+ρ∑i=1mmaxgix,0k,k∈0,1,was introduced and its exact property and its smoothing were investigated [27, 28].To improve the performance of the penalty function when solving the inequality constrained optimization problem, the following objective penalty function is introduced [29, 30]: (3)F1x,M=fx-Mp+∑i∈Igixp,where M∈R is an objective penalty parameter and p>0. Assume that x∗ is an optimal solution and f0(x∗) is the optimal objective function value of the original problem P. For this function, it is shown that the minimizers x(Mk) of the problem min⁡F1(x,Mk) tend to x∗ when a convergent sequence Mk tends to f0(x∗).Later, Meng et al. [31] considered the following objective penalty function: (4)F2x,M=fx-M2+∑i∈Igi+xp,where p>1 and M∈R is an objective penalty parameter. The objective penalty function is smooth and its exact property was proved for the objective penalty function.Li et al. [32] proposed the following objective penalty function for solving minmax programming problems with equality and inequality constraints: (5)Ex,t;M,ρ=12t-M+2+ρ2∑i∈Ifix-t+2+∑i∈Jgj+x2+∑i∈Lhl2xby combining the objective penalty and constraint penalty.In this paper, we will propose a new exact nonsmooth objective penalty function which is different from the functions defined by (3) and (4). Then motivated by the smoothing technique of the l1 exact penalty function in [23–25], we make a smoothing to the nonsmooth objective penalty function so that the nonsmooth objective penalty function can be numerically minimized by methods such as gradient-type method or Newton-type method.The remainder of this paper is organized as follows. In Section2, we propose a new exact nonsmooth objective penalty function and then make a second-order smoothing approximation to it. Error bound estimations among the optimal objective values of the nonsmooth objective penalty problem and the smoothed objective penalty problem are presented. Based on the second-order differentiable smoothing objective penalty function, we develop a solution method in Section 3 and prove its global convergence. Some numerical experiments are made in Section 4 to show the efficiency of the proposed method.


## 2. A New Objective Penalty Function and Its Smoothing

In this section, we consider the following objective penalty function:(6)Gx,M=fx-M2+∑i∈Igi+x.Correspondingly, the associated optimization problem is as follows: PMminGx,Ms.t.x∈Ywhere X⊂Y⊂Rn.For this problem, we have the following conclusion on the relationship between the optimal solution ofPM and P.Theorem 1.
Ifx∗ is an optimal solution of problem P, then x∗ is also an optimal solution of problem PM with M=fx∗.Proof.
Sincex∗ is an optimal solution to P and M=f(x∗), it holds that (7)Gx∗,M=fx∗-M2+∑i∈Igi+x∗=0.It is easy to see that G(x,M)≥0 for any x∈Rn. Hence x∗ is an optimal solution to PM.Theorem 2.
LetX be a connected and compact set and f:Rn→R be a continuous function. Set M∗=minx∈Xf(x) and M∗=maxx∈Xf(x). Suppose xM∗ is an optimal solution to PM for some M. Then
(i) ifG(xM∗,M)=0, then xM∗ is a feasible solution to P and M∗≤M≤M∗;
(ii) ifGxM∗,M>0 and M≤M∗, then M<M∗.Proof.
(i) It follows fromG(xM∗,M)=0 that gi(xM∗)≤0,∀i∈I, and f(xM∗)-M=0, so M∗≤M=f(xM∗)≤M∗. The conclusion is proved.
(ii) IfM∗≤M, then M∗≤M≤M∗. Since f is continuous, there exists x∈X such that M=f(x). Hence G(x,M)=0. On the other hand, since xM∗ is optimal to PM, it holds that G(xM∗,M)≤G(x,M)=0, which is contradict with G(xM∗,M)>0. Therefore, M<M∗.Theorem 3.
LetX be a connected and compact set, f:Rn→R be a continuous function, M∗=minx∈Xf(x) and M∗=maxx∈Xf(x), and x∗ be an optimal solution to P. Suppose xM∗ is an optimal solution to PM for some M, G(xM∗,M)>0, and M≤M∗. Then
(i) ifxM∗ is not feasible to P, then M<M∗ and fxM∗<M∗;
(ii) ifxM∗ is a feasible solution to P, then xM∗ is an optimal solution to P and M is an exact value of the objective penalty parameter.Proof.
(i) By (ii) in Theorem2, M<f(x∗)=M∗. If f(xM∗)≤M, then f(xM∗)≤M<M∗. On the other hand, if f(xM∗)>M, and from (6), one has (8)0<fxM∗-M2<GxM∗,M≤Gx∗,M=fx∗-M2.Since f(xM∗)-M>0 and f(x∗)-M>0, it follows that f(xM∗)-M<f(x∗)-M. Hence, f(xM∗)<f(x∗)=M∗.
(ii) It follows from the assumption and (6) that (9)0<fxM∗-M2=GxM∗,M≤Gx,M=fx-M2,∀x∈X.Since xM∗ is feasible to P, by (ii) in Theorem 2, one has M<M∗<f(xM∗) and M<M∗<f(x),∀x∈X. Hence, fxM∗-M>0 and f(x)-M>0. Then, (10)fxM∗-M≤fx-M,∀x∈X.Therefore, (11)fxM∗≤fx,∀x∈X.This means that xM∗ is an optimal solution to P.Theorems2 and 3 provide a way to solve problem P. However, the objective penalty function G(x,M) is not smooth. Now, we use a smoothing technique to make it twice continuously differentiable which can be minimized by methods such as Newton-type method. The obtained smooth objective penalty function is much different from the functions given in [23–25].Letpt=maxt,0, and define (12)pεt=14εe2t/ε,t≤0,t+14εe-2t/ε,t>0.Then (13)pε′t=12e2t/ε,t≤0,1-12e-2t/ε,t>0,and (14)pε′′t=1εe2t/ε,t≤0,1εe-2t/ε,t>0.It is easy to see that function pε(t) is twice continuously differentiable on R and (15)limε→0+pεt=pt.Based on this, we consider the following second-order smoothing approximation:(16)Gx,M,ε=fx-M2+∑i∈Ipεgix,where limε→0+G(x,M,ε)=G(x,M).The corresponding optimization problem toG(x,M,ε) is as follows: PM′minGx,M,εs.t.x∈Y.For problemsPM and PM′, we have the following conclusion.Lemma 4.
For anyx∈Rn and ε>0, it holds that (17)0≤Gx,M,ε-Gx,M≤14mε.Proof.
From the definition ofp(t) and pε(t), one has (18)pεt-pt=14εe2t/ε,t≤0,14εe-2t/ε,t>0.Hence, (19)0≤pεt-pt≤14ε.
Thus, for anyx∈Rn, it holds that (20)0≤pεgix-pgix≤14ε,∀i∈I,which means that (21)0≤∑i∈Ipεgix-∑i∈Ipgix≤14mε.It follows from (6) and (16) that (22)0≤Gx,M,ε-Gx,M≤14mε.Theorem 5.
Suppose positive sequence{εj} converges to 0 as j→∞, xj is a solution to minx∈YG(x,M,εj), and x¯ is an accumulating point of sequence {xj}. Then x¯ is an optimal solution to minx∈YGx,M.Proof.
Sincexj is a solution to minx∈YG(x,M,εj), one has (23)Gxj,M,εj≤Gx,M,εj.
It follows from Lemma4 that (24)Gxj,M≤Gxj,M,εj,and (25)Gx,M,εj≤Gx,M+14mεj.
From (23), (24), and (25), one has (26)Gxj,M≤Gxj,M,εj≤Gx,M,εj≤Gx,M+14mεj.Letting j→∞ yields (27)Gx¯,M≤Gx,M.Thus x¯ is an optimal solution to minx∈YGx,M.Theorem 6.
Letx∗ be an optimal solution of PM and x¯ be an optimal solution of PM′. Then (28)0≤Gx¯,M,ε-Gx∗,M≤14mε.Proof.
By Lemma4 and the assumption, one has (29)0≤Gx¯,M,ε-Gx¯,M≤Gx¯,M,ε-Gx∗,M,and (30)Gx¯,M,ε-Gx∗,M≤Gx∗,M,ε-Gx∗,M≤14mε.Then (31)0≤Gx¯,M,ε-Gx∗,M≤14mε.Theorem6 means that the optimal solution to PM′ is also an approximately optimal solution to PM when ε is sufficiently small.


## 3. A Smoothing Method

In this section, we will propose an algorithm for solving problemP based on the smoothed objective penalty function G(x,M,ε). The following algorithm is based on the relationship between M and M∗ given in Theorems 2 and 3.Algorithm 7.
Step  1. Take x0∈Rn,ε1>0,0<η<1,a1<minx∈Xf(x) and minx∈Xf(x)<b1<maxx∈Xf(x). Let M1=a1+b1/2, j=1.
Step  2. Solve minx∈YG(x,Mj,εj) starting at xj-1. Let xj be the global optimal solution. (xj is obtained by a quasi-Newton method.)
Step  3. If G(xj,Mj)=0, let aj+1=aj, bj+1=Mj, Mj+1=aj+1+bj+1/2, εj+1=ηεj, j=j+1 and go to Step 2.
Step  4. If xj is not feasible to P, let bj+1=bj, aj+1=Mj, Mj+1=aj+1+bj+1/2, εj+1=ηεj, j=j+1 and go to Step 2. Otherwise, if xj is feasible to P, xj is the approximate optimal solution to P.For Algorithm7, we always assume that a1<minx∈Xf(x) and minx∈Xf(x)<b1<maxx∈Xf(x) can be satisfied. Under this condition, we can establish the global convergence of Algorithm 7.Theorem 8.
Suppose thatlimx→+∞f(x)=+∞ and {xj} is an infinite sequence generated by Algorithm 7. Then the following hold:
(1) If the algorithm terminates at stepj¯, then xj¯ is an optimal solution to P.
(2) If the algorithm generates an infinite sequencexj, then it is bounded and its any limit point x∗ is an optimal solution to P.Proof.
First, we claim that sequences{aj} and {bj} defined in Algorithm 7 are such that {aj} is an increasing sequence and {bj} is an decreasing sequence with (32)aj≤Mj≤bj,j=1,2,⋯and (33)bj+1-aj+1=bj-aj2,j=1,2,⋯.
The following proof is by induction.
Forj=1, it follows from Algorithm 7 that a1≤M1=a1+b1/2≤b1, b2-a2=b1-a1/2. For the induction step, let the hypothesis hold for j-1. For j, we let aj=aj-1, bj=Mj-1, and Mj=aj+bj/2 in Step 3. By aj-1≤Mj-1≤bj-1, one has (34)aj=aj-1=aj-1+aj-12≤Mj=aj-1+Mj-12≤Mj-1+Mj-12=Mj-1=bj.In Step 4, let bj=bj-1,aj=Mj-1, and Mj=aj+bj/2. By aj-1≤Mj-1≤bj-1, one has (35)aj=Mj-1=Mj-1+Mj-12≤Mj=Mj-1+bj-12≤bj-1+bj-12=bj-1=bj.By induction, (32) holds for all j.
Consider the next iteration.In Step 3, letaj+1=aj, bj+1=Mj, then bj+1-aj+1=Mj-aj=bj-aj/2.In Step 4, letbj+1=bj, aj+1=Mj, then bj+1-aj+1=bj-Mj=bj-aj/2.
By induction, (33) holds for all j.
From Algorithm7, it is easy to see that {aj} is increasing and {bj} is decreasing. Then sequences {aj} and {bj} are both convergent. Let aj→a∗ and bj→b∗. It follows from (32) and (33) that a∗=b∗. Therefore, {Mj} also converges to a∗.
Now, we are at the position to prove the main conclusion in the section.
For (1), if Algorithm7 terminates at the j¯th iteration, it must terminate at Step 4; xj¯ is feasible to P. By Theorem 3, xj¯ is an optimal solution to P.
For (2), we first show that the sequencexj is bounded. For the sake of contradiction, suppose that the sequence {xj} is unbounded.
Sincexj is an optimal solution to minx∈YG(x,Mj,εj), for any fixed x¯∈X, (36)Gxj,Mj,εj≤Gx¯,Mj,εj=fx¯-Mj2+∑i∈I14εje2gix¯/εj,j=1,2,⋯.Due to Mj→a∗ and εj→0 as j→∞, we conclude that there is some L>0 such that (37)L>Gxj,Mj,εj≥fxj-Mj2,j=1,2,⋯.Since limx→+∞f(x)=+∞, we arrive at a contradiction, which shows that the sequence {xj} is bounded.
LetM∗=minx∈Xf(x). Without loss of generality, we assume xj→x∗ as j→∞. By Theorems 2 and 3 and Algorithm 7, we know that aj<M∗≤bj. It follows from (32) that a∗=M∗. Let y∗ be an optimal solution to P. Then M∗=fy∗. Note that (38)Gxj,Mj,εj≤Gy∗,Mj,εj=fy∗-Mj2+∑i∈I14εje2giy∗/εj.Letting j→∞ yields that (39)Gx∗,M∗≤0,which implies x∗∈X and M∗=f(x∗). Therefore, x∗ is an optimal solution to P.


## 4. Numerical Experiments

In this section, we will make some numerical experiments to show the efficiency of Algorithm7. Based on the different objective penalty functions, we give different algorithms to make a comparison. The algorithms based on the objective functions (6) or (4) are described below.Algorithm 9.
Step  1. Take x0∈Rn, a1<minx∈Xf(x), and minx∈Xf(x)<b1<maxx∈Xf(x). Let M1=a1+b1/2, j=1.
Step  2. Solve minx∈YG(x,Mj) starting at xj-1. Let xj be the global optimal solution.
Step  3. If G(xj,Mj)=0, let aj+1=aj, bj+1=Mj, Mj+1=aj+1+bj+1/2, j=j+1 and go to Step 2.
Step  4. If xj is not feasible to P, let bj+1=bj, aj+1=Mj, Mj+1=aj+1+bj+1/2, j=j+1 and go to Step 2. Otherwise, if xj is feasible to P, xj is the approximate optimal solution to P.Algorithm 10.
Step  1. Take x0∈Rn, a1<minx∈Xf(x), and minx∈Xf(x)<b1<maxx∈Xf(x). Let M1=a1+b1/2, j=1.
Step  2. Solve minx∈YF2(x,Mj) with p=1.5 starting at xj-1. Let xj be the global optimal solution.
Step  3. If F2(xj,Mj)=0, let aj+1=aj, bj+1=Mj, Mj+1=aj+1+bj+1/2, j=j+1 and go to Step 2.
Step  4. If xj is not feasible to P, let bj+1=bj, aj+1=Mj, Mj+1=aj+1+bj+1/2, j=j+1 and go to Step 2. Otherwise, if xj is feasible to P, xj is the approximate optimal solution to P.Example 11.
Consider the following problem considered in [33]: (40)minfx=x12+x22+2x32+x42-5x1-5x2-21x3+7x4s.t.g1x=2x12+x22+x32+2x1+x2+x4-5≤0g2x=x12+x22+x32+x42+x1-x2+x3-x4-8≤0g3x=x12+2x22+x32+2x42-x1-x4-10≤0.Leta1=-2×106, b1=0, M1=-106. The numerical results of Algorithm 7 on example 4.1 with ε1=0.05,η=0.1 and different starting points are shown in Table 1.Table 1
Numerical results of Algorithm7 on Example 11 with different starting points.
j x 0 x j g 1 ( x j ) g 2 ( x j ) g 3 ( x j ) f ( x j ) 1 ( - 10 , - 10 , - 10 , - 10 ) ( 0.16893,0.83692,2.0083 , - 0.96546 ) - 5.3237 e - 12 - 2.0108 e - 12 - 1.8767 - 44.2338 1 ( 10,10 , - 10 , - 10 ) ( 0.1691,0.83694,2.0082 , - 0.9555 ) - 1.3398 e - 10 - 5.0255 e - 11 - 1.8767 - 44.2338 1 ( - 10 , - 10,10,10 ) ( 0.16924,0.83683,2.0082 , - 0.96555 ) - 1.7465 e - 10 - 5.0245 e - 11 - 1.8772 - 44.2338 1 ( 10,10,10,10 ) ( 0.16903,0.83701,2.0082 , - 0.96556 ) - 1.339 e - 10 - 5.0243 e - 11 - 1.8763 - 44.2338 1 ( 5,5 , 5,5 ) ( 0.16899,0.83713,2.0081 , - 0.96562 ) - 2.5527 e - 11 - 9.9867 e - 12 - 1.8758 - 44.2338 1 ( 20,20,20,20 ) ( 0.16897,0.83705,2.0082 , - 0.96557 ) - 2.6782 e - 11 - 1.0057 e - 11 - 1.8761 - 44.2338The numerical results given in Table1 show that all algorithms are completed in the first iteration and the numerical result of Algorithm 7 does not depend on the selection of the starting points for this example.Leta1=-2×106,b1=0,M1=-106. The numerical results of Algorithm 9 or Algorithm 10 on this example with different starting point are shown in Tables 2 and 3.Table 2
Numerical results of Algorithm9 on Example 11 with different starting points.
j x 0 x j g 1 ( x j ) g 2 ( x j ) g 3 ( x j ) f ( x j ) 1 ( - 10 , - 10 , - 10 , - 10 ) ( 0.16989,0.83553,2.0085 , - 0.96503 ) - 1.3381 e - 10 - 4.9983 e - 11 - 1.8833 - 44.2338 1 ( 10,10 , - 10 , - 10 ) ( 0.16936,0.83591,2.0086 , - 0.96502 ) - 8.2839 e - 10 - 5.7484 e - 10 - 1.8813 - 44.2338 1 ( - 10 , - 10,10,10 ) ( 0.16963,0.8355,2.0086 , - 0.96489 ) - 2.6753 e - 11 - 1.0071 e - 11 - 1.8833 - 44.2338 1 ( - 10 , - 10 , - 10 , - 10 ) ( 0.16942,0.83559,2.0087 , - 0.96487 ) - 5.4548 e - 11 - 2.5295 e - 11 - 1.8828 - 44.2338Table 3
Numerical results of Algorithm10 on Example 11 with different starting points.
j x 0 x j g 1 ( x j ) g 2 ( x j ) g 3 ( x j ) f ( x j ) 1 ( 10,10 , - 10 , - 10 ) ( 0.16947,0.83564,2.0086 , - 0.9649 ) - 5.3531 e - 12 - 2.0135 e - 12 - 1.8826 - 44.2338 1 ( - 10 , - 10 , 10,10 ) ( 0.16972,0.83541,2.0086 , - 0.96488 ) - 2.6757 e - 11 - 1.007 e - 11 - 1.8837 - 44.2338From the numerical results on Example11, we can see that Algorithms 7, 9, and 10 can obtain almost the same approximate optimal solution. From the numerical results given in [33], we know that the optimal solution of Example 11 is (0.170160,0.835886,2.008125,-0.965392) with the objective function value -44.233828. Hence, the numerical results show that Algorithm 7 is efficient in this example.Example 12.
Consider the following problem considered in [24]: (41)minfx=x12+x22s.t.x12-x2≤0-x1≤0.For this example, we leta1=-400,b1=100,M1=-150. The numerical results of Algorithm 7 on Example 12 with ε1=10-5,η=0.1 and different starting point are shown in Table 4.Table 4
Numerical results of Algorithm7 on Example 12 with different starting points.
j x 0 x j g 1 ( x j ) g 2 ( x j ) f ( x j ) 1 ( 1,1 ) ( 0.00012003,0.00012002 ) - 0.00012 - 0.00012003 2.28812 e - 08 1 ( 0,0 ) ( 0.00036527,0.00036547 ) - 0.00036533 - 0.00036527 2.6699 e - 07Leta1=-400,b1=100,M1=-150. The numerical results of Algorithm 9 or Algorithm 10 on Example 12 with different starting point are shown in Tables 5 and 6.Table 5
Numerical results of Algorithm9 on Example 12 with different starting points.
j x 0 xj g1(xj) g2(xj) f ( x j ) 1 ( 1,1 ) ( 0.00018226,0.00018233 ) - 0.0001823 - 0.00018226 6.646 e - 08 1 ( 0,0 ) ( 0.00040823,0.00040826 ) - 0.00040809 - 0.00040823 3.3333 e - 07Table 6
Numerical results of Algorithm10 on Example 12 with different starting points.
j x 0 x j g1(xj) g2(xj) f ( x j ) 1 ( 1,1 ) ( 0.00081614,0.00081663 ) - 0.00081596 - 0.00081614 1.333 e - 06 1 ( 0,0 ) ( 0.00081597,0.00081656 ) - 0.00081589 - 0.00081597 1.3326 e - 06From Tables4–6, we can see that Algorithm 7 has better numerical stability than Algorithms 9 and 10 for the optimal solution and objective function value in this example. In fact, the given solution for Example 12 is (0,0) with the objective function value 0.


## 5. Concluding Remarks

In this paper, we proposed a method for smoothing the nonsmooth objective penalty function for inequality constrained optimization. Further, we showed the global convergence of the method under mild conditions. The given numerical experiments exhibit the efficiency of the proposed method.



---

*Source: 7484256-2018-06-06.xml*