4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Have you considered using something like Inverse Iteration just to grab the smallest eigenvalue out of $A_0 + t_1A_1 + t_2A_2$? $\endgroup$
    – Aron Ahmadia
    Jan 30, 2013 at 13:07
  • $\begingroup$ Did you check stanford.edu/~boyd/cvxbook ? $\endgroup$
    – Dominique
    Jan 30, 2013 at 13:23
  • $\begingroup$ 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. $\endgroup$
    – Brian Borchers
    Jan 30, 2013 at 16:34
  • $\begingroup$ @BrianBorchers Yes, but I thought I have explicitly mentioned it. $\endgroup$
    – dineshdileep
    Jan 30, 2013 at 17:19
  • $\begingroup$ 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. $\endgroup$
    – Brian Borchers
    Jan 30, 2013 at 17:32

1 Answer 1

Reset to default
3
$\begingroup$

The problem that you've described has very specialized structure. These kinds of eigenvalue optimization problems have been widely studied, so you'd do well to look at the literature on the subject and go from there. You don't really want to look at completely general purpose non differentiable convex optimization solvers that won't take advantage of the problem structure you've identified.

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – dineshdileep
    Jan 31, 2013 at 1:45
  • $\begingroup$ There are lots of algorithms for general unconstrained convex non-differentiable minimization problems that assume nothing more than the ability to find a subgradient vector at any given point. The simplest of these is the projected subgradient method. This is textbook material discussed in many books on convex optimization. For example, you'll find it in Bertsekas' textbook on nonlinear optimization. $\endgroup$
    – Brian Borchers
    Jan 31, 2013 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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