2
$\begingroup$

Let $\mathcal{U} = \{ [x_1, ..., x_n] \in \mathbb{R}^n : 0 \leq x_i \leq 1\}$ be the unit hypercube and $C \in \mathbb{R}^n\setminus\mathcal{U}$ fixed. Let us consider the following problem $$ \max_{X \in \mathcal{U}} \hspace{0.5cm}\|X - C\|^2.$$

Is there a known polynomial algorithm to solve the above? We can assume that $\|C\|$ is large enough.

$\endgroup$
4
$\begingroup$

As $x_i\in[0,1]$ we just need to compare the values of the endpoints since $(x_i-c_i)^2$ is minimised at $x_i=c_i$. It is easy to see that $x_i=0$ gives the maximum whenever $c_i\ge1/2$ and $x_i=1$ otherwise.

Thus we can treat $x_i$ as binary variables for the purpose of maximisation (see In an integer program, how I can force a binary variable to equal 1 if some condition holds? for integer programming formulations).

$\endgroup$
6
$\begingroup$

This answers a comment by the OP, to explain why the other answers are correct. It is due to the following standard result.

A concave objective subject to compact convex constraints has a global minimum at an extreme of the constraints.

You're maximizing a convex objective, which is equivalent to minimizing the negative of the objective, which is concave. The constraints are compact (bounded feasible set) and convex, so the result applies. Extreme of the constraints has $x_i$ at 0 or 1. Hence the answers from the other posters follow.

$\endgroup$
2
  • 2
    $\begingroup$ To make a great answer even better, it might be worth noting that the problem is particularly simple when the constraint set is an axis-aligned (hyper)cuboid and the objective is (a monotone function of) the Euclidean distance to a fixed reference point, since (using the Pythagorean theorem) the $n$-dimensional optimization task can then be trivially split into $n$ independent one-dimensional tasks. $\endgroup$ – Ilmari Karonen Dec 2 '20 at 21:24
  • $\begingroup$ @Ilmari Karonen Yes, n vs $2^n$. $\endgroup$ – Mark L. Stone Dec 3 '20 at 2:33
3
$\begingroup$

The solution is given by $x_i= 0$ if $abs(c_i) > abs(c_i -1)$ else $x_i = 1$.

$\endgroup$
2
  • 1
    $\begingroup$ Is there a reference to this result, or it is just an exercise (that I am suppose to easily prove myself) ? $\endgroup$ – C Marius Dec 2 '20 at 9:35
  • $\begingroup$ @C Marius See my answer. $\endgroup$ – Mark L. Stone Dec 2 '20 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.