[Ipopt] solving non-smooth large scale problem using ipopt

[Sebastian Nowozin]

Hi Chivalry,

a similar case occurs when solving structured support vector machines
(structured SVMs), and the most efficient methods there used to be dual
active set QP solvers, customly written for these problems.

However, recent literature has shown that the Frank-Wolfe method is quite
efficient for these type of QPs.

See, e.g.

http://jmlr.csail.mit.edu/proceedings/papers/v28/lacoste-julien13-supp.pdf
and the accompanying code
    https://github.com/ppletscher/BCFWstruct

If your problem is of similar type, these methods are worth a try.  If not,
maybe you want to investigate whether they can be adapted to your type of
problem.
(Structured SVMs are an important problem in machine learning and it took a
few years until we could reliably solve these problems.)

Sebastian


On Fri, May 8, 2015 at 4:04 PM, key01023 at gmail.com <key01023 at gmail.com>
wrote:

> Hi Sebastian,
>
> Thank you for your reply.
>
> Yes, we indeed have maximum of multiple linear functions. However, the
> multiple is about 2^80 many such linear functions. However, I have a way to
> walk around without enumerating all such linear functions and provide a
> oracle to objective function values and sub gradient value. Do you think it
> is still possible to use IPopt to solve it? Thank you.
>
> With regards,
> Chivalry
>
> On May 8, 2015, at 10:57 AM, Sebastian Nowozin <nowozin at gmail.com> wrote:
>
>
> Hi Chivalry,
>
> convex + non-smooth problems often originate from minimizing the maximum
> of multiple smooth convex problems.
>
> If this is the case in your instance, you can reformulate the problem by
> introducing additional variables containing the individual objective
> function values, and a set of inequality constraints.
> The resulting instance is a smooth convex problem with convex constraints
> and as such amenable using IpOpt.
>
> Sebastian
>
> On Fri, May 8, 2015 at 3:45 PM, key01023 at gmail.com <key01023 at gmail.com>
> wrote:
>
>> Dear all,
>> I have a large class of non smooth convex optimization problems with
>> about 8000 dimensions and I am looking for c++ solvers to solve that. I
>> tried level method  (extremely slow due to built up of sub-gradients),
>> optimal gradient method due to Nesterov (very slow convergence), limited
>> memory bundle method (LMBM) (no compilable solver available, failed to
>> compile LMBM). I want to ask whether ipopt can be applied to solve this
>> problem, because it uses limited memory BFGS which i guess somewhat
>> resembles the LMBM methods. If so, is there some c++ file examples showing
>> a case where we don’t need to provide the Hessian. Thank you.
>>
>> With regards,
>> Chivalry
>>
>> _______________________________________________
>> Ipopt mailing list
>> Ipopt at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/ipopt
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/ipopt/attachments/20150508/26b0d992/attachment-0001.html>