Robust DC optimization and its application in medical image processing

Abstract

BACKGROUND:

Many medical image processing problems can be translated into solving the optimization models. In reality, there are lots of nonconvex optimization problems in medical image processing.

OBJECTIVE:

In this paper, we focus on a special class of robust nonconvex optimization, namely, robust optimization where given the parameters, the objective function can be expressed as the difference of convex functions.

METHODS:

We present the necessary condition for optimality under general assumptions. To solve this problem, a sequential robust convex optimization algorithm is proposed.

RESULTS:

We show that the new algorithm is globally convergent to a stationary point of the original problem under the general assumption about the uncertain set. The application of medical image enhancement is conducted and the numerical result shows its efficiency.

Keywords

Medical image processing robust nonconvex optimization sequential robust convex optimization algorithm medical image enhancement

1. Introduction

Nowadays, medical image processing can effectively assist doctor to diagnoses illness. However, as depicted in Fig. 1, many medical images are blurred in the clinic. In order to obtain the clear image, as shown in Fig. 2, it is necessary to deal with the uncertain and blurred medical image. In fact, many medical image processing problems, such as medical image denoising, medical image segmentation and medical image registration, can be transformed into the optimization problem. Therefore, the modeling and solving of optimization problem plays an important role in medical image processing and analysis.

Many optimization models and heuristic algorithms have been proposed to deal with medical image processing problem. Chen and Chi illustrate the theory and algorithms of convex optimization for solving low-rank matrix estimation in medical imaging [1]. Chen et al. reconstruct convex energy function to improve the robustness and efficiency in magnetic resonance images [2]. Liu et al. propose a weighted variational model for selective medical image segmentation [3]. Rundo et al. introduce the Med Genetic Algorithm to improve the appearance and the visual quality of medical imaging [4]. Zha et al. present the method of non-convex weighted nuclear norm minimization, and apply it to the field of image restoration [5]. Recently, a nonconvex optimal idiom neighbor algorithm is used to solve a class of nonconvex optimization problems, and has made important progress in the field of image denoising [6].

The optimization theories and heuristic algorithms mentioned above are very useful for tackling the medical image processing problems. However, to deal with practical medical image processing problems, there are still some issues needed to be further improved based on the following two reasons: (1) In the extant medical image processing problems, the optimal control parameters of medical image processing models are assumed to be exactly known before. They are usually be acquired through clinical experience and subjective judgment of doctors. However, in the practical medical image processing problems, it is difficult to obtain the control parameters of each medical image processing models. The control parameters of these models are often uncertain. (2) In most medical models, the objective functions are usually convex. In practice, however, we often encounter nonconvex problems among medical image processing, especially in medical image restoration. Thus, medical models of nonconvex optimization problems should be built. And a new method to solve the nonconvex optimization problems would be proposed under the uncertain control parameters situation.

Figure 1.

The blurred image.

Figure 2.

The optimized image.

Based on these two reasons, this paper considers a special class of robust nonconvex optimization, namely, robust optimization where given the parameters, the objective function can be expressed as the difference of convex functions. We call it robust DC optimization (RDCO). Since there are many cases in medical image processing problem that need to deal with the special uncertain nonconvex problem. For instance, non-convex optimization is gradually applied to medical image restoration and medical image denoising [7, 8]. Several approaches have been proposed for robust nonconvex optimization. For example, Bertsimas et al. propose two efficient methods for unconstrained and constrained robust nonlinear optimization problems respectively [9, 10]; Houska and Diehl present a solution method by sequential convex bilevel programming [11]; Soleimanian and Jajaei discuss the solution for robust nonlinear optimization with a conic representable uncertainty set [12]. However, to the best of our knowledge, there is no research on RDCO using the special DC structure of the underlying problem.

In this paper, we aim to develop optimality conditions, computational algorithm and some applications for this problem. The key contributions of this paper are as follows. We present a new concept-robust critical point which helps to give a solution method. Then necessary optimality conditions are developed. We propose a new method to solve the RDCO via sequential robust convex optimization. We prove that the new method is globally convergent to a robust critical point. We demonstrate the usefulness of the proposed method to multi-objective medical image processing problem.

The rest of this paper is organized as follows. Section 2 develops the necessary optimality conditions. Section 3 details the computational methods and the global convergence of the proposed method is presented. Section 4 discusses the applications for the proposed method. Section 5 concludes the paper.

2. Optimality conditions for generalized RDCO

We investigate a robust nonconvex optimization model, it is showed as the difference of convex functions that were presented in many researchers’ study [13, 14, 15, 16]. Hoai and Tao use the difference of convex functions programming and DC algorithm to conduct image restoration [8]. Consider the following optimization problem with the difference of convex objective functions (DC optimization),

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n}}\{{f(x,w):=w^{T}(\phi(x)% -\psi(x)):\text{ s.t. }x\in S}\}$ (1)

where $w\in\mathbb{R}_{+}^{m}$ is an uncertainty parameter, $\phi,\psi:\mathbb{R}^{n}\to\mathbb{R}^{m}$ , functions $\phi_{j}$ , $\psi_{j}$ , $j\in I:=\{1,\cdots,m\}$ , in Eq. (1) defined on $\mathbb{R}^{n}$ with their values in the extended real line $\bar{\mathbb{R}}:=\mathbb{R}\cup\{\infty\}$ are proper, continuously differentiable, and convex; the set $S\subset\mathbb{R}^{n}$ is compact and convex. To deal with the uncertainty in Eq. (1), a popular methodology is robust optimization which assumes that the uncertainty $w$ lies in a given compact uncertainty set $W\subset\mathbb{R}_{+}^{m}$ . Then the following minmax formulation is developed,

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n}}\mathop{\max}\limits{}_{% w\in W}\{{f(x,w)=w^{T}(\phi(x)-\psi(x)):\mbox{ s.t. }x\in S}\}$ (2)

In this paper, we aim to develop optimality conditions, computational algorithm and some applications for this problem. We call it robust DC optimization (RDCO). Note that if $W$ is arbitrarily chosen from $\mathbb{R}^{m}$ , then, given a large enough number $u$ and set $W:=ue+W$ , we have $W\subset\mathbb{R}_{+}^{m}$ . Here $e:=(1,\cdots,1)^{T}\in\mathbb{R}^{m}$ . Though RDCO has not attracted much attention in the literature, there are some interesting potential applications.

Example 2.1 Consider the following uncertain signomial geometric optimization form,

$\displaystyle(\textit{SGP}):\mathop{\min}\limits_{x\in\mathbb{R}_{++}^{n}}% \left\{{\sum_{t\in N_{+}}{\delta_{t}}\prod_{j=1}^{n}{x_{j}^{n_{ij}}}-\sum_{t% \in N_{-}}{\delta_{t}}\prod_{j=1}^{n}{x_{j}^{n_{ij}}}:x\in S}\right\}$ (3)

Where $\eta_{tj}$ is arbitrary real number, $\delta_{t}\in U_{t}\subset\mathbb{R}_{+},t\in I:=N_{+}\cup N_{-}$ is an uncertain parameter and $U_{t}$ is compact and convex. Signomial geometric programming has been used in various fields, including circuit design, information theory, power control of wireless communication network, and queue proportional scheduling in fading broadcast channels, since the late 1960s [17, 18]. If let $y_{j}=\ln x_{j},\forall j\in I$ , the above problem can be cast into the following RDCO problem,

$\displaystyle\mathop{\min}\limits_{y\in\mathbb{R}^{n}}\mathop{\max}\limits_{% \delta\in\prod_{t\in N}{U_{t}}}\left\{{\sum_{t\in N_{+}}{\delta_{t}}\exp\left(% {\sum_{j=1}^{n}{\eta_{tj}}y_{j}}\right)-\sum_{t\in N_{-}}{\delta_{t}}\exp\left% ({\sum_{j=1}^{n}{\eta_{tj}}y_{j}}\right):y\in\bar{S}}\right\}$ (4)

Example 2.2 Consider the following multi-criteria DC program,

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n}}\{f(x):=\phi(x)-\psi(x),% \text{ s.t. }x\in S\}$ (5)

where $\phi$ , $\psi$ and $S$ are defined as in Eq. (1). This problem has wide applications and many researchers have begun to study this problem [19]. For example, Gadhi et al. discuss optimality conditions for DC vector optimization [20]. Qu et al. present optimality conditions and duality theorems for a special class of multi-objective DC optimization [21]. To optimize the portfolio selection with higher moments, Dinh and Niu propose a multi-objective DC programming approach [22]. Suppose the weights $w\in\mathbb{R}_{+}^{m}$ lie in a given compact and convex set $W\subset\{w\in\mathbb{R}_{+}^{m}|||w||_{1}=1\}$ . Then Hu and Mehrotra [23] proposed the following robust weighted multi-criteria model,

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n}}\mathop{\max}\limits_{w% \in W}\{w^{T}f(x)=w^{T}(\phi(x)-\psi(x)),\text{ s.t. }x\in S\}.$ (6)

We now discuss the optimality conditions for generalized RDCO, which can be given in the following form,

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n}}\mathop{\max}\limits_{w% \in C(x)}\{g(x)+h(x)+\phi(x,w)-\psi(x,w):\text{ s.t. }x\in S\},$ (7)

where $g,h:\mathbb{R}^{n}\to\mathbb{R}$ are convex and continuously differentiable and $\phi,\psi:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$ satisfy,

for any given $w,\phi$ and $\psi$ are proper, convex and lower semicontinuous with respect to $x$ ;

for any given $x,\phi$ and $\psi$ are not only twice differentiable with respect to $w$ but also concave and convex with respect to $w$ respectively.

The second condition implies that $\phi(x,\cdot)-\psi(x,\cdot)$ is concave about $w$ . In this section, we assume that, for any $x,C(x)$ is compact and convex. We also define that $C(x):=\{w\in\mathbb{R}^{m}|c({x,w})\leqslant 0\}$ , where the function $c:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}^{p}$ is assumed to be twice continuously differentiable and component-wise convex with respect to $w$ (for any $x$ ). When $g(x)$ and $h(x)$ are constant functions, $\phi(x,w):=w^{T}\phi(x)$ , $\psi(x,w):=w^{T}\psi(x)$ and $C(x):=W$ , then Eq. (7) reduces to Eq. (1), where $\phi,\psi$ and $W$ are defined as in Section 1. Therefore, Eq. (7) is an extension of Eq. (1) and is called generalized RDCO.

Definition 2.1 If a point $(x^{*},w^{*})$ satisfies

$w^{*}$ is a global maximizer of the function $\phi(x^{*},\cdot)-\psi(x^{*},\cdot)$ ;

$x^{*}$ is a local minimizer of Eq. (7), i.e., there is an open neighborhood $D_{x}$ of $x^{*}$ such that

$\displaystyle g(x^{*})+h(x^{*})+\phi(x^{*},w^{*})-\psi(x^{*},w^{*})\leqslant g% (x)+h(x)\mathop{\max}\limits_{w\in C(x)}\{\phi(x,w)-\psi(x,w)\},$ $\displaystyle\forall x\in D_{x}\cap S,$

then $(x^{*},w^{*})$ is a local min-max point to Eq. (7).

Define the Lagrangian function of the lower level problem,

$\displaystyle L(x,w,\lambda):=g(x)+h(x)+\phi(x,w)-\psi(x,w)-\lambda^{T}c(x,w).$

Then for any given $x\in S$ , a maximizer $w$ of $\phi(x,w)-\psi(x,w)$ over $C(x)$ is equivalent to solving the following KKT system,

$\displaystyle\nabla_{w}L(x,w,\lambda)=\nabla_{w}\phi(x,w)-\nabla_{w}\psi(x,w)-% \nabla_{w}c(x,w)\lambda=0$ (8) $\displaystyle c(x,w)\leqslant 0,\lambda\geqslant 0,\lambda^{T}c(x,w)=0$ (9)

To propose the necessary optimality conditions, we need the following assumptions:

Assumption 2.1 For any given $x\in S\cap D_{x}$ , $\exists$ a maximizer $w(x)$ and a unique Lagrangian multiplier $\lambda(x)$ such that Eqs (8) and (9) hold. Further, both $w(x)$ and $\lambda(x)$ are differentiable in an open neighborhood $D_{x}$ of $x$ .

When the Mangasarian-Fromovitz constraint qualification (MFCQ) for the lower level maximization problems holds, the existence of the multipliers $\lambda$ can be guaranteed. In this case the KKT conditions Eqs (8) and (9) are both necessary and sufficient to guarantee that $w$ denotes the maximizers of the concave lower level problems. Under the stronger linear independence constraint qualification (LICQ) $\lambda$ is also unique. The differentiability of $w(x)$ and $\lambda(x)$ in an open neighborhood $D_{x}$ of $x$ can be deduced from the nondegenerate assumption about the maximizer $w$ of the lower level maximization problem in Eq. (7), which is also discussed in the context of generalized semi-infinite programming [24]. Actually, under the nondegenerate assumption, the primal and dual solution $\hat{w}(x)$ and $\hat{\lambda}(x)$ of the parameterized lower level problems Eq. (7) can be regarded as differentiable function in $x$ [25, 26].

Theorem 2.1 (Necessary optimality conditions) Suppose Assumption 2.1 holds and $({x^{\ast},y^{\ast}})$ with $x^{\ast}\in S\cap\textit{dom}\varnothing({\cdot,w^{\ast}})$ is a local min-max point to Eq. (7). Then $\exists\lambda\in\mathbb{R}^{p}$ such that the following conclusions hold,

$\displaystyle\partial_{x}\psi(x^{*},w^{*})\subset\nabla g(x^{*})+\nabla h(x^{*% })+\partial_{x}\phi(x^{*},w^{*})+\nabla_{x}c(x^{*},w^{*})\lambda+N(S;x^{*}),$ (10) $\displaystyle\nabla_{w}\phi(x^{*},w^{*})-\nabla_{w}\psi(x^{*},w^{*})-\nabla_{w% }c(x^{*},w^{*})\lambda=0,$ (11) $\displaystyle c({x^{\ast},w^{\ast}})\leqslant 0,\lambda\geqslant 0,\lambda^{T}% c({x^{\ast},w^{\ast}})=0,$ (12)

where $\partial_{x}\phi({x^{\ast},w^{\ast}})$ and $\partial_{x}\psi(x^{\ast},w^{\ast})$ denotes the subdifferential of $g$ and $h$ at $x^{\ast}$ for given $w^{\ast}$ in the sense of convex analysis, $N({S;x^{\ast}})$ is the normal cone to the convex set $S$ at $x^{\ast}$ .

Proof: We prove this theorem in the following two possible cases regarding $x^{\ast}\in S\cap\textit{dom}\varnothing({\cdot,w^{\ast}})$ : either $x^{\ast}\notin\textit{dom}\psi({\cdot,w^{\ast}})$ or $x^{\ast}\in\textit{dom}\psi({\cdot,w^{*}})$ . The first case leads to $\partial_{x}\psi({x^{*},w^{*}})=\varnothing$ , and hence Eq. (10) holds automatically. For the remaining case of $x^{*}\in\textit{dom}\psi({\cdot,w^{*}})$ , we can prove that for any $w\in C(x),x^{*}\in\textit{dom}({\cdot,w^{*}})$ . Actually, from the twice differentiability of the function $h(\cdot)$ and the compactness of $C(x)$ , there is a large enough positive number $B$ such that,

$\displaystyle|{\psi(x^{*},w)-\psi(x^{*},w^{*})}|\leqslant B\|{w-w^{*}}\|,% \forall w\in C(x).$

This means that $x^{*}\in\textit{dom}\psi(\cdot,w),\forall w\in C(x)$ .

From the convexity of $\psi(\cdot,w)$ , we have that for any $v\in\partial_{x}\psi({x^{*},w})$ the following inequality holds,

$\displaystyle\psi(x,w)-\psi(x^{*},w)\geqslant\langle{v,x-x^{*}}\rangle,\forall x% \in S.$

This suggests that the reference local min-max point to Eq. (7) is also a local min-maxpoint to the following robust convex program:

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n}}\mathop{\max}\limits_{w% \in C(x)}\{\tilde{f}(x,w):=g(x)+h(x)+\phi(x,w)-\psi(x^{*},w)-\langle{v,x-x^{*}% }\rangle:\text{ s.t. }x\in S\}.$ (13)

Since the objective function over $x$ in Eq. (13) is convex in $x$ , its local min-max point $({x^{\ast},w^{\ast}})$ is a global min-max point to this problem, i.e.,

$\displaystyle\tilde{f}({x^{\ast},w})\leqslant\tilde{f}({x^{\ast},w^{\ast}}),% \forall w\in C({x^{\ast}}),\tilde{f}({x^{\ast},w^{\ast}})\leqslant\mathop{\max% }\limits_{w\in C(x)}\tilde{f}({x,w}),\forall x\in S.$

From Assumption 2.1, an optimal solution of Eq. (13) is equivalent to the following optimization problem,

$\displaystyle\mathop{\min}\limits_{x\in D_{x}\cap S}\hat{L}({x,w(x),\lambda(x)% }),$ (14)

where

$\displaystyle\widehat{L}(x,w(x),\lambda(x)):=g(x)+h(x)+\phi(x,w(x))-\psi(x^{*}% ,w(x))-\langle{v,x-x^{*}}\rangle$ $\displaystyle\quad-\lambda(x)^{T}c(x,w(x)),$

$w(x)$ and $\lambda(x)$ are the parameterized primal-dual solution of the lower level maximization problems as a function of $x\in D_{x}$ , where $D_{x}$ is an open neighbourhood of $\forall x\in D_{x}$ . From the complementarity of the lower level maximization problem, it is obvious that $\forall x\in D_{x}$

$\displaystyle\phi(x,w(x))-\psi(x^{*},w(x))-\langle{v,x-x^{*}}\rangle=\phi(x,w(% x))-\psi(x^{*},w(x))-\langle{v,x-x^{*}}\rangle$ $\displaystyle\quad-\lambda(x)^{T}c(x,w(x)).$

According to Eqs (8) and (9), the following relation holds,

$\displaystyle\frac{d}{dx}\hat{L}({x,w(x),\lambda(x)})=\partial_{x}\hat{L}({x,w% ,\lambda}).$ (15)

This implies, $\exists\lambda\in\mathbb{R}^{p}$ such that the following conclusion holds,

$\displaystyle v\in\nabla g(x^{*})+\nabla h(x^{*})+\partial_{x}\phi(x^{*},w^{*}% )+\nabla_{x}c(x^{*},w^{*})\lambda+N(S;x^{*}),\forall v\in\partial_{x}\psi(x^{*% },w).$ (16)

Let $w:=w^{\ast}$ in Eq. (16) and we have that this theorem is true.

Theorem 2.1 considers the first order necessary condition for the generalized RDCO. Actually, the problem can be reduced to a generalized semi-infinite problem orbilevel problem with convex lower level problem. Therefore, the problem studied in this paper is similar with the DC semi-infinite problem studied in [25], where the objective function is a DC function subject to convex inequality constraints. The authors in [25] present the first order necessary condition for the studied problem, which is different from ours in that we study the different problem from theirs. Houska and Diehl [11] also propose the first order necessary condition for nonlinear robust optimization, which is different from ours in that the results in this paper rely on the special structure (i.e., the nonlinear function is a DC function) of the problem.

It is noted that a local min-max point $({x^{\ast},w^{\ast}})$ is difficult to use for devising the solution methods for Eq. (7). Therefore, we seek to find a robust critical point (or robust KKT point) point of Eq. (7), namely, find a point $({x^{\ast},w^{\ast}})$ satisfying Eqs (10)–(12). It follows from Theorem 2.1 that the necessary optimality conditions for problem Eq. (2) can be derived as follows.

Corollary 2.1 Under the same conditions as in Theorem 2.1, if $({x^{\ast},w^{\ast}})$ is a local optimal solution to Eq. (2), then

$\displaystyle\nabla_{x}\psi(x^{*})w^{*}\subset\nabla_{x}\phi(x^{*})w^{*}+N(S;x% ^{*});$ (17) $\displaystyle\psi(x^{*})-\phi(x^{*})\in N(W,w^{*}).$ (18)

3. Sequential robust convex optimization approach

In the above section, the necessary optimality conditions for RDCO is presented. This section proceeds to propose the solution approach for problem Eq. (1). An algorithm is proposed, using a sequential of robust convex optimization problems to approximate the original problem. The global convergence of the proposed algorithm is also discussed.

3.1 Algorithm SRCOA

We consider the following RDCO problem,

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n},t\in\mathbb{R}}g(x)+t,% \text{ s.t. }\mathop{\max}\limits_{w\in W}\{w^{T}(\phi(x)-\psi(x))\}+h(x)% \leqslant t,x\in S,$ (19)

where $g,h:\mathbb{R}^{n}\to\mathbb{R}$ is continuously differentiable and convex, sets $S$ and $W$ , and functions $\phi$ and $\psi$ are defined as in Eq. (2). In fact, the standard Eq. (2) can be reformulated as an instance of Eq. (19):

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n},t\in\mathbb{R}}t,\text{ % s.t. }\mathop{\max}\limits_{w\in W}\{w^{T}(\phi(x)-\psi(x))\}\leqslant t,x\in S.$

For simplicity, in what follows, we denote the feasible set of problem Eq. (19) as $\Omega$ . It is difficult to solve Eq. (19) directly since the nonconvexity of constraints. Therefore, we develop the following algorithm to solve Eq. (19), which uses a sequential of robust convex optimization problems to approximate the original problem.

Algorithm SRCOA

Step 0.

Initialization: Find a feasible solution $x_{0}\in\Omega$ and set $k:=0$ ;

Step 1.

Generate New Iteration: Solve the following problem to get its optimal solution $x_{k+1}$ .

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n},t\in\mathbb{R}}g(x)+t,% \text{ s.t. }\mathop{\max}\limits_{w\in W}\{\phi(x)-\tilde{\psi}(x,x_{k})\}+h(% x)\leqslant t,x\in S.$ (20)

where $\tilde{\psi}({x,x_{k}}):=\psi({x_{k}})+\nabla\psi({x_{k}})^{T}({x-x_{k}})$ ;

Step 2.

Termination Check: Stop if $x_{k+1}=x_{k}$ ;

Step 3.

Update: Set $k:=k+1$ and go to Step 1.

Remarks: 1. Due to the convexity of $\psi_{j},j\in I$ , for any given $x,y\in\mathbb{R}^{n}$ ,

$\displaystyle\tilde{\psi}_{j}({x,y})=\psi_{j}(y)+\nabla\psi_{j}(y)^{T}({x-y})% \leqslant\psi_{j}(x).$

The above inequality together with the positive of $w\in W$ implies that

$\displaystyle\mathop{\max}\limits_{w\in W}w^{T}({\phi(x)-\tilde{\psi}(x,y)})% \geqslant\mathop{\max}\limits_{w\in W}w^{T}({\phi(x)-\psi_{j}(x)}),\forall x,y% \in\mathbb{R}^{n}.$

Therefore if $x_{k}\in\Omega$ , then the optimal solution $x_{k+1}$ of Eq. (4) satisfies

$\displaystyle t\geqslant\mathop{\max}\limits_{w\in W}w^{T}({\phi(x_{k+1})-% \tilde{\psi}(x_{k+1},x_{k})})+h(x)\geqslant\mathop{\max}\limits_{w\in W}w^{T}(% {\phi(x_{k+1})-\psi_{j}(x_{k+1})})+h(x),$

which implies that $x_{k+1}$ is also feasible to Eq. (19), i.e., $x_{k+1}\in\Omega$ .

2. In the algorithm, at each iteration, a robust convex optimization problem is solved. When the function $\Phi$ has a special structure, Eq. (20) can be reduced to the known robust problem. For example, consider a special DC function with $\phi_{j},\forall j\in I$ , all linear with respect to $x$ . Then, Eq. (20) reduces to a robust linear optimization problem. Therefore, at each iteration, the algorithm only needs to solve a robust linear optimization problem. If $\phi_{j},\forall j\in I$ , are all convex quadratic with respect to $x$ , then Eq. (20) is a robust quadratic optimization problem.

3. If $x_{k}=x_{k+1}$ , then from Corollary 2.1 $x_{k+1}$ is a stationary point of Eq. (2).

3.2 Global convergence

In the following two lemmas, we show that the algorithm is well defined.

Lemma 3.1 If the starting point x0 is feasible to Eq. (19), then the sequence $\{{x_{k}}\}$ generated by Algorithm SRCOA is also feasible to Eq. (19), i.e., $x_{k}\in\Omega,\forall k$ .

Proof: The proof follows directly from remark 1 of Algorithm SRCOA.

Lemma 3.2 Suppose the sequence $\{{x_{k}}\}$ is generated by Algorithm SRCOA, then the function value sequence $\{{g({x_{k}})}\}$ is nonincreasing and convergent.

Proof: It is obvious that $x_{k}$ is feasible to Eq. (20). Therefore, $g({x_{k+1}})\leqslant g({x_{k}}),\forall k=0,1,2,\ldots$ . This implies that $\{{g({x_{k}})}\}$ is nonincreasing. As the set S is compact and g is continuous, $\{{g({x_{k}})}\}$ is bounded. Hence, convergence follows from the non-increase and boundedness of $\{{g({x_{k}})}\}$ .

Now we focus on analyzing the global convergence of Algorithm SRCOA. Clearly, problem Eq. (20) is a convex problem and Algorithm SRCOA only updates the variable. Hence, in the following, we need to show that Algorithm SRCOA globally converges to a KKT point of Eq. (21). We define

$\displaystyle\Theta:=\{(x,t)\in S\times\mathbb{R}|\mathop{\max}\limits_{w\in W% }w^{T}(\phi(x)-\psi(x))+h(x)\leqslant t\},$ $\displaystyle\Theta(z):=\{(x,t)\in S\times\mathbb{R}|\mathop{\max}\limits_{w% \in W}w^{T}(\phi(x)-\tilde{\psi}(x,z))+h(x)\leqslant t\}.$

To prove global convergence, we need the following assumption about Slater’s condition which has been extensively used as constraint qualifications in convex optimization [18].

Assumption 3.2 Slater’s condition holds at $z\in\Theta(z)$ if $\text{int}(\Theta(z))\neq\varnothing$ .

Theorem 3.1 Suppose Assumption 3.2 holds and Assumption 3 holds at any accumulation point of the sequence $\{x_{k}\}$ generated by Algorithm SRCOA for problem Eq. (19), then any accumulation point of this sequence is a KKT point of Eq. (19). Further, Ifg is strictly convex, then $\{x_{k}\}$ converges to a KKT point of Eq. (19).

Proof: Note that Algorithm SRCOA updates only the variable $x$ and Assumption 3.2 holds at any accumulation point of $\{x_{k}\}$ . The proof for this theorem is similar to the proof of Property 3 of Hong, Yang and Zhang [27].

4. Applications

This section presents an application for Algorithm SRCOA. For this purpose, we suppose the set $W$ is generated as follows. Since $W$ is a compact and convex setin $\mathbb{R}_{m}^{+}$ , without any loss of generality, suppose

$\displaystyle W:=\{{w\in\mathbb{R}^{m}|{w=\bar{w}+Cv,v\in{V}_{s}}.}\}$ (21)

where $\bar{w}$ is a reference point, $C$ is a coefficient matrix in $\mathbb{R}^{m\times l}$ , and ${V}_{s}$ is a subset of

$\displaystyle{V}:=\{{v\in\mathbb{R}^{l}|{0\leqslant\bar{w}+Cv\leqslant b}.}\},$ (22)

Where $b\in\mathbb{R}_{++}^{m}$ is a fixed vector. Suppose the perturbation set $V_{s}$ is represented as conic set,

$\displaystyle{V}_{s}=\{{v\in{V}|{u\in\mathbb{R}^{p}\text{ s.t. }Bv+Mu+c\in K}}\},$ (23)

With $K$ as a closed convex cone in $\mathbb{R}^{h}$ , ${B\in\mathbb{R}}^{h\times l}$ and ${M\in\mathbb{R}}^{h\times p}$ are fixed matrices, and ${c\in\mathbb{R}}^{h}$ is a fixed vector.

We first rewrite the condition $v\in{V}$ as a conic formulation $\tilde{C}v+\tilde{c}\in\tilde{K}$ , where

$\displaystyle\tilde{C}:=\left[{{\begin{array}[]{*{20}c}C\\ C\\ \end{array}}}\right],\tilde{c}:=\left[{{\begin{array}[]{*{20}c}{\bar{w}}\\ {\bar{w}}\\ \end{array}}}\right],$ (24)

and $\tilde{K}:=\{(v,\varsigma)\in\mathbb{R}^{l\times l}|\eta=v,b\geqslant v% \geqslant 0\}$ . Obviously, the dual cone of $\tilde{K}$ is

$\displaystyle{\tilde{K}}^{\ast}:=\{{({v,\theta})\in\mathbb{R}^{l\times l}|{v+% \theta\geqslant 0}}\}.$

Let us represent the inner maximization problem of Eq. (19) as

$\displaystyle\mathop{\max}\limits_{v,u}{\bar{w}}^{T}({\phi(x)-\psi(x)})+v^{T}C% ^{T}({\phi(x)-\psi(x)})$ $\displaystyle\text{s.t. }\tilde{C}v+\tilde{c}\in\tilde{K}$ (25) $\displaystyle Bv+Mu+c\in K.$

The corresponding dual problem is

$\displaystyle\mathop{\max}\limits_{y,z}{\bar{w}}^{T}({\phi(x)-\psi(x)})+{% \tilde{c}}^{T}z+c^{T}y$ $\displaystyle\text{s.t. }{\tilde{C}}^{T}z+B^{T}y=-C^{T}({\phi(x)-\psi(x)})$ $\displaystyle M^{T}y=0,z\in{\tilde{K}}^{\ast},y\in K^{\ast},$

where $K^{\ast}$ is the dual cone of $K$ . If we define,

$\displaystyle z:=\left[{{\begin{array}[]{*{20}c}{s-({\phi(x)-\psi(x)})}\\ \theta\\ \end{array}}}\right],$

Then

$\displaystyle\mathop{\max}\limits_{y,\chi}{\bar{w}}^{T}\chi+c^{T}y$ $\displaystyle\text{s.t. }C^{T}\chi+B^{T}y=0$ (26) $\displaystyle({\phi(x)-\psi(x)})-\chi\leqslant 0,$ $\displaystyle M^{T}y=0,y\in K^{\ast},$

where $\chi:=s+\theta$ . If $\exists\bar{v}\in{V}_{s}$ and $\bar{u}\in\mathbb{R}^{p}$ , s.t., $b>\bar{w}+C\bar{v}>0$ and $B\bar{v}+M\bar{u}+c\in\text{int}(K)$ , then problem Eq. (4) is equivalent to problem Eq. (4). Therefore, in this case we can transform problem Eq. (19) into the following convex optimization problem,

$\displaystyle\mathop{\min}\limits_{x\in\mathbb{R}^{n},y\in\mathbb{R}^{k},\chi% \in\mathbb{R}^{m}}g(x)+t,$ $\displaystyle\text{s.t. }\bar{w}^{T}\chi+c^{T}y+h(x)\leqslant t,$ $\displaystyle C^{T}\chi+B^{T}y=0,$ (27) $\displaystyle({\phi(x)-\psi(x)})-\chi\leqslant 0,$ $\displaystyle M^{T}y=0,y\in K^{\ast}.$

Figure 3.

The four goals for medical image enhancement.

4.1 Robust medical image enhancement optimization

In this section, we present a multi-objective model for multi-period medical image processing optimization. Usually, as depicted in Fig. 3, the medical image enhancement includes image denoising, sharpen edges of image, improving image clarity and image filtering. However, medical image denoising will result in blurring of the edges and contour of medical image. In order to eliminate such adverse effect, medical image sharpening technology is needed to make the edges clear. Meanwhile, medical image enhancement also required to improve the clarity of the medical image locally or in whole. Medical image filtering can locally improve the image, and improving image clarity can optimize medical image in whole. In order to simultaneously achieve these four goals, we use this Algorithm SRCOA to deal with the problem of medical image enhancement. We first give some notations about four goals. For $i=1,\ldots,4$ , $t=1,\ldots,\tau$ , $x_{ti}\geqslant 0$ : expected level of medical image enhancement in goals $i$ at period $t$ , where $x_{ti}\geqslant 0,i=1,\ldots,4$ , $x_{t}:=(x_{t1},x_{t2},x_{t3},x_{t4})^{\tau}\in R^{n}$ : the group of the four goals at period $t$ ; $u_{ti}$ : the actual enhancement level of goal $i$ at period $t$ ; $u_{i}:=\sum_{t=1}^{\tau}u_{ti}$ : the final image enhancement level of goal $i$ at the whole periods; $u_{i}:=\sum_{t=1}^{\tau}E[u_{ti}]$ : the mean image enhancement level of goal $i$ at the whole planning periods; $\sigma_{ik}:=E[{({u_{i}-\mu_{i}})({u_{k}-\mu_{k}})}]$ : the covariance between $u_{i}$ and $u_{k}$ , $i,k=1,\ldots,4$ ; $s_{\textit{ijk}}:=E[{({u_{i}-\mu_{i}})({u_{j}-\mu_{j}})({u_{k}-\mu_{k}})}]$ : the co-skewness among $u_{i},u_{j}$ and $u_{k},i,j,k=1,\ldots,4$ ; $k:=E[{({u_{1}-\mu_{1}})({u_{2}-\mu_{2}})({u_{3}-\mu_{3}})({u_{4}-\mu_{4}})}]$ : the co-kurtosis among $u_{1},u_{2},\linebreak u_{3}$ and $u_{4}$ .

Where $\sigma_{ik}$ represents the comparison of the actual optimization rate of any two goals, and the smaller value indicates that the optimization rate between goal $i$ and $k$ is very close. Furthermore, $s_{\textit{ijk}}$ represents the co-skewness value of any three goals. The larger value of it, the earlier time reaches the average level for the image effect of each goals. And, $\kappa$ represents the co-kurtosis value of these four goals, and the higher this value indicates that the better optimization degree achieved by these four goals.

Under these notations, we focuses on minimizing the variance, and maximizing the expected return, the skewness and the kurtosis, i.e., the optimization aims at solving the following multi-objective model,

$\displaystyle\min f(x):=(-R(x),V(x),-S(x),-K(x))$

(28) $\displaystyle\text{s.t. }\sum_{i=1}^{4}{\sum_{t=1}^{T}{x_{ti}=1,x_{ti}% \geqslant 0,i=1,\cdots,4,t=1,\cdots,\tau.}}$

The reasons for choosing these four moments are that the kurtosis is undesirable while the positive skewness is desirable. Several other studies show that skewness and kurtosis are both important factors in the process of medical image enhancement. Therefore, for a more realistic medical image enhancement optimization model, skewness (third moment) and kurtosis (fourth moment) must be considered. Here the four moments of the medical image enhancement could be defined as follows:

$\displaystyle\textit{Mean}:R(x):=\sum_{i=1}^{4}{x_{i}\mu_{i}};$ $\displaystyle\textit{Kurtosis}:K(x):=\sum_{i,j,k,r=1}^{4}{\kappa_{\textit{ijkr% }}x_{i}x_{j}x_{k}x_{r}};$ $\displaystyle\textit{Skewness}:S(x):=\sum_{i,j,k=1}^{4}{s_{\textit{ijk}}x_{i}x% _{j}x_{k}};$ $\displaystyle\textit{Variance}:V(x):=\sum_{i,k=1}^{4}{\sigma_{ik}x_{i}x_{k}}.$

It is obvious that the above four moments as functions are all twice continuously differentiable with respect to $x$ . Therefore, it follows from the compactness of the constraint set of $x$ that there are four positive real numbers $\gamma_{p}$ , $p=1,2,3,4$ such that the following four functions are convex about the feasible solution $x$ of Eq. (4.1), i.e., functions $\frac{\gamma_{1}}{2}\|x\|^{2}+R(x)$ , $\frac{\gamma_{2}}{2}\|x\|^{2}+V(x)$ , $\frac{\gamma_{3}}{2}\|x\|^{2}-S(x)$ and $\frac{\gamma_{4}}{2}\|x\|^{2}-K(x)$ are all convex about the feasible solution $x$ of Eq. (4.1). This conclusion means that the four objective functions in Eq. (4.1) are all DC functions and they have the following DC decomposition,

$\displaystyle R(x)=\left({\frac{\gamma_{1}}{2}\|x\|^{2}+R(x)}\right)-\frac{% \gamma_{1}}{2}\|x\|^{2},$ $\displaystyle V(x)=\left({\frac{\gamma_{2}}{2}\|x\|^{2}+V(x)}\right)-\frac{% \gamma_{2}}{2}\|x\|^{2},$ $\displaystyle S(x)=\frac{\gamma_{3}}{2}\|x\|^{2}-\left({\frac{\gamma_{3}}{2}\|% x\|^{2}-S(x)}\right)\text{ and }$ $\displaystyle K(x)=\frac{\gamma_{4}}{2}\|x\|^{2}-\left({\frac{\gamma_{4}}{2}\|% x\|^{2}-K(x)}\right).$

From the definition of $R(x)$ and $V(x)$ , $\gamma_{1}$ and $\gamma_{2}$ can be as any positive number. The choice of $\gamma_{3}$ and $\gamma_{4}$ in the following numerical tests uses the methods given in [28]. We now use the robust weighted approach as described in Example 2 to the multi-objective DC model Eq. (4.1). The uncertain set W is given as Eqs (21)–(23), where

$\displaystyle\bar{\omega}:=(0.25,0.25,0.25,0.25)^{T}\in\mathbb{R}^{4},$ $\displaystyle\mathbb{V}:=\{v\in\mathbb{R}^{l}|\bar{\omega}+Cv\geqslant 0,e^{T}% (\bar{\omega}+Cv)=1\},$ $\displaystyle\mathbb{V}_{s}:=\{v\in\mathbb{V}|\|v\|_{1}\leqslant 1\},C\in% \mathbb{R}^{4\times l}.$

We solve this problem by Algorithm SRCOA with the start point $x_{0}:=(\frac{1}{4},\cdots,\frac{1}{4})^{T}\in\mathbb{R}^{n\tau}$ . In the numerical tests, we suppose that $\mu_{i}$ , $\kappa_{\textit{ijkr}}$ , $s_{\textit{ijk}}$ , and $\sigma_{ik}$ , $\forall i,j,k,r\in\{1,\cdots,4\}$ , are all stochastically generated in [0, 1] and every element of $C$ is stochastically generated from $\{-1,0,1\}$ . All codes are written in Matlab7.10 with built-in solver “fmincon” to solve the approximation problems. When there are multiple criteria in the process of medical image optimization, the numerical results are reported in Table 1, showing the iteration number (Iter) and the CPU (second) time. The numerical results show that the proposed algorithm is efficient for solving small-scale problems. This phenomenon is also highlighted by Hong, Yang and Zhang [27], i.e., the sequential convex approximation approach is efficient for solving small-scale problems. For this case, with the increase of the problem, the objective functions are becoming more complicated and the computation time for their values and gradients is becoming longer. While the method can only be efficient for small-scale problems, compared to other approaches in the literature, it has several advantages. First, it converges to a KKT point of RDCO problems theoretically compared with the methods proposed by Bertsimas, Nohadani and Teo [10]. Second, it proposes a new method for a special class of nonconvex robust optimization problems by using their special structure.

Table 1
Numerical results for Algorithm SRCOA

$n$ Iter CPU

5 2 6. 2259

10 5 51. 0672

15 14 71. 5

20 48 123. 8426

25 79 547. 8

5. Conclusion

$n$	Iter	CPU
5	2	6.	2259
10	5	51.	0672
15	14	71.	5
20	48	123.	8426
25	79	547.	8

In this paper, we study a special class of robust nonconvex optimization, robust DC optimization. By utilizing the special structure of the problem, a sequential robust convex optimization approach is proposed. The global convergence of the proposed algorithm is proved. To show the efficiency of the proposed algorithm, application of robust medical image enhancement optimization is presented. In future studies, it is interesting to generalize the idea in this paper to a general robust DC optimization, which implies that the problem is also decomposed as DC functions about the uncertain parameters.

Footnotes

Acknowledgments

We are grateful to the editors and the two anonymous referees. Their comments and suggestions have greatly helped us to improve this paper. This research has been supported by China Postdoctoral Science Foundation (2019M651540) and General Subject of Philosophy and Social Science Planning in Shanghai (2019BGL020).

Conflict of interest

The authors declare that no competing interests exist.

References

Chen

Chi

. Harnessing structures in big data via guaranteed low-rank matrix estimation. IEEE Signal Pro. Mag. 35(4) (2018), 14-31.

Chen

Zhao

Zhang

, et al. Automatic segmentation for brain MR images via a convex optimized segmentation and bias field correction coupled model. Magn. Reson. Imaging. 32(7) (2014), 941-955.

Liu

Zeng

. Weighted variational model for selective image segmentation with application to medical images. Pattern Recogn. 76 (2017), 367-379.

Leonardo

Andrea

Marco

, et al. MedGA. a novel evolutionary method for image enhancement in medical imaging systems. Expert Syst. with Applications. 119 (2019), 387-399.

Zha

Zhang

, et al. Non-convex weighted lp nuclear norm based ADMM framework for image restoration. Neurocomputing. 311 (2017), 209-24.

Ochs

Chen

Brox

, et al. iPiano inertial proximal algorithm for nonconvex optimization. Siam J Imaging Sci. 7(2) (2014), 1388-1419.

Chen

Feng

Ranftl

, et al. A higher-order MRF based variational model for multiplicative noise reduction. IEEE Signal Proc Let. 21(11) (2014), 1370-1374.

LTH

Dinh

. Difference of convex functions algorithms (DCA) for image restoration via a markov random field model. Optim Eng. 18(11) (2017), 1-34.

Bertsimas

Nohadani

Teo

. Nonconvex robust optimization forproblems with constraints. Informs J. Comput. 22(1) (2010), 44-58.

10.

Bertsimas

Nohadani

Teo

. Robust optimization for unconstrained simulation-based problems. Oper. Res. 58(1) (2010), 161-178.

11.

Houska

Diehl

. Nonlinear robust optimization via sequential convex bilevel programming. Math. Program. Ser. A. 142 (2013), 539-577.

12.

Soleimanian

Jajaei

. Robust nonlinear optimization with conicrepresentable uncertainty set. Eur. J. Oper. Res. 228 (2013), 337-344.

13.

Pham

. The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133 (2005), 23-46.

14.

Liu

Shen

. Multicategory ψ-learning. J. Am. Stat. Assoc. 101 (2006), 500-509.

15.

Liu

Shen

Doss

. Multicategory ψ-learning and support vector machine. J. Comput. Graph Stat. 14 (2005), 219-236.

16.

Neumann

Schnorr

Steidl

. Combined SVM-based feature selection and classification. Mach Learn. 61(1–3) (2005), 129-150.

17.

Hsiung

Kim

Boyd

. Tractable approximate robust geometric programming. Optim. Eng. 9 (2008), 95-118.

18.

Boyd

Kim

Patil

Horowitz

. Digital circuit sizing via geometric programming. Oper. Res. 53(6) (2005), 899-932.

19.

Goh

Souza

. Proximal point algorithms for multi-criteria optimization with the difference of convex objective functions. J. Optim. Theory Appl. 169(1) (2015), 280-289.

20.

Gadhi

Laghdir

Metrane

. Optimality conditions for D.C. vector optimization problems under reverse convex constraints. J. Global Optim. 33 (2005), 527-540.

21.

Goh

Souza

. Multiobjective DC programs with infinite convex constraints. J. Global Optim. 59 (2014), 41-58.

22.

Dinh

Niu

. An efficient DC programming approach for portfolio decision with higher moments. Comput. Optim. Appl. 50 (2011), 525-554.

23.

Mehrotra.

. Robust and stochastically weighted multiobjective optimization models and reformulations. Oper. Res. 60(4) (2012), 936-953.

24.

Robinson

. Strongly regular generalized equations. Math. Oper. Res. 5(1) (1980), 43-62.

25.

Dinh

Mordukhovich

Nghia.

TTA

. Subdifferentials of value functions and optimality conditions for DC and bilevel infinite and semi-infinite programs math. Program. Ser. B. 123 (2010), 101-138.

26.

Boyd

Vandenberghe

. Convex optimization, Cambridge University Press, Cambridge, UK, 2004.

27.

Hong

Yang

Zhang

. Sequential convex approximations to joint chance constrained programs: a monte carlo approach. Oper. Res. 59(3) (2011), 617-630.

28.

Zhang

Wang

. A global optimization using linear relaxation for generalized geometric programming. Eur. J. Oper. Res. 190 (2008), 345-356.