0
$\begingroup$

$\forall i \in \{1\ldots N\}$, let $x_i$ denotes a pint in $\mathbb{R}^2$ and $y_i\in \{-1,+1\}$ where $y_i=+1$ implies $x_i\in$ class A and $y_i=-1$ implies $x_i\in$ class B.

Let $ L=\left\{x\in \mathbb{R}^2|x^\top \beta+\beta_0=0 \right\}$, where $\beta=(\beta_1,\beta_2)\in \mathbb{R}^2$ and $\beta_0\in \mathbb{R}$.

Here the aim is to find an optimal separating hyperplane which separates both the class and maximizes the distance to the closest point from either class.

Consider the following formulation:

A: \begin{equation}\label{convex_form1} \begin{aligned} & \underset{\beta, \beta_0}{\text{maximize}} & & M\\ & \text{subject to} & & \dfrac{1}{||\beta||}y_i(\beta^\top x_i+\beta_0)\geq M,~\;\; \forall x_i\in X,~ y_i\in Y. \end{aligned} \end{equation}

B: \begin{equation}\label{convex_form2} \begin{aligned} & \underset{\beta, \beta_0}{\text{minimize}} & & ||\beta||\\ & \text{subject to} & & y_i(\beta^\top x_i+\beta_0)\geq 1,~\;\; \forall x_i\in X,~ y_i\in Y. \end{aligned} \end{equation}

C: \begin{equation}\label{convex_form3} \begin{aligned} & \underset{\beta, \beta_0}{\text{minimize}} & & \dfrac{1}{2}||\beta||^2\\ & \text{subject to} & & y_i(\beta^\top x_i+\beta_0)\geq 1,~\;\; \forall x_i\in X,~ y_i\in Y. \end{aligned} \end{equation}

Q1. How are formulations A, B, and C equivalent?

What I know: Formulation A, comes from the idea that, we want to find an optimal separating hyperplane that is at least $M$ units away from all the points. Choosing $M=\dfrac{1}{||\beta||}$ gives Formulation B. But why choose such a $M=\dfrac{1}{||\beta||}$ other than the reason that it results in Convex Optimization problem.

$\endgroup$
  • $\begingroup$ PS: $X$ denotes the set of all data point $x_i$ and $Y$ denotes all the outputs. $\endgroup$ – kosa Dec 25 '17 at 22:06
  • $\begingroup$ Can I get a reference where Formulation C is equivalent to A and B. Vandenberg has a different formulation called Linear Discriminator formulation in Chapter 8 equation 8.23, whose KKT conditions are similar to the Formulation C. $\endgroup$ – kosa Dec 25 '17 at 22:52
  • 1
    $\begingroup$ $\dfrac{1}{2}||\beta||^2\\$ is a strictly monotonically increasing function of $||\beta||$. Therefore, problems B and C have the same argmin(s). That is what is meant by their being equivalent. Of course, their optimal objective values may not be equal. $\endgroup$ – Mark L. Stone Dec 26 '17 at 15:21
  • $\begingroup$ Correct me if I am wrong. Is it not that the above statement is true for unconstrained convex optimization problems? And for constrained convex optimization problems we have to show that the solution to their KKT is equal, right? $\endgroup$ – kosa Dec 26 '17 at 16:34
  • $\begingroup$ It's true for constrained or unconstrained, convex or non-convex, satisfying necessary conditions (constraint qualification) for KKT or not. $\endgroup$ – Mark L. Stone Dec 26 '17 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.