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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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).

Improve this answer
$\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.

Improve this answer
$\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, 2020 at 21:24
  • $\begingroup$ @Ilmari Karonen Yes, n vs $2^n$. $\endgroup$
    – Mark L. Stone
    Dec 3, 2020 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$.

Improve this answer
$\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, 2020 at 9:35
  • $\begingroup$ @C Marius See my answer. $\endgroup$
    – Mark L. Stone
    Dec 2, 2020 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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