# Tools for solving DC (difference of convex) programming

 -1 Hi all, I have a few questions regarding DC programming: Are there good tools (besides generic non-convex solvers) that can solve a DC program, i.e. "maximizing f-g where both f and g are convex functions". Are there "free" tools for solving DC programs? Are MATLAB packages for solving DC programs? More specifically, the problem I want to solve is of the following form: $sup_f (\sum_{i=1}^{n/2} f(x_i) - \sum_{i=n/2+1}^n f(x_i) )$ where x_i's are constants (real numbers), and $$f$$ ranges over a set F of convex functions. Does this particular problem have an efficient solution? What about an approximation with provable guarantees? I appreciate the insight, Sina asked 08 Jul '13, 17:16 Sina 0●1●3 accept rate: 0% Rob Pratt 1.2k●2●6 Did you mean $$\max_g$$ in the second term? Are your variables the functions $$f$$ and $$g$$ and, if so, are there any restrictions on them besides being convex? (08 Jul '13, 18:14) Paul Rubin ♦♦ Sorry there was a typo. I just fixed it. So in the 3rd part of my question, there is no "g". In this particular example, there are two convex functions: one is $$\sum_i L(f(x_i))$$ and one is $$\sum_j L(f(y_j))$$. (08 Jul '13, 22:28) Sina 1 Convex functions of what? You said the x and y symbols were constants. (09 Jul '13, 15:39) Paul Rubin ♦♦ Yes, f is convex over the set of real numbers. So I am trying to see if this optimization is solvable for any given set of x_i and y_i constants if f is allowed to iterate over a class functions as long as it is a convex function. (09 Jul '13, 17:26) Sina 1 Why are there two 'max' terms? (10 Jul '13, 23:13) Austin Buchanan

 4 I think you have misunderstood "difference of convex" programming. Boyd's lecture slides state the problem as: minimize $$f_0 (x) - g_0 (x)$$ subject to $$f_i (x) - g_i (x) \le 0$$ for $$i=1,\dots, m$$ where $$f_i$$ and $$g_i$$ are given convex functions. The symbol $$x$$ refers to a (vector of) variable(s), not a constant. answered 10 Jul '13, 23:25 Austin Buchanan 1.3k●3●13 accept rate: 42% Thanks for the clarification, you are right. Do you have any thoughts on my first two questions? i.e., if I did have a DC problem, what would be a good tool to solve it with? (12 Jul '13, 12:00) Sina BARON (http://archimedes.cheme.cmu.edu/?q=baron) is a general-purpose solver. I know very little about DC problems. (12 Jul '13, 13:24) Austin Buchanan Thanks a lot. I just reformulated the problem, and I think the variable in my problem is the function f which belongs to a class of functions F. (FYI, this problem is known as the maximum discrepancy of F, see page 2 in http://machinelearning.wustl.edu/mlpapers/paper_files/BartlettM02.pdf ) (14 Jul '13, 14:44) Sina
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×190
×20
×1
×1