Quasi-Newton method for optimization

Given the set of 4 linear equations above, I'd like to optimize unknown parameters A, B, and C using a quasi-newton method. For example, coefficients r and given values R are as below:

Could you somebody help me with this?

[John D'Errico]

Why? Why would you possibly need to use a tool like quasi-Newton? Why would you even want to?

I can use a hammer to drive in a screw, but it would be a poor use of the tool, and I would not be happy with the result.

Is this a homework assignment for some strange reason? If so, then we should not be doing your homework.

Is this a problem you want to solve because you know how to use only one tool, or you heard about the method, and have decided to try to learn to use it? In any case, quasi-Newton is wildly the wrong tool.

Is final equation an equality constraint that MUST be satisfied, and the other three will be satisfied as well as possible? Or are all 4 equations allowed to have some error?

What measure would you apply to the residuals in any case?

[hinami]

Thanks for your comment.

First of all, I need to solve the equations for my research, definitely not for my homework.

r values are coefficients of spectral albedos at specific wavelengths, and R values are measured albedos.

A, B, and C represent the fractions of surface types.

I want to know the fractions of each surface type, and this method is likely one of the most popular approaches in this research area.

All 4 equations are allowed to have some errors.

[James Tursa]

"... All 4 equations are allowed to have some errors ..."

Really? You mean the fractions don't even have to add up to 1? Seems like it would make more sense to enforce the fraction total as a constraint. And add A>=0, B>=0, and C>=0 constraints as well.

[hinami]

You are right. Ideally, A+B+C should be 1 and all of these three unknown parameters should range between 0 and 1.

If these constraints can be enforced, it would be the best.

[Sam Chak]

Hi Hinami, can you provide more info about the constrained equations? Like telling us the name and your area of research. Are you looking for Constrained Nonlinear Optimization Algorithms?

[hinami]

Hi Sam,

I'd like to reproduce same approach described in a papper (https://tc.copernicus.org/articles/6/431/2012/). My research area is sea ice, though I'm a newface in this area.

[Sam Chak]

Hi Hinami,

I think your field belongs to Remote Sensing, and I'm no expert on this.

The authors stated on page 5 that they used the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm (which belongs to the quasi-Newton family) to solve the constrained system of linear equations {Eq. (2)}, but the set of Eq. (2) is ill-conditioned. Thus, the authors added another constraint on the interval of the solution between 0 and 1. See Eq. (3).

The 'fminunc' function is an unconstrained nonlinear optimization algorithm that uses the 'quasi-newton' algorithm by default. The 'fmincon' function deals with constrained nonlinear optimization problem and it uses a sequential quadratic programming (SQP) method.

https://www.mathworks.com/help/optim/ug/fminunc.html

https://www.mathworks.com/help/optim/ug/fmincon.html

[hinami]

Hi Sam,

Thanks for you suggestion. This is very helpfull. I'll try 'fmincon' function for the equations.

Answer 1

[Bruno Luong]

Use FMINCON to minimize

norm(r*x-R)^2

with constraints

sum(x)=1

x>=0

r=[0.22 9.94 0.08;
   0.16 0.95 0.08;
   0.07 0.87 0.08];
R = [0.49; 0.42; 0.19]

x = fmincon(@(x) norm(r*x-R)^2, ones(3,1)/3, [], [], ones(1,3), 1, zeros(3,1), []);
A = x(1)
B = x(2)
C = x(3)

Answer 2

[John D'Errico]

If all you need to do is solve the linear system of equations, subject to the EQUALITY constraint, use LSQLIN. That is the tool designed to solve the problem, (not a quasi-Newton algorithm or fmincon, both of which are overkill.)

r=[0.22 9.94 0.08;
   0.16 0.95 0.08;
   0.07 0.87 0.08];
R = [0.49; 0.42; 0.19];
Aeq = [1 1 1]; % the equality constraint
beq = 1;
lb = [0 0 0]; % bound constraints
ub = [1 1 1];
ABC = lsqlin(r,R,[],[],Aeq,beq,lb,ub);

ABC
ABC =
         0.969440866890935
        0.0305590528348618
      8.02742320184426e-08
      
A = ABC(1);
B = ABC(2);
C = ABC(3);

So A, B, and C are those 3 numbers. Best to leave them in the vector ABC, thouh you can extract tham as I did. They sum to 1. They lie in the interval [0,1].

You do NOT want to use a quasi-newton method to solve this, as it would be inappropriate, because quasi-newton methids are not designed to solve bound constrained problems with equality constraints. At least they are not so designed without considerable effort on your part, where you would need to learn a lot about optimization methods.

Anyway, just because they used the wrong tool to solve the problem in a paper, does not mean you should follow their lead. If they jumped off a bridge, and survived, does this mean it was a good idea?

You do not want to use fmincon to solve it, as that would be overkill to use an iterative method that requires starting values to solve a simple linear least squares problem that is subject to linear constraints.

Use lsqlin to solve that class of problem. It is designed to directly solve the problem where it will minimize the norm of the residuals norm(r*ABC - R), subject to the indicated constraints.

[Bruno Luong]

Another method is QUADPROG, which could be under lsqlin hood

x = quadprog(r'*r,-r'*R,[], [], ones(1,3), 1, zeros(3,1), [])

[Bruno Luong]

Another way less obvious is lsqnonneg (the main advantage is no need for optimization lbx)

M = [r'*r, ones(3,1); ones(1,3), 0];
y = [r'*R; 1]; 
x = lsqnonneg(M, y);
x = x(1:3)

Answer 3

[hinami]

These work fine.

Thank you all. Much appreciated.