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.

Gradient Descent

Gradient Descent is a technique where we repeatedly move closer to the optimal point. To do this, we must find the gradient of the objective function at the current point, and move based on the gradient. If we know the gradient, we know one direction on which a more optimal point exists, so we move based on the gradient. There are two major flaws of the usual Gradient Descent, though. One flaw is that if we start at a point where the gradient is too small, the convergence will be very slow. There are ways to solve this (Backtracking Line Search is an example), but we will not cover them too technically in this article. Just remember that the methods are done by tweaking the movements, and we would be good to go. The greater issue is that, our objective function may or may not have a gradient. Not always are the objective functions differentiable, so if the objective functions are not differentiable, we cannot use the traditional Gradient Descent.

Luckily, we can still use a similar way, called the Subgradient method. For every convex function at every point, a "subgradient" exists. If a gradient exists, the gradient is a subgradient. If it doesn't, we define any gradient-like vector, where the plane/line defined by the vector underestimates the function in any point, as the subgradient. We can use this subgradient just like the gradient in Gradient Descent. The only thing to remember is that we may not converge at all if the step size is fixed, so we must reduce the step size at every iteration. This method is very convenient if we have a way to easily determine a subgradient.

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.

Practice Tasks

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!