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

Linear regression

A popular example of least-squares problem arises in the context of fitting a line through points. This is illustrated below in two dimensions.

alt text 

In this example we seek to analyze how customers react to an increase in the price of a given item. We are given two-dimensional data points (z_i,y_i), i=1,ldots,m. The z_i's contain the prices of the item, and the y_i's the average number of customers who buy the item.

The generic equation of a non-vertical line is y = x_1 z+x_2, where x=(x_1,x_2) contains the decision variables. The quality of the fit of a generic line is measured via the sum of the squares of the error in the component y (blue dotted lines). Thus, the best least-squares fit is obtained via the least-squares problem

min_x : sum_{i=1}^m (x_1 z_i+x_2 - y_i)^2 .

Once the line is found, it can be used to predict the value of the average number of customers buying the item (y) for a new price (z). The prediction is shown in red.

The linear regression approach can be extended to multiple dimensions, that is, to problems where the z-axis in the above problem contains more than one dimension (see here). It can also be extended to the problem of fitting non-linear curves.