Using the support function for optimal shape design
1 Motivation
Led by problems of optimal placement and design of sensors, we are interested in considering the following shape optimization problem
\inf_{\omega\subset \Omega} d^H(\omega,\Omega), (1)
where d^H is the Hausdorff distance between \Omega and \omega defined as follows
d^H(\omega,\Omega):= \sup_{x\in \Omega} d(x,\omega),
with d(\cdot,\omega):= \inf_{y\in\omega}\|x-y\| is the distance from x to the set \omega.
Figure 1. The Hausdorff distance between the sensor \omega and the set \Omega
If no additional assumption on the sensor is assumed, the problem (1) does not admit a solution. In this post, we ask the sensor to be convex, which provides existence of optimal shapes as shown in the following proposition:
Proposition 1.1
Let \Omega\subset \R^n be a bounded set. The problem
\inf\{ J_\Omega(\omega)\ |\ \omega\ \text{is convex,}\ \omega\subset \Omega\ \text{and}\ |\omega|=\alpha |\Omega|\},
with \alpha\in (0,1], admits a solution.
Proof
Let (\omega_n) be a minimizing sequence of convex sets, i.e., such that |\omega_n|= \alpha |\Omega| and
\lim_{n\rightarrow +\infty} d^H(\omega_n,\Omega) = \inf_{\underset{\omega\subset \Omega}{|\omega|=\alpha |\Omega|}} d^H(\omega,\Omega).
Since all the convex sets \omega_n are included in the bounded set \Omega, we have by Blaschke selection Theorem [???] that there exists a convex set \omega^*\subset \Omega such that (\omega_n) converges up to a subsequence (that we also denote by (\omega_n)) to \omega^* with respect to the Hausdorff distance. Finally, by the continuity of the area with respect to the Hausdorff distance, we have
\omega^*| = \lim_{n\rightarrow +\infty} |\omega_n| = \alpha |\Omega|,
which ends the proof.
In the present post, we assume the box \Omega to be convex and make use of the classical properties of convex sets to propose an algorithm which computes the optimal sensor.
1.1 Classical definitions and lemmas
If \Omega is convex (not necessarily containing the origin), its support function is defined as follows:
h_\Omega:x\in \R^2\longmapsto \sup\{\langle x,y \rangle\ |\ y\in \Omega\}.</p> <p style="text-align: center;">[katex] Since the functions [katex]h_\Omega satisfy the scaling property h_\Omega(t x) = t h_\Omega(x) for t>0, it can be characterized by its values on the unit sphere \mathbb{S}^{1} or equivalently on the interval [0,2\pi]. We then adopt the following definition:
Definition 1.2
The support function of a planar bounded convex set \Omega is defined on [0,2\pi] as follows:
h_\Omega:[0,2\pi)\longmapsto \sup\left\{\left\langle \binom{\cos{\theta}}{\sin{\theta}}, y \right\rangle\ |\ y\in\Omega\right\}.
Figure 2. The Hausdorff distance between the sensor \omega and the set \Omega
The support function has some nice properties:
• It allows to provide a simple criterion of the convexity of \Omega. Indeed, \Omega is convex if and only if h_\Omega''+h_\Omega\ge 0 in the sense of distributions.
• It is linear for the Minkowski sum and dilatation. Indeed, if \Omega_1 and \Omega_2 are two convex bodies and \alpha, \beta >0, we have
h_{\alpha \Omega_1 + \beta \Omega_2}= \alpha h_{\Omega_1}+ \beta h_{\Omega_2},
see [2, Section 1.7.1].
• It allows to parametrize the inclusion in a simple way. Indeed, if \Omega_1 and \Omega_2 are two convex sets, we have
\Omega_1\subset \Omega_2\Longleftrightarrow h_{\Omega_1}\leq h_{\Omega_2}.
• It also provides elegant formulas for some geometrical quantities. Fro example the perimeter and the area of a convex body \Omega are given by
P(\Omega) = \int_0^{2\pi}h_\Omega(\theta)d\theta\ \ \ \text{and}\ \ \ |\Omega|= \frac{1}{2}\int_0^{2\pi} h_\Omega(\theta)(h_\Omega''(\theta)+h_\Omega(\theta))d\theta,
and the Hausdorff distance between two convex bodies \Omega_1 and \Omega_2 is given by
d^H(\Omega_1,\Omega_2)=\max_{\theta\in [0,2\pi]} |h_{\Omega_1}(\theta)-h_{\Omega_2}(\theta)|,
see [2, Lemma 1.8.14].
2 Description of the numerical method
2.1 Parametrization of the problem
We recall that if both \Omega and \omega are convex, we have the following characterization for the Hausdorff distance between \omega and \Omega,
d^H(\omega,\Omega)=\|h_\Omega-h_\omega\|_{\infty}:=\max_{\theta\in [0,2\pi]} |h_{\Omega_1}(\theta)-h_{\Omega_2}(\theta)|,
where h_\Omega and h_\omega respectively correspond to the support functions of the convex sets \Omega and \omega.
The use of the support function allows to transform the purely geometrical problem into the following analytical one:
\left\{\begin{matrix} \inf\limits_{h\in H^1_{\text{per}}(0,2\pi)} \|h_\Omega-h\|_{\infty},\\ h\leq h_\Omega,\\ h''+h\ge 0,\\ \frac{1}{2}\int_0^{2\pi} h(h''+h)d\theta = \alpha_0 |\Omega|. \end{matrix}\right. (2)
where H^1_{\text{per}}(0,2\pi) is the set of H^1 functions that are 2\pi-periodic.
In order to be able to perform numerical shape optimization, we have to retrieve a finite dimensional setting. The idea is to parametrize sets via Fourier coefficients of their support functions truncated at a certain order N\ge 1. Thus, we will look for solutions in the set
\mathcal{H}_N:= \left\{\theta\longmapsto a_0 + \sum_{k=1}^N \big(a_k \cos{(k\theta)}+ b_k\sin{(k\theta)}\big) \ \big|\ a_0,\dots,a_N,b_1,\dots,b_N\in \R\right\}.
This approach is justified by the following approximation proposition:
Proposition 2.1 ([2, Section 3.4])
Let \Omega\in \mathcal{K}^2 and \varepsilon>0. Then there exists N_\varepsilon and \Omega_\varepsilon with support function h_{\Omega_\varepsilon}\in \mathcal{H}_{N_\varepsilon} such that d^H(\Omega,\Omega_\varepsilon) \lt \varepsilon .
For more convergence results and application of this method for different problems, we refer to [1].
Thus, the infinitely dimensional problem (2) is approached by the following finitely dimensional problem.
\left\{\begin{matrix} \inf\limits_{(a_0,a_1,\dots,a_N,b_1,\dots,b_N)\in \R^{2N+1}} \max\limits_{\theta\in[0,2\pi]} h_\Omega(\theta) - a_0 - \sum\limits_{k=1}^N \big(a_k \cos{(k\theta)}+b_k\sin{(k\theta)}\big), \\ \forall \theta\in [0,2\pi], \ \ \ a_0+\sum\limits_{k=1}^N \big(a_k \cos{(k\theta)}+ b_k\sin{(k\theta)}\big)\leq h_\Omega(\theta), \\ \forall \theta\in [0,2\pi], \ \ \ h''+h\ge 0, \\ \frac{1}{2}\int_0^{2\pi} h(h''+h)= \alpha_0 |\Omega|. \end{matrix}\right.
Let M\in \N^*, we consider the regular subdivision (\theta_k)_{k\in \llbracket 1,M \rrbracket } of [0,2\pi], where \theta_k= \frac{2k\pi}{M}. The inclusion constraint h(\theta)\leq h_\Omega(\theta) and the convexity constraint h''(\theta)+h(\theta)\ge 0 are approximated by the following 2M linear constraints on the Fourier coefficients:
\forall k\in \llbracket1,M\rrbracket, \Bigg\{ \begin{array}{cc} a_0+\sum\limits_{j=1}^N \big(a_j \cos{(j\theta_k)}+ b_j\sin{(j\theta_k)}\big)\leq h_\Omega(\theta_k), \\ a_0+\sum\limits_{j=1}^N \big((1-j^2)\cos{(j\theta_k)}a_j + (1-j^2)\sin{(j\theta_k)}b_j \big) \ge 0. \end{array}
At last, straightforward computations show that the area constraint is equivalent to the following quadratic constraint:
\pi a_0^2 + \frac{\pi}{2} \sum\limits_{k=1}^N(1-k^2)(a_k^2+b_k^2)=\alpha_0 |\Omega|.
2.2 Computation of the gradients
A very important step in shape optimization is the computation of the gradients. In our case, the convexity and inclusion constraints are linear and the area constraint is quadratic (and thus its gradient is obtained by direct computations). Nevertheless, the computation of the gradient of the objective function is not straightforward as it is defined as a supremum. This is why we use a Danskin differentiation scheme to compute the derivative.
Proposition 2.2
Let us consider
g:(\theta,a_0,\dots,b_N)\longmapsto h_\Omega(\theta) - a_0 - \sum\limits_{k=1}^N \big(a_k \cos{(k\theta)}+b_k\sin{(k\theta)}\big)
and
j:(a_0,\dots,b_N)\longmapsto \max_{\theta \in [0,2\pi]} g(\theta,a_0,\dots,b_N).
The function j admits directional derivatives in every direction and we have
\frac{\partial j}{\partial a_0} = -1,
and for every k\in\llbracket 1,N \rrbracket,
\left\{\begin{matrix} \frac{\partial j}{\partial a_k} = \max\limits_{\theta^*\in \Theta} -\cos{(k \theta^*)}, \\ \frac{\partial j}{\partial b_k} = \max\limits_{\theta^*\in \Theta} -\sin{(k\theta^*)}, \end{matrix}\right.
where
\Theta:=\{\theta^*\in [0,2\pi]\ \ |\ \ G(\theta^*,a_0,\dots,b_N) = \max\limits_{\theta\in[0,2\pi]} G(\theta,a_0,\dots,b_N)\}.
Proof
Since the same scheme is followed for every coordinate, we limit our selves to present the proof for the fist coordinate a_0. In order to simplify the notations, we will write for every x\in \R, j(x) = j(a_0,\dots,a_{k-1},x,a_{k+1}\dots,b_N) and G(\theta,x) = G(\theta,a_0,\dots,a_{k-1},x,a_{k+1}\dots,b_N).
For every t\ge0, we denote by \theta_t\in[0,2\pi] a point such that
G(\theta_t,a_k+t) = j(a_k+t) = \max\limits_{\theta\in [0,2\pi]} G(\theta,a_k+t).
We have
j(a_k+t)-j(a_k)= G(\theta_t,a_k+t)-G(\theta_0,a_k) \ge G(\theta_0,a_k+t)-G(\theta_0,a_k)= -t \cos{(k \theta_0)}.
Thus,
\forall \theta_0\in \Theta,\ \ \ \liminf_{t\rightarrow 0^+} \frac{j(a_k+t)-j(a_k)}{t} \ge -\cos{(k \theta_0)},
which means that
\liminf_{t\rightarrow 0^+} \frac{j(a_k+t)-j(a_k)}{t} \ge \max\limits_{\theta_0\in \Theta}-\cos{(k \theta_0)}. (3)
Let us now consider a sequence (t_n) of positive numbers decreasing to 0, such that
\lim_{n\rightarrow +\infty} \frac{j(a_k+t_n)-j(a_k)}{t_n} = \limsup_{t\rightarrow 0^+} \frac{j(a_k+t)-j(a_k)}{t}.
We have for every n\ge 0,
j(a_k+t_n)-j(a_k)= G(\theta_{t_n},a_k+t_n)-G(\theta_0,a_k)\leq G(\theta_{t_n},a_k+t_n)-G(\theta_{t_n},a_k)=-t_n\cos{(k \theta_{t_n})}.
Thus,
\limsup_{t\rightarrow 0^+} \frac{j(a_k+t)-j(a_k)}{t} = \lim_{n\rightarrow +\infty} \frac{j(a_k+t_n)-j(a_k)}{t_n} \leq \limsup_{n\rightarrow +\infty}-\cos{(k\theta_{n})}=-\cos{(k\theta_{\infty})},
where \theta_\infty is an accumulation point of the sequence (\theta_n). It is not difficult to check that \theta_\infty \in \Theta. Thus, we have
\limsup_{t\rightarrow 0^+} \frac{j(a_k+t)-j(a_k)}{t} \leq \max\limits_{\theta_0\in \Theta}-\cos{(k \theta_0)}. (4)
By the inequalities (3) and (4) we deduce the announced formula for the derivative.
2.3 Numerical results
Now that we have parameterized the problem and computed the gradients, we are in position to perform shape optimization. We use the 'fmincon' Matlab routine. We consider a smooth set whose support function is given by
h_\Omega(t) = 9 + 0.1 \cos{t}-0.3\cos{2t} +0.2\cos{3t}-0.03\cos{4t}-0.1\cos{5t}+0.1\sin{t}-0.2\sin{2t} +0.1\sin{3t}-0.01\sin{4t}-0.01\sin{5t}.
and the area proportion \alpha_0\in \{0.01,0.1,0.4,0.7\}.
Figure 3. The optimal shape for \alpha_0\in \{0.01,0.1,0.4,0.7\}.
References
[1] P. R. S. Antunes and B. Bogosel. Parametric shape optimization using the support function. Comput. Optim. Appl., 82(1):107–138, 2022.[2] R. Schneider. Convex Bodies: The Brunn-Minkowski Theory. Cambridge University Press, 2nd expanded edition edition, 2013.
|| Go to the Math & Research main page
