non linear minimization problem

25 ビュー (過去 30 日間)
Alberto Menichetti
Alberto Menichetti 2016 年 5 月 10 日
コメント済み: Alberto Menichetti 2016 年 5 月 11 日
Suppose I have
aA + bB + cC = E
Where A,B,C are column vectors with components in R+; I need to find a,b,c in R such that a,b,c >= 1 and E is minimized. What's the "right" name for that kind of problem? Which class of algorithms should I use to solve that problem in matlab?
  3 件のコメント
Alberto Menichetti
Alberto Menichetti 2016 年 5 月 11 日
Obviously I wanted to write
|a,b,c|>=1

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

採用された回答

Teja Muppirala
Teja Muppirala 2016 年 5 月 11 日
It depends on what you mean by "minimize".
Do you mean the sum of squares, sum(E.^2)? If so then it's a quadratic programming problem and it's very easy to set up.
Do you mean the max(abs(E)) or sum(abs(E))? Then it is linear programming, and it is a bit more tricky (you need to set up the constraint matrices right).
In any case, the following is a sample of how you would do it.
----------------------------------
%% First: I'll make some random data to work with
rng(10)
N = 5; % Say 5-dimensions
A = randn(N,1);
B = randn(N,1);
C = randn(N,1);
ABC = [A B C];
%% Case 1: Minimize the sum of squares of E, also called L-2 norm
ABC = [A B C];
Q = ABC'*ABC;
abc_opt_L2 = quadprog(Q,[],[],[],[],[],ones(3,1))
E_opt = ABC*abc_opt_L2;
%% Case 2: Minimize sum(abs(E)) also called L-1 norm
f = [0 0 0 ones(1,N)];
A_cons = -eye(3+N);
A_cons = [A_cons; ABC -eye(N); -ABC -eye(N)];
b = [-1; -1 ;-1; zeros(N,1); zeros(2*N,1)];
values = linprog(f,A_cons,b,[],[]);
abc_opt_L1 = values(1:3)
E_opt = ABC*abc_opt_L1;
%% Case 3: Minimize max(abs(E)) also called L-infinity norm
f = [0 0 0 1];
A_cons = blkdiag(-eye(3+1));
A_cons = [A_cons; ABC -ones(N,1); -ABC -ones(N,1)];
b = [-1; -1 ;-1; -1; zeros(2*N,1)];
values = linprog(f,A_cons,b,[],[]);
abc_opt_Linf = values(1:3)
E_opt = ABC*abc_opt_Linf;
The code above gives me the following optimal values for a,b,c in each case
abc_opt_L2 =
1.0000
1.0851
1.0802
abc_opt_L1 =
1.0000
1.6379
1.6855
abc_opt_Linf =
1.0000
1.3236
1.0000
  1 件のコメント
Alberto Menichetti
Alberto Menichetti 2016 年 5 月 11 日
Thank you for the very detailed explaination. I tried to implement the cases you suggested but, even if I'm still trying to figure me out why, it seems that for my needs ga() is working well. I need that the components of E behave like the y of a function oscillating around 0

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

その他の回答 (3 件)

John D'Errico
John D'Errico 2016 年 5 月 10 日
You want to solve for 4 parameters, a,b,c,E. They all enter the problem linearly.
However, since the set of equality constraints
a*A + b*B + c*C - E = 0
will not by solved exactly in general, you have two competing goals, which you have not said how they will be resolved. So if there are multiple elements in those vectors, no single value for {a,b,c,E} exists to satisfy all equations at once.
So, you MIGHT choose to define this as a linear least squares problem subject to bound constraints on a,b,c, but that ignores the goal that E is minimized. (May E be negative?)
This is effectively a homogeneous linear system in 4 unknowns, subject to bound constraints on {a,b,c}, as well as an additional requirement on E.
1. If your vectors have length greater than 4 then there will in general be NO exact solution.
2. If your vectors have length exactly 4, then depending on the vectors, there may be infinitely many solutions, or there will be no solution other than that all the unknowns are 0. Of course, in that case, it would be impossible for a solution to satisfy the requirement that each of {a,b,c}>1.
3. If there are less than 4 elements in each vector, or if the system is rank deficient, then there will usually be infinitely many solutions and one would choose a solution that minimizes E, subject to the bounds.
So, much will depend on the length of your vectors, and the vectors themselves.
  1 件のコメント
Alberto Menichetti
Alberto Menichetti 2016 年 5 月 10 日
The size of my vectors is greater than 4 and yes E may be negative. So if I well understand your reply I should try to model that problem as a linear programming problem, looking for an approximate solution. Could you please make me an example of how to model that in matlab?

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


Brendan Hamm
Brendan Hamm 2016 年 5 月 10 日
This would be an instance of a linear problem (i.e. it is linear in the coefficients a, b and c). Therefore you would want to use the function linprog .

Bjorn Gustavsson
Bjorn Gustavsson 2016 年 5 月 10 日
Am I correct in interpreting R+ as the N-dimensional positive real number sub-space? And you want to minimize E for a, b, and c >= 1?
If so I suggest you turn off your computer and have a short sit-down with pen and paper, pencil will also do, and look at this problem for the 2-D case.
HTH
  1 件のコメント
Alberto Menichetti
Alberto Menichetti 2016 年 5 月 10 日
a,b,c >= |1|

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

Community Treasure Hunt

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

Start Hunting!

Translated by