### chromate00's blog

By chromate00, 3 months ago,

Before we begin: This blog is my attempt to Codeforces Month of Blog Posts. Simple rule: Write an interesting CodeForces blog post until February 15th and win \$300.

In this blog, I will be describing the concept of Convex Optimization, and techniques that can be used to solve Convex Optimization tasks. The blog will be divided into two parts — "What is Convex Optimization", and "How do we solve Convex Optimization tasks". This part of the blog is for "How do we solve Convex Optimization tasks". (Part 1 is here)

### There are just too many ways to solve them

One thing is for sure — There are too many ways to solve convex optimization tasks. By "too many", I mean, at least a dozen. We can't cover all of them here! So, I will be covering the methods that can be used in a majority of convex optimization tasks in this blog. Those methods would be Gradient Descent (including the Subgradient method), Coordinate descent, and Ternary Search.

### Coordinate Descent

Coordinate Descent is probably the simplest of the methods used for Convex Optimization. Not many tasks allow the usage of Coordinate Descent, but if we can use it, it makes solving the task much easier. Basically, we move along the axes on the euclidean plane. We define a variable "delta" initially, and in each step, we seek towards four directions (+x,-x,+y,-y) and see if moving towards any direction by delta reduces the value. If moving towards any direction reduces the value, we move towards that direction. If delta is constant, then we will clearly be stuck in one point at some point in time (likely the second step), so we decrease delta at every step. Coordinate Descent's flaw is that it can be stuck at situations where there are more than one direction having greatest reduction. Still, this flaw does not exist on one dimension, so you can simply treat it as a "Lazy man's Ternary Search" in one dimension.

### Ternary Search

At this point you may say, "Wait, isn't ternary search limited to one dimension?" and you may be right. But think about it, $\mathbb{R}^2$ is just $\mathbb{R}$ in two axes. Instead of just one dimension, we can think of using the result from ternary search (the minimized/maximized value) as the function to minimize/maximize in another ternary search. This is one very simple way to solve convex optimization tasks, and is guaranteed to work very often. (If time complexity isn't an issue, that is!) Again, coordinate descent always works in one dimension, so you can replace one ternary search with coordinate descent if you want to.

Easy Difficulty

• Almost any ternary search task. Try to prove whether the objective function is convex before you solve it!

Medium Difficulty

• NCNA 2019 — "Weird Flecks, but OK": Usage of the Smallest Enclosing Circle task. (Kattis) (Baekjoon)
• Waterloo's local Programming Contests — "A Star not a Tree?": The Geometric Median task. (Baekjoon)

Medium-Hard Difficulty

• JAG Summer Camp 2019 — "All your base are belong to us": if K=1, this is the Smallest Enclosing Circle. if K=N, this is the Geometric Median. Is our objective function convex even for any arbitrary N? Time to find out. (Baekjoon)
• 2013 Japan Domestic Contest — "Anchored Balloon": Designing the objective function may be tricky for this task. Bruteforcing is one solution for the task, but using convex optimization techniques to solve it is a very good practice. (Baekjoon)

Hard Difficulty

• Asia Regional Contest 2007 in Tokyo — "Most Distant Point from the Sea": Some people reading the task may know this as a half-plane intersection task. And you're not wrong. Still, This task can be solved as a Convex Optimization task well enough in the TL! (Baekjoon)
• SWERC 2021-2022 "Pandemic Restrictions": The intended solution was based on convex optimization. For proof, please check the official editorial of the mirror contest. (CF Gym)

UPD: Solutions here!

• +26