# Minimizing a convex cost function

I'm reviewing basic techniques in optimization and I'm stuck on the following. We aim to minimize the cost function $$f(x_1,x_2) = \frac{1}{2n} \sum_{k=1}^n \left(\cos\left(\frac{\pi k}{n}\right) x_1 + \sin\left(\frac{\pi k}{n}\right) x_2\right)^2.$$ I'd like to show some basic properties, specifically what its Lipschitz constant is, whether or not it is strongly convex, and where it obtains its minimum.

In finding the Lipschitz constant, $$\frac{\partial f}{\partial x_1} = \frac{1}{n} \sum_{k=1}^n \left(\cos\left(\frac{\pi k}{n}\right) x_1 + \sin\left(\frac{\pi k}{n}\right) x_2\right)\cos\left(\frac{\pi k}{n}\right),$$$$\frac{\partial f}{\partial x_2} = \frac{1}{n} \sum_{k=1}^n \left(\cos\left(\frac{\pi k}{n}\right) x_1 + \sin\left(\frac{\pi k}{n}\right) x_2\right)\sin\left(\frac{\pi k}{n}\right),$$ but for arbitrarily large $x_1$ and $x_2$, doesn't this imply this imply the derivatives are unbounded and thus the function not Lipschitz?

I'm having a similar problem in computing the minimum of the function, as I set one of the above equations to zero, solve for $x_1$, plug it into the other, and solving for $x_2$ simply gets $x_2 (\cdots) = 0$, where $(\cdots)$ is some jarble of product sums but nevertheless a constant, and thus meaningless in determine the value of $x_2$.

• What's wrong with the conclusion that at the minimum, $x_2 =0$? – user7530 Mar 19 '14 at 6:32
• Also, notice that $f$ is just a quadratic form in $x_1,x_2$, with some particularly elaborate constants. So it is locally (but not globally, as you point out) Lipschitz continuous. You can check convexity by looking at the second-order terms, but it is "obviously" convex as it is the sum of squared linear terms. – user7530 Mar 19 '14 at 6:38
• @user7530: Oh, I guess there's nothing wrong with concluding $x_2=0$, which would then imply $x_1=0$ and which re-looking at the function is obviously going to be output the minimum. I should be more confident in my work! As an answer below, could you elaborate a little more on how to prove local Lipschitz continuity, and the strong convexity? – Dustin Tran Mar 19 '14 at 6:46

## 2 Answers

Looking at your derivatives is quite interesting since $$\sum _{k=1}^n \cos\left(\frac{\pi k}{n}\right) \cos \left(\frac{\pi k}{n}\right) =\frac{n} {2}$$ $$\sum _{k=1}^n \cos\left(\frac{\pi k}{n}\right) \sin \left(\frac{\pi k}{n}\right) =0$$ $$\sum _{k=1}^n \sin\left(\frac{\pi k}{n}\right) \sin \left(\frac{\pi k}{n}\right) =\frac{n} {2}$$ This then leads to $$\frac{\partial f}{\partial x_1} = \frac{x_1}{2}$$ $$\frac{\partial f}{\partial x_2} = \frac{x_2}{2}$$ So, the derivatives are zero for $x_1=0$ and $x_2=0$ and this is the only solution.

In response to your comment: a general useful fact is that any energy of the form $$\sum_i \left(\sum_j \alpha_{i,j} x_j\right)^2$$ for constants $\alpha_{i,j}$ is convex. This is because this energy can be written in matrix form as $$\|Ax\|^2 = x^T A^TA x$$ for $A_{i,j} = \alpha_{i,j}$; the Hessian of this energy is $2A^TA$ which is necessarily symmetric positive-semidefinite.

It follows that the energy is strongly convex if $A$ has full rank, which is the case for your objective function for $n>1$.