Canonical dual methods for general box constrained nonconvex and nonsmooth optimization problems

Abstract

This paper presents a canonical duality theory for general box constrained nonconvex and nonsmooth optimization problems. The theory is illustrated perfectly by showing mainly a canonical dual transformation and a triality theory. It is proved that the general box constrained nonconvex and nonsmooth optimization problems can be changed into the perfect dual problems, which can be solved easily. The perfect dual transformation is developed for eliminating the duality gap,while the triality theorem studies global and local extreme conditions. Applications and examples are illustrated.

Keywords

Canonical (perfect) dual transformation triality theory box constrains nonconvex and nonsmooth minimization global and local optimization

1. Primal problem and its dual problem

The general box constrained nonconvex and nonsmooth optimization problem is proposed as a primal problem $(P)$ given as follows:

$\displaystyle(P):\begin{cases}\displaystyle\min_{x\in R^{n}}P_{t}(x)=\frac{1}{% 2}x^{T}Ax-x^{T}f+W(x,t)\\ s.t.\quad-l\leqslant x\leqslant l\\ \end{cases}$ (1)

where

$\displaystyle W(x,t)=\begin{cases}\displaystyle\frac{1}{2}a_{1}\left(\frac{1}{% 2}|Bx-t|^{2}-\mu_{1}\right)^{2},&\text{if∼{}}|Bx-t|\leqslant h;\\ \displaystyle\frac{1}{2}a_{2}\left(\frac{1}{2}|Bx-t|^{2}-\mu_{2}\right)^{2},&% \text{if∼{}}|Bx-t|>h.\\ \end{cases}$ (2)

is a nonconvex and nonsmooth function and $a_{1}$ , $a_{2}$ and $h$ are all positive constants $\mu_{2}=\frac{h^{2}}{2}+\sqrt{\frac{a_{1}}{a_{2}}}|\frac{h^{2}}{2}-\mu_{1}|$ , $\mu_{1}$ is a given arbitrary constant, $B\in R^{m\times n}$ is a matrix and $A=A^{T}\in R^{n\times n}$ is a symmetrix matrix, $t\in R^{m}$ is a vector of parameter and and $l,f\in R^{n}$ are non-zero vectors, $|\cdot|:R^{n}\to R$ denotes the Euclidean norm.

The nonconvex and nonsmooth optimization problem $(P)$ appears frequently in many applications [1, 2, 3, 4, 5, 6, 7, 9, 13, 14, 15]. while, it is usually difficult to find out the optimal solutions of the nonconvex and nonsmooth function $P_{t}(x)$ with box constrained by traditional methods. Luckly, the elegant duality theorem are studied and used successfully for showing this problem by Gao and strang [8, 10].

As indicated in [6], the key idea of the perfect dual transformation method is to introduce a geometric operator to make the nonconvex function $W(x,t)$ and the general box constrains written in the elegant form [8]. To study the general box constrained nonconvex and nonsmooth optimization problem, it is necessary to reformulate the constraints $-l\leqslant x\leqslant l$ in canonical form $x_{i}^{2}\leqslant l,(i=1,2,\ldots,n)$ with a geometric operator $y=\Lambda(x):R^{n}\to R\times R^{n}$ , the primal problem $(P)$ can be denoted as $y=\Lambda(x)=(\varepsilon,q)=\left(\frac{1}{2}|Bx-t|^{2},x_{i}^{2}-l\right)$ , where $\varepsilon=\frac{1}{2}|Bx-t|^{2}$ is a scale, and $q=\left\{{q_{i}}\right\}=\left\{{x_{i}^{2}-l}\right\}$ for $i=1,2,\ldots,n$ . Let $Y_{a}\subset R\times R^{n}$ be the domain of $y=\Lambda(x)$ and denote

$\displaystyle Y_{a}=\left\{{\left.{y=(\varepsilon,q)\in R\times R^{n}}\right|% \varepsilon\geqslant 0,q\leqslant 0}\right\}.$

The effective domain of $(P)$ is $X_{a}=\left\{{\left.{x\in R^{n}}\right|x_{i}^{2}\leqslant l,i=1,2,\ldots,n}\right\}$ , then a canonical function $U(y)$ on $Y_{a}\subset R\times R^{n}$ can be written as

$\displaystyle U(y)=U(\varepsilon,q)=\begin{cases}\displaystyle\frac{1}{2}a_{1}% (\varepsilon-\mu_{1})^{2}+\varphi(q),&\displaystyle\text{if∼{}}\varepsilon\in% \left[{0,\frac{h^{2}}{2}}\right];\\ \\ \displaystyle\frac{1}{2}a_{2}(\varepsilon-\mu_{2})^{2}+\varphi(q),&% \displaystyle\text{if∼{}}\varepsilon\in\left(\frac{h^{2}}{2},+\infty\right).\\ \end{cases}$

where

$\displaystyle\varphi(q)=\begin{cases}0,&\text{if∼{}}q\in\left({-\infty,0}% \right];\\ +\infty,&\text{if∼{}}q\in(0,+\infty).\\ \end{cases}$

We denote

$\displaystyle\bar{{F}}(x)=x^{T}f-\frac{1}{2}x^{T}Ax,$

which is a canonical function on $R^{n}$ in sense that its $G\hat{{a}}teaux$ derivative $x^{*}=D\bar{{F}}(x)=f-Ax:R^{n}\to R^{n}$ .

Is one-to-one onto mapping. Thus, the primal problem Eq. (1) can be written in the following unconstrained perfect form

$\displaystyle(P):\min_{x\in R^{n}}P_{t}(x)=U(\Lambda(x))-\bar{{F}}(x)\to sta,% \forall x\in R^{n}.$ (3)

where the notation $s t a$ stands for finding all stationary points of the problem stated in Eq. (3).

Let $y\ast=(\varepsilon^{*},q^{*})\in R\times R^{n}$ be a dual variable of $y$ . then the Fenchel canonical conjugate of $U(y)$ can be defined by

$\displaystyle U^{*}(y^{*})=\sup_{y\in R\times R^{n}}\left\{{y^{T}y^{*}-U(y)}% \right\},$

and its effective domain $Y_{a}^{*}=\left\{{\left.{y^{*}=(\varepsilon^{*},q^{*})\in R\times R^{n}}\right% |\varepsilon^{*}\geqslant 0,q^{*}\leqslant 0}\right\}$ , then by convex analysis, we have the following equivalent relations [5] hold:

$\displaystyle y^{*}\in\partial U(y)\Leftrightarrow y\in\partial U^{*}(y^{*})$ (4)

and the extended canonical duality relations Eq. (4) can be written the following forms

$\displaystyle y^{*}\in\partial U(y)\Leftrightarrow y\in\partial U^{*}(y^{*})% \Leftrightarrow U(y)+U^{*}(y^{*})=y^{T}y^{*}.$

By the canonical dual transformation developed in [6], the canonical dual function of $P(x)$ is defined by

$\displaystyle P^{d}(y^{*})=\bar{{F}}^{\Lambda}(y^{*})-U^{*}(y^{*}),$ (5)

where $\bar{{F}}^{\Lambda}(y^{*})$ is the is the so-called $\Lambda$ -canonical dual transformation [8] defined by

$\displaystyle\bar{{F}}^{\Lambda}(y^{*})=\left\{{\left.{<\Lambda(x),y^{*}>-\bar% {{F}}^{\Lambda}(x)}\right|D\bar{{F}}^{\Lambda}(x)=<\Lambda(x),y^{*}>,x\in X_{a% }}\right\}=-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-1}% f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*})})^{-1}G(\varepsilon^{*})-t% \right]\varepsilon^{*}-\sum\nolimits_{i=1}^{n}{q_{i}^{*}l_{i}}$

where $F(\varepsilon^{*},q^{*})\overset{\Delta}{=}A+B^{T}B\varepsilon^{*}+2Diagq^{*}$ and $G(\varepsilon^{*})\overset{\Delta}{=}f+B^{T}t\varepsilon^{*}$ . The matrix $A+B^{T}B\varepsilon^{*}+2Diagq^{*}$ is invertible, where $Diagq^{*}\in R^{n\times n}$ represents a diagonal matrix with $q_{i}^{*},(i=1,2,\ldots,n)$ as its diagonal entries and the dual variable $q^{*}=\left\{{q_{i}^{*}}\right\}$ is also a vector in $R^{n}$ .

In the case of $a_{1}>a_{2}$ , the canonical conjugate function $U^{*}(y^{*})=U^{*}(\varepsilon^{*},q^{*})$ of $U(y)$ can be written as

$\displaystyle U^{*}(y^{*})=\left\{{\left.{<y,y^{*}>-U\left(y\right)}\right|DU(% y)=y^{*}}\right\}=\begin{cases}\displaystyle\frac{1}{2a_{1}}(\varepsilon^{*})^% {2}+\mu_{1}\varepsilon^{*},&\displaystyle\text{if∼{}}-a_{1}\mu_{1}\leqslant% \varepsilon^{*}\leqslant a_{1}\left(\frac{h^{2}}{2}-\mu_{1}\right),q^{*}% \geqslant 0\\ \\ \displaystyle\frac{h^{2}}{2}\varepsilon^{*}-\frac{1}{2a_{1}}\left(\frac{h^{2}}% {2}-\mu_{1}\right)^{2},&\displaystyle\text{if∼{}}a_{1}\left(\frac{h^{2}}{2}-% \mu_{1}\right)\leqslant\varepsilon^{*}\leqslant a_{2}\left(\frac{h^{2}}{2}-\mu% _{2}\right),q^{*}\geqslant 0\\ \\ \displaystyle\frac{1}{2a_{2}}(\varepsilon^{*})^{2}+\mu_{2}\varepsilon^{*},&% \displaystyle\text{if∼{}}\varepsilon^{*}>a_{2}\left(\frac{h^{2}}{2}-\mu_{2}% \right),q^{*}\geqslant 0.\\ \end{cases}$

The dual feasible spaces are three subsets of $R\times R^{n}$ :

$\displaystyle Y_{1}^{*}=\left\{y^{*}=(\varepsilon^{*},q^{*})|y^{*}\in R\times R% ^{n},-a_{1}\mu_{1}\leqslant\varepsilon^{*}\leqslant a_{1}\left(\frac{h^{2}}{2}% -\mu_{1}\right),q^{*}\geqslant 0,\det F(\varepsilon^{*},q^{*})\neq 0\right\},$ $\displaystyle Y_{2}^{*}=\bigg{\{}y^{*}=(\varepsilon^{*},q^{*})|y^{*}\in R% \times R^{n},a_{1}\left(\frac{h^{2}}{2}-\mu_{1}\right)\leqslant\varepsilon^{*}% \leqslant a_{2}\left(\frac{h^{2}}{2}-\mu_{2}\right),q^{*}\geqslant 0,\quad\det F% (\varepsilon^{*},q^{*})\neq 0\bigg{\}},$ $\displaystyle Y_{3}^{*}=\left\{y^{*}=(\varepsilon^{*},q^{*})|y^{*}\in R\times R% ^{n},\varepsilon^{*}>a_{2}\left(\frac{h^{2}}{2}-\mu_{2}\right),q^{*}\geqslant 0% ,\det F(\varepsilon^{*},q^{*})\neq 0\right\}.$

Thus, the canonical dual problem ( $P^{d}$ ) is formulated as

$\displaystyle P^{d}(y^{*})=P^{d}(\varepsilon^{*},q^{*})=\begin{cases}% \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{1}{2a_{1}}(\varepsilon^{*})^{2}+\mu_{1}% \varepsilon^{*}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{i},&\text{if∼{}}(% \varepsilon^{*},q^{*})\in Y_{1}^{*},\\ \\ \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{h^{2}}{2}\varepsilon^{*}-\frac{1}{2}a_{1}% \left(\frac{h^{2}}{2}-\mu_{1}\right)^{2}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^% {*}l_{i},&\text{if∼{}}(\varepsilon^{*},q^{*})\in Y_{2}^{*},\\ \\ \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{1}{2a_{2}}(\varepsilon^{*})^{2}+\mu_{2}% \varepsilon^{*}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{i},&\text{if∼{}}(% \varepsilon^{*},q^{*})\in Y_{3}^{*}.\\ \end{cases}\to sta.$

In the case of $a_{1}<a_{2}$ , the elegant conjugate function $U^{*}(y^{*})=U^{*}(\varepsilon^{*},q^{*})$ of $U(y)$ can be given as

$\displaystyle U^{*}(y^{*})=\left\{<y,y^{*}>-U\left(y\right)|DU(y)=y^{*}\right% \}=\begin{cases}\displaystyle\frac{1}{2a_{2}}(\varepsilon^{*})^{2}+\mu_{2}% \varepsilon^{*},&\displaystyle\text{if∼{}}-a_{2}\mu_{2}\leqslant\varepsilon^{*% }\leqslant a_{2}\left(\frac{h^{2}}{2}-\mu_{2}\right),q^{*}\geqslant 0\\ \\ \displaystyle\frac{h^{2}}{2}\varepsilon^{*}-\frac{1}{2a_{2}}\left(\frac{h^{2}}% {2}-\mu_{2}\right)^{2},&\displaystyle\text{if∼{}}a_{2}\left(\frac{h^{2}}{2}-% \mu_{2}\right)\leqslant\varepsilon^{*}\leqslant a_{1}\left(\frac{h^{2}}{2}-\mu% _{1}\right),q^{*}\geqslant 0\\ \\ \displaystyle\frac{1}{2a_{1}}(\varepsilon^{*})^{2}+\mu_{1}\varepsilon^{*},&% \displaystyle\text{if∼{}}\varepsilon^{*}>a_{1}\left(\frac{h^{2}}{2}-\mu_{1}% \right),q^{*}\geqslant 0\\ \end{cases}$

Similarly, we get dual feasible subsets in $R\times R^{n}$ :

$\displaystyle Y_{4}^{*}=\left\{{\left.{y^{*}=(\varepsilon^{*},q^{*})}\right|y^% {*}\in R\times R^{n},-a_{2}\mu_{2}\leqslant\varepsilon^{*}\leqslant a_{2}\left% (\frac{h^{2}}{2}-\mu_{2}\right),q^{*}\geqslant 0,\det F(\varepsilon^{*},q^{*})% \neq 0}\right\},$ $\displaystyle Y_{2}^{*}=\bigg{\{}\left.{y^{*}=(\varepsilon^{*},q^{*})}\right|y% ^{*}\in R\times R^{n},a_{2}\left(\frac{h^{2}}{2}-\mu_{2}\right)<\varepsilon^{*% }\leqslant a_{1}\left(\frac{h^{2}}{2}-\mu_{1}\right),q^{*}\geqslant 0,\det F(% \varepsilon^{*},q^{*})\neq 0\bigg{\}},$ $\displaystyle Y_{3}^{*}=\left\{{\left.{y^{*}=(\varepsilon^{*},q^{*})}\right|y^% {*}\in R\times R^{n},\varepsilon^{*}>a_{1}\left(\frac{h^{2}}{2}-\mu_{1}\right)% ,q^{*}\geqslant 0,\det F(\varepsilon^{*},q^{*})\neq 0}\right\}.$

Then, the canonical dual problem ( $P^{d}$ ) is formulated as

$\displaystyle P^{d}(y^{*})=P^{d}(\varepsilon^{*},q^{*})=\begin{cases}% \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle-\left[{\frac{1}{2a_{2}}(\varepsilon^{*})^{2}+\mu_{2}\varepsilon^% {*}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{i},&\text{if∼{}}(\varepsilon^{*% },q^{*})\in Y_{4}^{*},\\ \\ \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle-\left[{\frac{h^{2}}{2}\varepsilon^{*}-\frac{1}{2}a_{2}\left(% \frac{h^{2}}{2}-\mu_{2}\right)^{2}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{% i},&\text{if∼{}}(\varepsilon^{*},q^{*})\in Y_{5}^{*},\\ \\ \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle-\left[{\frac{1}{2a_{1}}(\varepsilon^{*})^{2}+\mu_{1}\varepsilon^% {*}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{i},&\text{if∼{}}(\varepsilon^{*% },q^{*})\in Y_{6}^{*}.\\ \end{cases}\to sta.$

Theorem 1 (Canonical duality theorem). The problem ( $P^{d}$ ) is canonically dual to the primal problem ( $P$ ) means that if $\bar{{y}}^{*}=(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})$ is a KKT point of the canonical dual problem (P), then the vector defined by

$\displaystyle\bar{{x}}=F(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})^{-1}G(\bar{{% \varepsilon}}^{*})$

is a KKT point of ( $P$ ) and

$\displaystyle P_{t}(\bar{{x}})=P^{d}(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})=P^% {d}(y^{*}).$

Proof Without loss of generality, we suppose that $\bar{{y}}^{*}=(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})\in Y_{4}^{*}$ is a KKT point of ( $P^{d}$ ), then the criticality condition $\nabla_{\varepsilon^{*}}P^{d}(\varepsilon^{*},q^{*})=0$ (where $\nabla_{\varepsilon^{*}}P^{d}$ stands for the $G\hat{{a}}teaux$ derivative of $P^{d}$ at $\varepsilon^{*}$ ) leads to the following equation

$\displaystyle\frac{1}{2}(BG(\bar{{\varepsilon}}^{*}))^{T}(F(\bar{{\varepsilon}% }^{*},\bar{{q}}^{*}))^{-2}(BG(\bar{{\varepsilon}}^{*}))-(BG(\bar{{\varepsilon}% }^{*}))^{T}(F(\bar{{\varepsilon}}^{*},\bar{{q}}^{*}))^{-1}t+\frac{1}{2}t^{2}-% \left(\frac{1}{a_{2}}\bar{{\varepsilon}}^{*}+\mu_{2}\right)=0$

In terms of $\bar{{x}}=F(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})^{-1}G(\bar{{\varepsilon}}^{% *})$ and the Eq. (1), we have

$\displaystyle\frac{1}{a_{2}}\bar{{\varepsilon}}^{*}+\mu_{2}=\frac{1}{2}|Bx-t|^% {2}=\varepsilon$

On the other hand, the criticality condition $\nabla_{\varepsilon^{*}}P^{d}(\varepsilon^{*},q^{*})\leqslant 0$ leads to the KKT condition

$\displaystyle x_{i}^{2}(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})-l_{i}\leqslant 0% ,\bar{{q}}_{i}^{*}\geqslant 0,\bar{{q}}_{i}^{*}(\bar{{x}}_{i}^{2}(\bar{{% \varepsilon}}^{*},\bar{{q}}^{*})-l_{i})\leqslant 0,i=1,2,\ldots,n$ (7)

where $x_{i}^{2}(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})$ stands for the $i$ -th component of the vector $\bar{{x}}=F(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})^{-1}G(\bar{{\varepsilon}}^{% *})$ . Thus, $x_{i}^{2}(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})$ is also a KKT point of the primal problem ( $P$ ). By Eq. (7), we get $\bar{{q}}_{i}^{*}l_{i}=\bar{{x}}_{i}^{2}\bar{{q}}_{i}^{*},i=1,2,\ldots,n$ . Thus, by $\bar{{x}}=F(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})^{-1}G(\bar{{\varepsilon}}^{% *})$ and

$\displaystyle\frac{1}{2a_{2}}(\bar{{\varepsilon}}^{*})^{2}+\mu_{2}\bar{{% \varepsilon}}^{*}=-\frac{1}{2}a_{2}\left(\frac{1}{2}|B\bar{{x}}-t|^{2}-\mu_{2}% \right)^{2}+\frac{1}{2}|B\bar{{x}}-t|^{2}\bar{{\varepsilon}}^{*},$

we have

$\displaystyle P^{d}(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})=\frac{1}{2}\bar{{x}% }^{T}F\left({\bar{{\varepsilon}}^{*},\bar{{q}}^{*}}\right)\bar{{x}}-\bar{{x}}^% {T}f+\frac{1}{2}t^{T}t-t^{T}B\bar{{\varepsilon}}^{*}\bar{{x}}=\frac{1}{2}|B% \bar{{x}}-t|^{2}\bar{{\varepsilon}}^{*}+\bar{{q}}_{i}^{*}\left({\bar{{x}}_{i}^% {2}(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})-l_{i}}\right)+\frac{1}{2}\bar{{x}}^% {T}A\bar{{x}}-\bar{{x}}^{T}f+\frac{1}{2}a_{2}\left(\frac{1}{2}|B\bar{{x}}-t|^{% 2}-\mu_{2}\right)^{2}-\frac{1}{2}|B\bar{{x}}-t|^{2}\bar{{\varepsilon}}^{*}=% \frac{1}{2}\bar{{x}}^{T}A\bar{{x}}+\frac{1}{2}a_{2}\left({\frac{1}{2}|B\bar{{x% }}-t|^{2}-\mu_{2}}\right)^{2}-\bar{{x}}^{T}f=P_{t}(\bar{{x}})$

This proves the theorem.

The Theorem 1 implies that there is no duality gap between the ( $P$ ) and ( $P^{d}$ ). It was apparent to all that the KKT conditions are only necessary for nonconvex quadratic programming problem, we will show the global and local extreme conditions of the primal problem ( $P$ ) next.

2. Global and local extreme conditions

To identify the global and local extreme conditions of the nonconvex and nonsmooth problem ( $P$ ), we had better introduce two useful feasible subsets of $Y_{i}^{*}(i=1,2,3,4,5,6)$ are respectively defined by

$\displaystyle Y_{+}^{*}=\left\{{\left.{(\varepsilon^{*},q^{*})^{T}\in Y_{i}^{*% }}\right|F(\varepsilon^{*},q^{*})\text{is positive definite}}\right\},$ $\displaystyle Y_{-}^{*}=\left\{{\left.{(\varepsilon^{*},q^{*})^{T}\in Y_{i}^{*% }}\right|F(\varepsilon^{*},q^{*})\text{is negative definite}}\right\}.$

Theorem 2 (Triality Theorem). Suppose that the vector $\bar{{y}}^{*}=(\varepsilon^{*},q^{*})^{T}$ is a solution of $Y_{i}^{*}(i=1,2,3,$ $4,5,6)$ and $\bar{{x}}=F(\varepsilon^{*},q^{*})^{-1}G(\varepsilon^{*})$ .

If $\bar{{y}}^{*}\in Y_{+}^{*}$ , then $\bar{{y}}^{*}$ is a global maximizer of $P^{d}$ on $Y_{+}^{*}$ , while $\bar{{x}}$ is a global minimizer of $P_{t}(x)$ on $X_{a}$ and

$\displaystyle P_{t}(\bar{{x}})=\min_{x\in X_{a}}P_{t}(x)=\max_{y^{*}\in Y_{+}^% {*}}P^{d}(y^{*})=P^{d}(\bar{{y}}^{*}).$

If $\bar{{y}}^{*}\in Y_{-}^{*}$ , then on the neighborhoods $X_{o}\times Y_{o}^{*}\subset X_{a}\times Y_{i}^{*}$ of $(\bar{{x}},\bar{{y}}^{*})$ , we get that either

$\displaystyle P_{t}(\bar{{x}})=\min_{x\in X_{o}}P_{t}(x)=\min_{y^{*}\in Y_{o}^% {*}}P^{d}(y^{*})=P^{d}(\bar{{y}}^{*})$

$\displaystyle P_{t}(\bar{{x}})=\max_{x\in X_{o}}P_{t}(x)=\max_{y^{*}\in Y_{o}^% {*}}P^{d}(y^{*})=P^{d}(\bar{{y}}^{*}),$

holds.

Proof Without loss of generality, suppose that $\bar{{y}}^{*}=(\varepsilon^{*},q^{*})\in Y_{4}^{*}$ . The extended Lagrangian $\Xi:R^{n}\times R^{1+n}\to Y_{4,5,6}^{*}$ related to ( $P$ ) can be written as

$\displaystyle\Xi(x,y^{*})=\Xi(x,\varepsilon^{*},q^{*})=(\Lambda(x))^{T}y^{*}-U% ^{*}(y\ast)+\frac{1}{2}x^{T}Ax-x^{T}f=\frac{1}{2}x^{T}F(\bar{{\varepsilon}}^{*% },\bar{{q}}^{*})x-t^{T}B\bar{{\varepsilon}}^{*}x+\frac{1}{2}t^{T}t-x^{T}f-U^{*% }(y^{*}).$

By Theorem 1, we have that the vector $\bar{{y}}^{*}=(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})\in Y_{i}^{*}$ is a KKT point of $P^{d}$ if and only if $\bar{{x}}=F(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})^{-1}G(\bar{{\varepsilon}}^{% *})$ is a KKT point of ( $P$ ), and $P_{t}(\bar{{x}})=\Xi(\bar{{x}},\bar{{y}}^{*})=\Xi\left({\bar{{x}},\bar{{% \varepsilon}}^{*},\bar{{q}}^{*}}\right)=P^{d}(\bar{{y}}^{*})$ .

If $\bar{{y}}^{*}\in Y_{+}^{*}$ , the matrix $F(\varepsilon^{*},q^{*})$ is definite, the extended Lagrangian $\Xi$ is convex on $x\in R^{n}$ and concave in both $\varepsilon^{*}\in R$ and $q^{*}\in R^{n}$ , i.e. it is a saddle function on $R^{n}\times Y_{+}^{*}$ . Thus, we obtain that

$\displaystyle P^{d}(\bar{{y}}^{*})=\max_{y^{*}\in Y_{+}^{*}}P^{d}(y^{*})=\max_% {y^{*}\in Y_{+}^{*}}\min_{x\in X_{a}}\Xi(x,y^{*})=\min_{x\in X_{a}}\max_{y^{*}% \in Y_{+}^{*}}\Xi(x,y^{*})=\min_{x\in X_{a}}\left\{{\frac{1}{2}x^{T}Ax-x^{T}f+% \max_{y^{*}\in Y_{+}^{*}}\left\{{(\Lambda(x))^{T}y^{*}-\bar{{U}}^{*}(y^{*})}% \right\}}\right\}.$

with the fact that

$\displaystyle U(\Lambda(x))=\max_{y^{*}\in Y_{+}^{*}}\left\{{(\Lambda(x))^{T}y% ^{*}-U^{*}(y^{*})}\right\}=\begin{cases}\displaystyle\frac{1}{2}\left(\frac{1}% {2}|Bx-t|^{2}-\mu_{2}\right)^{2}&\text{if∼{}}x\in X_{a}\\ +\infty&\text{otherwise}.\\ \end{cases}.$

If $\bar{{y}}^{*}\in Y_{-}^{*}$ , the matrix $F(\bar{{\varepsilon}}^{*},\bar{{q}}^{*})$ is indefinite, In this case, the function $\Xi(x,y^{*})$ is a so-called super-Lagrangian [8], and it is locally concave in both $x\in X_{o}\subset X_{a}$ and $y^{*}\subset Y_{o}\subset Y_{-}^{*}$ . Thus, by the triality theory developed in [8], we get either

$\displaystyle P_{t}(\bar{{x}})=\min_{x\in X_{o}}P_{t}(x)=\min_{x\in X_{o}}\max% _{y^{*}\in Y_{o}^{*}}\Xi(x,y^{*})=\min_{y^{*}\in Y_{o}^{*}}\max_{x\in X_{o}}% \Xi(x,y^{*})=\min_{y^{*}\in Y_{o}^{*}}P^{d}(y^{*})=P^{d}(\bar{{y}}^{*})$

$\displaystyle P_{t}(\bar{{x}})=\max_{x\in X_{o}}P_{t}(x)=\max_{x\in X_{o}}\max% _{y^{*}\in Y_{o}^{*}}\Xi(x,y^{*})=\max_{y^{*}\in Y_{o}^{*}}\max_{x\in X_{o}}% \Xi(x,y^{*})=\max_{y^{*}\in Y_{o}^{*}}P^{d}(y^{*})=P^{d}(\bar{{y}}^{*}).$

This proves the Triality theorem.

The Theorem 2 reveals an important fact that the nonconvex and nonsmooth problem ( $P$ ) can be converted into a concave maximization dual problem $P^{d}$ . And the condition $\bar{{y}}^{*}\in Y_{-}^{*}$ provides local extremal conditions for the problem ( $P$ ), while the condition $\bar{{y}}^{*}\in Y_{+}^{*}$ provides global extremal conditions for the general box constrained nonconvex and nonsmooth minimization problem ( $P$ ).

3. Application and examples

The canonical duality theory can be applied to many applications especially in engineering and science applications. Now we show examples to illustrate the theory presented in this paper in the case of $n=1$ and $n=2$ respectively.

Examples. In the case of $n=1$ , the nonconvex and nonsmooth function

$\displaystyle P_{t}(x)=\frac{1}{2}ax^{2}-fx+W(x,t)$

where

$\displaystyle W(x,t)=\begin{cases}{\displaystyle\frac{1}{2}}a_{1}(y-\mu_{1})^{% 2},&\text{if∼{}}0\leqslant y\leqslant{\displaystyle\frac{h^{2}}{2}}\\ \\ {\displaystyle\frac{1}{2}}a_{2}(y-\mu_{2})^{2},&\text{if∼{}}y>{\displaystyle% \frac{h^{2}}{2}}\\ \end{cases}$

and

$\displaystyle y=\Lambda(x)=\frac{1}{2}(bx-t)^{2}.$

If $a_{1}>a_{2}$ , the canonical dual function of $P_{t}(x)$ is

$\displaystyle P^{d}(y^{*})=\begin{cases}\displaystyle-\frac{(f+bt\varepsilon^{% *})^{2}}{2(a+b^{2}\varepsilon^{*}+2q^{*})}-\frac{1}{2a_{1}}(\varepsilon^{*})^{% 2}+\left(\frac{1}{2}t^{2}-\mu_{1}\right)\varepsilon^{*}-q^{*}l,&\text{if∼{}}y^% {*}\in Y_{1}^{*},\\ \\ \displaystyle-\frac{(f+bt\varepsilon^{*})^{2}}{2(a+b^{2}\varepsilon^{*}+2q^{*}% )}+\left(\frac{1}{2}t^{2}-\frac{h^{2}}{2}\right)\varepsilon^{*}+\frac{1}{2}a_{% 1}\left({\frac{h^{2}}{2}-\mu_{1}}\right)^{2}-q^{*}l,&\text{if∼{}}y^{*}\in Y_{2% }^{*},\\ \\ \displaystyle-\frac{(f+bt\varepsilon^{*})^{2}}{2(a+b^{2}\varepsilon^{*}+2q^{*}% )}-\frac{1}{2a_{2}}(\varepsilon^{*})^{2}+\left(\frac{1}{2}t^{2}-\mu_{2}\right)% \varepsilon^{*}-q^{*}l,&\text{if∼{}}y^{*}\in Y_{3}^{*}.\\ \end{cases}$

If $a_{1}<a_{2}$ , the canonical dual function of $P_{t}(x)$ is

$\displaystyle P^{d}(y^{*})=\begin{cases}\displaystyle-\frac{(f+bt\varepsilon^{% *})^{2}}{2(a+b^{2}\varepsilon^{*}+2q^{*})}-\frac{1}{2a_{2}}(\varepsilon^{*})^{% 2}+\left(\frac{1}{2}t^{2}-\mu_{2}\right)\varepsilon^{*}-q^{*}l,&\text{if∼{}}y^% {*}\in Y_{4}^{*},\\ \\ \displaystyle-\frac{(f+bt\varepsilon^{*})^{2}}{2(a+b^{2}\varepsilon^{*}+2q^{*}% )}+\left(\frac{1}{2}t^{2}-\frac{h^{2}}{2}\right)\varepsilon^{*}+\frac{1}{2}a_{% 2}\left({\frac{h^{2}}{2}-\mu_{2}}\right)^{2}-q^{*}l,&\text{if∼{}}y^{*}\in Y_{5% }^{*},\\ \\ \displaystyle-\frac{(f+bt\varepsilon^{*})^{2}}{2(a+b^{2}\varepsilon^{*}+2q^{*}% )}-\frac{1}{2a_{1}}(\varepsilon^{*})^{2}+\left(\frac{1}{2}t^{2}-\mu_{1}\right)% \varepsilon^{*}-q^{*}l,&\text{if∼{}}y^{*}\in Y_{6}^{*}.\\ \end{cases}$

Thus, if we choose $a=\frac{1}{2},b=-1,f=t=1,\frac{1}{2}=a_{1}>a_{2}=\frac{1}{32},l=4,\mu_{1}=% \frac{7}{2},h=2$ , and then $\mu_{2}=8$ , the function $P_{t}(x)$ :

$\displaystyle P_{t}(x)=\begin{cases}\displaystyle\frac{1}{16}x^{4}+\frac{1}{4}% x^{3}-\frac{3}{4}x^{2}-\frac{5}{2}x+\frac{9}{4},&\text{if∼{}}x\in\left[{-3,1}% \right],\\ \\ \displaystyle\frac{1}{256}x^{4}+\frac{1}{64}x^{3}-\frac{45}{128}x^{2}-\frac{79% }{64}x+\frac{225}{256},&\text{if∼{}}x\in\left[{-4,-3}\right)\cup\left({1,4}% \right].\\ \end{cases}$

and its canonical dual function $P^{d}(y^{*})$ :

$\displaystyle P^{d}(y^{*})=$ $\displaystyle\begin{cases}\displaystyle-\frac{(1-\varepsilon^{*})^{2}}{2(-% \frac{1}{2}+\varepsilon^{*}+2q^{*})}-(\varepsilon^{*})^{2}-3\varepsilon^{*}-4q% ^{*},\\ \\ \quad\displaystyle\text{if∼{}}y^{*}\in Y_{1}^{*}=\left\{{\left.{y^{*}=(% \varepsilon^{*},q^{*})\in R\times R}\right|-\frac{1}{2}+\varepsilon^{*}+2q^{*}% \neq 0,-\frac{7}{4}\leqslant\varepsilon^{*}\leqslant-\frac{3}{4},q^{*}% \geqslant 0}\right\},\\ \\ \displaystyle-\frac{(1-\varepsilon^{*})^{2}}{2(-\frac{1}{2}+\varepsilon^{*}+2q% ^{*})}-\frac{3}{2}\varepsilon^{*}+\frac{9}{16}-4q^{*},\\ \\ \quad\displaystyle\text{if∼{}}y^{*}\in Y_{2}^{*}=\left\{{\left.{y^{*}=(% \varepsilon^{*},q^{*})\in R\times R}\right|-\frac{1}{2}+\varepsilon^{*}+2q^{*}% \neq 0,-\frac{3}{4}\leqslant\varepsilon^{*}\leqslant-\frac{3}{16},q^{*}% \geqslant 0}\right\},\\ \\ \displaystyle-\frac{(1-\varepsilon^{*})^{2}}{2(-\frac{1}{2}+\varepsilon^{*}+2q% ^{*})}-16(\varepsilon^{*})^{2}-\frac{15}{2}\varepsilon^{*}-4q^{*},\\ \\ \quad\displaystyle\text{if∼{}}y^{*}\in Y_{3}^{*}=\left\{{\left.{y^{*}=(% \varepsilon^{*},q^{*})\in R\times R}\right|-\frac{1}{2}+\varepsilon^{*}+2q^{*}% \neq 0,\varepsilon^{*}>-\frac{3}{16},q^{*}\geqslant 0}\right\}.\\ \end{cases}$

Figure 1.

(a) Graph of the nonconvex and nonsmooth function $P_{t}(x)$ with box constrained Normal distribution and real Frequency; (b) Graph of the function $P^{d}(y^{*})$ .

In $Y_{1}^{*}=\left\{{\left.{y^{*}=(\varepsilon^{*},q^{*})\in R\times R}\right|-% \frac{1}{2}+\varepsilon^{*}+2q^{*}\neq 0,-\frac{7}{4}\leqslant\varepsilon^{*}% \leqslant-\frac{3}{4},q^{*}\geqslant 0}\right\}$ the canonical dual function $P^{d}(y^{*})$ has one root:

$\displaystyle\bar{{y}}_{1}^{*}=(\bar{{\varepsilon}}_{1}^{*},\bar{{q}}_{1}^{*})% =\left(-\frac{3}{2},\frac{3}{8}\right)=(-1.5000,0.3750).$

In $Y_{2}^{*}=\left\{{\left.{y^{*}=(\varepsilon^{*},q^{*})\in R\times R}\right|-% \frac{1}{2}+\varepsilon^{*}+2q^{*}\neq 0,-\frac{3}{4}\leqslant\varepsilon^{*}% \leqslant-\frac{3}{16},q^{*}\geqslant 0}\right\}$ the canonical dual function $P^{d}(y^{*})$ has no any roots. In $Y_{3}^{*}=\{\left.{y^{*}=(\varepsilon^{*},q^{*})\in R\times R}\right|-\frac{1}% {2}+\varepsilon^{*}+2q^{*}\neq 0,\;\varepsilon^{*}>-\frac{3}{16},$ $q^{*}\geqslant 0\}$ the canonical dual function $P^{d}(y^{*})$ has one real root:

$\displaystyle\bar{{y}}_{2}^{*}=(\bar{{\varepsilon}}_{2}^{*},\bar{{q}}_{2}^{*})% =\left(-\frac{7}{64},\frac{149}{256}\right)=(-0.1094,0.5820).$

By Theorem 1, we have

$\displaystyle\bar{{x}}_{1}=F(\bar{{\varepsilon}}_{1}^{*},\bar{{q}}_{1}^{*})^{-% 1}G(\bar{{\varepsilon}}_{1}^{*})=\frac{f+bt\bar{{\varepsilon}}_{1}^{*}}{a+b^{2% }\bar{{\varepsilon}}_{1}^{*}+2\bar{{q}}_{1}^{*}}=\frac{1-\bar{{\varepsilon}}_{% 1}^{*}}{-\frac{1}{2}+\bar{{\varepsilon}}_{1}^{*}+2\bar{{q}}_{1}^{*}}=-2,$ $\displaystyle\bar{{x}}_{2}=F(\bar{{\varepsilon}}_{2}^{*},\bar{{q}}_{2}^{*})^{-% 1}G(\bar{{\varepsilon}}_{2}^{*})=\frac{f+bt\bar{{\varepsilon}}_{2}^{*}}{a+b^{2% }\bar{{\varepsilon}}_{2}^{*}+2\bar{{q}}_{2}^{*}}=\frac{1-\bar{{\varepsilon}}_{% 2}^{*}}{-\frac{1}{2}+\bar{{\varepsilon}}_{2}^{*}+2\bar{{q}}_{2}^{*}}=-\frac{71% }{55}=1.2909.$

Since $-\frac{1}{2}+\bar{{\varepsilon}}_{1}^{*}+2\bar{{q}}_{1}^{*}<0$ and $-\frac{1}{2}+\bar{{\varepsilon}}_{2}^{*}+2\bar{{q}}_{2}^{*}>0$ , $y_{1}^{*}\in Y_{-}^{*}$ , $y_{2}^{*}\in Y_{+}^{*}$ , by Theorem 2, we know that $\bar{{x}}_{1}=-2$ is a local maximizer of $P_{t}(x)$ and $P_{t}(\bar{{x}}_{1})=P^{d}(\bar{{y}}_{1}^{*})=3.2500$ is a local maximizer of $P^{d}(y^{*})$ , while, $\bar{{x}}_{2}=1.2909$ is a global minimizer of $P_{t}(x)$ and $P_{t}(\bar{{x}}_{2})=P^{d}(\bar{{y}}_{2}^{*})=-0.0871$ (see Fig. 1).

In the case of $n=2$ , the nonconvex and nonsmooth function

$\displaystyle P_{t}(x)=\frac{1}{2}x^{T}Ax-x^{T}f+W(x,t)$

where

$\displaystyle W(x,s)=\begin{cases}\displaystyle\frac{1}{2}a_{1}\left(\frac{1}{% 2}|Bx-t|^{2}-\mu_{1}\right)^{2},&\text{if∼{}}|Bx-t|\leqslant h\\ \\ \displaystyle\frac{1}{2}a_{2}\left(\frac{1}{2}|Bx-t|^{2}-\mu_{2}\right)^{2},&% \text{if∼{}}|Bx-t|>h\\ \end{cases}$

is a nonconvex and nonsmooth function and $\mu_{2}=\frac{h^{2}}{2}+\sqrt{\frac{a_{1}}{a_{2}}}|\frac{h^{2}}{2}-\mu_{1}|$ , $\mu_{1}$ is an arbitrary constant.

If $a_{1}>a_{2}$ , the canonical dual function of $P_{t}(x)$ is

$\displaystyle P^{d}(y^{*})=\begin{cases}\displaystyle-\frac{1}{2}(G(% \varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-1}f-\frac{1}{2}t^{T}\left[{B% (F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{1}{2a_{1}}(\varepsilon^{*})^{2}+\mu_{1}% \varepsilon^{*}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{i},&\text{if∼{}}y^{% *}\in Y_{1}^{*},\\ \\ \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{h^{2}}{2}\varepsilon^{*}-\frac{1}{2}a_{1}% \left(\frac{h^{2}}{2}-\mu_{1}\right)^{2}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^% {*}l_{i},&\text{if∼{}}y^{*}\in Y_{2}^{*},\\ \\ \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{1}{2a_{2}}(\varepsilon^{*})^{2}+\mu_{2}% \varepsilon^{*}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{i},&\text{if∼{}}y^{% *}\in Y_{3}^{*}.\\ \end{cases}$

If $a_{1}<a_{2}$ , the canonical dual function of $P_{t}(x)$ is

$\displaystyle P^{d}(y^{*})=$ $\displaystyle\begin{cases}\displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(% \varepsilon^{*},q^{*}))^{-1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}% ))^{-1}G(\varepsilon^{*})-t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{1}{2a_{2}}(\varepsilon^{*})^{2}+\mu_{2}% \varepsilon^{*}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{i},&\text{if∼{}}(% \varepsilon^{*},q^{*})\in Y_{4}^{*},\\ \\ \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{h^{2}}{2}\varepsilon^{*}-\frac{1}{2}a_{2}% \left(\frac{h^{2}}{2}-\mu_{2}\right)^{2}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^% {*}l_{i},&\text{if∼{}}(\varepsilon^{*},q^{*})\in Y_{5}^{*},\\ \\ \displaystyle-\frac{1}{2}(G(\varepsilon^{*}))^{T}(F(\varepsilon^{*},q^{*}))^{-% 1}f-\frac{1}{2}t^{T}\left[{B(F(\varepsilon^{*},q^{*}))^{-1}G(\varepsilon^{*})-% t}\right]\varepsilon^{*}\\ \\ \displaystyle\qquad-\left[{\frac{1}{2a_{1}}(\varepsilon^{*})^{2}+\mu_{1}% \varepsilon^{*}}\right]-\sum\nolimits_{i=1}^{n}q_{i}^{*}l_{i},&\text{if∼{}}(% \varepsilon^{*},q^{*})\in Y_{6}^{*}.\\ \end{cases}$

Figure 2.

Graph of the nonconvex and nonsmooth function $P_{t}(x)$ with general box constrained.

Thus, if we choose $A=\begin{bmatrix}-\frac{1}{2}&0\\ 0&-\frac{1}{2}\\ \end{bmatrix},B=\begin{bmatrix}1&0\\ 0&1\\ \end{bmatrix},s=f=\begin{bmatrix}1\\ 1\\ \end{bmatrix},l=\begin{bmatrix}1\\ 4\\ \end{bmatrix},1=a_{1}<a_{2}=4,\mu_{1}=\frac{3}{2},h=2$ , and then $\mu_{2}=\frac{9}{4}$ . In the effective domain $Y_{4}^{*}=\{{y^{*}=(\varepsilon^{*},q^{*})\in R\times R^{2}}|-\frac{1}{2}+% \varepsilon^{*}+2q^{*}$ is inversible, $-9\leqslant\varepsilon^{*}\leqslant-1,q_{i}^{*}\geqslant 0,i=1,2.\},$ the canonical dual function $P^{d}(y^{*})$ has one real root:

$\displaystyle\bar{{y}}_{1}^{*}=(\bar{{\varepsilon}}_{1}^{*},\bar{{q}}_{1}^{*},% \bar{{q}}_{2}^{*})=\bigg{(}-7,\frac{3}{4},\frac{9}{4}\bigg{)}.$

In the effective domain $Y_{5}^{*}=\{\left.{y^{*}=(\varepsilon^{*},q^{*})\in R\times R^{2}}\right|-% \frac{1}{2}+\varepsilon^{*}+2q^{*}$ is inversible, $-1<\varepsilon^{*}\leqslant\frac{1}{2},q_{i}^{*}\geqslant 0,i=1,2.\}$ and The effective domain $Y_{6}^{*}=\{\left.{y^{*}=(\varepsilon^{*},q^{*})\in R\times R^{2}}\right|-% \frac{1}{2}+\varepsilon^{*}+2q^{*}$ is inversible, $\varepsilon^{*}>\frac{1}{2},q_{i}^{*}\geqslant 0,i=1,2.\}$ , the canonical dual function $P^{d}(y^{*})$ has no any roots in either $Y_{5}^{*}$ or $Y_{6}^{*}$ .

Since $\bar{{y}}_{1}^{*}=(\bar{{\varepsilon}}_{1}^{*},q_{1}^{*},q_{2}^{*})=(-7,\frac{% 3}{4},\frac{9}{4})$ , we know $\det F(\bar{{\varepsilon}}_{1}^{*},\bar{{q}}_{1}^{*},\bar{{q}}_{2}^{*})>0$ . by Theorem 2, we have that $y_{1}^{*}\in Y_{+}^{*}$ ,

$\displaystyle\bar{{x}}_{1}=F(\bar{{\varepsilon}}_{1}^{*},\bar{{q}}_{1}^{*})^{-% 1}G(\bar{{\varepsilon}}_{1}^{*})=\begin{bmatrix}{\displaystyle\frac{1+\bar{{% \varepsilon}}_{1}^{*}}{-\frac{1}{2}+\bar{{\varepsilon}}_{1}^{*}+2\bar{{q}}_{1}% ^{*}}}\\ \\ {\displaystyle\frac{1+\bar{{\varepsilon}}_{1}^{*}}{-\frac{1}{2}+\bar{{% \varepsilon}}_{1}^{*}+2\bar{{q}}_{1}^{*}}}\\ \end{bmatrix}=\begin{bmatrix}1\\ 2\\ \end{bmatrix}$

is a global minimizer of $P_{t}(x)$ and $P_{t}(\bar{{x}}_{1})=P^{d}(\bar{{y}}_{1}^{*}=(\bar{{\varepsilon}}_{1}^{*},\bar% {{q}}_{1}^{*},\bar{{q}}_{2}^{*}))=\frac{15}{8}=1.8750$ (see Fig. 2).

4. Conclusions

The canonical dual transformation can be used to easily obtain the complete solutions and global or local extreme of $P_{t}(x)$ by converting a high dimensional ( $n\geqslant 2$ ) box constrained nonconvex and non smoooth problem into a one-dimensional canonical dual problem. And we can check the fact that the canonical dual function $P^{d}(y^{*})$ is concave on the dual feasible space $Y_{+}^{*}$ , when $Y_{+}^{*}$ is non-empty, its dual problem $P^{d}$ has one KKT point in $Y_{+}^{*}$ at least. Thus, we can easily find all critical points and extremal by well-developed deterministic optimization methods.

Footnotes

Acknowledgments

The authors acknowledge the support from Natural Science Foundation of China under Grant No. 71671064 and Fundamental Research Funds for the Central Universities under Grant no. 2018ZD14 and no. 2016XS70.

References

Benjamin

and Sachin

, Reliable estimates of error in self-diffusivity from molecular simulations using statistical bootstrap, Journal of Computational Methods in Sciences and Engineering (2018), 1–19.

Falk

, Elastic phase transitions and nonconvex energy functions, Free Boundary Problem: Theory and Applications I (1990), 45–59.

Genetha Gray

Herbert Lee

K.H.

and Guenther

, Simultaneous optimization and uncertainty quantification, Journal of Computational Methods in Sciences and Engineering 12(12) (2012), 99–110.

Gao

D.Y.

, Solutions and optimality criteria to box constrained nonconvex minimization problems, Journal of Industrial and Management Optimization 3(2) (2017), 293–304.

Gao

D.Y.

Watson

Easterling

Thacker

and Billups

, Solving the canonical dual of box-and integer-constrained nonconvex quadratic programs via a deterministic direct search algorithm, Optimization Methods and Software 28(2) (2013), 313–326.

Gao

D.Y.

and Sherali

H.D.

, Canonical duality theory: Connection between nonconvex mechanics and global optimization, Advances in Mechanics and Mathematics III Springer (2006).

Gao

D.Y.

, Nonconvex semi-linear problems and canonical duality solutions, Advances in Mechanics and Mathematics II (2003), 261–312.

Gao

D.Y.

, Duality principles in nonconvex systems: Theory, methods and applications, Kluwer Academic Publishers, Dordrecht/Boston/London III (2000).

Gao

D.Y.

, Dual extremum principles in finite deformation theory with applications in post-buckling analysis of nonlinear beam model, Applied Mechanics Review, ASME 50 (1997), 64–71.

10.

Gao

D.Y.

and Strang

, Geometric nonlinearity: Potential energy, complementary energy, and the gap function, Quarterly of Applied Mathematics 47(3) (1989), 487–504.

11.

Liu

and Liu

, Canonical duality for box constrained nonconvex and nonsmooth optimization problems, Mathematical Problems in Engineering 3 (2015), 1–9.

12.

Liu

Gao

D.Y.

and Gao

, Canonical duality theory for solving nonconvex and nonsmooth optimization problem, Optim Eng 10 (2009), 153–165.

13.

Liu

Gao

D.Y.

and Gao

, Perfect duality theory and solutions to a class of unconstrained nonconvex and nonsmooth optimization, Optimization and Engineering 108(3) (2009), 158–167.

14.

Latorre

and Gao

D.Y.

, Canonical duality for solving general nonconvex constrained problems, Optimization Letters 10(8) (2016), 1763–1779.

15.

Ruan

Gao

D.Y.

and Gao

D.Y.

, Canonical duality approach for non-linear dynamical systems, Ima Journal of Applied Mathematics 79(2) (2014), 313–325.