1

My question is as follows \begin{equation} \max_W\max_{D_k}D_kW \end{equation} where \begin{equation} D_k = ((x_{i}^{1}-x_{j}^{1})^{2},(x_{i}^{2}-x_{j}^{2})^{2},...(x_{i}^{n}-x_{j}^{n})^{2}) \end{equation}

$D_k$ is a $1 \times n$ vector and $W$ is an $n \times 1$ vector. We have $W > 0$ and $\sum w_i=1$.

$x_{i}, x_{j} \in X$ $X$ is a set of data points.

I wish to find a vector w that can maximize the value of the largest $D_kW$. This objective function aims to capture a $W$ that can make at least one pair of points $x_i$ and $x_j$ far away from each other.

I searched the web thoroughly and found a similar question like this problem. But it is different as it is a max operator inside a minimization objective function. it can be solved by introducing an auxiliary variable. However, for my question, if I should introduce an auxiliary variable, I would also need it to be as close to $\max_{D_k}(D_kW)$ as possible.

Community
  • 1
arescat
  • 11
  • I'm pretty sure $$\max_W \max_{D_k} f(W,D_k) = \max_{W,D_k} f(W,D_k) = \max_{D_k}\max_W f(W,D_k),$$ meaning you don't need to treat it specially in any way. – Jeff Snider Feb 04 '14 at 02:27
  • When you write $$\max_{D_k}$$ what is the free variable? Values of $x$, or $i$ and $j$, or something else? – Jeff Snider Feb 04 '14 at 04:12
  • the free variable are the i and j. I don't think the two max can be merged together. i.e. suppose $D_1$ is (0, 1) and $D_2$ is (1,0) and $W$ is ($w_1$, $w_2$). You can see, depending on W, the $\max_{D_k}D_kW$ could be either w1 or w2. – arescat Feb 04 '14 at 04:39
  • That just means there are two global minimizers. Your problem is symmetric w.r.t. $i$ and $j$, so you will always have (at least) two. – Jeff Snider Feb 04 '14 at 12:26
  • You also need to have some bound on $W$. In your example, assuming $x_0\ne x_1$, as $w_1\to\infty$ the objective grows without bound. – Jeff Snider Feb 04 '14 at 12:28
  • The bound of the $W$ is $W>0$ and $\sum w_i = 1$. Do you know some way to find the optimal value of $W$ to achieve the global optimal? currently, I am thinking of first fix $W$ and then find $D_k$. later use the $D_k$ to find a new $W$. Do this iteratively until $W$ doesn't change that much. – arescat Feb 04 '14 at 17:18
  • Your $D_k=\big((x_i^1-x_j^1)^2,\dotsc,(x_i^n-x_j^n)^2\big)$ has lots of redundant elements. The largest value will be in the first, last or second to last coordinate, the optimal $W=(1,0,0,\dotsc,0)$ or $W=(0,0,\dotsc,0,1)$ or $W=(0,0,\dotsc,0,1,0)$. I would try to reformulate the problem as $\max (x_i-x_j)^2$ or something similar and get rid of $D_k$. – Jeff Snider Feb 04 '14 at 18:04
  • To answer your question, I think this is a kind of mixed-integer problem. You could formulate a relaxation of it where $x(i)$ is a polynomial which takes the value $x_i$ at $i$. This may not be the best way, but it's what comes to mind first. – Jeff Snider Feb 04 '14 at 18:07

0 Answers0