Minimization subject to positive definite constraint

Hi all,

I would appreciate any idea on how to solve the following:

I'm trying to extract vector x from the matrix equation:

M*x=S

where M is a known matrix and S is a known vector. M is somehow ill-conditioned and S is a noisy vector arising from experimental measurements. Therefore, a naive x=M\S inversion yields junk.

I still have a hope though: There is an additional constraint for the problem. There exists a POSITIVE SEMIDEFINITE matrix G whose entries are linear functions of the elements of x. For example, G(1,1)=x(1), G(1,2)=x(3), G(2,2)=1-x(1), etc. I know the analytical form of G in terms of x.

I've been using fminsearch together with a cheap function that calculates norm(M*x-S) and adds a penalty if vector x is such that G is non-positive semidefinite. However, the result is still poor. Does anyone know if there is code around that I can adapt to solve my problem.

Any inputs will be highly appreciated.

Answer 1

[Walter Roberson]

I wonder whether your G is continuous in the x values?

fminsearch documents that,

"fminsearch can often handle discontinuity, particularly if it does not occur near the solution. fminsearch may only give local solutions."

Possibly this is one of the cases where the discontinuities matter?

I also wonder if your penalty is continuous rather than absolute such as +infinity ? +infinity or an increment that is such that the changes in value of the function are less than eps() of the penalty could end up generating a flat surface of penalized areas, and it might be quite difficult to get out of such an area.

[Joel Yuen]

Hi Walter.

Thanks for your prompt answer.

Yes, indeed G is a continuous function of x. As I wrote above, the entries of G are simple linear functions of x and look either like "x(i)" or "1-x(i)" for some row i in the vector x.

The penalty is continuous. It looks as follows:

function penalty=deviation(M,x,S);

%First penalty to find reasonable solutions for the matrix equation

penalty1=norm(M*x-S);

G=... %Some long expression of x. I'm not transcribing it here.

%Second penalty for non-positive definite matrices G

eig_G=eig(G);

penalty2=0;

if any(eig_G<0)

penalty2=-100000*sum(eig_G(eig_G<0));

end

penalty=penalty1+penalty2

-----

Any comments on this?