liveBook · Manning

Convex optimization

As explained in Timeless Algorithms, The Foundational Ideas

Convex optimization is optimization in which the objective and feasible region have convex structure, allowing local optima to be global optima under standard conditions.

In a hard-margin support vector machine (SVM), convex optimization selects the separating boundary with the widest margin. The objective is convex, and the constraints are linear, so an optimal solution is global rather than an inferior local solution. section 8.2.3

Minimize 12||w||2 subject to yi(w∙x+b)≥1 for all i

This formulation minimizes the squared weight norm while requiring every training point to be correctly separated by the margin. section 8.2.3

Training observations that meet the constraint with equality are support vectors: they lie on the margin boundaries and constrain their maximum separation. Data that is not perfectly separable requires a more flexible soft-margin formulation. section 8.2.3

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Formulates the hard-margin objective and linear constraints, explains global optimality and support vectors, then points to soft margins for nonseparable data.
Examples
Uses the hard-margin SVM objective, its separation constraints, and margin-boundary support vectors as the concrete example.
What you can do after
Understand how convexity and linear constraints yield a globally optimal maximum-margin separator when training data is linearly separable.
How it connects
Connects convex optimization to support vector machines, maximum-margin classification, support vectors, and generalization.

Also explained in

Compare how 2 books explain convex optimization →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.