Very often people who compare performance of different algorithms in convex optimization use randomly generated data. For instance, this often happens in compressed sensing and signal processing.

Is this practice justified? How one can repeat their experiment? How this can prove that Algorithm 1 is more effective than Algorithm 2. Perhaps, with another instance of random data Algorithm 2 will beat Algorithm 1.

Are there some classical test problem for comparing algorithms? In image processing for this there are several fixed pictures.

Also I'm interested in some test problems in convex optimization that are highly nonlinear, i.e., that are not quadratic plus some simple convex function such as norm or indicator function.

  • $\begingroup$ Because often checking non-random constraints is as hard as solving the problem! $\endgroup$ – Ehsan M. Kermani Nov 11 '14 at 17:19
  • $\begingroup$ What do you mean? Is it difficult to make a library of test problems in convex optimization such as netlib in linear programming? $\endgroup$ – cheyp Nov 11 '14 at 17:27
  • $\begingroup$ @user3814143: The difficulty with testing against a standard library is that it is not too hard to create an algorithm which does well on all of the items in the library while being very bad in general. Moreover, I think that testing against random data is well-justified. Most data that you get in the real world may as well be random. $\endgroup$ – Eric Stucky Nov 16 '14 at 9:32

I believe that because there is a vast variety of convex problems with totally different structure. The term "convex problem" does not really define a representation for the family of problems that we can play with. Therefore building a library of convex problems seems impossible. Because nobody built such a library, everybody just solves random problems.

Linear algebra is simpler. All problems of "solve a linear equation" have the same structure - a matrix and a vector. All problems "find the eigenvalues of this matrix" also have the same structure.

P.S - I am not considering specialized or iterative algorithms for equation solving here.

| cite | improve this answer | |

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.