This is a follow-up to this blog, as a self-editorial for the three practice tasks from Medium-Hard to Hard. As solving the task after proving is quite easy (you can just directly use the techniques in the blog), I will only prove why the task is a convex optimization task.
JAG Summer Camp 2019 — "All your base are belong to us"
Only considering the farthest $$$k$$$ points makes the proof harder. Think more openly.
Instead of the sum of the maximum $$$k$$$ distances, can we express our objective as a maximum of sums?
Instead of considering the farthest $$$k$$$ points, let's consider all subsets of points with size $$$k$$$. Then we can express our objective function like this.
This is the maximum of all $$$\displaystyle{n \choose k}$$$ sums, and as the distance function is convex, the sum of convex functions is convex, and the intersection of convex functions is convex, this objective function is convex. Then, the maximum of all subset sums would be the sum of the largest $$$k$$$ distances, therefore this objective function is equivalent to the one to maximize in this task.
2013 Japan Domestic Contest — "Anchored Balloon"
Think of the objective function as how high the balloon can go at a certain 2-dimensional coordinate $$$(x,y)$$$.
The sentence "The balloon is initially placed at (0, 0) on the ground." is meaningless. In convex optimization, we reach any local maximum (which is the global maximum in convex optimization) regardless of where we begin.
We can express our objective function like this.
Why $$$({l_i}^2-(x_i - x)^2-(y_i - y)^2)$$$ without the square root? If we use the square root here, negative values will cause errors, and we may have to cut it to $$$0$$$ when the value is negative (meaning that the balloon cannot fly upwards). But in that case, the function is no longer convex. So, we must not use the square root in our objective function. For the answer, it suffices to evaluate the value of the square root of the objective function in the end. Do note that even if the objective function is concave instead of convex, we can still treat it as a convex function by inverting the sign.
Asia Regional Contest 2007 in Tokyo — "Most Distant Point from the Sea"
Think of the objective function as literally the distance to the closest line. (Treat the line segment as a straight line)
The objective function may seem convex already, but we need it concave if we would like to maximize it. However, if the distance function is convex, how do we make it concave?
Let's define $$$\mathbf{sdist}(L,p)$$$ as a "signed distance function" from a line to a point. Basically, one side of it has positive sign, the other side of it has negative sign. In this task, the sign will be positive if the point is towards the inside of the polygon, and negative if it is not. While $$$sdist(L,p)$$$ itself is not "strictly" concave, its intersection will be strictly concave if the half-plane intersection encloses a convex polygon. (We do not have to directly understand this in this task yet) Then our objective function will be like this.
Now, as our objective function is concave, we can just solve the task normally. (or you can just switch the sign and treat it as convex)
BONUS: Did you realize that this definition of $$$f(x,y)$$$ essentially includes the whole half-plane intersection implicitly? If you did, can you use this definition on some other half-plane intersection tasks?
Comments (0)
