|
In support vector machine, we write the Lagrangian function from the primal optimization problem and then derive the dual problem in terms of Lagrangian multiplier. There are many algorithm exist such as SMO to get the optimal solution for the derived dual problem which in turns provides the solution for primal problem. Currently im looking for a reference algorithm for any problem (not necessarily classification) where the primal problem is solved directly without deriving dual. i.e algorithm is derived based on Lagrangian function and its KKT condition. To be precise, is there any problem with an objective function and constraint set(both equality and inequality) where we derive the algorithm based only on its Lagrangian function and KKT condition |
|
I think I can provide some answers if you're willing to tolerate a loose enough definition of "solve". There is an entire class of projected gradient (or forward-backward splitting) methods which work by taking a step in the direction of the gradient of the objective function and projecting the result back into the feasible set. There a generalization of these techniques to soft penalties called proximal gradient. Specifically for support vector machines with the soft margin you can write the optimization problem without constraints at all by minimizing ||w||^2 + sum_i max(0, 1- y_i (w dot x_i)). Then again you can use stochastic subgradient descent to get Pegasos, a method for solving SVMs which is really fast, and has time to achieve a given generalization error which provably grows sublinearly with the dataset size. These techniques, however, do not explicitly involve the KKT conditions as they are focused on getting a good solution to the optimization problem at hand, and not the optimal solution, so they cannot be described as solving the problem in a strict way, but they are still (and some would argue even more) useful to machine learning despite/because of this. @Alexandre Thanks for your input.
(Dec 20 '11 at 00:49)
Learner
|
