Is there any solver for convex optimization in C++ (or some dedicated scheme while no solver is yet available) that could solve a convex optimization problem with objective function value given by an oracle? Thank you.

My specific problem is this:

\[\mathop {\max }\limits_\lambda \mathop {\min }\limits_{\sigma \in {{\{ 0,1\} }^N}} {E_{\sigma ,\,\lambda }} \]

wherer lambda is a vector, and for each

\[{\sigma \in {{\{ 0,1\} }^N}} \]

E is a linear function of lambda \[{E_{\sigma ,\,\lambda }} \]

In words: It is actually maximize over lambda the piece-wise linear function defined by the minimum of exponential number of linear functions. Given lambda I have an effective scheme to obtain sigma and thus calculate \[\mathop {\min }\limits_{\sigma \in {{\{ 0,1\} }^N}} {E_{\sigma ,\,\lambda }} \] . so my problem is effectively a convex optimization with objective function given by my oracles (maximize over a concave function) and I am wondering whether there would be some solvers suitable to this type of problem. Or if there is any dedicated procedure for this while no solvers available.

Thank you:D

asked 13 Nov '14, 11:25

Chivalry's gravatar image

Chivalry
229117
accept rate: 0%

I am unaware of such a solver, but in general your problem (i.e., solve a convex problem with an oracle for the objective function) is difficult. As an example, consider optimizing over the TSP polytope.

(13 Nov '14, 13:21) Austin Buchanan

It is difficult, but we really need to solve it:) do you know some paper on it?

(13 Nov '14, 14:49) Chivalry
1

It seems you could use any LP solver and just keep adding cuts (constraints) supplied by the oracle.

(17 Nov '14, 16:48) Paul Rubin ♦♦

actually, I am also trying this out and just wonder whether there might be some developed advanced method for that.... :D

(17 Nov '14, 16:50) Chivalry

Im not quite sure, but maximizing a concave non-differential function sounds like subgradient methods to me?

(18 Nov '14, 07:10) Sune

Hello,

Did you take a look at CVX?

It is not a 'solver' but a modeling system for convex programs which then uses and underlying solver. Since the version 2.0 it can be used with Gurobi and MOSEK and, if your problem is not too large scale, I believe it can tackle that kind of problem.

link

answered 14 Nov '14, 03:06

JorgeGarciaCastillo's gravatar image

JorgeGarciaC...
294
accept rate: 0%

1

Thank you. But it seems cvx could not solve when my input objective function is an oracle...

(14 Nov '14, 08:12) Chivalry
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:

×231
×20

Asked: 13 Nov '14, 11:25

Seen: 823 times

Last updated: 18 Nov '14, 07:10

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