Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables

I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this.

Read the following only if you want to know the function I want to minimize (this is a concave function, I want to maximize it, which is equivalent to minimizing its negative) . \begin{align} f(t_1,t_2)=\min_{u^Tu=1,u\in \mathbb{R}^{N}}u^T(A_0+t_1A_1+t_2A_2)u \end{align} $A_0,A_1,A_2$ are all $N \times N$ real symmetric matrices. Actually $f(t_1,t_2)$ is the lowest eigenvalue of matrix $A_0+t_1A_1+t_2A_2$ for a given $t_1,t_2$. I know this can be solved by semi-definite programming.

• Have you considered using something like Inverse Iteration just to grab the smallest eigenvalue out of $A_0 + t_1A_1 + t_2A_2$? Jan 30, 2013 at 13:07
• Did you check stanford.edu/~boyd/cvxbook ? Jan 30, 2013 at 13:23
• Just so we're clear, you want to maximize the concave function $f(t_1,t_2)$, right? The statement of your problem is contradictory as written. Jan 30, 2013 at 16:34
• @BrianBorchers Yes, but I thought I have explicitly mentioned it. Jan 30, 2013 at 17:19
• The confusion here is that if you take the parenthetical comment out, you're left with "the function that I want to minimize f(t1,t2)=..." implying that you actually want to minimize f. This contradicts what you've written within the paranetheses. Jan 30, 2013 at 17:32

You haven't told us anything about how big $N$ is. This can be very important, since the other size parameter here is the length of the $t$ vector, which is absolutely tiny for your particular eigenvalue problem.
You've already mentioned the SDP formulation of this problem. If $N$ is reasonably small (say less than $N=10000$), then off the shelf semidefinite programming tools (SeDuMi, SDPA, CSDP, etc.) using the primal-dual interior point method should be easy to apply to this problem. In terms of your time, this is probably the quickest way to solve the problem.
On the other hand, if $N$ is really huge, you'll want to look at methods that are more specialized for eigenvalue optimization problems.
• dimension of $N$ would be within 10. Yes, I agree, may be there exist customized solutions for the kind of problem i have given. Still i would like to know any such general algorithm. Jan 31, 2013 at 1:45