1
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Is there anyway that you can get a subgradient along with the optimal solution to the inner problem? $\endgroup$
    – Brian Borchers
    Commented Nov 17, 2014 at 0:05
  • 1
    $\begingroup$ What else do you know about $f(\lambda)=\min_\sigma E_{\sigma,\lambda}$? Is it differentiable? Could you compute or approximate derivatives? Is $\lambda$ scalar or a large or small vector? $\endgroup$
    – Wolfgang Bangerth
    Commented Nov 17, 2014 at 7:13
  • $\begingroup$ @BrianBorchers:Actually, I could compute a subgradient:D $\endgroup$
    – user40780
    Commented Nov 17, 2014 at 20:16
  • $\begingroup$ @WolfgangBangerth, f(λ)=minσEσ,λ is not differentiable, but it is piece wise linear. I actually could compute its sub gradient. λ is a large vector.... $\endgroup$
    – user40780
    Commented Nov 17, 2014 at 20:17
  • $\begingroup$ So if $f(\lambda)$ is piecewise linear, is it also concave (because you maximize)? $\endgroup$
    – Wolfgang Bangerth
    Commented Nov 17, 2014 at 20:34

2 Answers 2

Reset to default
4
$\begingroup$

OK- so you're trying to maximize a concave function which is piecewise linear, and you can evaluate the function and get a subgradient at any desired point. This is equivalent to minimizing a convex non-differentiable function using only function and subgradient evaluations (just minimize minus the objective function.)

You should read the papers by Yuri Nesterov on these problems (e.g. http://link.springer.com/article/10.1007/s10107-004-0552-5) Basically, he establishes bounds for the optimal performance of an algorithm and shows that his algorithm (which smooths the non-smooth problem and then apply an optimal algorithm for the smoothed problem) is optimal in its order of convergence.

Since Nesterov's 2005 paper there has been a lot of research on fast first order methods for nonsmooth convex optimization, particularly for applications related to image processing and compressive sensing. Although higher performance can be achieved if you assume strong convexity (which may not be possible in your case), there are algorithms that do not require this assumption. See for example Arnold Neumaier's OSGA algorithm (http://arxiv.org/pdf/1402.1125.pdf)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you very much for your reply. So do you think there are packages available for non-OR people on this kind of problem? Since in our department, most people are not sure about the exact implementation and derive our own codes based on reading would be error prone and problematic... Thank you. $\endgroup$
    – user40780
    Commented Nov 18, 2014 at 16:03
  • 1
    $\begingroup$ These methods are so simple to implement that there isn't much reason to have a solver library- it wouldn't be more than 100 lines of code. Most of the effort will be an implementing your code for the objective function and subgradient. Since you're probably already working within some framework (for example you might be using a library for linear algebra routines) that might well determine how you should implement the solver. I'm not aware of any C++ libraries for this. There are lots of MATLAB codes you can download. $\endgroup$
    – Brian Borchers
    Commented Nov 18, 2014 at 17:12
  • $\begingroup$ Piecewise linear functions are not strongly convex. $\endgroup$
    – tmyklebu
    Commented Nov 18, 2014 at 23:31
  • $\begingroup$ Right- since the objective is piecewise linear it clearly isn't strongly convex. I should have written "which isn't possible in your case." $\endgroup$
    – Brian Borchers
    Commented Nov 18, 2014 at 23:38
1
$\begingroup$

If your objective function is piecewise linear and concave, then it is the minimum of a bunch of globally linear functions. Let me put this in the more usual minimization framework (instead of maximization -- just flip the sign):

So you're trying to solve $$ \min_\lambda f(\lambda) $$ where $f(\lambda)$ is piecewise linear and convex. Then I can write $$ f(\lambda) = \min_i f_i(\lambda) $$ where each of the $f_i$ are linear. There is a canonical way of solving this, namely by introducing a scalar slack variable $\mu$ and writing the problem as $$ \min_{\lambda,\mu} \mu \\ \text{so that }\quad \mu \ge f_i(\lambda), \qquad i=1...N. $$ This is now a linear program: the objective function and all constraints are linear. Even if large, there are very efficient ways of solving this problem if only you can characterize the $f_i$. In your case, I imagine these are exactly the $E_\sigma(\lambda)$ for each of the possible $\sigma$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you. I think you are thinking of combing LP and constraint generation without introducing all the rows at once, right ... But I implemented this method, when N grows this method would easily become exponential (which means exponential number of planes needs to be generated).... Do you think there are some methods to counter it? thank you $\endgroup$
    – user40780
    Commented Nov 26, 2014 at 6:53
  • $\begingroup$ No, it's just a linear program because each $f_i(\lambda)$ has the form $f_i(\lambda)=v_i^T \lambda$ for some vector $v_i$. There are incredibly efficient ways to solve linear programs. Or are you thinking that it will be exponential because the constraints are generated by the elements of the set $\{0,1\}^N$? Yes, well, I guess that is unavoidable with any kind of approach unless you have a way to prune this set somehow. $\endgroup$
    – Wolfgang Bangerth
    Commented Nov 26, 2014 at 11:43
  • $\begingroup$ So I am actually thinking of combining analytic center cutting plane method(ACCPM) together with LP row generation.... Or some other method, do you know of some dedicated package for this kind of problem? Is it called minimax? $\endgroup$
    – user40780
    Commented Nov 26, 2014 at 14:14
  • $\begingroup$ This is beyond my knowledge of the area. $\endgroup$
    – Wolfgang Bangerth
    Commented Nov 26, 2014 at 18:06
  • 2
    $\begingroup$ An important trick in implementing the cutting plane approach is discarding inequalities that aren't binding on the current solution (and thus aren't really needed.) The hope is that a relatively small number of the right inequalities will be sufficient. The ACCPM essentially does this in a more sophisticated way than straight forward use of a general purpose LP solver, but then againa general purpose LP solver might perform so well that the more sophisticated approach isn't needed. You might look at the COIN-OR project, OBOE, which implements ACCPM. $\endgroup$
    – Brian Borchers
    Commented Nov 27, 2014 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.