Ordinary, Constrained, Multi-objective, and Nonlinear least square.

In the first part, I discussed the ordinary least square problem in detail. In this part (part 2) I will go over the multi-objective least-square problems. If you have not already read the first part please refer to the following article for more information:
For more information and a more detailed explanation, please refer to my YouTube channel.
Multi-Objective Least Square
Assuming we are looking for a solution that makes more than one objective/cost functions small. This problem is referred to as a multi-objective optimization problem. If all the objective functions are in the form of a least-square problem then the problem is called the multi-objective least square problem.
Problem Formulation
Suppose we have K least-square objective function and our goal is to find a single x that makes all of them small.
Where each Aᵢ is mᵢ x n matrix and each bᵢ is mᵢ x 1 vector. There are many ways to solve and formulate the multi-objective LS problem but perhaps the most common method is to minimize the weighted sum of all objective functions, where the weights determine the influence or importance of each objective function.
where λ’s are the weights for each objective function. Here I introduce two methods to solve the multi-objective LS problems.
Method 1: Direct DifferentiationIn this method, we take the derivative of Jₜₒₜ with respect to x and set it to zero.
Although this method seems easy enough but the second method is more common and provides a better intuition. Method 1: Stacked MatrixThis is a better approach to solve the multi-objective LS problems since it takes advantage of the solution of the OLS problem and directly model the problem as an OLS problem. We first construct a new matrix A and B, then formulate the problem as a simple OLS problem as follows using what we derived in figure 2.
This method only works if the stacked A has linearly independent columns similar to an OLS where it requires matrix A to have linearly independent columns (tall and left invertible matrix).
When Stacked Matrix has Linearly Independent Columns
As it was mentioned before, to use the stacked matrix approach we need to make sure the stacked matrix is left-invertible or has linearly independent columns, this means:
- If at least one of the matrices A₁, A₂, . . ., Aₖ has linearly independent columns then the stacked matrix will have the linearly independent columns.
-
However the stacked matrix can have linearly independent columns even if all the matrices A₁, A₂, . . ., Aₖ have linearly dependent columns and this happens when the following condition is met: Assume A₁ is m₁x n, A₂ is m₂ x n and Aₖ is mₖ by n then if each m_i is less than or equal to n but their sum is greater than or equal to n then the stacked matrix is still tall and can be a left invertible matrix (Linearly independent columns). Mathematically this means the following:
Tikhonov Regularization
Suppose you are trying to solve a least square problem given:
- Matrix A does not have linearly independent columns.
- Or we would like to minimize ||Ax – b||² such that ||x|| is small (norm of x is small).
One way to formulate this problem is as follows:
In figure 7, the λ is a positive weight and determines the importance of the second objective function compared to the first one. If λ is zero then we go back to the OLS. if λ is small then we place more weights on the first objective function. This is a common way of formulating the multi-objective problem by normalizing the weight of the primary objective function to 1 and let λ denotes the relative weights.
To solve the above equation we can use either method 1 or method 2, but to demonstrate the stacked matrix approach, we will be using the second method.
Before solving the above problem in figure 8, it is important to prove that stacked matrix A has linearly independent columns. There are two ways to prove this:
- The identity matrix has linearly independent columns therefore the stacked matrix has linearly independent columns whether A has dependent columns or not.
- Follow the standard procedure to prove the linear independence for the columns:
Now that the stacked matrix has linearly independent columns then the solution can be determined easily as follows:
To learn more about multi-objective Least Squares, please refer to my YouTube channel.
What is next:
Make sure to check out part 3 article on constrained least square.
Conclusion
In this article, I discuss multi-objective least square problems, in the next part (part 3) I will discuss the constrained- least square problems. If you find any part of this article or the previous one complicated, please refer to my YouTube channel, where I have a series of videos on numerical linear algebra and Optimization, which requires no prior knowledge in matrix algebra or optimization.