Optimization in Matlab

[David Naylor]

Hi everyone,

I'm really inexperienced with Matlab (aside from hw1 I've never used it), and I'm having a little trouble seeing how to fit the SVM optimization problem into the format expected by quadprog. According to the help page, quadprog solves problems of the form:

             min 0.5*x'*H*x + f'*x   subject to:  A*x <= b 

              x

I'm struggling to see how fit the slack variables into this when the only things I can supply are H, f, A and B. I imagine it's simple, I just don't know what I'm doing. Can someone give me a push in the right direction?

Thanks!

David

[Mu Li]

Hi David,

You can try to group w and the slack variables together  by x = [w;s] if both of them are column vectors, and then construct the according others. Besides, you can use any  other languages you like.

Best,

Mu

David

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.
To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.
To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Vagelis Papalexakis]

Hey!

You can also try using CVX for matlab where you can write in a more free style and explicitly declare more optimization variables. It's easy to use and you don't really need to learn  how to use it for the purposes of that particular optimization problem (I'm mostly referring to the primal problem)

You can download it from here: http://cvxr.com/

The installation is just running a matlab script and saving the matlab path afterwards (i.e. typing "savepath")

Hope that helps

Vagelis

[Yitong Zhou]

Me too, struggling.... For the primal problem, I think you need to derive the matrix to make it fit for the standard quadprog style...

Well, I am having problems with dual problem,got the error:

Some combination of the bounds, linear constraints, and linear terms

in the objective function immediately lead to the solution.

anyone has idea how to debug it?

Yitong

在 2013年2月16日星期六UTC-5上午11时53分08秒，David Naylor写道：

[Yitong Zhou]

Ok, I got it!  The Y tags should be set to {1,-1}?, if set as {1,0}...seems that the dual problem won't solve...

在 2013年2月16日星期六UTC-5下午10时06分17秒，Yitong Zhou写道：

[Daniel Maturana]

Hi, is it okay if we use SGD for the primal problem?
thanks
Daniel

[Alex Smola]

hi guys,

solving the primal with SGD is NOT ok. SGD in the primal won't even be possible in the case of infinite dimensional hilbert spaces. sgd using the dual problem tends not to give terribly good quality solutions unless you know what you're doing. 

as for programming, you can choose ANY programming language you want (but you must be able to code in at least one of them). 

matlab - quadprog

python - cvxopt cvxmod

c/c++ - ooqp, loqo (free for academic use)

afaict even excel has a quadratic programming solver. many years ago when i checked, it was faulty but i (hope/believe) that it's been fixed in the meantime. 

so, you have the constraint \sum_i \alpha_i y_i = 0 and moreover 0 \leq \alpha_i \leq C

the latter constraint is simply 1 * \alpha \leq C and -1 * \alpha \leq 0 (the identity is also a matrix). as for the equality constraint, either pick a different interface or think about how you could express it as two inequalities. 

cheers,

alex

--

                            ''~``

                           ( o o )

+----------------------.oooO--(_)--Oooo.---------------------------+

| Prof. Alexander J. Smola             http://alex.smola.org       |

| 5000 Forbes Ave                      phone: (+1) 408-759-1044    |

| Gates Hillman Center 8002            Carnegie Mellon University  |

| Pittsburgh 15213 PA    (   )   Oooo. Machine Learning Department |

+-------------------------\ (----(   )-----------------------------+                          

                          \_)    ) /

                                (_/