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

$\endgroup$
  • 1
    $\begingroup$ Is there anyway that you can get a subgradient along with the optimal solution to the inner problem? $\endgroup$ – Brian Borchers Nov 17 '14 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 Nov 17 '14 at 7:13
  • $\begingroup$ @BrianBorchers:Actually, I could compute a subgradient:D $\endgroup$ – user40780 Nov 17 '14 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 Nov 17 '14 at 20:17
  • $\begingroup$ So if $f(\lambda)$ is piecewise linear, is it also concave (because you maximize)? $\endgroup$ – Wolfgang Bangerth Nov 17 '14 at 20:34
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)

$\endgroup$
  • $\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 Nov 18 '14 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 Nov 18 '14 at 17:12
  • $\begingroup$ Piecewise linear functions are not strongly convex. $\endgroup$ – tmyklebu Nov 18 '14 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 Nov 18 '14 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$.

$\endgroup$
  • $\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 Nov 26 '14 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 Nov 26 '14 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 Nov 26 '14 at 14:14
  • $\begingroup$ This is beyond my knowledge of the area. $\endgroup$ – Wolfgang Bangerth Nov 26 '14 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 Nov 27 '14 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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