title: How to implement a soft-margin SVM model using Matlab's quadprog?
body: <p>Suppose we are given a training dataset <code>{yᵢ, xᵢ}</code>, for <code>i = 1, ..., n</code>, where <code>yᵢ</code> can either be <code>-1</code> or <code>1</code> and <code>xᵢ</code> can be e.g. a 2D or 3D point. </p>
  
  <p>In general, when the input points are <em>linearly separable</em>, the SVM model can be defined as follows </p>
  
  <pre><code>min 1/2*||w||²
  w,b
  </code></pre>
  
  <p>subject to the constraints (for <code>i = 1, ..., n</code>)</p>
  
  <pre><code>yᵢ*(w*xᵢ - b) &gt;= 1
  </code></pre>
  
  <p>This is often called the <a href="https://en.wikipedia.org/wiki/Support_vector_machine#Hard-margin" rel="nofollow noreferrer"><strong>hard-margin</strong> SVM model</a>, which is thus a <a href="https://en.wikipedia.org/wiki/Constrained_optimization" rel="nofollow noreferrer">constrained minimization problem</a>, where the unknowns are <code>w</code> and <code>b</code>. We can also omit <code>1/2</code> in the function to be minimized, given it's just a constant.</p>
  
  <p>Now, the <a href="https://ch.mathworks.com/help/optim/ug/quadprog.html" rel="nofollow noreferrer">documentation</a> about Matlab's <code>quadprog</code> states</p>
  
  <blockquote>
    <p><code>x = quadprog(H, f, A, b)</code> minimizes <code>1/2*x'*H*x + f'*x</code> subject to the restrictions <code>A*x ≤ b</code>. <code>A</code> is a matrix of doubles, and <code>b</code> is a vector of doubles.</p>
  </blockquote>
  
  <p>We can implement the hard-margin SVM model using <code>quadprog</code> function, to get the weight vector <code>w</code>, as follows</p>
  
  <ul>
  <li><code>H</code> becomes an identity matrix.</li>
  <li><code>f'</code> becomes a zeros matrix.</li>
  <li><code>A</code> is the left-hand side of the constraints</li>
  <li><code>b</code> is equal to <code>-1</code> because the original constraint had <code>&gt;= 1</code>, it becomes <code>&lt;= -1</code> when we multiply with <code>-1</code> on both sides.</li>
  </ul>
  
  <hr>
  
  <p>Now, I am trying to implement a <a href="https://en.wikipedia.org/wiki/Support_vector_machine#Soft-margin" rel="nofollow noreferrer"><strong>soft-margin</strong> SVM model</a>. The minimization equation here is</p>
  
  <pre><code>min (1/2)*||w||² + C*(∑ ζᵢ)
  w,b
  </code></pre>
  
  <p>subject to the constraints (for <code>i = 1, ..., n</code>)</p>
  
  <pre><code>yᵢ*(w*xᵢ - b) &gt;= 1 - ζᵢ
  </code></pre>
  
  <p>such that <code>ζᵢ &gt;= 0</code>, where <code>∑</code> is the summation symbol, <code>ζᵢ = max(0, 1 - yᵢ*(w*xᵢ - b))</code> and <code>C</code> is a <a href="https://en.wikipedia.org/wiki/Hyperparameter_(machine_learning)" rel="nofollow noreferrer">hyper-parameter</a>.</p>
  
  <p>How can this optimization problem be solved using the Matlab's <code>quadprog</code> function? It's not clear to me how the equation should be mapped to the parameters of the <code>quadprog</code> function. </p>
  
  <p>The "<strong>primal</strong>" form of the soft-margin SVM model (i.e. the definition above) can be converted to a "<a href="https://en.wikipedia.org/wiki/Support_vector_machine#Dual" rel="nofollow noreferrer"><strong>dual</strong></a>" form. I did that, and I am able to get the Lagrange variable values (in the dual form). However, I would like to know if I can use <code>quadprog</code> to solve directly the primal form without needing to convert it to the dual form.</p>