Linear Equilibrium Problem

Problem Definition

Imagine you're trying to match a puzzle with imperfect pieces. That's the situation we face in the linear equilibrium problem. We have a matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^m$ , but the equation system $A \cdot x = b$ may not have an exact solution.

In cases like this, we search for the best solution we can obtain by minimizing the error function

F(x) = \|A \cdot x - b\|_2^2

This function measures how far the product result $A \cdot x$ is from our desired target $b$ .

Optimization Problem

Now let's understand what we actually want to achieve. The minimization problem

\min_x \|A \cdot x - b\|_2^2

is the core of the linear equilibrium problem or what is often called the linear least squares problem. Imagine looking for the best position to throw a ball so it lands as close as possible to the target, even though you can't hit it exactly.

Why do we use this approach? Because in many real situations, the data we have contains noise or disturbances that make finding an exact solution impossible.

Formula Expansion

Now let's break down this formula to see what actually happens inside it

\min_x \|A \cdot x - b\|_2^2 = \min_x \sum_{i=1}^{n} (A \cdot x - b)_i^2

This expanded form shows that we're actually summing the squares of each error component. Similar to calculating the total squared distance between several prediction points and the actual target points. By squaring each error, we give a larger penalty to big errors compared to small ones.

Alternative Norms

It turns out there are several different ways to measure error, depending on the characteristics of the problem we're dealing with.

$\ell_1$ -norm works by summing the absolute values of errors

\min_x \|A \cdot x - b\|_1 = \min_x \sum_{i=1}^{n} |(A \cdot x - b)_i|

This approach is like measuring distance by walking in a city with grid-shaped streets. You have to move horizontally and vertically only, no diagonal movement. This method is more resistant to extreme outlier data.

$\ell_\infty$ -norm focuses on the largest error

\min_x \|A \cdot x - b\|_\infty = \min_x \max_{i=1,\ldots,n} |(A \cdot x - b)_i|

Imagine you're adjusting the height of an uneven table. This method will focus on fixing the highest or lowest table leg, ensuring no single part is too extreme.

The right choice of norm depends on the type of error we most want to avoid and the characteristics of the data we have.

Geometric Interpretation

Linear Equilibrium Problem Solution

Geometric illustration showing the relationship between vector

b

, projection

A\hat{x}

, and error vector.

This geometric visualization helps us understand what's actually happening. The flat plane in this diagram represents the column space of matrix $A$ (called Image A), which is all possible results of multiplication $A \cdot x$ .

Vector $b$ is the target we want to reach, but it may not lie within the column space of matrix $A$ . The optimal solution $\hat{x}$ produces $A\hat{x}$ which is the closest point to $b$ in that column space.

Vector $A\hat{x} - b$ shows the error vector connecting the best projection with the original target. Like a shadow of an object falling to the floor, $A\hat{x}$ is the closest "shadow" of $b$ in the available space.

Solution Methods

Each type of norm requires a different solution approach. Problems with $\ell_1$ -norm and $\ell_\infty$ -norm can be solved using linear optimization techniques, where we transform the problem into a form that can be handled by linear programming algorithms.

Meanwhile, the least squares problem with Euclidean norm has a special advantage. When errors in the data follow a normal distribution pattern (bell-shaped), then the solution we obtain provides the best estimate in a statistical sense, called the maximum likelihood estimator.