# Optimization Condition and Algorithm of Optimization with Convertible
Nonconvex Function111This work was supported by the National Natural Science
Foundation of China (Grant No. 11871434).

Min Jiang  Rui Shen  Zhiqing Meng  Chuangyin Dang  School of Management,
Zhejiang University of Technology, Hangzhou, Zhejiang, 310023, China  School
of Economics, Zhejiang University of Technology, Hangzhou, Zhejiang, 310023,
China  Department of Advanced Design and System Engineering, City University
of Hong Kong, Kowloon, Hong Kong

(Jan. 9, 2022)

###### Abstract

The paper introduces several new concepts for solving nonconvex or nonsmooth
optimization problems, including convertible nonconvex function, exact
convertible nonconvex function and differentiable convertible nonconvex
function. It is proved herein many nonconvex functions or nonsmooth (or
discontinuous) functions are actually convertible nonconvex functions and
convertible nonconvex function operations such as addition, subtraction,
multiplication or division result in convertible nonconvex functions. The
sufficient condition for judging a global optimal solution to unconstrained
optimization problems with differentiable convertible nonconvex functions is
proved, which is equivalent to Karush-Kuhn-Tucker(KKT) condition. Two Lagrange
functions of differentiable convertible nonconvex function are defined with
their dual problems defined accordingly. The strong duality theorem is proved,
showing that the optimal objective value of the global optimal solution is
equal to the optimal objective value of the dual problem, which is equivalent
to KKT condition. An augmented Lagrangian penalty function algorithm is
proposed and its convergence is proved. So the paper provides a new idea for
solving unconstrained nonconvex or non-smooth optimization problems and avoids
subdifferentiation or smoothing techniques by using some gradient search
algorithms, such as gradient descent algorithm, Newton algorithm and so on.

###### keywords:

convertible nonconvex function, convertible nonconvex function optimization,
global optimal solution, sufficient condition, Lagrange dual, algorithm.

##  1 Introduction

The following optimization problem is defined by

(P1) $\displaystyle\min$ $\displaystyle f(\boldsymbol{x})$ $\displaystyle
s.t.$ $\displaystyle\boldsymbol{x}\in X\subset R^{n}.$

When $X=R^{n}$, (P1) is unconstrained optimization. When $f$ is a nonconvex
function, it is difficult to find a global optimal solution to (P1). In 1976,
McCormick presented a method to find a global optimal solution to (P1) when
$f$ is a factorable function, where (P1) is called factorable programming[22].
The main idea of factorable programming is that when a convergent sequence of
global solutions $\boldsymbol{x}^{k}$ to a sequence of convex underestimating
programming is obtained, $\boldsymbol{x}^{*}$ is a global optimal solution to
(P1) as $\boldsymbol{x}^{k}\to\boldsymbol{x}^{*}$, as shown in [3, 14, 22,
28]. Hence, Sherali and Wang(2001)[27], Tawarmalani and Sahinidis(2004)[30],
and Granvilliers(2020)[10] showed a branch and bound algorithm for solving a
global optimal solution to factorable programming. In 1988, Jackson and
Mccormick proved the results of second-order sensitivity analysis of
factorable programming guarantee the stability of the optimal solution to
factorable programming[19]. Then, factorable programming was applied in
encyclopedia of operations research and management science [20]. Furthermore,
Hascot et al.(2013)[13] proved that factorable programming is suitable for
designing an algorithm to solve large-scale optimization problems. All the
above shows that there are effective algorithms for solving a global solution
to factorable programming.

Hanson and Mond(1987)[11] pointed out that only the nonconvex optimization
with special structure can find a global optimal solution to (P1), i.e. when
$f$ is not convex but convex transformable (so (P1) is called convex
transformable programming). Since convex transformable programming is
converted into a relaxed convex optimization, Hirschberger(2005)[15], Neto et
al.(2006)[24], Andreas et al.(2009)[1], Khajavirad et al.(2014)[21] and Nohra
and Sahinidis(2018)[25] gave algorithms to solve a global solution. Grant et
al.(2006)[9] gave out methods to solve nonconvex optimization problems, and
Shen et al.(2017)[26] gave a multiconvex programming which is a nonconvex
optimization problem composed of multiconvex functions. In recent years, in
engineering, various practical models of multiconvex programming are studied
as shown in [4, 16, 18, 29]. But, to find a global optimal solution to
multiconvex programming is more difficult than to find one to other nonconvex
optimization problems.

In summary, some convex transformable functions are factorable as shown in
[21]. The above special nonconvex functions have some weaknesses. For example,
they require a complex technique to construct convex underestimating
programming of factor programming, which makes it difficult to construct its
global algorithm. Besides, Khajavirad et al pointed our that it is difficult
to judge whether a nonconvex function is convex transformable [21]. In
addition, the major obstacle is that the optimal condition of the global
optimal solution to nonconvex and nondifferentiable optimization problem (P1)
has not been found in theory.

On the other hand, subdifferential theory and smoothing techniques are widely
used to solve nonconvex and nondifferentiable optimization problem in [5, 6,
7, 17]. When $f$ in (P1) is nonconvex or nonsmooth, it is difficult to find
its a global solution under optimization condition or dual problem.

In this paper, if $f(\boldsymbol{x})$ is nonconvex, nonsmooth or discontinuous
on $\boldsymbol{x}\in R^{n}$, an idea of mapping $f$ from $R^{n}$ to a higher
dimensional space $R^{n}\times R^{m}$ such that
$f(\boldsymbol{x})=g(\boldsymbol{x},\boldsymbol{y})$ with
$(\boldsymbol{x},\boldsymbol{y})\in X(g)\subset R^{n}\times R^{m}$ in
Definition 2.1, where $g$ is a differentiable and convex, is proposed to solve
(P1). So,

$\min\limits_{\boldsymbol{x}\in
X}f(\boldsymbol{x})=\min\limits_{(\boldsymbol{x},\boldsymbol{y})\in
X(g)}g(\boldsymbol{x},\boldsymbol{y}).$

When $X(g)$ is expected to have a good structure, a global or local optimal
solution to $\min\limits_{(\boldsymbol{x},\boldsymbol{y})\in
X(g)}g(\boldsymbol{x},\boldsymbol{y})$ may be found. The paper applies this
idea and proves theoretically that the sufficient conditions and Lagrangian
dual theorem can be realized for solving a global or local optimal solution to
the unconstrained optimization (P1) to avoid using subdifferentiation or
smoothing techniques, which allows us to directly use some gradient search
algorithms, such as gradient descent algorithm, Newton algorithm and so on.

So, the main contributions include the three results as follows. (1) The
definition of convertible nonconvex function, exact convertible nonconvex
function and differentiable convertible nonconvex function, which covers a
large scale of nonconvex or discontinuous functions, such as convex
transformable functions, multiconvex functions, 0-norm functions, etc. (2) The
sufficient conditions and the duality theorem of a global optimal solution to
(P1) are proved in theory. However, it is impossible to obtain these results
if the convertible function form technology is not used. (3) An augmented
Lagrangian penalty function algorithm is designed to find an approximately
optimal solution to (P1) where some gradient search algorithms are directly
used.

The remainder of this paper is organized as follows. In Section 2, the
definition, some examples and some properties of (exact, differentiable)
convertible nonconvex function are given. In Section 3, unconstrained
optimization with a differentiable convertible nonconvex function is defined
and the sufficient conditions of its global optimal solution are proved. In
Section 4, the Lagrange function of a differentiable convertible nonconvex
function and dual problems of unconstrained optimization are defined. Their
dual properties are discussed. An augmented Lagrangian penalty function
algorithm and its convergence are given. In Section 5, a conclusion is given.

##  2 Convertible Nonconvex Function

Convertible nonconvex function, exact convertible nonconvex function and
differentiable convertible nonconvex function are defined first. Then examples
are given to show some nonconvex, nonsmooth or discontinuous functions are
differentiable exact convertible nonconvex ones.

###### Definition 1

Let $s+r+1$ functions: $g,g_{i},h_{j}:R^{n}\times R^{m}\to
R^{1}$($i=1,2,\cdots,s;j=1,2,\cdots,r$) be convex and $f:R^{n}\rightarrow R$
be nonconvex or nonsmooth. Let a set

$\displaystyle
X(f)=\\{(\boldsymbol{x},\boldsymbol{y})|g_{i}(\boldsymbol{x},\boldsymbol{y})\leq
0,i=1,2,\cdots,s;h_{j}(\boldsymbol{x},\boldsymbol{y})=0,j=1,2,\cdots,r\\}$ (1)

For a fixed $\boldsymbol{x}$, let

$\displaystyle X(f(\boldsymbol{x}))=\\{\boldsymbol{y}\in
R^{m}|(\boldsymbol{x},\boldsymbol{y})\in X(f)\\}$ (2)

and

$\displaystyle X(g)=\\{(\boldsymbol{x},\boldsymbol{y})\in
X(f)|g(\boldsymbol{x},\boldsymbol{y})=f(\boldsymbol{x})\\}.$ (3)

$\bullet$ If for each $(\boldsymbol{x},f(\boldsymbol{x}))$ there is a
$\bar{\boldsymbol{y}}\in X(f(\boldsymbol{x}))$ such that
$f(\boldsymbol{x})=g(\boldsymbol{x},\bar{\boldsymbol{y}})$ and

$\displaystyle f(\boldsymbol{x})=\min\limits_{\boldsymbol{y}\in
X(f(\boldsymbol{x}))}g(\boldsymbol{x},\boldsymbol{y}),$

then $f$ is called a convertible nonconvex function.
$[g:g_{1},g_{2},\cdots,g_{s};h_{1},h_{2},\cdots,h_{r}]$ is convertible
nonconvex form of $f$, briefing as
$f=[g:g_{1},g_{2},\cdots,g_{s};h_{1},h_{2},\cdots,h_{r}]$. Moreover, the
following concepts are defined.

$\bullet$ If $f$ is continuous on $R^{n}$ and
$g,g_{1},g_{2},\cdots,g_{s},h_{1},h_{2},\cdots,h_{r}$ are continuous on
$R^{n}\times R^{m}$, $f$ is called strong continuous convertible nonconvex
function.

$\bullet$ If $s+r+1$ functions:
$g,g_{i},h_{j}$($i=1,2,\cdots,s;j=1,2,\cdots,r;s>0$) are differentiable, $f$
is called a differentiable convertible nonconvex function.

$\bullet$ If $f$ is a differentiable convertible nonconvex function and
$f(\cdot)$ is a differentiable function on $R^{n}$, $f$ is a strong
differentiable convertible nonconvex function.

$\bullet$ If $g(\boldsymbol{x},\boldsymbol{y})=f(\boldsymbol{x})$ for any
$(\boldsymbol{x},\boldsymbol{y})\in X(f)$, then $f$ is called an exact
convertible nonconvex function and $(\boldsymbol{x},\boldsymbol{y})$ is called
a mappable point of $f$.

Remark  The definition of convertible nonconvex function differs form that of
upper(lower)-$C^{k}$ function [8], where the upper(lower)-$C^{k}$ function is
continuous. For example, 0-norm $\|\boldsymbol{x}\|_{0}$ is not upper-$C^{k}$
function [8], because it is not continuous. But, $\|\boldsymbol{x}\|_{0}$ is a
convertible nonconvex function in Example 4.

In this paper, we always assume that $f$ is a convertible nonconvex function.
If $s=0$, inequality does not exist in the convertible nonconvex form of $f$.
If $f$ is an exact convertible nonconvex function, $X(f)=X(g)$.

Some examples of convertible nonconvex functions are given as follows.

Example 1 Two convertible nonconvex forms of
$f(x_{1},x_{2})=|x_{1}x_{2}|^{\frac{1}{3}}+x_{1}^{2}+x_{2}^{2}$ are defined by

$\displaystyle
f=[g:g_{1};h_{1},h_{2},h_{3},h_{4}]=[y_{4}+x_{1}^{2}+x_{2}^{2}:-y_{4};0.5(x_{1}+x_{2})^{2}-y_{1}-0.5y_{2},$
$\displaystyle x_{1}^{2}+x_{2}^{2}-y_{2},y_{1}^{2}-y_{3},y_{4}^{6}-y_{3}]$

and

$\displaystyle
f=[g:g_{1};h_{1},h_{2},h_{3},h_{4}]=[y_{4}+x_{1}^{2}+x_{2}^{2}:-y_{4};0.25(x_{1}+x_{2})^{2}-y_{1}-0.25y_{2},$
$\displaystyle(x_{1}-x_{2})^{2}-y_{2},y_{1}^{2}-y_{3},y_{4}^{6}-y_{3}]$

respectively. Then, $f=[g:g_{1};h_{1},h_{2},h_{3},h_{4}]$ is differentiable
exact convertible nonconvex. And, the convertible nonconvex form of $f$ is not
only one. $f$ is noncovex and nonsmooth.

Example 2 Let $\boldsymbol{b}_{1},\boldsymbol{b}_{2}\in R^{n}$ be given. A
convertible nonconvex forms of
$f(\boldsymbol{x})=(\sqrt{|\boldsymbol{b}_{1}^{\top}\boldsymbol{x})|}-\sqrt{|\boldsymbol{b}_{2}^{\top}\boldsymbol{x}|})^{2}$
is defined by

$\displaystyle
f=[g:g_{1},g_{2};h_{1},h_{2},h_{3},h_{4}]=(y_{1}-y_{2})^{2}:-y_{1},-y_{2};y_{1}^{2}-y_{3},y_{2}^{2}-y_{4},$
$\displaystyle(\boldsymbol{b}_{1}^{\top}\boldsymbol{x})^{2}-y_{3},(\boldsymbol{b}_{2}^{\top}\boldsymbol{x})^{2}-y_{4}].$

$f$ is differentiable exact convertible nonconvex.

Example 3 Let multi-classification function
$f(\boldsymbol{x})=\sum\limits_{i=1}^{I}(|\boldsymbol{a}_{i}^{\top}\boldsymbol{x}|-b_{i})^{2}$
be nonsmooth and nonconvex in [23], where sample data
$(\boldsymbol{a}_{i},b_{i})\in R^{n}\times R^{1}(i=1,2,\cdots,I)$ are given.
Let

$\displaystyle f(\boldsymbol{x})=g(\boldsymbol{x},\boldsymbol{y})$
$\displaystyle=$ $\displaystyle\sum\limits_{i=1}^{I}(y_{i}-b_{i})^{2}:$
$\displaystyle g_{i}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$
$\displaystyle-y_{i}\leq 0,\ i=1,2,\cdots,I;$ $\displaystyle
h_{i}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$ $\displaystyle
y_{i}^{2}-y_{i+I}=0,\ i=1,2,\cdots,I,$ $\displaystyle
h_{i+I}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$
$\displaystyle(\boldsymbol{a}_{i}^{\top}\boldsymbol{x})^{2}-y_{i+I}=0,\
i=1,2,\cdots,I,$

where $\boldsymbol{y}\in R^{2I}$.
$f=[g:g_{1},\cdots,g_{I};h_{1},\cdots,h_{2I}]$ is twice differentiable exact
convertible nonconvex.

We have the following properties.

###### Proposition 1

If $f,f_{1},f_{2}:R^{n}\to R^{1}$ are convertible nonconvex, then the
following conclusions hold,

(i) $\alpha f_{1}$ is convertible nonconvex, where $\alpha\not=0$.

(ii) $\alpha_{1}f_{1}+\alpha_{2}f_{2}$ is convertible nonconvex, where
$\alpha_{1},\alpha_{2}\not=0$.

(iii) $f_{1}f_{2}$ is convertible nonconvex.

(iv) $\phi(f)$ is convertible nonconvex, where $\phi:R^{1}\to R^{1}$ is a
monotone increasing convex function.

(v) $\max\\{f_{1},f_{2}\\}$ is convertible nonconvex.

(vi) $\frac{f_{1}}{f_{2}}$ is convertible nonconvex.

(vii) $-log(f_{1})$ is convertible nonconvex.

(viii) $exp(af_{1})$ is convertible nonconvex, where $a>1$.

By Proposition 1, all polynomial functions are convertible nonconvex. By
Proposition 1, G-convex functions in Example 1-7 in [21] are convertible
nonconvex. Some multi-convex functions are convertible nonconvex, such as
$f(\boldsymbol{x})=x_{1}x_{2}\cdots x_{n}$. Therefore, convertible nonconvex
functions include a wide range of non-convex functions. By Proposition 2.1,
the following corollaries hold.

###### Corollary 1

If $f,f_{1},f_{2}:R^{n}\to R$ are exact convertible nonconvex, then the
results of all operations in Proposition 2.1 are exact convertible nonconvex.

In the following example, the nonsmooth, nonconvex and discontinuous function
is a differentiable convertible nonconvex function.

Example 4 Let 0-norm function
$f(\boldsymbol{x})=\lambda\|\boldsymbol{x}\|_{0}+b(\boldsymbol{x})$ in machine
learning be nonsmooth nonconvex and discontinuous in [5, 6], where $b:R^{n}\to
R^{1}$ is convex. There are $\boldsymbol{y}\in R^{2n}$ such that

$\displaystyle f(\boldsymbol{x})=g(\boldsymbol{x},\boldsymbol{y})$
$\displaystyle=$
$\displaystyle\lambda\sum\limits_{i=1}^{n}y_{i}+b(\boldsymbol{x}):$
$\displaystyle g_{i}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$
$\displaystyle-y_{i}\leq 0,i=1,2,\cdots,n,$ $\displaystyle
g_{i+n}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$ $\displaystyle
y_{i}\leq 1,i=1,2,\cdots,n;$ $\displaystyle
h_{j}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$
$\displaystyle(x_{i}+y_{i}-1)^{2}-y_{i+n}=0,i=1,2,\cdots,n,$ $\displaystyle
h_{i+n}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$ $\displaystyle
x_{i}^{2}+(y_{i}-1)^{2}-y_{i+n}=0,i=1,2,\cdots,n,$ $\displaystyle
h_{i+2n}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$ $\displaystyle
y_{i}^{2}-y_{i}=0,i=1,2,\cdots,n.$

So, $f$ is twice differentiable convertible nonconvex. But, $f$ is not exact
convertible nonconvex.

The above examples tell us that some nonsmooth, nonconvex or discontinuous
functions may be twice differentiable convertible nonconvex functions such
that many of nonsmooth ,nonconvex optimization problems can be converted to
differentiable convertible nonconvex optimization problems. Hence, it is very
meaningful to study differentiable convertible nonconvex optimization
problems.

##  3 Unconstrained Optimization with Convertible Nonconvex Function

In this section, it is always assumed that $f$ is a differentiable convertible
nonconvex function with
$f=[g:g_{1},g_{2},\cdots;g_{s},h_{1},h_{2},\cdots,h_{r}]$. But,
$f(\boldsymbol{x})$ is not necessarily differentiable or convex.

The following unconstrained optimization problem is considered:

(UOP) $\displaystyle\min\;$ $\displaystyle f(\boldsymbol{x})$ s.t.
$\displaystyle\boldsymbol{x}\in R^{n},$

where $f:R^{n}\rightarrow R$ is differentiable convertible nonconvex. The
constrained optimization problem of (CNP) is defined by

(CNP) $\displaystyle\min\;$ $\displaystyle g(\boldsymbol{x},\boldsymbol{y})$
s.t. $\displaystyle g_{i}(\boldsymbol{x},\boldsymbol{y})\leq
0,i=1,2,\cdots,s,$ $\displaystyle
h_{j}(\boldsymbol{x},\boldsymbol{y})=0,j=1,2,\cdots,r,$
$\displaystyle\boldsymbol{x}\in R^{n},\boldsymbol{y}\in R^{m}.$

(UOP) or (CNP) is called convertible nonconvex programming. Since
$f:R^{n}\rightarrow R$ is convertible nonconvex, it is clear

$\min\limits_{\boldsymbol{x}\in R^{n}}\
f(\boldsymbol{x})=\min\limits_{(\boldsymbol{x},\boldsymbol{y})\in X(f)}\
g(\boldsymbol{x},\boldsymbol{y})=\min\limits_{(\boldsymbol{x},\boldsymbol{y})\in
X(g)}\ g(\boldsymbol{x},\boldsymbol{y}).$

When $r=0$ or all $h_{j}(\boldsymbol{x},\boldsymbol{y})=0(j=1,2,\cdots,r)$ are
linear, (CNP) is a convex programming.

Let $\boldsymbol{d}=(\boldsymbol{d}_{1},\boldsymbol{d}_{2})\in R^{n}\times
R^{m}$. The linear programming of (CNP) at a fixed
$(\boldsymbol{x},\boldsymbol{y})$ is defined by

$\displaystyle\mbox{(CNP)}(\boldsymbol{x},\boldsymbol{y})\qquad$
$\displaystyle\min\;$ $\displaystyle\nabla
g(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}$ s.t. $\displaystyle
g_{i}(\boldsymbol{x},\boldsymbol{y})+\nabla
g_{i}(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}\leq
0,i=1,2,\cdots,s,$ $\displaystyle\nabla
h_{j}(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}\leq
0,j=1,2,\cdots,r,$ $\displaystyle\boldsymbol{d}\in R^{n}\times R^{m}.$

Let set $I=\\{1,2,\cdots,s\\}$, $J=\\{1,2,\cdots,r\\}$ and vector functions

$\displaystyle\boldsymbol{g}(\boldsymbol{x},\boldsymbol{y})=(g_{1}(\boldsymbol{x},\boldsymbol{y}),g_{2}(\boldsymbol{x},\boldsymbol{y}),\cdots,g_{s}(\boldsymbol{x},\boldsymbol{y}))^{\top}$

and

$\displaystyle\boldsymbol{h}(\boldsymbol{x},\boldsymbol{y})=(h_{1}(\boldsymbol{x},\boldsymbol{y}),h_{2}(\boldsymbol{x},\boldsymbol{y}),\cdots,h_{r}(\boldsymbol{x},\boldsymbol{y}))^{\top}.$

When $f(\boldsymbol{x})$ is differentiable on $\boldsymbol{x}\in R^{n}$, it is
easy to determine that $\boldsymbol{x}$ is not the optimal solution to (UOP)
when $\nabla f(\boldsymbol{x})\not=0$. However, it is very difficult to judge
the global optimal solution to (UOP). How to judge the global optimal solution
of (CNP) is proved in the following.

###### Theorem 1

Suppose that $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$. If there is an
optimal solution $\boldsymbol{d}^{*}$ to
(CNP)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ such that $\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}^{*}\geq 0$, then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to (CNP),
$\boldsymbol{x}^{*}$ is an optimal solution to (UOP) and there are
$\boldsymbol{u}^{*}=(u_{1}^{*},u_{2}^{*},\cdots,u_{s}^{*})^{\top}\geq 0$ and
$\boldsymbol{v}^{*}=(v_{1}^{*},v_{2}^{*},\cdots,v_{r}^{*})^{\top}\geq 0$ such
that

$\displaystyle\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\nabla\boldsymbol{g}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{u}^{*}+\nabla\boldsymbol{h}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{v}^{*}=0.$
(4) $\displaystyle
u^{*}_{i}g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}=0,i=1,2,\cdots,s.$
(5)

Proof. For any $(\boldsymbol{x},\boldsymbol{y})\in X(g)$, we have

$\displaystyle
g(\boldsymbol{x},\boldsymbol{y})-g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\geq\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})],$
$\displaystyle 0\geq g_{i}(\boldsymbol{x},\boldsymbol{y})\geq
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\nabla
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})],\
i=1,2,\cdots,s,$ $\displaystyle
0=h_{j}(\boldsymbol{x},\boldsymbol{y})-h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\geq\nabla
h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})],\
j=1,2,\cdots,r.$

So, $(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$
is a feasible solution to (CNP)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$, then

$\displaystyle f(\boldsymbol{x})-f(\boldsymbol{x}^{*})$ $\displaystyle=$
$\displaystyle
g(\boldsymbol{x},\boldsymbol{y})-g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$
$\displaystyle\geq$ $\displaystyle\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]$
$\displaystyle\geq$ $\displaystyle\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}^{*}\geq 0.$

Hence, $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to
(CNP) and $\boldsymbol{x}^{*}$ is an optimal solution to (UOP). Because
(CNP)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is linear programming, it is
rewritten as

$\displaystyle\mbox{(CNP)}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\qquad$
$\displaystyle\max\;$ $\displaystyle-\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}$ s.t.
$\displaystyle\nabla
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}\leq-
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*}),\ i=1,2,\cdots,s,$
$\displaystyle\nabla
h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}\leq
0,j=1,2,\cdots,r,$ $\displaystyle\boldsymbol{d}\in R^{n}\times R^{m}.$

So, the dual problem (DTCP)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ of
(CNP)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is defined as follows.

$\displaystyle\mbox{(DTCP)}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\qquad$
$\displaystyle\min\;$
$\displaystyle-\sum\limits_{i=1}^{s}u_{i}g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\sum\limits_{j=1}^{s}0\cdot
v_{j}$ s.t. $\displaystyle\sum\limits_{i=1}^{s}u_{i}\nabla
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\sum\limits_{j=1}^{r}v_{i}\nabla
h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=-\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ $\displaystyle u_{i},v_{j}\geq
0,i=1,2,\cdots,s,j=1,2,\cdots,r;$

where $(u_{1},u_{2},\cdots,u_{s})$ and $(v_{1},v_{2},\cdots,v_{r})$ are dual
variables. By the strong dual theorem of linear programming, there is an
optimal solution
$\boldsymbol{u}^{*}=(u_{1}^{*},u_{2}^{*},\cdots,u_{r}^{*})^{\top}\geq 0$ and
$\boldsymbol{v}^{*}=(v_{1}^{*},v_{2}^{*},\cdots,v_{r}^{*})^{\top}\geq 0$ to
$\mbox{(DTCP)}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ such that

$0\leq-\sum\limits_{i=1}^{s}u_{i}^{*}g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=-\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}^{*}\leq 0.$

Hence, (4) and (5) are true.

So, (4) and (5) are a KKT condition of (CNP) of (UOP). Theorem 1 means that
there is optimization condition of (UOP) if $f$ is not differentiable.
Usually, if $f$ has subdifferentiation at optimal point $\boldsymbol{x}^{*}$,
there may be an optimality condition $0\in\partial f(\boldsymbol{x}^{*})$ in
[7]. By Theorem 1, the following corollary is true.

###### Corollary 2

Suppose that $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$. Let the
problem $\mbox{(CNPP)}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$

$\displaystyle\min\;$ $\displaystyle\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]$
s.t. $\displaystyle g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\nabla
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]\leq
0,\ i=1,2,\cdots,s,$ $\displaystyle\nabla
h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]\leq
0,j=1,2,\cdots,r,$ $\displaystyle(\boldsymbol{x},\boldsymbol{y})\in X(g).$

If $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to
(CNPP)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$, then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to (CNP) and
$\boldsymbol{x}^{*}$ is an optimal solution to (UOP), i.e. if
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is not an optimal solution to (CNP),
then there is an $(\boldsymbol{x},\boldsymbol{y})\in X(g)$ such that $\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]<0$.

Because (CNPP)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is not linear
programming, it is difficult to solve it. The inverse proposition of Theorem 1
holds as follows.

###### Theorem 2

Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$. If there are
$\boldsymbol{u}^{*}=(u_{1}^{*},u_{2}^{*},\cdots,u_{r}^{*})^{\top}\geq 0$ and
$\boldsymbol{v}^{*}=(v_{1}^{*},v_{2}^{*},\cdots,v_{r}^{*})^{\top}\geq 0$ such
that (4) and (5) hold, then $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an
optimal solution to (CNP) and $\boldsymbol{x}^{*}$ is an optimal solution to
(UOP).

The following conclusion is clear.

###### Theorem 3

Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$. If $\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=0$, then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to (CNP) and
$\boldsymbol{x}^{*}$ is an optimal solution to (UOP).

If the condition of Theorem 1 or Theorem 2 does not hold, the global optimal
solution to (CNP) is judged by solving linear programming
(CNP0)$(\boldsymbol{x},\boldsymbol{y})$.

The linear programming (CNP0)$(\boldsymbol{x},\boldsymbol{y})$ of (CNP) at a
fixed $(\boldsymbol{x},\boldsymbol{y})$ is defined as follows.

$\displaystyle\mbox{(CNP0)}(\boldsymbol{x},\boldsymbol{y})\qquad$
$\displaystyle\min\;$ $\displaystyle\nabla
g(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}$ s.t. $\displaystyle
g_{i}(\boldsymbol{x},\boldsymbol{y})+\nabla
g_{i}(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}\leq
0,i=1,2,\cdots,s,$ $\displaystyle\nabla
h_{j}(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}=0,j=1,2,\cdots,r,$
$\displaystyle\boldsymbol{d}\in R^{n}\times R^{m}.$

Let two directional sets at a fixed $(\boldsymbol{x},\boldsymbol{y})$ be
defined respectively by

$\displaystyle T(\boldsymbol{x},\boldsymbol{y})=\\{\boldsymbol{d}\in
R^{n}\times R^{m}$ $\displaystyle|$ $\displaystyle
g_{i}(\boldsymbol{x},\boldsymbol{y})+\nabla
g_{i}(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}\leq
0,i=1,2,\cdots,s,$ (6) $\displaystyle\nabla
h_{j}(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}\leq
0,j=1,2,\cdots,r\\}$

and

$\displaystyle T_{0}(\boldsymbol{x},\boldsymbol{y})=\\{\boldsymbol{d}\in
R^{n}\times R^{m}$ $\displaystyle|$ $\displaystyle
g_{i}(\boldsymbol{x},\boldsymbol{y})+\nabla
g_{i}(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}\leq
0,i=1,2,\cdots,s,$ (7) $\displaystyle\nabla
h_{j}(\boldsymbol{x},\boldsymbol{y})^{\top}\boldsymbol{d}=0,j=1,2,\cdots,r\\}.$

It is clear that $T_{0}(\boldsymbol{x},\boldsymbol{y})\subset
T(\boldsymbol{x},\boldsymbol{y})$. For
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$, we have
$X(g)\subset[T(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+(\boldsymbol{x}^{*},\boldsymbol{y}^{*})].$

Let a set at a fixed $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ be defined by

$\displaystyle
K_{g}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\\{(\boldsymbol{x},\boldsymbol{y})\in
R^{n}\times R^{m}$ $\displaystyle|$ $\displaystyle\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]<0\\}.$

We have the following Lemmas.

###### Lemma 1

Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$. If

$\displaystyle X(f)\cap
K_{g}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\emptyset$ (8)

holds, then $g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\leq
g(\boldsymbol{x},\boldsymbol{y})$ for all $(\boldsymbol{x},\boldsymbol{y})\in
X(g)$, i.e. $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution
to (CNP) and $\boldsymbol{x}^{*}$ is an optimal solution to (UOP)

###### Lemma 2

Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$. If

$\displaystyle X(f)\cap
K_{g}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\cap[T(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\backslash
T_{0}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]=\emptyset$
(9)

holds, then $g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\leq
g(\boldsymbol{x},\boldsymbol{y})$ for all $(\boldsymbol{x},\boldsymbol{y})\in
X(g)\cap[T(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\backslash
T_{0}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]$.

###### Theorem 4

Suppose

$\displaystyle[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})]\in
T_{0}(\boldsymbol{x}^{*},\boldsymbol{y}^{*}),\forall(\boldsymbol{x},\boldsymbol{y})\in
X(g)$ (10)

or (9) holds for $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$. If there
is an optimal solution $\boldsymbol{d}^{*}$ to
(CNP0)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ such that $\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}^{*}\geq 0$, then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to (CNP) and
$\boldsymbol{x}^{*}$ is an optimal solution to (UOP) and there are
$\boldsymbol{u}^{*}=(u_{1}^{*},u_{2}^{*},\cdots,u_{s}^{*})^{\top}\geq 0$ and
$\boldsymbol{v}^{*}=(v_{1}^{*},v_{2}^{*},\cdots,v_{r}^{*})^{\top}\in R^{r}$
such that

$\displaystyle\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\nabla\boldsymbol{g}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{u}^{*}+\nabla\boldsymbol{h}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{v}^{*}=0.$
(11) $\displaystyle
u^{*}_{i}g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}=0,i=1,2,\cdots,s.$
(12)

Proof. The proof process is similar to the proof of theorem 7.

###### Theorem 5

Suppose (9) or (10) holds for $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in
X(g)$. If there are
$\boldsymbol{u}^{*}=(u_{1}^{*},u_{2}^{*},\cdots,u_{s}^{*})^{\top}\geq 0$ and
$\boldsymbol{v}^{*}=(v_{1}^{*},v_{2}^{*},\cdots,v_{r}^{*})^{\top}\in R^{r}$
such that (11) and (12) hold, then $\boldsymbol{x}^{*}$ is an optimal solution
to (UOP).

Proof. Because for
$\boldsymbol{u}^{*}=(u_{1}^{*},u_{2}^{*},\cdots,u_{s}^{*})^{\top}\geq 0$ and
$\boldsymbol{v}^{*}=(v_{1}^{*},v_{2}^{*},\cdots,v_{r}^{*})^{\top}\in R^{r}$
(11)) and (12)) hold, $\boldsymbol{u}^{*}$, $\boldsymbol{v}^{*}$ is a feasible
solution to linear programming
(DTCP0)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$. It is clear that
$\boldsymbol{d}=0$ is a feasible solution to linear programming
(CNP0)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$. By the strong dual theorem,
there is an optimal solution $\boldsymbol{d}^{*}$ to
(CNP0)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ such that $\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}^{*}\geq 0$,
(11)) and (12)) hold. Hence, by Theorem 4, $\boldsymbol{x}^{*}$ is an optimal
solution to (UOP).

The following theorem is concluded by combining Theorem 4 and Theorem 5.

###### Theorem 6

Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$. Then there is an
optimal solution $\boldsymbol{d}^{*}$ to
(CNP0)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ such that $\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}^{*}\geq 0$ if
and only if there are
$\boldsymbol{u}^{*}=(u_{1}^{*},u_{2}^{*},\cdots,u_{s}^{*})^{\top}\geq 0$ and
$\boldsymbol{v}^{*}=(v_{1}^{*},v_{2}^{*},\cdots,v_{r}^{*})^{\top}\in R^{r}$
such that (11)) and (12)) hold.

Theorem 6 means that $\boldsymbol{x}^{*}$ doesn’t have to be an optimal
solution to (UOP) if there is an optimal solution $\boldsymbol{d}^{*}$ to
(CNP0)$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ such that $\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{d}^{*}\geq 0$ for
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$.

Example 5 Consider a nonconvex and non-Lipschitz optimization problem:

(EX5) $\displaystyle\min$ $\displaystyle\
f(x)=|x_{1}x_{2}|^{\frac{1}{3}}+x_{1}^{2}+x_{2}^{2}$ $\displaystyle s.t.$
$\displaystyle(x_{1},x_{2})\in R^{2}.$

A form of convertible nonconvex optimization of (EX5) is defined by

(MEX5-1) $\displaystyle\min$ $\displaystyle\
g(x_{1},x_{2},y_{1},y_{2},y_{3},y_{4})=y_{4}+x_{1}^{2}+x_{2}^{2},$
$\displaystyle s.t.$ $\displaystyle
g_{1}(x_{1},x_{2},y_{1},y_{2},y_{3},y_{4})=-y_{4}\leq 0,$ $\displaystyle
h_{1}(x_{1},x_{2},y_{1},y_{2},y_{3},y_{4})=0.5(x_{1}+x_{2})^{2}-y_{1}-0.5y_{2}=0,$
$\displaystyle
h_{2}(x_{1},x_{2},y_{1},y_{2},y_{3},y_{4})=x_{1}^{2}+x_{2}^{2}-y_{2}=0,$
$\displaystyle h_{3}(x_{1},x_{2},y_{1},y_{2},y_{3},y_{4})=y_{1}^{2}-y_{3}=0,$
$\displaystyle h_{4}(x_{1},x_{2},y_{1},y_{2},y_{3},y_{4})=y_{4}^{6}-y_{3}=0.$

It is clear that
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=(x_{1}^{*},x_{2}^{*},y_{1}^{*},y_{2}^{*},y_{3}^{*},y_{4}^{*})=(0,0,0,0,0,0)\in
X(g)$. Let $\boldsymbol{d}=(d_{1},d_{2},d_{3},d_{4},d_{5},d_{6})^{\top}$
correspond to $(x_{1},x_{2},y_{1},y_{2},y_{3},y_{4})$. We have

$\displaystyle\mbox{(MEX5-1)}(0,0,0,0,0,0)\qquad$ $\displaystyle\min\;$
$\displaystyle\nabla g(0,0,0,0,0,0)^{\top}\boldsymbol{d}=d_{6}\geq 0$ s.t.
$\displaystyle-d_{6}\leq 0,-d_{3}-0.5d_{4}\leq 0,-d_{4}\leq 0,-d_{5}\leq
0,-d_{5}\leq 0,$ $\displaystyle d_{1},d_{2},d_{3},d_{4},d_{5},d_{6}\in R.$

By Theorem 1, $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=(0,0,0,0,0,0)$ is an
optimal solution to (MEX5-1) and

$\displaystyle\nabla g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+u_{1}\nabla
g_{1}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+v_{1}\nabla
h_{1}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+v_{2}\nabla
h_{2}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ $\displaystyle+v_{3}\nabla
h_{3}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+v_{4}\nabla
h_{4}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=0,$

where $u_{1}=1,(v_{1},v_{2},v_{3},v_{4})=(0,0,0,0)$.

Example 5 shows that the convertible nonconvex optimization may obtain an
optimal solution to (UOP) via the convertible nonconvex forms of $f$ if $f$ is
a nonconvex and nonsmooth. If $\min f(\boldsymbol{x})$ is noncovex and
nonsmooth optimization, it is necessary to define the subgradient of $f$ in
[17] such that optimization condition and dual may be obtained. Especially,
smoothing function $f$ is necessary if its algorithm is designed. In next
section, we discuss that Lagrange dual and algorithm of (CNP) to avoid using
smoothing techniques and sub gradients.

##  4 Lagrange Dual and Algorithm of (CNP)

It is well known that Lagrange duality can be used to solve optimization
problems. Especially, there is a zero gap between the optimal objective value
of the Lagrangian dual problem of the convex optimization problem and the
optimal objective value of the original problem under some constraint
qualifications, which is a very important advantage in using the dual problem
of convex optimization to get the global optimal solution. In this section, we
will establish the Lagrangian duality of (CNP) and its algorithm.

Let $R^{s}_{+}=\\{\boldsymbol{u}\in R^{s}|\boldsymbol{u}\geq 0\\}$ and
$R^{r}_{+}=\\{\boldsymbol{v}\in R^{r}|\boldsymbol{v}\geq 0\\}$. For any
$(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times R^{m},\boldsymbol{u}\in
R^{s}_{+},\boldsymbol{v}\in R^{r}$, a Lagrange function of (CNP) is defined by

$\displaystyle
L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})=g(\boldsymbol{x},\boldsymbol{y})+\boldsymbol{u}^{\top}\boldsymbol{g}(\boldsymbol{x},\boldsymbol{y})+\boldsymbol{v}^{\top}\boldsymbol{h}(\boldsymbol{x},\boldsymbol{y}).$
(13)

Let a dual function of
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$ on
$(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}$ be defined by

$\displaystyle\theta(\boldsymbol{u},\boldsymbol{v})=\min\\{L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})|(\boldsymbol{x},\boldsymbol{y})\in
R^{n}\times R^{m}\\}.$ (14)

For any $(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times
R^{m},(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}_{+}$, a
Lagrange function of (CNP) is defined by

$\displaystyle
L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})=g(\boldsymbol{x},\boldsymbol{y})+\boldsymbol{u}^{\top}\boldsymbol{g}(\boldsymbol{x},\boldsymbol{y})+\boldsymbol{v}^{\top}\boldsymbol{h}(\boldsymbol{x},\boldsymbol{y}).$
(15)

Let a dual function of
$L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$ on
$(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}_{+}$ be defined by

$\displaystyle\theta_{+}(\boldsymbol{u},\boldsymbol{v})=\min\\{L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})|(\boldsymbol{x},\boldsymbol{y})\in
R^{n}\times R^{m}\\}.$ (16)

Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in R^{n}\times R^{m}$ and
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$ be given.
For all $(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times R^{m}$ and
$(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}$, if

$\displaystyle
L(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u},\boldsymbol{v})\leq
L(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})\leq
L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*}),$ (17)

then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
is called a saddle point of
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$.

Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in R^{n}\times R^{m}$ and
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}_{+}$ be
given. For all $(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times R^{m}$ and
$(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}_{+}$, if

$\displaystyle
L_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u},\boldsymbol{v})\leq
L_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})\leq
L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*}),$
(18)

then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
is called a saddle point of
$L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$.

The following conclusions are clear.

###### Proposition 2

If $(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}_{+}$, then
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})=L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$
and
$\theta(\boldsymbol{u},\boldsymbol{v})=\theta_{+}(\boldsymbol{u},\boldsymbol{v})$.

###### Proposition 3

If
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
is a saddle point of
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$ with
$R^{s}_{+}\times R^{r}_{+}$, then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
is a saddle point of
$L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$.

A dual optimization problem of (CNP) is defined by

(DCNP) $\displaystyle\max\ \theta(\boldsymbol{u},\boldsymbol{v})$
$\displaystyle\ s.t.\ (\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times
R^{r}.$

It is clear that $\theta(\boldsymbol{u},\boldsymbol{v})$ is a concave function
on $(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}$.

A dual optimization problem of (CNP) is defined by

(PDCNP) $\displaystyle\max\ \theta_{+}(\boldsymbol{u},\boldsymbol{v})$
$\displaystyle\ s.t.\ (\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times
R^{r}_{+}.$

It is clear that $\theta_{+}(\boldsymbol{u},\boldsymbol{v})$ is a concave
function on $R^{s}_{+}\times R^{r}_{+}$. By (13),(14),(15) and (16), the
following weak duality is clear.

###### Proposition 4

(i) For all $(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times R^{m}$ and
$(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}$,
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})\geq\theta(\boldsymbol{u},\boldsymbol{v})$.

(ii) For all $(\boldsymbol{x},\boldsymbol{y})\in X(g)$ and
$(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}$,
$g(\boldsymbol{x},\boldsymbol{y})\geq\theta(\boldsymbol{u},\boldsymbol{v})$.

(iii) For all $(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times R^{m}$ and
$(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}_{+}$,
$L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})\geq\theta_{+}(\boldsymbol{u},\boldsymbol{v})$.

(iv) For all $(\boldsymbol{x},\boldsymbol{y})\in X(g)$ and
$(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}_{+}$,
$g(\boldsymbol{x},\boldsymbol{y})\geq\theta_{+}(\boldsymbol{u},\boldsymbol{v})$.

The strong duality theorem is true as follows.

###### Theorem 7

(i) If
$L(\boldsymbol{x}^{*},\boldsymbol{y}^{*},\boldsymbol{u}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
at $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in R^{n}\times R^{m}$ and
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$, then

$\displaystyle\nabla
L(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})=\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\nabla\boldsymbol{g}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{u}^{*}+\nabla\boldsymbol{h}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{v}^{*}=0.$
(19)

(ii) If
$g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
at $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(g)$ and
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$, then (19)
and

$\displaystyle
u_{i}^{*}g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=0,i=1,2,\cdots,s$ (20)

hold, $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to
(CNP) and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$ is an optimal solution to
(DCNP).

(iii) Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in R^{n}\times R^{m}$ and
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}_{+}$. Then

$\displaystyle\nabla
L_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})=\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\nabla\boldsymbol{g}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{u}^{*}+\nabla\boldsymbol{h}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})^{\top}\boldsymbol{v}^{*}=0$
(21)

holds if and only if
$L_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*},\boldsymbol{u}^{*},\boldsymbol{v}^{*})=\theta_{+}(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.

(iv) Let $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(f)$ and
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}_{+}$. Then
(21) and

$\displaystyle
u_{i}^{*}g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=0,i=1,2,\cdots,s$ (22)

hold if and only if
$g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\theta_{+}(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.
Furthermore, $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution
to (CNP) and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$ is an optimal solution
to (PDCNP).

By Theorem 7, there is a zero gap between the optimal objective value of the
Lagrangian dual problem of (CNP) and the optimal objective value of the
original problem (CNP). But, if a Lagrange function
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$ is
convex on $(\boldsymbol{x},\boldsymbol{y})$ at
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$, the
conclusion of zero gap holds by the proof of Theorem 7(iii) and (iv).

###### Corollary 3

(i) Suppose that for $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in R^{n}\times
R^{m}$ and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$,
the Lagrange function
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$ is
convex on $(\boldsymbol{x},\boldsymbol{y})$ at
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$. If (20) holds, then
$L(\boldsymbol{x}^{*},\boldsymbol{y}^{*},$
$\boldsymbol{u}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.

(ii) Suppose that for $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(f)$ and
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$, the
Lagrange function
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$ is
convex on $(\boldsymbol{x},\boldsymbol{y})$ at
$(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$. If (20) holds, then
$g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.

###### Proposition 5

(i) Suppose that $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in R^{n}\times
R^{m}$ and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$.
Then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*},\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
is a saddle point of
$L(\boldsymbol{x},\boldsymbol{y},\boldsymbol{u},\boldsymbol{v})$ if and only
if
$L(\boldsymbol{x}^{*},\boldsymbol{y}^{*},\boldsymbol{u}^{*},\boldsymbol{v}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.

(ii) Suppose that (20) holds at $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in
X(f)$ and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$.
Then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
is a saddle point of
$L(\boldsymbol{x},\boldsymbol{y},\boldsymbol{u},\boldsymbol{v})$ if and only
if
$g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.

(iii) Suppose that $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in R^{n}\times
R^{m}$ and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times
R^{r}_{+}$. Then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*},\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
is a saddle point of
$L_{+}(\boldsymbol{x},\boldsymbol{y},\boldsymbol{u},\boldsymbol{v})$ if and
only if
$L_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*},\boldsymbol{u}^{*},\boldsymbol{v}^{*})=\theta_{+}(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.

(iv) Suppose that (22) holds at $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in
X(f)$ and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times
R^{r}_{+}$. Then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
is a saddle point of
$L_{+}(\boldsymbol{x},\boldsymbol{y},\boldsymbol{u},\boldsymbol{v})$ if and
only if
$g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\theta_{+}(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.

Define an augmented Lagrange penalty function of (CNP) as follows

$\displaystyle
A(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v},\rho)$
$\displaystyle=$ $\displaystyle
g(\boldsymbol{x},\boldsymbol{y})+\boldsymbol{u}^{\top}\boldsymbol{g}(\boldsymbol{x},\boldsymbol{y})+\boldsymbol{v}^{\top}\boldsymbol{h}(\boldsymbol{x},\boldsymbol{y})$
(23)
$\displaystyle+\rho\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})^{2}+\rho\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x},\boldsymbol{y})^{2},$
$\displaystyle(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times
R^{m},(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r},$

where $\rho>0$ is a penalty parameter and
$g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})=\max\\{g_{i}(\boldsymbol{x},\boldsymbol{y}),0\\}$.
Define an augmented Lagrange penalty function of (CNP) as follows

$\displaystyle
A_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v},\rho)$
$\displaystyle=$ $\displaystyle
g(\boldsymbol{x},\boldsymbol{y})+\boldsymbol{u}^{\top}\boldsymbol{g}(\boldsymbol{x},\boldsymbol{y})+\boldsymbol{v}^{\top}\boldsymbol{h}(\boldsymbol{x},\boldsymbol{y})$
(24)
$\displaystyle+\rho\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})^{2}+\rho\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x},\boldsymbol{y})^{2},$
$\displaystyle\ \ (\boldsymbol{x},\boldsymbol{y})\in R^{n}\times
R^{m},(\boldsymbol{u},\boldsymbol{v})\in R^{s}_{+}\times R^{r}_{+},$

where $\rho>0$ is a penalty parameter and
$g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})=\max\\{g_{i}(\boldsymbol{x},\boldsymbol{y}),0\\}$.
Theorem 8 shows that (23) and (24) are exact penalty function for $\rho>0$.

###### Theorem 8

(i) If $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in X(f)$ is an optimal
solution to
$\min\limits_{(\boldsymbol{x},\boldsymbol{y})}L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
at $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times R^{r}$, then
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to
$\min\limits_{(\boldsymbol{x},\boldsymbol{y})}A(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
for all $\rho>0$.

(ii) Suppose that (22) holds for $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in
X(f)$ and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in R^{s}_{+}\times
R^{r}_{+}$. Then (21) holds if and only if
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to
$\min\limits_{(\boldsymbol{x},\boldsymbol{y})}A_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
for all $\rho>0$.

Proof. (i) For any $(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times R^{m}$, we
have

$\displaystyle
A(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
$\displaystyle=$ $\displaystyle
g(\boldsymbol{x},\boldsymbol{y})+\sum\limits_{i=1}^{s}u_{i}^{*}g_{i}(\boldsymbol{x},\boldsymbol{y})+\rho\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})^{2}$
$\displaystyle+\sum\limits_{i=1}^{r}v_{j}^{*}h_{j}(\boldsymbol{x},\boldsymbol{y})+\rho\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x},\boldsymbol{y})^{2}$
$\displaystyle\geq$ $\displaystyle
L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*})+\rho\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})^{2}+\rho\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x},\boldsymbol{y})^{2}$
$\displaystyle\geq$ $\displaystyle
L(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})=A(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho).$

Hence, $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to
$\min\limits_{(\boldsymbol{x},\boldsymbol{y})}A(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
for all $\rho>0$.

(ii) Let us prove that $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal
solution to
$\min\limits_{(\boldsymbol{x},\boldsymbol{y})}A_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
for all $\rho>0$, when (21) and (22) hold. Let any
$(\boldsymbol{x},\boldsymbol{y})\in R^{n}\times R^{m}$. Since
$g(\boldsymbol{x},\boldsymbol{y})$,
$g_{i}(\boldsymbol{x},\boldsymbol{y})(i=1,2,\cdots,s)$ and
$h_{j}(\boldsymbol{x},\boldsymbol{y})(i=1,2,\cdots,r)$ are convex, we have

$\displaystyle
g(\boldsymbol{x},\boldsymbol{y})-g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\geq\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})[(\boldsymbol{x},\boldsymbol{y})-(x^{*},\boldsymbol{y}^{*})],$
(25) $\displaystyle
g_{i}(\boldsymbol{x},\boldsymbol{y})-g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\geq\nabla
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})],i=1,2,\cdots,s,$
(26) $\displaystyle
h_{j}(\boldsymbol{x},\boldsymbol{y})-h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\geq\nabla
h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})[(\boldsymbol{x},\boldsymbol{y})-(\boldsymbol{x}^{*},\boldsymbol{y}^{*})],i=1,2,\cdots,r.$
(27)

From (25) , (26), (27) and Theorem7(iv), we have

$\displaystyle
A_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
$\displaystyle=$ $\displaystyle
g(\boldsymbol{x},\boldsymbol{y})+\sum\limits_{i=1}^{s}u_{i}^{*}g_{i}(\boldsymbol{x},\boldsymbol{y})+\rho\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})^{2}$
$\displaystyle+\sum\limits_{i=1}^{r}v_{j}^{*}h_{j}(\boldsymbol{x},\boldsymbol{y})+\rho\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x},\boldsymbol{y})^{2}$
$\displaystyle\geq$ $\displaystyle
L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*})+\rho\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})^{2}+\rho\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x},\boldsymbol{y})^{2}$
$\displaystyle\geq$ $\displaystyle
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=A_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho).$

Hence, $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to
$\min\limits_{(\boldsymbol{x},\boldsymbol{y})}A_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
for all $\rho>0$.

Now, when $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is an optimal solution to
$\min\limits_{(\boldsymbol{x},\boldsymbol{y})}A_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
for all $\rho>0$, it is clear that

$\displaystyle\nabla
A_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
$\displaystyle=$ $\displaystyle\nabla
g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\sum\limits_{i=1}^{s}u_{i}^{*}\nabla
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$
$\displaystyle+\rho\sum\limits_{i=1}^{s}2g_{i}^{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\nabla
g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})+\sum\limits_{j=1}^{r}v_{i}^{*}\nabla
h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$
$\displaystyle+\rho\sum\limits_{j=1}^{r}2h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\nabla
h_{j}(\boldsymbol{x}^{*},\boldsymbol{y}^{*}),$ $\displaystyle=$
$\displaystyle\nabla
L_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})=0.$

Hence,
$L_{+}(\boldsymbol{x}^{*},\boldsymbol{y}^{*};\boldsymbol{u}^{*},\boldsymbol{v}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$.

Theorem 7 and 8 mean that
$g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
or
$g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\theta_{+}(\boldsymbol{u}^{*},\boldsymbol{v}^{*})$
does not hold, if there is no $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})\in
R^{n}\times R^{m}$ and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})\in
R^{s}_{+}\times R^{r}_{+}$ such that (20) or (22) holds. This means that (20)
or (22) is necessary, if an global optimal solution to (CNP) is to be found by
Theorem 7. Let us see the following example.

Example 6 Consider the optimization(Example 5):

(EX5) $\displaystyle\min$ $\displaystyle\
f(x)=|x_{1}x_{2}|^{\frac{1}{3}}+x_{1}^{2}+x_{2}^{2}$ $\displaystyle s.t.$
$\displaystyle(x_{1},x_{2})\in R^{2}.$

The convertible nonconvex optimization of (EX5) is defined by (MEX5-1). The
Lagrange function of (MEX5-1) is defined as

$\displaystyle
L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})=y_{4}+x_{1}^{2}+x_{2}^{2}-u_{1}y_{4}+v_{1}(0.5(x_{1}+x_{2})^{2}-y_{1}-0.5y_{2})$
$\displaystyle+v_{2}(x_{1}^{2}+x_{2}^{2}-y_{2})+v_{3}(y_{1}^{2}-y_{3})+v_{4}(y_{4}^{6}-y_{3}),$

where $\forall u_{1}\geq 0$ and
$(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})\in R^{2}\times
R^{4}\times R^{1}_{+}\times R^{4}_{+}$. The dual function of
$L_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$ is
obtained by

$\theta_{+}(\boldsymbol{u},\boldsymbol{v})=\left\\{\begin{array}[]{ll}0&\mbox{if
}~{}u_{1}=1,v_{1}=v_{2}=v_{3}=v_{4}=0\\\ -\infty&\mbox{if }~{}u_{1}\not=1\
\mbox{or}\ \boldsymbol{v}\in R^{4}_{+}\setminus\\{0\\}.\end{array}\right.$

It is clear that
$g(\boldsymbol{x},\boldsymbol{y})\geq\theta_{+}(\boldsymbol{u},\boldsymbol{v})$
for all

$(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})\in R^{2}\times
R^{4}\times R^{1}_{+}\times R^{4}_{+}.$

When $u^{*}_{1}=1$, $v_{1}^{*}=v_{2}^{*}=v_{3}^{*}=v_{4}^{*}=0$ and
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=(0,0,0,0,0,0)$,
$g(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=\theta(\boldsymbol{u}^{*},\boldsymbol{v}^{*})=0$.
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$ is the optimal solution to (MEX5-1).
The Lagrange function of (MEX5-1) is defined as

$\displaystyle
L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})=y_{4}+x_{1}^{2}+x_{2}^{2}-u_{1}y_{4}+v_{1}(0.5(x_{1}+x_{2})^{2}-y_{1}-0.5y_{2})$
$\displaystyle+v_{2}(x_{1}^{2}+x_{2}^{2}-y_{2})+v_{3}(y_{1}^{2}-y_{3})+v_{4}(y_{4}^{6}-y_{3}),$

where $(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})\in
R^{2}\times R^{4}\times R^{1}_{+}\times R^{4}$. The dual function of
$L(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})$ is obtained
by

$\theta_{+}(\boldsymbol{u},\boldsymbol{v})=\left\\{\begin{array}[]{ll}0&\mbox{if
}~{}u_{1}=1,v_{1}=v_{2}=v_{3}=v_{4}=0\\\ -\infty&\mbox{if }~{}u_{1}\not=1\
\mbox{or}\ \boldsymbol{v}\in R^{4}\setminus\\{0\\}.\end{array}\right.$

The augmented Lagrange penalty function of (MEX5-1) is defined as

$\displaystyle
A_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v},\rho)$
$\displaystyle=$ $\displaystyle
y_{4}+x_{1}^{2}+x_{2}^{2}-u_{1}y_{4}+v_{1}(0.5(x_{1}+x_{2})^{2}-y_{1}-0.5y_{2})$
$\displaystyle+v_{2}(x_{1}^{2}+x_{2}^{2}-y_{2})+v_{3}(y_{1}^{2}-y_{3})+v_{4}(y_{4}^{6}-y_{3})$
$\displaystyle+\rho[\max\\{-y_{4},0\\}^{2}+(0.5(x_{1}+x_{2})^{2}-y_{1}-0.5y_{2})^{2}$
$\displaystyle+(x_{1}^{2}+x_{2}^{2}-y_{2})^{2}+(y_{1}^{2}-y_{3})^{2}+(y_{4}^{6}-y_{3})^{2}],$

where $\rho>0$ and
$(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v})\in R^{2}\times
R^{4}\times R^{1}_{+}\times R^{4}_{+}$. By Theorem 8 and Example 5, it is
clear that $(\boldsymbol{x}^{*},\boldsymbol{y}^{*})=(0,0,0,0,0,0)$ is an
optimal solution to
$\min\limits_{(\boldsymbol{x},\boldsymbol{y})}A_{+}(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u}^{*},\boldsymbol{v}^{*},\rho)$
for all $\rho>0$ and $(\boldsymbol{u}^{*},\boldsymbol{v}^{*})=(1,0,0,0,0)$.

In order to obtain a solution to (UOP), by Theorem 8, we may find an
approximate solution to (CNP) by the augmented Lagrange penalty optimization
as follows

$\displaystyle\mbox{(CNP)}(\boldsymbol{u},\boldsymbol{v},\rho)$
$\displaystyle\min$ $\displaystyle
A(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v},\rho),$
$\displaystyle s.t.$ $\displaystyle(\boldsymbol{x},\boldsymbol{y})\in
R^{n}\times R^{m}.$

Let
$\boldsymbol{g}^{+}(\boldsymbol{x},\boldsymbol{y})=(g^{+}_{1}(\boldsymbol{x},\boldsymbol{y}),g^{+}_{2}(\boldsymbol{x},\boldsymbol{y}),\cdots,g^{+}_{s}(\boldsymbol{x},\boldsymbol{y}))^{\top}$.

To solve (CNP)$(\boldsymbol{u},\boldsymbol{v},\rho)$, we propose an algorithm
of augmented Lagrange penalty function of (CNP)(which is called ALPF
Algorithm).

ALPF Algorithm:

Step 1:

Let $\epsilon>0,\rho_{1}>0,N>1,(\boldsymbol{x}^{0},\boldsymbol{y}^{0})\in
R^{n}\times R^{m}$, $\boldsymbol{v}^{1}\in R^{r}$,
$\boldsymbol{u}^{1}=\boldsymbol{g}^{+}(\boldsymbol{x}^{0},\boldsymbol{y}^{0})$,$\boldsymbol{v}^{1}=0$,
and $k=1$.

Step 2:

Solve $(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\in R^{n}\times R^{m}$ to
problem
$\lim\limits_{(\boldsymbol{x},\boldsymbol{y})}A(\boldsymbol{x},\boldsymbol{y},\boldsymbol{u}^{k},\boldsymbol{v}^{k},\rho_{k})$
such that $\nabla
A(\boldsymbol{x}^{k},\boldsymbol{y}^{k},\boldsymbol{u}^{k},\boldsymbol{v}^{k},\rho_{k})=0$,
and go to Step 3.

Step 3:

If $u_{i}^{k}g_{i}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})=0(i=1,2,\cdots,s)$
at $(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\in X(f)$ and
$L(\boldsymbol{x},\boldsymbol{y},\boldsymbol{u}^{k},\boldsymbol{v}^{k})$ is
convex on $(\boldsymbol{x},\boldsymbol{y})$ for
$(\boldsymbol{u}^{k},\boldsymbol{v}^{k})\in R^{s}_{+}\times R^{r}$, then stop
and $\boldsymbol{x}^{k}$ is an optimal solution to (UOP). Otherwise, go to
Step 4.

Step 4:

If
$|A(\boldsymbol{x}^{k},\boldsymbol{y}^{k},\boldsymbol{u}^{k},\boldsymbol{v}^{k},\rho_{k})-g(\boldsymbol{x}^{k},\boldsymbol{y}^{k})|<\epsilon$
and
$\|\boldsymbol{g}^{+}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\|+\|\boldsymbol{h}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\|<\epsilon$,
then stop and $\boldsymbol{x}^{k}$ is an approximate solution to (UOP).
Otherwise, for $i=1,2,\cdots,s,$ let
$u^{k+1}_{i}=$$\left\\{\begin{array}[]{l}u^{k}_{i}+2\rho_{k}g^{+}_{i}(\boldsymbol{x}^{k},\boldsymbol{y}^{k}),\mbox{}\hskip
36.135ptif\mbox{}\hskip
21.68121ptg_{i}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\geq 0,\\\
0,\mbox{}\hskip 122.85876ptif\mbox{}\hskip
21.68121ptg_{i}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})<0,\\\
\end{array}\right.$
$\boldsymbol{v}^{k+1}=\boldsymbol{v}^{k}+2\rho_{k}\boldsymbol{h}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})$,
$\rho_{k+1}=N\rho_{k}$, $k:=k+1$ and go to Step 2.

Note: By Theorem 7 and Theorem 8, if
$A(\boldsymbol{x}^{k},\boldsymbol{y}^{k};\boldsymbol{u}^{k},\boldsymbol{v}^{k},\rho_{k})=g(\boldsymbol{x}^{k},\boldsymbol{y}^{k})$
and $(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\in X(g)$ for some $k$, then
$\theta(\boldsymbol{u}^{k},\boldsymbol{v}^{k})=g(\boldsymbol{x}^{k},\boldsymbol{y}^{k})$
and $\boldsymbol{x}^{k}$ is an optimal solution to (UOP). Hence,
$\boldsymbol{x}^{k}$ may be an approximate solution to (UOP) if
$|A(\boldsymbol{x}^{k},\boldsymbol{y}^{k};\boldsymbol{u}^{k},\boldsymbol{v}^{k},\rho_{k})-g(\boldsymbol{x}^{k},\boldsymbol{y}^{k})|<\epsilon$
and
$\|\boldsymbol{g}^{+}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\|+\|\boldsymbol{h}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\|<\epsilon$
hold. ALPF Algorithm may be able to find an approximate global optimal
solution to (UOP). Under some conditions, that ALPF Algorithm can converge to
a KKT point of (CNP) for $\epsilon=0$ is proved.

Let

$S(\pi,g)=\\{(\boldsymbol{x},\boldsymbol{y})\mid\pi\geq
g(\boldsymbol{x},\boldsymbol{y})\\},$

which is called a level set. If $S(\pi,g)$ is bounded for any given $\pi>0$,
then $S(\pi,g)$ is called to be bounded.

###### Lemma 3

Suppose that sequence $\\{(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\\}$ is
obtained by ALPF Algorithm for every $k=1,2,\cdots$. Let sequence
$\\{(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\\}$ converge to
$(\boldsymbol{x}^{*},\boldsymbol{y}^{*})$. If
$g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})<0$ for some $i$, then
$u_{i}^{k}\to 0$ as $k\to+\infty$.

Proof. If $g_{i}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})<0$ for some $i$, there
is $k^{\prime}>0$ such that
$g_{i}^{k}(\boldsymbol{x}^{*},\boldsymbol{y}^{*})<0$ for all $k>k^{\prime}$.
By Step 4 of ALPF Algorithm, we have $u^{k+1}_{i}=0$ for all $k>k^{\prime}$.
Hence, $u_{i}^{k}\to 0$ as $k\to+\infty$.

###### Theorem 9

Let $\epsilon=0$. Suppose that sequence
$\\{(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\\}$ is obtained by ALPF Algorithm
for every $k=1,2,\cdots$. Let, for every $k=1,2,\cdots,$ sequence
$\\{H_{k}(\boldsymbol{x}^{k},\boldsymbol{y}^{k},\rho_{k})\\}$ be bounded and
the level set $S(\pi,g)$ be bounded, where

$H_{k}(\boldsymbol{x}^{k},\boldsymbol{y}^{k},\rho_{k})=g(\boldsymbol{x}^{k},\boldsymbol{y}^{k})+\rho_{k}\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})^{2}+\rho_{k}\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})^{2}.$

(i) If the algorithm stops at finite step $k$, then $\boldsymbol{x}^{k}$ is a
global optimal solution to (UOP).

(ii) If sequence $\\{(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\\}$ is infinite,
then $\\{(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\\}$ is bounded and any limit
point $(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})$ of it belongs to $X(f)$, and
there exist $\eta>0$, $\alpha_{i}\geq 0(i=1,2,\cdots,s)$ and
$\beta_{j}(j=1,2,\cdots,r)$, such that

$\displaystyle\eta\nabla
g(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})+\sum\limits_{i=1}^{s}\alpha_{i}\nabla
g_{i}(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})+\sum\limits_{i=1}^{r}\beta_{j}\nabla
h_{j}(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})=0.$ (28)
$\displaystyle\alpha_{i}\nabla
g_{i}(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})=0,i=1,2,\cdots,s.$ (29)

If $\beta_{j}\geq 0(j=1,2,\cdots,r)$, then $\boldsymbol{x}^{*}$ is an optimal
solution to (UOP)

Proof. (i) The conclusion is clear by Theorem 7 and Corollary 3.

(ii) By ALPF Algorithm, since
$\\{H_{k}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k},\rho_{k})\\}$ is bounded as
$k\to+\infty$, there must be some $\pi>0$ such that

$\displaystyle\pi$ $\displaystyle>$ $\displaystyle
H_{k}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k},\rho_{k})$ $\displaystyle=$
$\displaystyle
g(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})+\rho_{k}\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})^{2}+\rho_{k}\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})^{2}$
$\displaystyle\geq$ $\displaystyle
g(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k}).$

$\\{(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})\\}$ is bounded because the level
set $S(\pi,f)$ is bounded. Without loss of generality, suppose
$(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})\to(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})$.
Since $g$ is continuous, $S(\pi,f)$ is closed. So,
$g(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})$ is bounded and there is a
$\sigma>0$ such that $g(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k}>-\sigma$.

From the above inequality, we have that

$\displaystyle\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})^{2}+\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})^{2}\leq\frac{1}{\rho_{k}}(\pi-g(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k}))<\frac{\pi+\sigma}{\rho_{k}}.$

And
$\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})^{2}+\sum\limits_{j=1}^{r}(h_{j}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k}))^{2}\to
0$ as $\rho_{k}\to+\infty$. So, $(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})\in
X(f)$.

By ALPF algorithm, there is infinite sequence
$\\{\boldsymbol{x}^{k},{\boldsymbol{y}}^{k},\boldsymbol{u}^{k},\boldsymbol{v}^{k},\rho_{k})\\}$
such that $\nabla
A(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k};\boldsymbol{u}^{k},\boldsymbol{v}^{k},\rho_{k})=0$.
We have

$\displaystyle\nabla
g(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})+\sum\limits_{i=1}^{s}\bar{u}^{k}_{i}\nabla
g_{i}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})+\sum\limits_{j=1}^{r}v^{k+1}_{j}\nabla
h_{j}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})=0,$ (30)

where
$\bar{u}^{k}_{i}=u^{k}_{i}+2\rho_{k}g_{i}^{+}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k})\geq
0,i=1,2,\cdots,s$ and
$v^{k+1}_{j}=v^{k}_{j}+2\rho_{k}h_{j}(\boldsymbol{x}^{k},{\boldsymbol{y}}^{k}),j=1,2,\cdots,r$.
Let

$\displaystyle\gamma_{k}=1+\sum\limits_{i=1}^{s}\bar{u}^{k}_{i}+\sum\limits_{j=1}^{r}(\max\\{v^{k+1}_{j},0\\}+\max\\{-v^{k+1}_{j},0\\})>0.$

Let $\eta^{k}=\frac{1}{\gamma_{k}}>0$,
$\alpha_{i}^{k}=\frac{\bar{u}^{k}_{i}}{\gamma_{k}}\geq 0(i=1,2,\cdots,s)$;
$\mu_{j}^{k}=\frac{\max\\{v^{k+1}_{j},0\\}}{\gamma_{k}}\geq 0(j=1,2,\cdots,r)$
and $\nu_{j}^{k}=\frac{\max\\{-v^{k+1}_{j},0\\}}{\gamma_{k}}\geq
0(j=1,2,\cdots,r)$. Then,

$\displaystyle\eta^{k}+\sum\limits_{i=1}^{s}\alpha_{i}^{k}+\sum\limits_{j=1}^{r}(\mu_{j}^{k}+\nu_{j}^{k})=1.$
(31)

Clearly, as $k\to\infty$, we have
$\eta^{k}\rightarrow\eta>0,\alpha_{i}^{k}\rightarrow\alpha_{i}(i=1,2,\cdots,s),\mu_{j}^{k}\rightarrow\mu_{j}(j=1,2,\cdots,r)$
and $\nu_{j}^{k}\rightarrow\nu_{j}(j=1,2,\cdots,r)$. By (30) and (31), we have

$\displaystyle\eta\nabla
g(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})+\sum\limits_{i=1}^{s}\alpha_{i}\nabla
g_{i}(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})+\sum\limits_{j=1}^{r}(\mu_{i}-\nu_{i})\nabla
h_{j}(\boldsymbol{x}^{*},{\boldsymbol{y}}^{*})=0.$ (32)

By (32) and Lemma 3, let $\beta^{k}_{i}=\mu_{i}^{k}-\nu_{i}^{k}\to\beta_{i}$
as $k\rightarrow+\infty$, (28) and (29) hold.

Now,
$((\boldsymbol{x}_{1},\boldsymbol{y}_{1}),(\boldsymbol{x}_{2},\boldsymbol{y}_{2}),\cdots,(\boldsymbol{x}_{p},\boldsymbol{y}_{p}))$
is called a decomposition of $(\boldsymbol{x},\boldsymbol{y}))$ on $S$ if it
satisfies the following conditions:

(i)
$\boldsymbol{x}=(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\cdots,\boldsymbol{x}_{p})^{\top}\in
S$, where $\boldsymbol{x}_{j}=(x_{j1},x_{j2},\cdots,x_{jp_{j}})\in
R^{p_{j}},j=1,2,\cdots,p$ and $\sum\limits_{j=1}^{p}p_{j}=n$;

(ii)
$\boldsymbol{y}=(\boldsymbol{y}_{1},\boldsymbol{y}_{2},\cdots,\boldsymbol{y}_{p})^{\top}\in
R^{m}$, where $\boldsymbol{y}_{j}=(y_{j1},y_{j2},\cdots,y_{jq_{j}})\in
R^{q_{j}},j=1,2,\cdots,p$ and $\sum\limits_{j=1}^{p}q_{j}=m$;

(iii)
$((\boldsymbol{x}_{1},\boldsymbol{y}_{1}),(\boldsymbol{x}_{2},\boldsymbol{y}_{2}),\cdots,(\boldsymbol{x}_{p},\boldsymbol{y}_{p}))$
is a rearrangement of $(\boldsymbol{x},\boldsymbol{y})$;

(iv) there are no identical variables between
$(\boldsymbol{x}_{k},\boldsymbol{y}_{k})$ and
$(\boldsymbol{x}_{j},\boldsymbol{y}_{j})$ for any $j,k=1,2,\cdots,p,k\not=j)$.

Let
$(\boldsymbol{x}_{j},\boldsymbol{y}_{j}\mid(\boldsymbol{x},\boldsymbol{y})):=((\boldsymbol{x}_{1},\boldsymbol{y}_{1}),(\boldsymbol{x}_{2},\boldsymbol{y}_{2}),\cdots,(\boldsymbol{x}_{p},\boldsymbol{y}_{p}))$,
where $(\boldsymbol{x}_{j},\boldsymbol{y}_{j})$ is a variable, i.e. all
$(\boldsymbol{x}_{k},\boldsymbol{y}_{k})(k=1,2,\cdots,p,k\not=j)$ are fixed
except $(\boldsymbol{x}_{j},\boldsymbol{y}_{j})$.

Let $R^{s_{j}}_{+}=\\{\boldsymbol{\beta}_{j}\in
R^{s_{j}}\mid\boldsymbol{\beta}_{j}\geq 0\\},j=1,2,\cdots,p$. Let
$\boldsymbol{\alpha}_{j}\in R^{r_{j}},\boldsymbol{\beta}_{j}\in
R^{s_{j}}_{+},j=1,2,\cdots,p$ be Lagrange parameters and $\sigma>0$ be a
penalty parameter with
$(\boldsymbol{x},\boldsymbol{y})=((\boldsymbol{x}_{1},\boldsymbol{y}_{1}),(\boldsymbol{x}_{2},\boldsymbol{y}_{2}),\cdots,(\boldsymbol{x}_{p},\boldsymbol{y}_{p}))$,
$\boldsymbol{u}=(\boldsymbol{\alpha}_{1},\boldsymbol{\alpha}_{2},\cdots,\boldsymbol{\alpha}_{p})$
and
$\boldsymbol{v}=(\boldsymbol{\beta}_{1},\boldsymbol{\beta}_{2},\cdots,\boldsymbol{\beta}_{p})$.

In order to solve (CNP), we reduce the scale problem of (CNP) and use the
decomposition method to solve (CNP) with ALPF Algorithm. The augmented
Lagrange penalty functions of all subproblems
(CNP)${}_{j}(\boldsymbol{\alpha}_{j},\boldsymbol{\beta}_{j},\sigma)(j=1,2,\cdots,p)$
are defined by

$\displaystyle
A_{j}(\boldsymbol{x}_{i},\boldsymbol{y}_{j}\mid(\boldsymbol{x},\boldsymbol{y});\boldsymbol{\alpha}_{j},\boldsymbol{\beta}_{j},\sigma)$
$\displaystyle=$ $\displaystyle
g(\boldsymbol{x}_{i},\boldsymbol{y}_{j}|(\boldsymbol{x},\boldsymbol{y}))+\boldsymbol{\alpha}_{j}^{\top}\boldsymbol{h}_{j}(\boldsymbol{x}_{j},\boldsymbol{y}_{j}\mid(\boldsymbol{x},\boldsymbol{y})$
(33)
$\displaystyle+\boldsymbol{\beta}_{j}^{\top}\boldsymbol{g}_{j}(\boldsymbol{x}_{j},\boldsymbol{y}_{j}\mid(\boldsymbol{x},\boldsymbol{y})+\frac{1}{2}\sigma\|\boldsymbol{h}_{j}(\boldsymbol{x}_{j},\boldsymbol{y}_{j}\mid(\boldsymbol{x},\boldsymbol{y})\|^{2}$
$\displaystyle+\frac{1}{2}\sigma\max\\{\boldsymbol{g}_{j}(\boldsymbol{x}_{j},\boldsymbol{y}_{j}\mid(\boldsymbol{x},\boldsymbol{y}),0\\}^{2},$

where $(\boldsymbol{x}_{j},\boldsymbol{y}_{j})$ is variable, i.e. all
$(\boldsymbol{x}_{k},\boldsymbol{y}_{k})(k=1,2,\cdots,p,k\not=j)$ are fixed
except for $(\boldsymbol{x}_{j},\boldsymbol{y}_{j})$. By (33), for
$j=1,2,\cdots,p$, unconstraint optimization subproblems are defined by

$\displaystyle\mbox{(CNP)}_{j}(\boldsymbol{\alpha}_{j},\boldsymbol{\beta}_{j},\sigma)\qquad$
$\displaystyle\min\;$ $\displaystyle
A_{j}(\boldsymbol{x}_{j},\boldsymbol{y}_{j}|(\boldsymbol{x},\boldsymbol{y});\boldsymbol{\alpha}_{j},\boldsymbol{\beta}_{j},\sigma)$
s.t. $\displaystyle(\boldsymbol{x}_{j},\boldsymbol{y}_{j})\in R^{p_{j}}\times
R^{q_{j}}.$

For $j=1,2,\cdots,p$ and $n=ep$, the subproblems (CNP)j are solved by
repeatedly using the ALPF Algorithm such that larger scale problem (CNP) may
be solved.

Finally, a nonconvex optimization problem with convertible nonconvex function
$f$ is defined by

(UOP) $\displaystyle\min$ $\displaystyle f(\boldsymbol{x})$ $\displaystyle
s.t.$ $\displaystyle\boldsymbol{x}\in S,$

where $S$ is nonempty set in $R^{n}$. If $f$ is a differentiable convertible
nonconvex function with
$f=[g:g_{1},g_{2},\cdots,g_{s};h_{1},h_{2},\cdots,h_{r}]$, then
$A(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v},\rho)$ is
defined by (23). So , the following problem is solved by ALPF Algorithm.

$\displaystyle\mbox{(CNP)}(\boldsymbol{u},\boldsymbol{v},\rho)$
$\displaystyle\min$ $\displaystyle
A(\boldsymbol{x},\boldsymbol{y};\boldsymbol{u},\boldsymbol{v},\rho),$
$\displaystyle s.t.$ $\displaystyle\boldsymbol{x}\in S,\boldsymbol{y}\times
R^{m}.$

We have obtained numerical results of three examples with Matlab.

Example 7 A nonconvex optimization problem is (Problem 1 in [32])

(EX7) $\displaystyle\min$ $\displaystyle
f(\boldsymbol{x})=2x_{1}^{2}-1.05x_{1}^{4}+\frac{1}{6}x_{1}^{6}-x_{1}x_{2}+x_{2}^{2}$
$\displaystyle s.t.$ $\displaystyle|x_{1}|\leq 3,|x_{2}|\leq 3.$

An optimal solution to (EX7) is (0,0) in [32]. Let
$(\boldsymbol{x},\boldsymbol{y})=(x_{1},x_{2},y_{1},y_{2},y_{3})$. A
convertible nonconvex form of $f$ is defined by

$\displaystyle
f(\boldsymbol{x})=[2x_{1}^{2}-1.05y_{1}+\frac{1}{6}y_{2}+0.5(x_{1}-x_{2})^{2}-0.5y_{3}+x_{2}^{2}:$
$\displaystyle-x_{1}-3\leq 0,x_{1}-3\leq 0,-x_{2}-3\leq 0,-x_{4}-3\leq 0;$
$\displaystyle
x_{1}^{4}-y_{1}=0,x_{2}^{6}-y_{2}=0,x_{1}^{2}+x_{2}^{2}-y_{3}=0].$

In ALPF Algorithm, the starting parameters
$\epsilon=10^{-6},\rho_{1}=10,N=100,\boldsymbol{u}^{0}=(0,0,0)$ and
$(\boldsymbol{x}^{0},\boldsymbol{y}^{0})=(2,2,2,2,2)$ are taken. At the 3th
step, an approximate solution $\boldsymbol{x}^{3}=(0.000000,0.000000)$ to
(EX7) is obtained.

Example 8 A nonconvex nonsmooth optimization problem is (Problem 5 in [2])

(EX8) $\displaystyle\min$ $\displaystyle
f_{n}(\boldsymbol{x})=n\max\\{|x_{i}|:i=1,2,\cdots,n\\}-\sum\limits_{i=1}^{n}|x_{i}|$
$\displaystyle s.t.$ $\displaystyle\boldsymbol{x}\in R^{n}.$

An optimal solution to (EX8) is
$\boldsymbol{x}^{*}=(\pm\alpha,\pm\alpha,\cdots,\pm\alpha)^{\top}$ in [2] with
$f(\boldsymbol{x}^{*})=0$ for $\alpha\in R^{1}$ in [2]. Let $\boldsymbol{x}\in
R^{n},\boldsymbol{y}\in R^{2n+1}$. A convertible nonconvex form of $f$ is
defined by

$\displaystyle g(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$
$\displaystyle ny_{2n+1}-\sum\limits_{i=1}^{n}y_{i}$ $\displaystyle
h_{i}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$ $\displaystyle
y_{i}^{2}-y_{i+n}=0,\ i=1,2,\cdots,n,$ $\displaystyle
h_{n+i}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$ $\displaystyle
x_{i}^{2}-y_{i+n}=0,\ i=1,2,\cdots,n,$ $\displaystyle
g_{i}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$ $\displaystyle-
y_{i}\leq 0,\ i=1,2,\cdots,n,$ $\displaystyle
g_{n+i}(\boldsymbol{x},\boldsymbol{y})$ $\displaystyle=$ $\displaystyle
y_{i}-y_{2n+1}\leq 0,\ i=1,2,\cdots,n.$

In ALPF Algorithm, the starting parameters
$\epsilon=10^{-6},\rho_{1}=10,N=100,(\boldsymbol{u}^{0},\boldsymbol{v}^{0})=(0,0,\cdots,0)$
and $(\boldsymbol{x}^{0},\boldsymbol{y}^{0})=(1,2,3,\cdots,3n+1)$ are taken.
For $n=5$, at the 4th step, an approximate solution
$\boldsymbol{x}^{4}=(3.4366,-3.4366,-3.4366,3.4366,3.4366)$ to (EX8) is
obtained.

We can also use the penalty function method to solve (CNP). Define a penalty
function of (CNP) as follows

$\displaystyle\mbox{(CNP)}(\rho)$ $\displaystyle\min$ $\displaystyle
F(\boldsymbol{x},\boldsymbol{y};\rho)=g(\boldsymbol{x},\boldsymbol{y})+\rho\sum\limits_{i=1}^{s}g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})^{2}+\rho\sum\limits_{j=1}^{r}h_{j}(\boldsymbol{x},\boldsymbol{y})^{2},$
$\displaystyle s.t.$ $\displaystyle\ \ (\boldsymbol{x},\boldsymbol{y})\in
R^{n}\times R^{m},$

where $\rho>0$ is a penalty parameter and
$g_{i}^{+}(\boldsymbol{x},\boldsymbol{y})=\max\\{g_{i}(\boldsymbol{x},\boldsymbol{y}),0\\}$.
By using Matlab, the starting parameters $\epsilon=10^{-6},\rho_{1}=10,N=100$
and $(\boldsymbol{x}^{0},\boldsymbol{y}^{0})=(1,2,3,\cdots,3n+1)$ are taken in
(CNP)$(\rho)$ for (EX8). For $n=10$, at the 4th step, an approximate solution
$\boldsymbol{x}^{4}=(-3.4015,3.4015,$ $3.4015,3.4015,3.4015,3.4015,3.4015,$
$3.4015,3.4015,-3.4015)$ to (EX8) is obtained.

For $n=500$ and $p=100$, the subproblems (CNP)j are solved by repeatedly $100$
times using decomposed ALPF Algorithm. An approximate solution
$\boldsymbol{x}^{4}=(3.3484,3.3484,3.3484,\cdots,-3.3484)$ is obtained.

Example 9 A especial case in Example 4 (in [5]) is defined by

(EX9) $\displaystyle\min$ $\displaystyle
f_{n}(\boldsymbol{x})=(\sum\limits_{i=1}^{n}ix_{i}-2n)^{2}+\lambda\|\boldsymbol{x}\|_{0}$
$\displaystyle s.t.$ $\displaystyle\boldsymbol{x}\in R^{n}.$

For $(x_{i},y_{i},y_{i+n})$, $i=1,2,\cdots,n$, a convertible nonconvex form of
$f_{n}(\boldsymbol{x})$ is defined by

$\displaystyle[(\sum\limits_{i=1}^{n}ix_{i}-2n)^{2}+\lambda\sum\limits_{i=1}^{n}y_{i}^{2}:((x_{i}+y_{i}-1)^{2}-y_{i+n},$
$\displaystyle
x_{i}^{2}+(y_{i}-1)^{2}-y_{i+n},y_{i}^{2}-y_{i})=0,i=1,2,\cdots,n].$

Let
$e^{k}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})=\|\boldsymbol{g}^{+}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\|+\|\boldsymbol{h}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})\|$.
Let $n=10$,
$\epsilon=0.000001,\rho_{1}=10,N=10,(\boldsymbol{x}^{0},\boldsymbol{y}^{0})\in
R^{n}\times R^{m}$, $\boldsymbol{v}^{1}\in
R^{r}$,$(\boldsymbol{x}^{0},\boldsymbol{y}^{0})=(0,0,0,\cdots,0)$,
$\boldsymbol{u}^{1}=\boldsymbol{g}^{+}(\boldsymbol{x}^{0},\boldsymbol{y}^{0})$,$\boldsymbol{v}^{1}=0$.
The numerical results of (EX9) are obtained by ALPF Algorithm at
$\lambda_{1}=1$ and $\lambda_{1}=10$ in Table 1 and Table 2. Table 1 and Table
2 show that approximate sparse solution may be obtained by ALPF Algorithm when
the penalty parameter increases.

Table 1. The numerical results of (EX9) are obtained by ALPF Algorithm at
$\lambda_{1}=1$.
$k$ $\rho_{k}$ $\boldsymbol{x}^{k}$ $f(\boldsymbol{x}^{k})$
$\|\boldsymbol{x}^{k}\|_{0}$ $e^{k}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})$ 1
5 (0.0021,0.0044,0.0059,0.0072,0.0088, 1.9135 1.9131 0.1372
0.0119,0.0129,0.0202,-0.4906,2.3972) 2 50
(-0.0003,-0.0005,-0.0005,-0.0007,-0.0008, 2.0066 2.0066 0.0063
-0.0011,-0.0012,-0.0018,-1.1625,3.0500) 3 500
(0.0000,0.0000,-0.0000,-0.0000,-0.0000, 2.0002 2.0002 0.0001
-0.0000,-0.0000,-0.0000,-0.9386,2.8448)

Table 2. The numerical results of (EX9) are obtained by ALPF Algorithm at
$\lambda_{1}=10$.
$k$ $\rho_{k}$ $\boldsymbol{x}^{k}$ $f(\boldsymbol{x}^{k})$
$\|\boldsymbol{x}^{k}\|_{0}$ $e^{k}(\boldsymbol{x}^{k},\boldsymbol{y}^{k})$ 1
5 (0.0506,0.1013,0.1519,0.2025,0.2532, 0.2564 0.0000 1.4050
0.3038,0.3544,0.4051,0.4557,0.5063) 2 50
(-0.0051,-0.0101,-0.0152,-0.0203,-0.0253, 10.0000 1.0000 0.1209
-0.0304,-0.0354,-0.0405,-0.0456,2.1443) 3 500
(0.0000,0.0000,0.0000,0.0000,0.0000, 10.0000 1.0000 0.0000
0.0000,0.0000,0.0000,0.0000,2.0000)

By ALPF Algorithm,let the starting parameters
$\epsilon=10^{-4},\sigma_{1}=5,N=10,\boldsymbol{\alpha}_{j}^{0}=(0,0,\cdots,0)$
and $\boldsymbol{\beta}_{j}^{0}=(0,0,0,\cdots,0)$ be taken. The subproblems
(CNP)${}_{j}(\boldsymbol{\alpha}_{j},\boldsymbol{\beta}_{j},\rho)(j=1,2,\cdots,p)$
are solved by repeatedly $p$ times using the ALPF Algorithm. Let $n=ep$. When
$e=5,p=1,2,6,10,20,$ $100,200$,$\lambda=1,10$, values of 0-norm
$\|\boldsymbol{x}^{k}\|_{0}$ are obtained by ALPF Algorithm in Table 3.
Numerical results show that values of 0-norm $\|\boldsymbol{x}^{k}\|_{0}$
decrease in Table 3 when $\lambda$ increases.

Table 3. The values of 0-norm $\|\boldsymbol{x}^{k}\|_{0}$ of (EX9) are
obtained by ALPF Algorithm.

$n=5p$ | $\lambda=1$ | $\lambda=10$
---|---|---
5 | 1 | 1
10 | 2 | 2
30 | 15 | 10
50 | 22 | 17
100 | 54 | 37
500 | 325 | 192
1000 | 611 | 382

Hence, the above examples illustrate that it is efficient to solve an
approximate optimal solution to (UOP) by using the ALPF algorithm with
Maltlab, to avoids using subdifferentiation or smoothing techniques.

##  5 Conclusion

In this paper, a new concept-(exact) convertible nonconvex function is
proposed. It involves many nonconvex and nonsmooth functions, even
discontinuous nonconvex functions. The convertible nonconvex function is a set
of convex functions which map the known nonconvex function to the constrained
equalities and inequalities in high dimensional space. These constraint
functions are convex. The sufficient condition of global optimal solution is
proved, which is equivalent to KKT condition. The strong duality theorem of
Lagrange function of convertible nonconvex function is proved. Therefore, an
augmented Lagrangian penalty function algorithm is proposed and its
convergence is proved. If there is a global optimal solution to the
optimization problem of convertible nonconvex function, then the algorithm may
be find a global optimal solution theoretically. Numerical results show that
it is efficient to solve (UOP) by ALPF Algorithm avoids using
subdifferentiation or smoothing techniques, allowing a direct use of some
gradient search algorithms, such as gradient descent algorithm, Newton
algorithm and so on.

This paper provides a new idea for solving nonconvex or nonsmooth optimization
problems in theory. It has important potential value for solving nonconvex or
nonsmooth optimization problems in many application fields.

## References

  * [1] L. Andreas, W. Joakim, W. Tapio,Some transformation techniques with applications in global optimization, Journal of Global Optimization, 43(2-3),391-405(2009).
  * [2] A.M. Bagirov, A method for minimizing of quasidifferentiable functions. Optim Methods Software, 17(1):31-60.(2002)
  * [3] G.A. Bunin, Extended reverse-convex programming: an approximate enumeration approach to global optimization, Journal of Global Optimization, 65:191-229(2016),
  * [4] W.Y. Chiu, Method of reduction of variables for bilinear matrix inequality problems in system and control designs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(7):1241-1256(2017).
  * [5] X.J. Chen, D.D. Ge, Z.Z. Wang, Y.Y. Ye, Complexity of unconstrained $L_{2}-L_{p}$ minimization. Mathematical Programming, Ser. A 143:371-383(2014).
  * [6] X.J. Chen,F.M Xu, Y.Y. Ye,Lower bound theory of nonzero entries in solutions of $L_{2}-L_{p}$ minimization. SIAM J. Sci. Comput,32,2832-2852(2010).
  * [7] F.H. Clarke,Opimization and Nonsmooth Analysis. John Wiley & Sons. In(1983)c.
  * [8] A. Daniilidis and J. Malick, Filling the gap between lower-C-1 and lower-C-2 functions . Journal of Convex Analysis, 12(2), pp.315-329(2005).
  * [9] M. Grant,S. Boyd, Y.Y. Ye. Disciplined convex programming. In L. Liberti and N. Maculan, editors. Global Optimization: From Theory to Implementation, Nonconvex Optimization and its Applications, Springer, 2006,155-210(2006).
  * [10] L. Granvilliers . Filtering Domains of Factorable Functions Using Interval Contractors . H. A. Le Thi et al. (Eds.): WCGO 2019, AISC 991, pp. 99-108, 2020. , https://doi.org/10.1007/978-3-030-21803-4-10.
  * [11] M.A. Hanson, B. Mond, Convex transformable programming problems and invexity . Journal of Information & Optimization Sciences,1987, 8(2): 201-217(1987).
  * [12] P. Hartman, On functions representable as a difference of convex functions, Pac. J. Math. 9(3),707-713(1959).
  * [13] L. Hascot, S. Hossain, T. Steihaug, Structure in Optimization: Factorable Programming and Functions . E. Gelenbe and R. Lent (eds.), Computer and Information Sciences III, 449 DOI: 10.1007/978-1-4471-4594-3-46, Springer-Verlag London 2013.
  * [14] T.T. He,M. Tawarmalani, A new framework to relax composite functions in nonlinear programs. Mathematical Programming,online(2020),https://doi.org/10.1007/s10107-020-01541-x
  * [15] M. Hirschberger, Connectedness of efficient points in convex and convex transformable vector optimization. Optimization: A Journal of Mathematical Programming and Operations Research,54(3):283-304(2005).
  * [16] L. Hours, C. Jones, A parametric multiconvex splitting technique with application to real-time NMPC. In 53rd IEEE Conference on Decision and Control, 2014, 5052-5057.
  * [17] Y.K. Huang, H.W. Liu,Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization , Computional Optimization and Application, 65:671-698(2016).
  * [18] H. Ichihara, E. Nobuyama, Difference of multiconvex relaxation of parameterized LMIs: Control applications. SICE 2003 Annual Conference, 2003,ieeexplore.ieee.org
  * [19] R.H.F. Jackson, G.P. Mccormick, Second-Order Sensitivity Analysis In Factorable Programming - Theory And Applications, . Mathematical Programming, 41(1)1-27(1988).
  * [20] R.H.F. Jackson,Factorable Programming in Encyclopedia of Operations Research and Management Science . 2013 Editors: Saul I. Gass, Michael C. Fu, First Online: 23 January 2016, DOI: https://doi.org/10.1007/978-1-4419-1153-7-328
  * [21] A. Khajavirad, J.J. Michalek,N.K. Sahinidis,Relaxations of factorable functions with convex-transformable intermediates, Mathematical Programming. 144:107-140(2014).
  * [22] G.P. McCormick, Computability of global solutions to factorable nonconvex programs: part I-convex underestimating problems, Mathematical Programming. 10, 147-175(1976).
  * [23] M. Mohri, A. Rostamizadeh, A. Talwalkar, Foundations of Machine Learning. The MIT Press Cambridge, Massachusetts, London, England(2012)
  * [24] J.X.D.C. Neto, O.P. Ferreira, L.R.L Perez, S.Z. Nemeth,Convex and Monotone Transformable Mathematical Programming Problems and a Proximal-Like Point Method. Journal of Global Optimization. 35:53-69(2006).
  * [25] C.J. Nohra, N.V. Sahinidis, Global optimization of nonconvex problems with convex-transformable intermediates, Journal of Global Optimization, 72:255-276(2018).
  * [26] X. Shen, S.Diamond, M. Udell, Y. Gu, Disciplined multi-convex programming, Control And Decision Conference (CCDC), Chongqing, Chinese, 2017, ieeexplore.ieee.org, DOI: 10.1109/CCDC.2017.7978647.
  * [27] H.D. Sherali, H.J. Wang, Global optimization of nonconvex factorable programming problems . Mathematical Programming. 89, 459-478(2001).
  * [28] F. Serrano, Intersection Cuts for Factorable MINLP, A. Lodi and V. Nagarajan (Eds.): IPCO 2019, LNCS 11480, pp. 385-398, https://doi.org/10.1007/978-3-030-17953-3-2
  * [29] S.Suh, S. Shin, J. Lee, C.K. Reddy, J. Choo, Localized user-driven topic discovery via boosted ensemble of nonnegative matrix factorization. Knowledge and Information Systems, 2018, https://link.springer.com/article/10.1007/s10115-017-1147-9.
  * [30] M. Tawarmalani, N.V. Sahinidis,Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming. 99, 563-591(2004).
  * [31] H.A.L. Thi, T.P. Dinh, DC programming and DCA: thirty years of developments. Math. Program., Ser. B (2018) 169:5-68.
  * [32] L.S. Zhang, C,K. Ng, D. Li, W.W. Tian, A New Filled Function Method for Global Optimization, Journal of Global Optimization, 28: 17-43(2004).