0

Are there column generation approaches to solving classes of convex optimization problems other than LPs, and are they guaranteed to find a global minimizer?

littleO
  • 51,938
  • Are you familiar with cutting plane methods? I've always found it hard to understand if the community distinguishes between the two. – Michael Grant May 17 '16 at 14:07
  • @MichaelGrant I have some experience with cutting plane methods, but I hadn't recognized a connection with column generation algorithms. Can column generation for LPs be viewed as a cutting plane method? – littleO May 18 '16 at 01:17
  • I think they are very closely related, yes. With column generation, you are generating individual linear constraints programmatically. Aren't those cutting planes separating the feasible set from its complement? – Michael Grant May 18 '16 at 01:20
  • I vaguely recall hearing of using column generation LP solvers to solve nonlinear convex problems. – Michael Grant May 18 '16 at 01:23
  • "from its complement" that's not right. The columns generated / cutting planes separate the feasible set from an infeasible test point. – Michael Grant May 18 '16 at 05:44

1 Answers1

2

Column generation is a standard tool for large scale, possibly smooth convex optimization problem.

Standard application are radiation therapy, traffic equilibrium among others.

Under suitable assumption column-generation scheme can also converge to critical point of non convex problems.

Take a look at

http://www.math.chalmers.se/~mipat/LATEX/CGSD.ps http://oa.upm.es/15270/1/INVE_MEM_2011_122534.pdf

AndreaCassioli
  • 932