1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What's wrong with the conclusion that at the minimum, $x_2 =0$? $\endgroup$ – user7530 Mar 19 '14 at 6:32
  • $\begingroup$ 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. $\endgroup$ – user7530 Mar 19 '14 at 6:38
  • $\begingroup$ @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? $\endgroup$ – Dustin Tran Mar 19 '14 at 6:46
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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