On several results of Chandrasekaran-Tamir conjecture (Q1343415)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On several results of Chandrasekaran-Tamir conjecture |
scientific article |
Statements
On several results of Chandrasekaran-Tamir conjecture (English)
0 references
9 October 1995
0 references
Let \(a_ i\) \((1\leq i\leq m)\) be \(m\) points in \(\mathbb{R}^ n\), the \(n\)- dimensional Euclidean space, \(w_ i\) \((1\leq i\leq m)\) be \(m\) positive numbers, set \[ T(x)= \begin{cases} (\sum^ m_{j= 1} w_ j\| x- a_ j\|^{- 1}\cdot a_ j)\cdot(\sum^ m_{i= 1} w_ j\| x- a_ j\|^{- 1})^{- 1},\quad &\text{if } x\neq a_ j\;(1\leq j\leq m)\\ a_ j,\quad & \text{if } x = a_ j.\end{cases} \] In 1989, Chandrasekaran and Tamir presented the conjecture: if the dimension of the convex hull generated by \(a_ i\) \((1\leq i\leq m)\) equals \(n\), then the equation \(T(x)= a_ i\) has only finitely many solutions. Our paper obtains the following results for the \(C- T\) conjecture: let \(J= \{1,\dots, m\}\), \(A= \{a_ i,\;1\leq i\leq m\}\), \(B= \text{conv}(A)\), \(Q_ i= \{x\in \mathbb{R}^ n| T(x)= a_ i,\;x\not\in A\}\), \(\lambda_ i(x)= \left(\sum_{j\neq i,j\in J} w_ j\| x- a_ j\|^{- 1}\right)^{-1}\), \(f(x)= \sum_{j\in J} w_ j\| x- a_ j\|\), then Theorem 1. If \(\dim B= n\), then for all \(i\in J\), \(Q_ i\) is a compact set. Theorem 2. If \(\dim B= n\), then for all \(x, y\in Q_ i\) only one of the following cases holds. \hskip10mm (1) \(\| x- a_ i\|< \| y- a_ i\|\), \(f(x)< f(y)\), \(\lambda_ i(x)< \lambda_ i(y)\), \hskip10mm (2) \(\| x- a_ i\|> \| y- a_ i\|\), \(f(x)> f(y)\), \(\lambda_ i(x)> \lambda_ i(y)\). Suppose \(S(\alpha, z)= \{x\in \mathbb{R}^ n\mid w_ j\| x- a_ j\|^{- 1}= \alpha z_ j\), for all \(j\in J\backslash \{i\},\;\alpha> 0\}\). Theorem 3. If \(\dim B=n\), then for each positive solution \(z\) of \(\sum_{j\neq i} z_ i(a_ j- a_ i)= 0\), we have \(\left|\bigcup_{\alpha> 0} S(\alpha, z)\right|< 2\), where \(| S|\) denotes the number of elements in \(S\). As a corollary, we prove the \(C- T\) conjecture for \(m= n+ 2\). Corollary. If \(\dim B= n\) and \(m= n+ 2\), then \(| Q_ i|\leq 2\), for all \(i\in J\). The \(C- T\) conjecture originates from the Fermat-Weber facility location problem, the optimization problem (F): \(\min_{x\in \mathbb{R}^ n} f(x)\). In 1937, Weiszfeld presented a simple iterative algorithm for (F), i.e. \(x_{k+ 1}= T(x_ k)\). Kuhn proved the local convergence in the case that finite points are excepted, if \(a_ i\) \((1\leq i\leq m)\) are not collinear. But in 1989, Chandrasekaran and Tamir got an example to show that the solution set of \(T(x)= a_ i\) may be an unbounded continuously curvature and thus the above conclusion of Kuhn is not correct. However, by using the results in our paper, we can prove the local convergence.
0 references
Chandrasekaran-Tamir conjecture
0 references
Fermat-Weber facility location
0 references
local convergence
0 references