# Canonical Duality for Box Constrained Nonconvex and Nonsmooth Optimization Problems

Authors: Jing Liu; Huicheng Liu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper presents an application of the canonical duality theory for box constrained nonconvex and nonsmooth optimization problems. By use of the canonical dual transformation method, which is developed recently, these very
difficult constrained optimization problems inRn can be converted into the canonical dual problems, which can be solved by deterministic methods. The global and local extrema can be identified by the triality theory. Some examples are listed to illustrate the applications of the theory presented in the paper.


---

## Body

## 1. Primal Problems

The methods of solving nonconvex and nonsmooth optimization have been the topic of intense research during the last forty years. As we know, the general methods of nonsmooth optimization are based on some subdifferentials. However, in the general nonconvex and nonsmooth optimization problem, due to the nonconvexity and nonsmoothness of the objective functions and inequality constraints, the computation of subdifferential is rather time-consuming. So the traditional theories and direct methods are very difficult in solving the nonconvex and nonsmooth optimization and global optimality with constraints. Recently, some effective methods have been studied to solve certain box constrained nonconvex minimization problems [1–8].In this paper, the primary goal is to solve the following box constrained nonconvex and nonsmooth optimization problems (in short, the primal problem(P)). Consider(1)P:minx∈χa⁡Psx=12xTAx+Wx,s-xTf,where χa={x∈Rn∣-1≤x≤1,x∈{-1,1}n} (the notation {-1,1}n denotes integer vectors of Rn with components either -1 or 1) is a feasible space, f∈Rn is a nonzero vector, and A=AT is an n times n matrix. W(x,s):Rn×Rm→R is a nonconvex and nonsmooth function. Here, we simply assume that W(x,s) is defined by (2)Wx,s=12a112Bx-s2-μ12,ifBx-s≤c,12a212Bx-s2-μ22,ifBx-s>c,where B is an m times n matrix, s∈Rm is a vector of parameter, μ2=c2/2+a1/a2c2/2-μ1,μ1 is an arbitrary constant, a1 and a2 are both nonzero positive constants, ·:Rn→R is the Euclidean norm, and c is an arbitrary positive constant. In constrained global optimization problems, W could be the indicator of a feasible set [9]. In particular, if we abandon the box constraint, problem (P) will be turned into unconstrained optimal problem which has been discussed in [10]. The primal problem (P) appears frequently in many applications, such as semilinear nonconvex partial differential equations, structural limit analysis, discretized optimal control problems with distributed parameters, and network communication [6, 11, 12].In the primal problem(P), the box constraint -1≤x≤1 is equivalent to xi2≤1(i=1,…,n). Thus, based on the traditional Lagrangian multiplier method, we have (3)Lx,λi=12xTAx+Wx,s-xTf+λixi2-1.In the case where A is positive definite, for a given λi>0(i=1,…,n), the traditional dual function can be defined via the Fenchel-Moreau-Young duality theory: (4)P∗λi=min⁡Lx,λi:x∈Rn.However, due to the nonconvexity of the objective function Ps(x), the Young-Fenchel inequality can lead to a weak duality relationship in general nonconvex systems: (5)minx∈χa⁡Psx≥maxλi≥0⁡P∗λi.The nonzero value θ=minx∈χaPs(x)-maxλi≥0P∗(λi) is called the duality gap, which is usually -∞ if A is indefinite. This nonzero duality gap shows that the Fenchel-Rockafellar duality theory and method can be used mainly in convex systems. In order to eliminate this duality gap, many modified Fenchel-Rockafellar duality theories and methods for nonconvex optimization problems have been proposed [12–20]. Recently, the so-called canonical dual transformation method (without the duality gap) has been developed in general nonconvex systems [21]. This method is a newly useful tool for optimal problem. At present, the method has been successfully used for a large class of nonsmooth or nonconvex minimization [9, 10, 21, 22].In this paper, we will present the application of the canonical dual transformation method for the solutions of the box constrained nonconvex and nonsmooth optimization problems (P) in Rn. In the next section, a perfect dual problem is formulated, which is equivalent to the primal problem in the sense that they have the same set of critical points. Section 3 shows the sufficient conditions for global and local minima. In Section 4, some concrete examples for box constrained nonconvex and nonsmooth optimization problems are presented. We state some conclusions in Section 5.


## 2. Canonical Dual Problem and Complete Solutions

In order to use the canonical dual transformation method to solve the box constrained nonconvex and nonsmooth optimization problem, we need to reformulate the constraint-1≤x≤1 in canonical form xi2≤1,i=1,2,…,n.Following the stand procedure of the canonical dual transformation method developed in [21], the canonical geometrical operator Λ:Rn→R×Rn in the primal problem (P) can be defined as (6)y=Λx=12Bx-s2,xi2-1=ϵ,ρ,where ϵ=1/2|Bx-s|2 is a scale and ρ={ρi}={xi2-1} for i=1,2,…,n. Let Ya⊂R×Rn be the range of the mapping y=Λ(x) which can be written as(7)Ya=y=ϵ,ρT∈R×Rn∣ϵ≥0,ρ≤0.According to the canonical transformation method, we define a real-valued function V:Ya→R. Thus, the nonconvex and nonsmooth function W(x,s) can be written in a canonical form: (8)Wx,s=Vy.Then V(y) is a canonical function defined on the subset Ya⊂R which can be written as (9)Vy=Vϵ,ρ=12a1ϵ-μ12+φρ,if0≤ϵ≤c22,12a2ϵ-μ22+φρ,ifϵ>c22,where (10)φρ=0,ifρ≤0,+∞,otherwise.We yet assume that matrixA is invertible. For each given nonzero vector f∈Rn, the function F:Rn→R is defined by (11)Fx=xTf-12xTAx,where F is a canonical function on Rn since its Gâteaux derivative x∗=DF(x)=f-Ax:Rn→Rn is one-to-one onto mapping. Thus, we can rewrite the primal minimization problem (P) in the unconstrained canonical form ((Pq) in short):(12)Pq:Px=VΛx-Fx⟶sta,∀x∈Rn,where sta stands for finding all the stationary points of P(x).Lety∗=ϵ∗,ρ∗T∈R×Rn be a dual variable of y and A+BTBϵ∗+2Diagρi∗≠0, where Diagρi∗∈Rn×n represents a diagonal matrix with ρi∗(i=1,2,…,n) as its diagonal entries and the dual variable ρ∗={ρi∗}(i=1,2,…,n) is also a vector in Rn. Then the Λ-canonical conjugate FΛ(y∗) of the canonical function F(x) can be well defined by the Λ-canonical dual transformation [21]:(13)FΛy∗=Λx,y∗-Fx∣DFx=DΛx,y∗,x∈Xa=-12Gϵ∗T·Fϵ∗,ρ∗-1Gϵ∗+12sTsϵ∗-∑i=1nρi∗,where F(ϵ∗,ρ∗)=defA+BTBϵ∗+2Diagρi∗, G(ϵ∗)=deff+BTsϵ∗, DΛ(x) is the Gâteaux derivative of Λ at x, and DF(x) denotes the gradient F at x.In the case ofa1>a2, by the definition of the canonical function, V:Ya→R is Gâteaux differentiable, and the duality relation y∗=DV(y):Ya→Ya∗=R×Rn is invertible, where DV denotes the Gâteaux derivative of V at y. Thus, the canonical conjugate V∗(y∗)=V∗(ϵ∗,ρ∗), where y∗=(ϵ∗,ρ∗)T∈R×Rn of V(y), can be obtained by the Legendre transformation: (14)V∗y∗=y,y∗-Vy∣DVy=y∗=12a1ϵ∗2+μ1ϵ∗,if-a1μ1≤ϵ∗≤a1c22-μ1,ρ∗≥0c22ϵ∗-12a1c22-μ12,ifa1c22-μ1<ϵ∗≤a2c22-μ2,ρ∗≥012a2ϵ∗2+μ2ϵ∗,ifϵ∗>a2c22-μ2,ρ∗≥0.The dual feasible spaces are three subsets of R×Rn: (15)Yα1∗=y∗=ϵ∗,ρ∗T∈R×Rn∣-a1μ1≤ϵ∗≤a1c22-μ1,ρ∗≥0,detFϵ∗,ρ∗≠0,Yβ1∗=y∗=ϵ∗,ρ∗T∈R×Rn∣a1c22-μ1<ϵ∗≤a2c22-μ2,ρ∗≥0,detFϵ∗,ρ∗≠0,Yγ1∗=y∗=ϵ∗,ρ∗T∈R×Rn∣ϵ∗>a2c22-μ2,ρ∗≥0,detFϵ∗,ρ∗≠0.By replacingW(x,s)=V(y) in P(x) by the complementary form yTy∗-V∗(y∗), we obtain the Gao-Strang total complementary function Ξ:Rn×Yμ∗→R(μ∈{α1,β1,γ1}): (16)Ξx,y∗=yTy∗-V∗y∗-Fx.Thus, on the dual feasible spaces, the canonical dual function Pd(y∗) can be formulated as (17)Pdy∗=staΞx,y∗:x∈Rn=FΛy∗-V∗y∗.The canonical dual problem can be formulated as problem (Pqd):(18)Pdy∗=Pdϵ∗,ρ∗=-12Gϵ∗TFϵ∗,ρ∗-1Gϵ∗+12sTsϵ∗-12a1ϵ∗2+μ1ϵ∗-∑i=1nρi∗,ifϵ∗,ρ∗T∈Yα1∗,-12Gϵ∗TFϵ∗,ρ∗-1Gϵ∗+12sTsϵ∗-c22ϵ∗-12a1c22-μ12-∑i=1nρi∗,ifϵ∗,ρ∗T∈Yβ1∗,-12Gϵ∗TFϵ∗,ρ∗-1Gϵ∗+12sTsϵ∗-12a2ϵ∗2+μ2ϵ∗-∑i=1nρi∗,ifϵ∗,ρ∗T∈Yγ1∗.⟶sta.In the case ofa1<a2, the canonical conjugate V∗(y∗)=V∗(ϵ∗,ρ∗) of V(y) can be written as (19)V∗y∗=y,y∗-Vy∣DVy=y∗=12a2ϵ∗2+μ2ϵ∗,if-a2μ2≤ϵ∗≤a2c22-μ2,ρ∗≥0.c22ϵ∗-12a2c22-μ22,ifa2c22-μ2<ϵ∗≤a1c22-μ1,ρ∗≥0.12a1ϵ∗2+μ1ϵ∗,ifϵ∗>a1c22-μ1,ρ∗≥0.It is similar to that in the case of a1>a2 where the dual feasible spaces are also three subsets of R×Rn: (20)Yα2∗=y∗=ϵ∗,ρ∗T∈R×Rn∣-a2μ2≤ϵ∗≤a2c22-μ2,ρ∗≥0,detFϵ∗,ρ∗≠0,Yβ2∗=y∗=ϵ∗,ρ∗T∈R×Rn∣a2c22-μ2<ϵ∗≤a1c22-μ1,ρ∗≥0,detFϵ∗,ρ∗≠0,Yγ2∗=y∗=ϵ∗,ρ∗T∈R×Rn∣ϵ∗>a1c22-μ1,ρ∗≥0,detFϵ∗,ρ∗≠0.Hence, on the dual feasible spaces, the canonical dual problem (Pqd) can be formulated as (21)Pdy∗=Pdϵ∗,ρ∗=-12Gϵ∗TFϵ∗,ρ∗-1Gϵ∗+12sTsϵ∗-12a2ϵ∗2+μ2ϵ∗-∑i=1nρi∗,ifϵ∗,ρ∗T∈Yα2∗,-12Gϵ∗TFϵ∗,ρ∗-1Gϵ∗+12sTsϵ∗-c22ϵ∗-12a2c22-μ22-∑i=1nρi∗,ifϵ∗,ρ∗T∈Yβ2∗,-12Gϵ∗TFϵ∗,ρ∗-1Gϵ∗+12sTsϵ∗-12a1ϵ∗2+μ1ϵ∗-∑i=1nρi∗,ifϵ∗,ρ∗T∈Yγ2∗,⟶sta.Theorem 1 (perfect duality theorem).
Suppose that vectory-∗=(ϵ-∗,ρ-∗)T is a stationary point of the canonical dual problem (Pqd); then the vector defined by (22)x-=Fϵ-∗,ρ-∗-1Gϵ-∗is a stationary point of the primal problem (Pq), and (23)Px-=Pdϵ-∗,ρ-∗.Proof.
Without loss of generality, we suppose thaty-∗=(ϵ-∗,ρ-∗)T∈Yα1 is a stationary point of (Pqd); then we have the following canonical dual equation: (24)12BGϵ-∗TFϵ-∗,ρ-∗-2·BGϵ-∗-BGϵ-∗TFϵ-∗,ρ-∗-1s+12s2=1a1ϵ-∗+μ1.In terms of x-=F(ϵ-∗,ρ-∗)-1G(ϵ-∗) and (24), one has that (25)1a1ϵ-∗+μ1=12Bx-s2=ϵ.By the condition 0≤ϵ≤c2/2, it is obtained that -a1μ1≤ϵ∗≤a1(c2/2-μ1). On the other hand, as y-∗=(ϵ-∗,ρ-∗)T is the stationary point of (Pqd), then (26)x-i2ϵ-∗,ρ-∗-1≤0,ρ-i∗≥0,ρ-i∗x-i2ϵ-∗,ρ-∗-1=0,i=1,…,n,where x-i(ϵ-∗,ρ-∗) is the ith component of the vector x-=F(ϵ-∗,ρ-∗)-1G(ϵ-∗). It is obvious that x-(ϵ-∗,ρ-∗) is also a stationary point of the primal problem (P). Thus, by x-=F(ϵ-∗,ρ-∗)-1G(ϵ-∗) and (27)12a1ϵ-∗2+μ1ϵ-∗=-12a112Bx--s2-μ12+12Bx--s2ϵ-∗,we have (28)Pdϵ-∗,ρ-∗=12xTFϵ-∗,ρ-∗x-sTBϵ-∗x+12sTs-xTf=12Bx--s2ϵ-∗+ρ-i∗x-i2ϵ-∗,ρ-∗-1+12xTAx-xTf+12a112Bx--s2-μ12-12Bx--s2ϵ-∗=12xTAx+12a112Bx--s2-μ12-xTf=Psx-.This proves the theorem.Theorem1 shows that, by use of the canonical dual transformation, the primal problem (P) can be converted into a canonical dual problem, which can be solved to obtain the stationary points. However, the stationary conditions are only necessary for nonconvex optimization problem. In the next section we will present the optimality criteria.


## 3. Optimality Criteria

The two subsets of the setYμ∗(μ∈{α1,β1,γ1,α2,β2,γ2}) are, respectively, defined by (29)Y+∗=ϵ∗,ρ∗T∈Yμ∗∣Fϵ∗,ρ∗is positive definite,Y-∗=ϵ∗,ρ∗T∈Yμ∗∣Fϵ∗,ρ∗is negative definite.Theorem 2 (triality theorem).
For each dual solutiony-∗=(ϵ∗,ρ∗)T∈Yμ∗(μ∈{α1,β1,γ1,α2,β2,γ2}), one lets (30)x-=Fϵ∗,ρ∗-1Gϵ.
Ify-∗=(ϵ∗,ρ∗)T∈Y+∗, then y-∗ is a global maximizer of Pd on Y+∗, while x- is a global minimizer of P on Rn, and (31)Px-=minx∈Xa⁡Px=maxy∗∈Y+∗⁡Pdy∗=Pdy-∗.
Ify-∗=(ϵ∗,ρ∗)T∈Y-∗, then, on the neighborhoods Yo∗⊂Yμ∗ and Xo⊂Xa of y-∗ and the associated x-, respectively, we have that either (32)Px-=minx∈Xo⁡Px=miny∗∈Yo∗⁡Pdy∗=Pdy-∗or (33)Px-=maxx∈Xo⁡Px=maxy∗∈Yo∗⁡Pdy∗=Pdy-∗holds.Proof.
Without loss of generality, we suppose thatμ=α1; that is, y-∗=(ϵ-∗,ρ-∗)T∈Yα1. The extended Lagrangian Ξ:Rn×Y+∗→R can be written as (34)Ξx,y∗=Ξx,ϵ∗,ρ∗=ΛxTy∗-V∗y∗+12xTAx-xTf=12xTFϵ-∗,ρ-∗x-sTBϵ-∗x+12sTs-xTf-V∗y∗.It can be easily proved that the critical points of Ξ(x,ϵ∗,ρ∗) solve the primal problem, and P(x-)=Ξ(x-,ϵ-∗,ρ-∗). By Theorem 1, we know that the vector y-∗=(ϵ-∗,ρ-∗)T∈Yμ∗ is a stationary point of problem (Pqd) if and only if x-=F(ϵ-∗,ρ-∗)-1G(ϵ-∗) is a stationary point of problem (Pq) and (35)Px-=Ξx-,y-∗=Ξx-,ϵ-∗,ρ-∗=Pdy-∗.If F(ϵ∗,ρ∗) is definite, the extended Lagrangian Ξ is convex on x∈Rn and concave in each ϵ∗∈R and ρ∗∈Rn; that is, the extended Lagrangian Ξ is a saddle function on Rn×Y+∗. By formula (12) and the definition of Λ(x), one has that(36)VΛx=maxy∗∈Y+∗⁡ΛxTy∗-V∗y∗=1212Bx-s2-μ12ifx∈Xa,∞otherwise.Thus, we have (37)Pdy-∗=maxy∗∈Y+∗⁡Pdy∗=maxy∗∈Y+∗minx∈Xa⁡Ξx,y∗=minx∈Xamaxy∗∈Y+∗⁡Ξx,y∗=minx∈Xa⁡12xTAx-xTf+maxy∗∈Y+∗⁡ΛxTy∗-V-∗y∗=minx∈Xa⁡Psx=Psx-.
Ify-∗∈Y-∗, the matrix F(ϵ∗,ρ∗) is indefinite; the function Ξ is a so-called super-Lagrangian [22]; that is, it is locally concave in each of its variables x and y∗ on the neighborhood Xo×Yo∗. In this case, by the triality theory developed in [21], we have either (38)Px-=minx∈Xo⁡Px=minx∈Xomaxy∗∈Yo∗⁡Ξx,y∗=miny∗∈Yo∗maxx∈Xo⁡Ξx,y∗=miny∗∈Yo∗⁡Pdy∗=Pdy-∗or (39)Px-=maxx∈Xo⁡Px=maxx∈Xomaxy∗∈Yo∗⁡Ξx,y∗=maxy∗∈Yo∗maxx∈Xo⁡Ξx,y∗=maxy∗∈Yo∗⁡Pdy∗=Pdy-∗.The theorem is proved.Theorem2 shows that if y¯∗∈Y+∗, then x¯ is global minimizer of Ps(x), while the stationary point y¯∗∈Y-∗, then x¯ is either a local minimizer or a local maximizer of the primal problem (P). The optimality criteria provides the sufficient conditions of both global and local minina, which can be used to develop for solving the nonconvex and nonsmooth problem with box constraints.


## 4. Numerical Tests

The canonical duality theory can be applied to solve many constrained nonconvex and nonsmooth problems in engineering and science. Now we list some examples to illustrate the applications of the theory presented in this paper.Example 1.
In the case ofn=1, the nonconvex and nonsmooth function (40)Px=12ax2+Wx,s-fxs.t.-1≤x≤1,where(41)Wx,s=Vy=12a1y-μ12,if0≤y≤c22,12a2y-μ22,ify>c22,y=Λx=12bx-s2.If we choose a=-0.5,b=-1.0,f=1/6,s=1/4,20=a1>a2=5,μ1=1/4,c=1/2, then μ2=3/8; the function Ps(x) can be written as(42)Psx=52x4+52x3-2916x2-12196x+245512,ifx∈-34,14.58x4+58x3-6164x2-229384x+6052048,ifx∈-1,-34∪14,1.And its canonical dual function Pd(y∗) can be written as(43)Pdy∗=-1/21/6-1/4ϵ∗2-1/2+ϵ∗+2ρ∗-140ϵ∗2-732ϵ∗-ρ∗,ify∗∈y∗=ϵ∗,ρ∗T∈R2∣-12+ϵ∗+2ρ∗≠0,-5≤ϵ∗≤-52,ρ∗≥0.-1/21/6-1/4ϵ∗2-1/2+ϵ∗+2ρ∗-332ϵ∗+532-ρ∗,ify∗∈y∗=ϵ∗,ρ∗T∈R2∣-12+ϵ∗+2ρ∗≠0,-52<ϵ∗≤-54,ρ∗≥0.-1/21/6-1/4ϵ∗2-1/2+ϵ∗+2ρ∗-110ϵ∗2-1132ϵ∗-ρ∗,ify∗∈y∗=ϵ∗,ρ∗T∈R2∣-12+ϵ∗+2ρ∗≠0,ϵ∗>-54,ρ∗≥0.In the effective domain Yα1∗={y∗=(ϵ∗,ρ∗)T∈R2∣-1/2+ϵ∗+2ρ∗≠0,-5≤ϵ∗≤-5/2,ρ∗≥0}, the canonical dual function Pd(y∗) has one real root: (44)y-1∗=ϵ-1∗,ρ-1∗T=-4.9994,0T.In the effective domain Yβ1∗={y∗=(ϵ∗,ρ∗)T∈R2∣-1/2+ϵ∗+2ρ∗≠0,-5/2<ϵ∗≤-5/4,ρ∗≥0}, the canonical dual function Pd(y∗) does not have any real roots. In the effective domain Yγ1∗={y∗=(ϵ∗,ρ∗)T∈R2∣-1/2+ϵ∗+2ρ∗≠0,ϵ∗>-5/4,ρ∗≥0}, the canonical dual function Pd(y∗) has two real roots: (45)y-2∗=ϵ-2∗,ρ-2∗T=-0.4687,0.3424T,y-3∗=ϵ-3∗,ρ-3∗T=0.5424,0T.Since y-3∗=(ϵ-3∗,ρ-3∗)T∈Y+∗, by Theorem 2, we know that (46)x-3=1/6-1/4ϵ-3∗-1/2+ϵ-3∗+2ρ-3∗=0.7335is a global minimizer of Ps(x) and Ps(x-3)=Pd(y-3∗)=Pd(ϵ-3∗,ρ-3∗)=-0.2273, while x-1=-0.2576 is a local maximizer and x-2=-1 is a local minimizer (see Figure 1(a)). The graphs of the box constrained nonconvex and nonsmooth function P(x) and its canonical dual function Pd(y∗) are shown in Figure 1.Figure 1
(a) Graph of thePs(x) in one-dimensional spcae. (b) Graph of the canonical dual function Pd(y∗).
(a)
(b)Example 2.
In the case ofn=2, if we choose A=B=1001, s=f=11, 1=a1<a2=9, μ1=1/8, c=1/4, then μ2=1/16, and the function Ps(x) can be written as(47)Psx=12x12+x22-x1-x2+1212x1-12+12x2-12-182,ifx1-12+x2-12≤116,12x12+x22-x1-x2+9212x1-12+12x2-12-1162,ifx1-12+x2-12>116.In the effective domain Yα2∗={y∗=ϵ∗,ρ∗T∈R×R2∣1+ϵ∗+2ρi∗≠0,-9/16≤ϵ∗<-9/32,ρi∗≥0,i=1,2}, the canonical dual function Pd(y∗) has one real root (48)y¯1∗=ϵ¯1∗,ρ¯1∗,ρ¯2∗T=-916,0,0T.Neither in the effective domain Yβ2∗={y∗=(ϵ∗,ρ∗)T∈R×R2∣1+ϵ∗+2ρi∗≠0,-9/32≤ϵ∗<-3/32,ρi∗≥0,i=1,2} nor in the effective domain Yγ2∗={y∗=ϵ∗,ρ∗T∈R×R2∣1+ϵ∗+2ρi∗≠0,ϵ∗≥-3/32,ρi∗≥0,i=1,2}, the canonical dual function Pd(y∗) have any real roots.
Sincey-1∗=(ϵ-1∗,ρ-1∗,ρ-2∗)T=(-9/16,0,0)T∈Y+∗, by Theorem 2, we know that (49)x-=Fϵ-∗,ρ-∗-1Gϵ-∗=1+ϵ∗1+ϵ∗+2ρ1∗1+ϵ∗1+ϵ∗+2ρ2∗=11is a global minimizer of Ps(x) and Ps(x-)=Pd(y-1∗)=Pd(ϵ-1∗,ρ-1∗,ρ-2∗)=-1 (see Figure 2).Figure 2
Graph of the functionPs(x) in two-dimensional spcae.


## 5. Conclusions

It is very difficult to solve the nonconvex and nonsmooth optimization problem with box constraints via the traditional methods. However, using the canonical dual transformation method, which is presented in the paper, we can easily obtain the global minimizer ofPs(x) by solving its canonical dual problem. As the canonical dual function Pd(y∗) is concave on the dual feasible space Y+∗, when Y+∗ is nonempty, the canonical dual function Pd(y∗) has one stationary point in Y+∗ at least. Thus, we can solve the canonical dual problem by well-developed deterministic optimization methods. The presented paper shows again that the canonical dual transformation method may possess important computational impacts on global optimization.



---

*Source: 354263-2015-08-09.xml*