Finite Step Method for the Constrained Optimization Problem in Phase Contrast Microscopic Image Restoration

Theorem 1.

Let x^* ∈ Ω. Then x^* is a solution of problem (5) – (6) if and only if

Proof. Necessity. We construct a Lagrange function for problem (5) – (6)

where

Let x^* be a solution of the considered problem. We write the optimal condition for problem (5) – (6) at the point x^* using the Lagrange function. Then, there exists a number ${\text{λ}}_0^{\text{*}}$ and a vector ${\text{λ}}^{\text{*}}=\left({\text{λ}}_1^{\text{*}},\dots ,{\text{λ}}_{\text{n}}^{\text{*}}\right)$ such that the following condition holds

It is easy to show that this condition is equivalent in the following form

It is obvious that ${\text{λ}}_0^{\text{*}}>0$. If λ(*)=0, then ${\text{λ}}_0^{\text{*}}\ne 0$ and $\text{f'}\left({\text{x}}^{\text{*}}\right)\triangleq {\text{Cx}}^{\text{*}}-\text{d}=0$. Hence, condition (7) holds trivially. In this way, it is easy to obtain condition (7) in the case of λ^*≠0. Thus, we have established that conditions (7) and (9) are equivalent.

Sufficiency. By the convexity of function f(x), we have f(x)−f(x^*) ≥ (x−x^* )^T f′(x^*).

Given that f′ = (x^*)=Cx^*−d, this inequality becomes f(x)−f(x^*) ≥ x^T(Cx^*−d)−x^*T(Cx^*−d)

By virtue of condition (7), we obtain f(x) − f(x^*) ≥ 0 for all x ∈ Ω, which completes the proof.

By introducing the index set I(x)={i|x_i=0,1 ≤ i ≤ n}

at a point x ∈ Ω, then the optimality condition (7) for problem (5) – (6) can be reformulated as follows.

Theorem 2.

x^* is a solution for problem (5) – (6) if and only if

We define the auxiliary problem in the following form:

where I is a subset of indices {1,2,…,n}.

The following lemma establishes a connection between problems (5) – (6) and (11).

Lemma 2. If x^* is a solution for problem (5) – (6), then it becomes a solution to problem (11) for I = I(x^*).

Proof. If I(x^*) = ø, then it is obvious that x^* > 0, and theorem 2 implies that f′(x^*) = Cx^* − d = 0. On the other hand, x^* = C⁻¹d is a solution of (11). Thus, the assertion of the theorem holds in this case. Let I(x^*) ≠ ϕ. We write the Lagrange function for the problem (11)

where λ₀ ∈ ℝ and λ_I = {λ_j|j∈I} ∈ R^m(I) are Lagrange multipliers, m(I) is the cardinality of the set I, and m(I) = m(I(x^*)). As x^* is the solution of problem (5) – (6), then it satisfies condition (8), particularly for number j, such that j ∈ I(x^*)

We show that ${\text{λ}}_0^{\text{*}}>0$ holds in (12). Indeed, if ${\text{λ}}_0^{\text{*}}=0$, then (12) implies ${\text{λ}}_{\text{j}}^{\text{*}}=0$, ∀j ∈ I(x^*).

On the other hand, it is easy to see that ${\text{λ}}_{\text{j}}^{\text{*}}=0$, j ∉ I(x^*) according to condition (8). This contradicts condition ${\text{λ}}_0^{\text{*}}+\left|\right|{\text{λ}}^{\text{*}}\left|\right|>0$. In addition, it is easy to see that there exists a ${\text{λ}}_{\text{j}}^{\text{*}}$ such that ${\text{λ}}_{\text{j}}^{\text{*}}\ne 0$, j ∈ I(x^*). As

then by condition (10) we obtain

Combining conditions (12) and (13), we have

It is the necessary condition for the problem (11) with Lagrange multipliers $\left({\text{λ}}_0^{\text{*}},{\text{λ}}_{\text{I}}^{\text{*}}\right)=\left({\text{λ}}_0^{\text{*}},{\text{λ}}_{\text{j}}^{\text{*}}\right),\text{j}\in \text{I}\left({\text{x}}^{\text{*}}\right)$ at the point x^*. As problem (11) is convex, then (14) also becomes a sufficient condition. Consequently, the point x^* is the solution of problem (11), which completes the proof.

Before we consider the numerical method for solving problem (5) – (6), we introduce a definition for a stationary point.

Definition 1. v ∈ ℝⁿ is called a stationary point for problem (5) – (6) if v ∈ Ω and V is a solution of (11) for some I ⊂ {1,2,…,n}.

Proposition 1. There exists an FSM for solving problem (5) – (6).

Proof. As the set {1,2,…,n} has a finite number of subsets I, and the problem (11) has a unique solution by virtue of the strong convexity of the function f(x), then the number of stationary points of the problem (5) – (6) is finite. By Lemma 2, to find the solution of problem (5) – (6), it is sufficient to look through all of its stationary points and identify the one that minimizes the value of the function f(x). As problem (11) is an unconstrained minimization problem in the space ℝ^n−m(I), then this problem can be solved by the conjugate gradient method for a finite number of steps, which is less than n−m(I). Thus, finding the solution to problem (5) – (6) will finish in a finite number of steps.

In practice, of course, brute force methods for finding all the stationary points of problem (5) – (6) would require too much computation even for a value of n that is not very large. We introduce a more efficient iterative method to find stationary points of problem (5) – (6) compared with the brute force method. This method can be divided into two stages. The first stage involves moving from a feasible point x⁰ ∈ Ω to a stationary point x̅ ∈ Ω, such that f(x̅) ≤ f(x⁰). In the second stage, we check whether the stationary point x̅ has become a solution to problem (5) – (6), and if not, we find a feasible point x̃, such that f(x̃) < f(x̅).

As a result, we construct a sequence of stationary points, such that the function f(x) is strictly decreasing, and it is therefore impossible to return to a stationary point obtained previously. Since the number of stationary points is finite, when the process of generating the sequence terminates, the current stationary point becomes a solution to problem (5) – (6). We consider these schemes in detail.

Scheme 1. Moving from a feasible point to a stationary point.

Let x⁰ ∈ Ω be a given point. We need to find a stationary point x̅, such that f(x̅) ≤ f(x⁰). For this purpose, we construct a sequence x^k ∈ Ω, k = 1,2,… and x̅^k ∈ ℝⁿ, k = 0,1,2,… as follows. Assume that x^k ∈ Ω has already been built for a given k = 0,1,…, then we take the solution of problem (11) as x̅^k, which is solved by the conjugate gradient method at I = I_k = I(x^k).

Note that

as x^k ∈ Ω _I.

There are two possible cases: x ̅ ^k ∈ Ω or x̅^k ∉ Ω. If x̅^k ∈ Ω, then by definition x^k is a stationary point of problem (5) – (6). Let x̅^k ∉ Ω. Then, we construct a point

where parameter λ_k is determined from the following condition

and obviously, λ_k ≠ 1.

Using the definition of Ω in problem (5) – (6) and definition (17), we can find an explicit formula to calculate the parameter λ_k.

Indeed, from definition (17), we have

or

Hence, we obtain $\left({\text{x}}_{\text{i}}^{\text{k}}-{\text{x̅}}_{\text{i}}^{\text{k}}\right)\le {\text{x}}_{\text{i}}^{\text{k}},\text{i}=1,2,\dots ,\text{n}$. This inequality holds trivially for all i ∈ I(x^k), as ${\text{x}}_{\text{i}}^{\text{k}}={\text{x̅}}_{\text{i}}^{\text{k}}=0$. We define the index set ${\text{I}}_1^{\text{k}}$

As x̅^k ∉ Ω, there exists a number j ∈ {1,2,…,n}\I(x^k), such that . Furthermore, . Hence, ${\text{I}}_1^{\text{k}}\ne \varnothing$. Then, it is easy to see that λ_k is defined as

It is obvious that 0 < λ_k < 1. By construction of the sequence {x^k}, we have x^k+1 ∈ Ω. On the other hand, taking into account (15) and the convexity of f(x), we conclude that

Verify that I(x^k) ⊂ I(x^k+1), I(x^k) ≠ I(x^k+1). Indeed, if i ∈ I(x^k), then ${\text{x̅}}_{\text{i}}^{\text{k}}=0={\text{x}}_{\text{i}}^{\text{k}}$, and therefore, ${\text{x}}_{\text{i}}^{\text{k}+1}=0$, i.e., i ∈ I(x^k+1). On the other hand, it is clear that ${\text{x}}_{{\text{j}}_0}^{\text{k}+1}=0$, and therefore, j₀ ∈ I(x^k+1), but j₀∉I(x^k+1). Consequently, the set I(x^k+1) contains at least one more element than I(x^k). Thus, the following approximation x^k+1 ∈ Ω is constructed, such that f(x^k+1) ≤ f(x^k) and the set I(x^k+1) is substantially wider than I(x^k).

However, the set I(x^k)) ⊂ {1,2,…,n} cannot expand infinitely. Therefore, the described process terminates at some k-th iteration, and x̅ = x̅^k is a stationary point of problem (5) – (6) when x̅^k ∈ Ω. Thus, by virtue of (15) and (18), we have f(x̅) ≤ f(x^k) ≤ f(x^k−1) ≤ … ≤ f(x⁰).

Note that if f(x̅) = f(x⁰), then the uniqueness of the solution of problem (11) for I = I(x⁰) implies x̅ = x⁰. Thus, x̅ = x⁰ or f(x̅) < f(x⁰).

Scheme 2. Check the optimality of the stationary point.

Let the stationary point x̅=x̅^k be obtained as the result of the previous scheme. It is necessary to check that x̅ is the solution of problem (5) – (6) or to find a point x̅⁰, such that f(x̅⁰) < f(x̅). For this purpose, we first need to check the optimal condition (7) at point x̅, i.e.,

If this condition holds, then we conclude that x̅ is a solution of the problem. Otherwise, we need to perform one iteration of the GPM [19], starting from the point x̅.

We construct the point x(α) as follows:

Then, the parameter α is determined from the condition

The number α ̅ >0, satisfying the inequalities f(Pr_Ω(x̅−(α̅)f′(x̅))) < f(x̅), can be found in a finite number of steps by checking these inequalities sequentially for α = λ^k, where k = 0,1,… and λ is a fixed number from (0,1) until it holds. After the number (α̅) is found, x̅⁰ = (Pr_Ω(x̅ − (α̅)f′(x̅)) will be constructed. In this way, we construct the FSM to solve the problem (5) – (6), as shown in Table 1.

Theorem 3.

The sequence {x̅^k}, k=0,1,2,… generated by the FSM converges to the solution of problem (5) – (6) in a finite number of steps.

The proof follows directly from the proof of theorem 2 and the construction of schemes 1 and 2.