1
$\begingroup$

I'm doing an exercise work about Support Vector Machines which involves solving a quadratic program of the form

$$\begin{aligned} & \underset{\boldsymbol\alpha \in \mathbb{R}^N}{\text{minimize:}} & & \frac{1}{2}\boldsymbol\alpha^TQ\boldsymbol\alpha +\textbf{p}^T\boldsymbol\alpha \\ & \text{subject to:} & & \; A\boldsymbol\alpha \geq \textbf{c}, \end{aligned}$$

where $Q$ is a positive-semidefinite matrix, $A$ a matrix and $\textbf{p}, \textbf{c}, \boldsymbol\alpha$ are vectors.

I've been reading about quadratic programming and about the methods of solving one but I haven't found any concrete pencil-and-paper example of how to actually solve this problem with, let's say, using the conjugate gradient method. In many textbooks I get directed into using online softwares for solving this problem but this doesn't fulfill my appetite, because I want to understand what is going on under the hood.

Could I get a concrete example or get directed to one, where I can see or implement myself all the steps needed to solve a quadratic program? The algorithm could be interior-point method for example.

Thank you!

$\endgroup$
  • 1
    $\begingroup$ Conjugate gradients cannot be used on a constrained problem like this. You should be looking at information on interior-point methods or the simplex method for quadratic programming. $\endgroup$ – Michael Grant Mar 31 '15 at 13:58
1
$\begingroup$

May I suggest the Frank-Wolfe method? Here's an example found by a quick google on "Frank Wolfe example"

http://aerostudents.com/files/valueEngineeringAndOperationsOptimisation/FrankWolfeAlgorithmDemonstration.pdf

$\endgroup$

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.