Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Least-Squares and Variants

alt text 

The ordinary least-squares (OLS) problem is a particularly simple optimization problem that involves the minimization of the Euclidean norm of a ‘‘residual error" vector that is affine in the decision variables. The problem is one of the most ubiquituous optimization problems in engineering and applied sciences. It can be used for example to fit a straight line through points, as in the figure on the left. The least-squares approach then amounts to minimize the sum of the area of the squares with side-length equal to the vertical distances to the line.

We discuss a few variants amenable to the linear algebra approach: regularized least-squares, linearly-constrained least-squares. We also explain how to use ‘‘kernels’’ to handle problems involving non-linear curve fitting and prediction using non-linear functions.

Outline