# 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$? – Aron Ahmadia Jan 30 '13 at 13:07
• Did you check stanford.edu/~boyd/cvxbook ? – Dominique Jan 30 '13 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. – Brian Borchers Jan 30 '13 at 16:34
• @BrianBorchers Yes, but I thought I have explicitly mentioned it. – dineshdileep Jan 30 '13 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. – Brian Borchers Jan 30 '13 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. – dineshdileep Jan 31 '13 at 1:45