Hi all,

I have a few questions regarding DC programming:

  1. 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".

  2. Are there "free" tools for solving DC programs? Are MATLAB packages for solving DC programs?

  3. 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's gravatar image

Sina
013
accept rate: 0%

retagged 03 Feb '16, 09:58

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26

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

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.

link

answered 10 Jul '13, 23:25

Austin%20Buchanan's gravatar image

Austin Buchanan
1.3k313
accept rate: 42%

edited 10 Jul '13, 23:35

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 08 Jul '13, 17:16

Seen: 4,678 times

Last updated: 09 Feb '16, 05:47

OR-Exchange! Your site for questions, answers, and announcements about operations research.