This paper addresses the nonconvex optimization problem with the cost function and constraints given by d.c. functions. The original problem is reduced to a problem without inequality and equality constraints by means of the exact penalization techniques. Furthermore, the penalized problem is presented as a d.c. minimization problem. For the latter problem we develop the global optimality conditions (GOCs) which reduce the nonconvex optimization problem to a family of convex problems. In the paper the properties of the GOCs are investigated. The effectiveness of the GOCs is demonstrated by examples.
Consider the following problem: (P) :
f0(x) := g0(x) − h0(x) ↓ mxin; x ∈ S; fi(x) := gi(x) − hi(x) ≤ 0; i ∈ I = {1; : : : ; m}; fi(x) := gi(x) − hi(x) = 0; i ∈ E = {m + 1; : : : ; l};
V(P) := inf(f0; F ) := inxf{f0(x) | x ∈ F )} > −∞:
Exact Penalty Introduce the penalty function W (·) for Problem (P) as follows
W (x) := max{0; f1(x); : : : ; fm(x)} + ∑ |fj(x)| :
Further, along with Problem (P), consider the penalized problem without the inequality and equality constraints: (P ) : (x) , f0(x) +
W (x) ↓ mxin; x ∈ S; where ≥ 0 is a penalty parameter.
As well-known, if z ∈ Sol(P ), and z is feasible in (P), i.e. z ∈ F , then z turns out to be a global solution to (P): z ∈ Sol(P) [Nocedal et al., 2006, Bonnans et al., 2006, Izmailov et al., 2014, Hiriart-Urruty et al., 1993, Clarke, 1983, Burke, 1991]. On the other hand, the inverse implementation does not, in general, hold.
Hence, the crucial moment of the exact penalization (EP) theory is the existence of a threshold value ∗ ≥ 0
of the penalty parameter ≥ 0 for which Sol(P ) ⊂ Sol(P) ∀ ≥ ∗: In other words, for ≥ ∗ Problems
(P) and (P ) turn out to be equivalent in the sense that Sol(P) = Sol(P )
On the other hand, the existence of the threshold exact penalty parameter ∗ ≥ 0 allows us to solve a single unconstrained problem instead of a sequence of unconstrained problems with k → ∞ [Byrd et al., 2012, Di Pillo et al., 2012, Di Pillo et al., 2015].
Recall that under various constraint qualification (CQ) conditions
Assume that some regularity condition is fulfilled that ensures the existence of such threshold value ∗ ≥ 0 of penalty parameter. 3
Global Optimality Conditions (GOC) Before all, we will prove that the cost function as a difference of convex functions. Indeed, since
(·) of Problem (P ) is a d.c. function, i.e. it can be represented |fi(x)| = max{gi(x) − hi(x); hi(x) − gi(x)} ± [gi(x) + hi(x)] = 2 max{gi(x); hi(x)} − [gi(x) + hi(x)]; it can be readily seen that where (x) =△ f0(x) + max{0; fi(x); i ∈ I} + ∑ |fi(x)| = G (x) − H (x); i∈E H (x) := h0(x) + [∑ hi(x) + ∑(gj(x) + hj(x))]; i∈I j∈E G (x) := (x) + H (x) = g0(x) + max{∑ hj(x); [gj(x) + ∑j̸=i hj(x)]; i ∈ I}+ j∈I j∈I (1) (2) (3) (4) ∑ max{gi(x); hi(x)}: (5) i∈E Obviously, G (·) and H (·) are both convex functions [Hiriart-Urruty et al., 1993, Rockafellar et al., 1998, Rockafellar, 1970], so that the function (·) is a d.c. function, as claimed. Besides, it is clear, that for a feasible (in (P)) point z ∈ S we have
W (z) =△ max{0; f1(z); : : : ; fm(z)} + ∑ |fi(z)| = 0;
i∈E and therefore, for := f0(z), we obtain Theorem 3.1. Let a point z ∈ F be a solution to Problem (P) and value of penalty parameter.
Then, for every pair (y; ) ∈ IRn × IR such that the following inequality holds 0 > G (u) −
− ⟨∇H (y); u − y⟩; Then, using the equation (7) and the convexity of the function H (·), we derive 0 > G (u) − − H (u) + H (y) = (u) − = (u) − (z); or, (z) > (u); z ∈ F ; u ∈ S: Hence, the point z can not be a solution to (P ).
Moreover, if z and u are feasible in (P), z; u ∈ F , and since W (u) = 0, we obtain f0(z) = (z) > (u) = f0(u): It means that z ∈= Sol(P) and u ∈ F is a vector better than z ∈ F .
Hence, the conditions (7)–(8) of Theorem 3.1 possess the classical constructive (algorithmic) property (once the conditions are violated, one can find a feasible vector which is better than the point under investigation).
Let us demonstrate the effectiveness of this property by an example.
Example 3.1. Consider the problem
x f1(x) = x21 + x2 − 1 = 0: 2 x ∈ IR2; } Remark 3.1. It is not difficult to note that Theorem 3.1 reduces the solution of the nonconvex Problem (P ) to an investigation of the family of the convex (linearized) problems (P L(y)) : Φ y(x) := G (x) − ⟨∇H (y); x⟩ ↓ min; x x ∈ S; depending on the pairs (y; ) ∈ IRn+1 which fulfill the equation (7) (or, what is the same), (P L(y)) : Φ y(x) := G (x) − ⟨∇h0(y) +
∇hi(y) + [∑ i∈I j∈E ∑(∇gj (y) + ∇hj (y))]; x⟩ ↓ min; x x ∈ S: (9′)
It is worth noting that the linearization is carried out with respect to the “unified” nonconvexity of Problem (P) accumulated by the function H (·) (see (P)–(1) and (4)) that includes all the functions hi(·); i ∈ {0} ∪ I ∪ E ; gj (·); j ∈ E , which generate all nonconvexity in Problems (P) and (P ) (according to the representations (3)–(5)).
Hence, the verification of the principal inequality (8) can be performed by solving the linearized problems (P L(y)) and varying the parameters (y; ) satisfying (7). Besides, we have to verify (8), which can be rewritten as follows
V(P L(y)) ≥
− ⟨∇H (y); y⟩ =: N (y; ); where V(P L(y)) is the optimal value of the linearized problem (P L(y)) Remark 3.2. Suppose, we found a triple (y; ; u), (y; ) ∈ IRn × IR; principal inequality (8) is violated, i.e.
H (y) = − , u ∈ S, such that the (6) (7) (8) (9) (8′) (10) It is easy to see that the point z = (√22 ; √22 )⊤, equation ∇f0(z) + 1∇f1(z) = 0 ∈ IR2 with 1 = −2. However, it is not clear whether the point z is a global solution. In order to decide on it, let us apply Theorem 3.1.
:= f0(z) = 2, is feasible: f1(z) = 0 and satisfies the KKTg0(x) = (x1 + x2)2; h0(x) = (x1 − x2)2; g1(x) = x22 + x22; h1(x) ≡ 1:
:= 3 > | 1| = 2. Then, according to (4) and (5), we have
H (x) = h0(x) + [g1(x) + h1(x)] = (x1 − x2)2 + 3(x21 + x22 + 1); G (x) = g0(x) + 2 max{g1(x); h1(x)} = (x1 + x2)2 + 6 max{x12 + x22; 1}: } Let choose, now, y = (−1; 0:5)⊤ which is unfeasible in the problem (10). Then we have
H (y) = (y1 − y2)2 + 3(y12 + y22 + 1) = 9 and, as a consequence, we derive = H (y) + = 9 + 2 = 11. Furthermore, let choose a feasible point u = (−0:6; 0:8)⊤, u21 + u22 = 1, and compute G (u) (see (12))
G (u) = (u1 + u2)2 + 6 max{u12 + u22; 1} = (0:2)2 + 6 = 6:04: Besides, it is not difficult to compute that u − y = (−0:6; 0:8)⊤ − (−1; 0:5)⊤ = (0:4; 0:3)⊤, ∇H (y) = 2(y1 − y2; y2 − y1)⊤ + 6(y1; y2)⊤ = 2(4y1 − y2; 4y2 − y1)⊤ = (−9; 6)⊤:
⟨∇H (y); u − y⟩ = ⟨(−9; 6)⊤; (0:4; 0:3)⊤⟩ = −3:6 + 1:8 = −1:8;
+ ⟨∇H (y); u − y⟩ = 11 − 1:8 = 9:2 > 6:04 = G (u): The latter inequality means that in Problem (10) the principal inequality (8) of Theorem 3.1 is violated.
Hence, the point z = (√22 ; √22 )⊤ is not a global solution to the problem (10) in virtue of Theorem 3.1. Indeed, it is confirmed by the inequality f0(u) = −0:48 < = f0(z) = 2.
Let consider now possible relations between the conditions (7)–(8) of Theorem 3.1 and the classical optimality conditions, in particular, the KKT theorem for Problem (P). For this purpose, suppose that a feasible (in Problem (P)) point z satisfies the conditions (7)–(8) of Theorem 3.1.
First, let set in (7)–(8) y = z. Then we immediately derive that := H (z) + = G (z). Therefore, from (8) it follows the validity of the inequality
G (x) − G (z) ≥ ⟨∇H (z); x − z⟩ ∀x ∈ S: It implies that the point z (satisfying (7)–(8)) is a solution to the linearized convex problem as follows (P L(z)) :
G (x) − ⟨∇H (z); x⟩ ↓ min; x Since (P L(z)) is a convex problem, then the following inclusion is, as well-known, the necessary and sufficient optimality condition for z being a solution to (P L(z)): When S = IRn, the inclusion (13) implies which is the necessary optimality condition for Problem (P ) with S = IRn [Hiriart-Urruty, 1985, Strekalovsky, 2003]. Thus, the conditions (7)–(8) of Theorem 3.1 entail the well-known optimality conditions (13) and (13′) [Nocedal et al., 2006, Bonnans et al., 2006, Izmailov et al., 2014, Floudas et al., 2004, Strekalovsky, 2013, Strekalovsky, 2014, Strekalovsky, 2017, Strekalovskiy, 2003] for Problem (P ).
Nevertheless, the natural question arises on whether it is possible to find a triple (y; ; u) ∈ IR2n+1, satisfying (7) and which violates the inequality (8). (11) (12) (13) (13′) Theorem 3.2. Assume, that a feasible in Problem (P) point z is not an "-solution to (P), i.e. In addition, let a vector v ∈ IRn satisfy the following inequality Then, for any penalty parameter conditions take place > 0 one can nd a tuple (y; ; u), (y; ) ∈ IRn+1, u ∈ F , the following inf(f0; F ) + " = V(P) + " < := f0(z): (H) : f0(v) >
− ": (a) H (y) = (b) G (y) ≤ ; (c) G (u) − − + "; < ⟨∇H (y); u − y⟩: (14) (15) (16) (17) (18) (19) (20′)
Now let us demonstrate the effectiveness of the GOCs of Theorems 3.1 and 3.2 on another example.
f0(x) = x21 − 2x22 + x23 ↓ min; x ∈ IR3;
2 x f1(x) = x23 − x1 − x22 = 0; f2(x) = 4x1x3 = 0; It can be readily seen that the point z = (0; 0; 0)⊤; := f0(z) = 0 is a degenerate KKT point in the problem (17), since f1(z) = f2(z) = 0; ∇f0(z) = ∇f1(z) = ∇f2(z) = (0; 0; 0)⊤. However, it is not clear whether the KKT vector z is a global solution to (17) or not. Therefore, let us apply Theorems 3.1 and 3.2 to clarify the situation.
It is easy to see that in the problem (17) we have g0(x) = x21 + x2; h0(x) = 2x22; g1(x) = x2; h1(x) = gx221(x+) x=22.(x1In+axd3d)2it;iohn,2(uxs)in=g(xth1e−dx.c3.)2:representation f2(x) = 4x1x3 3= (x1 + x3)2 − (x1 − x3)2; 3we obtain
For simplicity of presentation, we will apply the denotation S = [−2; 1] for bounding the variable x2 ∈ IR, but in the investigation of the linearized problems we use two inequality constraints x2 ≤ 1; x2 + 2 ≥ 0: Hence, according to (3)–(5) we have Let us set := 1; y = ( 16 ; 1; 76 )⊤ ∈= F . Then we obtain
H (x) = h0(x) + ∑[gj(x) + hj(x)] =
j∈E = 2x22 + [(x23 + x21 + x22) + (x1 + x3)2 + (x1 − x3)2] = 2x22 + [3x21 + 3x23 + x22];
G (x) = g0(x) + 2 ∑max{gj(x); hj(x)} =
j∈E = x21 + x23 + 2 [max{x23; x21 + x22} + max{(x1 + x3)2; (x1 − x3)2}]:
∇H (x) = (0; 4x2; 0)⊤ + (6x1; 2x2; 6x3)⊤ = 6(x1; x2; x3)⊤; besides, ∇H (y) = (1; 6; 7)⊤:
In order to find a suitable point in u ∈ F , consider the linearized problem as follows (P L(y)) :
G (x) − ⟨∇H (y); x⟩ = x12 + x32 + 2 max{x32; x12 + x22}+ + 2 max{(x1 + x3)2; (x1 − x3)2} − ⟨(1; 6; 7)⊤; x⟩ ↓ mxin; x ∈ IR3; −2 ≤ x2 ≤ 1: (20) It is not difficult to see that the problem (20) amounts to the following one [Hiriart-Urruty, 1998] x21 + x23 + 2 1 + 2 2 − x1 − 6x2 − 7x3 ↓ (mx;in); x32 ≤ 1; x21 + x22 ≤ 1;
= ( 1; 2) ∈ IR2; (x1 + x3)2 ≤ 2; (x1 − x3)2 ≤ 2; x2 ≤ 1; x2 + 2 ≥ 0; x ∈ IR3:
Besides, as above, it can be readily seen that the Slater condition holds in (20′). Furthermore, the solution vector (u; ∗) ∈ IR5 satisfies the complementarity conditions as follows 1(x32 − 1) = 0 = 2(x12 + x22 − 1); 3[(x1 + x3)2 − 2] = 0 = 4[(x1 − x3)2 − 2]; }
1(x2 − 1) = 0 = 2(x2 + 2): and, besides, we have for ∗ = ( ∗1; ∗2)⊤ ∗1 = max{ u32; u12 + u22 };
∗2 = max{ (u1 + u3)2; (u1 − u3)2 }: In addition, since the Lagrange function for the problem (20′) has thee following form (21) (22) (24) (25) (25′)
L(x; ; 1; 2; 3; 4; 1; 2) = x21 + x23 + 2 1 + 2 2 − x1 − 6x2 − 7x3+ + 1(x32 − 1) + 2(x12 + x2 − 1) + 3[(x1 + x3)2 − 2] + 4[(x1 − x3)2 − 2] + 1(x2 − 1) − 2(x2 + 2); (23) 2 (an, besides, ( 1; 2; 3; 4; 1; 2) tions [Rockafellar, 1993] ∈
IR+6), then the
KKT system
contains the following equa
It can be readily seen that the point u = (0; 1; 1)⊤ satisfies the KKT conditions (21),(24),(25) with ∗ = ( ∗1; ∗2)⊤ = (1; 1)⊤ (see (22)). Indeed, the equation (25) with u = (0; 1; 1)⊤ take the form (a) (b) (c) 2 3 − 1 − 2 4 = 0; or 2 2 − 6 + 1 − 2 = 0; 2 − 7 + 2 1 + 2 3 + 2 4 = 0: 3 − 4 = 21 ; Then, from (25′) (a) we derive 3 = 54 , 4 = 34 . Further, from (25′) (c) with the help of (24) it follows that 2 1 = 5 − 2( 3 + 4) = 1, i.e. 1 = 12 , 2 = 23 .
On the other hand, thanks to (21) we see that 2 = 2(u) = 0.Then (25′) (b) provides that 1 = 3. Hence, the point u = (0; 0; 1)T really is a KKT point in (20′), and, due to convexity of problem (20′), u is also a solution to (20) ((u; ∗)T is a solution to (20′)).
Now let us verify whether the principal inequality (8) of Theorem 3.1 holds with (y; ; u) where ( 1 7 ) 1 = H (y) + ; = f0(z) = 0. First compute H (y) with y = ; 1; : H (y) = 3(y12 + y22 + y32) = 7 . 6 6 6 1
Thus, = H (y) = 7 6 . Furthermore, + ⟨∇H(y); (u − y)⟩ = 5 56 . On the other hand, it can be readily computed, that G (u) = u21 + u23 + 2 ∗1 + 2 ∗2 = 5.
5 Therefore, we have G (u) = 5 < 5 6 = + ⟨∇H(y); u − y⟩.
Hence, the principal inequality (8) of Theorem 3.1 is violated, and, as a consequence, the degenerate KKT point z = (0; 0; 0)T is not a global solution to the problem (17). ( 1 7 )T Moreover, by solving the linearized problem (PL(y)) with y = ; 1; , we constructed the feasible in (17) 6 6 point u = (0; 1; 1)T , which is better than z, since f0(u) = −1 < 0 = f0(z) = 0.
Furthermore, it can be readily seen, as above, that the point u = (0; 1; 1)T is also a KKT point in the original problem (17), but not a global solution to (17). Moreover we can show this fact, by repeating the same procedure of finding another pair (y1; 1), such that H (y1) = 1 − 1, where 1 := f0(u) = f0(z1); z1 := u; and by solving the linearized problem (PL1) := (PL(y1)), which provides the point u1 such that
So, by the procedure described above we give a hint how may be constructed one of the simplest global search procedures which is able to escape stationary points and local solutions in non-convex Problem (P). 4
Sufficient Optimality Conditions Now we turn to the question on when the conditions (7)–(8) of Theorem 3.1 become sufficient for a feasible point being a global solution to nonconvex Problem (P).
Theorem 4.1. Suppose that for a feasible in Problem (P) point z, := f0(z), the condition (H){(15) is ful lled. In addition, let some penalty parameter > 0 be given. Finally, assume that for every pair (y; ) ∈ IRn × IR, satisfying the relation (a) Acknowledgements Then, the point z ∈ F turns out to be an "-global solution to Problem (P ) as well as to Problem (P). This work was supported by the Russian Science Foundation (Project No. 15-11-20015).