Loosely Constrained Least Squares Solution

5 ビュー (過去 30 日間)
Cy Haukdal
Cy Haukdal 2020 年 8 月 30 日
編集済み: Cy Haukdal 2020 年 9 月 16 日
Thanks in advance!
I am attempting to find the least squares solution to the matrix equation Ax=b. A, n x m, is a thin matrix, where n>>m, leading to an overdetermined system. Additionally, the system is constrained loosely by the equation Cx=d, where C is a 4x21 matrix and d is a 4x1 vector. Finally, the solutions should fall within the range [-1 1].
For context, I am attempting to optimize a set of Chebyshev polynomial coefficients (hence the solution limit of [-1 1]) defined over the interval [-1 1], expanded to the 20th order, where the polynomial and polynomial first derivative endpoints are pinned to known values (Cx=d). A (n x m) here represents m nominal Chebyshev terms of the first kind (1, x, 2x^2-1, etc.) evaluated at n points between -1 and 1. b represents the value of the original polynomial evaluated at the same n points between -1 and 1, leaving the solution x to be the optimized Chebyshev coefficients.
As such, I applied the following options to lsqlin:
options = optimset('MaxIterations', 1000000, 'TolFun', 1e-5, 'TolCon', 1-e3)
And called lsqlin for each set of coefficients to optimize:
x = lsqlin(C,d,A,b,[],[],-1,1,[],options)
As previously stated, the constraint tolerance is loose, and error on the range of e-3 is acceptable. However, this method of calling lsqlin does not seem to allow for the constraints to have any tolerance. The first derivative endpoints of the resulting polynomials are pinned to the constraint values as desired, but to numerical precision, without any error allowance. This results in lsqlin being unable to find a solution to the problem within the allowed iterations (or even test runs two orders of magnitude higher), and unreasonable results output where coefficients are found to be on the order of e3, not within [-1 1].
Is there something I am missing with the application of constraint tolerances here? Or, is there a way to place a hierarcy on constraints, such that one will be met (coefficients within [-1 1]) at the expense of the other constraints?
Thanks again!
-CH

採用された回答

John D'Errico
John D'Errico 2020 年 8 月 30 日
編集済み: John D'Errico 2020 年 8 月 30 日
Your concept of what a constraint tolerance means is wrong. and loose equality constraints are not something you can set.
Instead, you want to set inequality constraints. That is, if you are willing to have these loose constraints, do this:
LooseTol = 1e-3;
CC = [C;-C];
dd = [d + LooseTol ; -d + LooseTol];
lb = -ones(1,size(A,2));
ub = ones(1,size(A,2));
x = lsqlin(A,b,CC,dd,[],[],lb,ub);
Effectively, I have constrained
C*x <= d + LooseTol
C*x >= d - LooseTol
By use of general linear inequality constraints.
  5 件のコメント
John D'Errico
John D'Errico 2020 年 8 月 31 日
I don't understand. Before you were saying the bounds were not being satisfied. Clearly they were in the cases you show.
In those examples, we see one case where the solution you expected was not the one that was found. In another case, the solution is the same.
What we do not know is if the linear system may be well posed or not. If it is rank deficient, then you may not get a unique solution. In fact, you can get infinitely many solutions, so the solution you expect need not be the one you get.
It is a little hard to know what is the issue here. I would do things like test the condition number of the matrix A. Is it large? (I.e., near 1/eps?) If so, then problems will exist. Is the solution you think to be "correct" really a valid solution? Are the constraints active at that set? What would the unconstrained problem yield as a solution?
Cy Haukdal
Cy Haukdal 2020 年 8 月 31 日
編集済み: Cy Haukdal 2020 年 9 月 16 日
To be more specific, a Chebyshev polynomial should both be characterized by coefficients and values within [-1 1].
In this case, the bounds applied via Cx=d are met, the bounds on the soultion values are met [-1 1], but the problem is incorrectly solved, indicated both by relation to expected solution and values outside of [-1 1].
To answer your questions:
  • The problem is not well posed if multiple solutions exist, although since lsqlin is exiting based on iterations, its possible the answers are not solutions
  • The matrix A is not rank deficient
  • The condition number of A is 2.9
  • It is unknown if the solutions are valid, but it is assumed, since there are successful cases
  • "correct" solutions meet all constraints imposed on Ax=b
  • Unconstrained problem A\b produces the correct/expected solution in all cases, but with end conditions which are insufficient for my purposes. Also implies solutions are valid.
Even in the above runs, the error at constrained points is orders of magnitude below the tolerance. I think the issue still lies here.

サインインしてコメントする。

その他の回答 (1 件)

Bruno Luong
Bruno Luong 2020 年 8 月 30 日
alpha = some positive value; % larget alpha, norm(C*x-d) gets smaller
E = [A; alpha*C];
f = [b; alpha*d];
x = lsqlin(E,f,[],[],[],[],-1,1,[],options)
  3 件のコメント
Bruno Luong
Bruno Luong 2020 年 8 月 30 日
You might be right John. I just copy OP's bounds and focussing on the change of cost function and equality constraints.
John D'Errico
John D'Errico 2020 年 8 月 30 日
Yes. I realize that you surely know the difference. This was more for the benefit of the OP, or others who would see your response.

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeLinear Least Squares についてさらに検索

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by