{'fraction_non_alphanumeric': 0.05730769230769231, 'fraction_numerical': 0.015256410256410256, 'mean_word_length': 4.128862590401052, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the minimal distance between two surfaces

This article revisits previous results presented in Optimization which were challenged later by Voisei and Zalinescu (V-Z) in the same journal. We aim to use the points of view of V-Z to modify the original results and highlight that the consideration of the so called Gao-Strang total complementary function is indeed quite useful for establishing necessary conditions for solving this problem.


Introduction and Primal Problem
Minimal distance problems between two surfaces arise naturally from many applications, which have been recently studied by both engineers and scientists (see [13,15]). In this article, the problem presents a quadratic minimization problem with equality constraints: we let x := (y, z) and (P) : min Π(x) = 1 2 y − z 2 : h(y) = 0, g(z) = 0 , where h : IR n → IR and g : IR n → IR are defined by h(y) := 1 2 y t Ay − r 2 , are disjoint such that if z ∈ Z c then h(z) > 0. For example, it can be proved that if c = 0, r > 0, η > 0.5r 2 and f < 0.5(0.5r 2 − η) 2 /r then, Y c ∩ Z c = ∅ and if z ∈ Z c then h(z) > 0. Notice that the feasible set X c = Y c × Z c ⊂ IR n × IR n , defined by X c = {x ∈ IR n × IR n : h(y) = 0, g(z) = 0}, is, in general, non-convex. By introducing Lagrange multipliers λ, µ ∈ IR to relax the two equality constraints in X c , the classical Lagrangian associated with the constrained problem (P) is L(x, λ, µ) = 1 2 y − z 2 + λh(y) + µg(z).
Due to the non-convexity of the constraint g, the problem may have multiple local minima. The identification of the global minimizer has been a fundamentally difficult task in global optimization. The canonical duality theory is a newly developed, potentially useful methodology, which is composed mainly of (i) a canonical dual transformation, (ii) a complementary-dual principle, and (iii) an associated triality theory. The canonical dual transformation can be used to formulate dual problems without duality gap; the complementary-dual principle shows that the canonical dual problem is equivalent to the primal problem in the sense that they have the same set of KKT points; while the triality theory can be used to identify both global and local extrema. In global optimization, the canonical duality theory has been successfully used for solving many non-convex/non-smooth constrained optimization problems, including polynomial minimization [3,6], concave minimization with inequality constraints [5], nonlinear dynamical systems [17], nonconvex quadratic minimization with spherical [4], box [7], and integer constraints [1].
In the next section, we will show how to correctly use the canonical dual transformation to convert the non-convex constrained problem into a canonical dual problem. The global optimality condition is proposed in Section 2. Applications are illustrated in Section 3. The global minimizer is uniquely identified by the triality theory proposed in [2].

Canonical dual problem
In order to use the canonical dual transformation method, the key step is to introduce a so-called geometrical operator ξ = Λ(z) and a canonical function V (ξ) such that the non-convex function in g(z) can be written in the so-called canonical form W (z) = V (Λ(z)). By the definition introduced in [2], a differentiable function V : V a ⊂ IR → V a * ⊂ IR is called a canonical function if the duality relation ς = DV (ξ) : V a → V a * is invertible. Thus, for the non-convex function defined by (5), we let then the quadratic function V (ξ) := 1 2 α(ξ − η) 2 is a canonical function on the domain V a = {ξ ∈ IR : ξ ≥ 0} since the duality relation is invertible. By the Legendre transformation, the conjugate function of V (ξ) can be uniquely defined by It is easy to prove that the following canonical relations Through this total complementary function, the canonical dual function can be defined by Let the dual feasible space S a be defined by where I ∈ IR n×n is the identity matrix. Then the canonical dual function Π d is well defined by (9). In order to have the explicit form of Π d , we need to calculate Therefore, where x(λ, µ, ς) is given by (11).
The stationary points of the function Ξ play a key role in identifying the global minimizer of (P). Because of this, let us put in evidence what conditions the stationary points of Ξ must satisfy: The following result can be found in [19]. Their proof will be presented for completeness.
Following the canonical duality theory, in order to identify the global minimizer of (P), we first need to look at the Hessian of Ξ: Proof : Since (λ,μ,ς) ∈ S + a , it is clear thatx ∈ X c and is the only global minimizer of Ξ(·,λ,μ,ς). From (7), notice that V is a strictly convex function, therefore V * (ς) = sup{ξς − V (ξ) : ξ ≥ 0} and in particular, Ξ(x,λ,μ,ς) = L(x,λ,μ). Suppose now that there exists x ′ ∈ X c \ {x} such that we would have the following: but because of (19) this is equivalent to This contradicts the fact thatx is the only global minimizer of Ξ(·,λ,μ,ς), therefore, we must have that Remark 1 : Notice that Theorem 2.3 ensures that a stationary point in S + a will give us the only solution of (P). Therefore, the existence and uniqueness of the solution of (P) is necessary in order to find a stationary point of Π d in S + a . From this it should be evident that the examples provided in [19] does not contradict any of the results established under the new conditions of Theorems 2.2 and 2.3. It is a conjecture proposed in [7] that in nonconvex optimization with box/integer constraints, if the canonical dual problem does not have a critical point in S + a , the primal problem could be NP-hard.

Numerical Results
The graphs in this section were obtained using WINPLOT [14].
To put in evidence that this stationary point is in fact in S + a , notice that the eigenvalues of A are given by: . respectively. Finally, the global minimizer of (P) is given by Equation (11): 3.3. Example given in [19] Let n = 2, α = η = 1, c = (1, 0), f = √ 6 96 , 0 , r = 1 and A = I. As it was pointed out in [19], there are no stationary points in S + a . Under the new conditions of Theorem 2.3, this is expected since the problem has more than one solution (see figure 3). The following was found ( [19]) to be one of the global minimizers of (P):  Figure 3.: Example given in [19] Notice that S a and S + a are defined as in Equations (20) and (21). In order to solve this problem, we will introduce a perturbation. Instead of the given f , we will consider f n = Remark 1 : The combination of the linear perturbation method and canonical duality theory for solving nonconvex optimization problems was first proposed in [18] with successful applications in solving some NP-complete problems [20]. High-order perturbation methods for solving integer programming problems were discussed in [8].  Figure 4.: Perturbations of Example given in [19], n = 64 to the left and n = 100000 to the right.

Concluding remarks and future research
• The total complementary function (Equation (8)) is indeed useful for finding necessary conditions for solving (P) by means of the Canonical Duality theory.
• The examples presented in [19] do not contradict the new conditions and results presented here. • As stated by Theorem 2.3, in order to use the canonical dual transformation a necessary condition is that (P) has a unique solution. The question if this condition is sufficient remains open. • The combination of the perturbation and the canonical duality theory is an important method for solving nonconvex optimization problems which have more than one global optimal solution. • Finding a stationary point of Π d in S + a is not a simple task. It is worth to continue studying this problem in order to develop an efficient algorithm for solving challenging problems in global optimization.