MATLAB Central Newsreader - Common tangent

Re: Common tangent

Giuseppe Brunello — Mon, 11 Feb 2008 03:38:01 -0500

Thank you for all replies and sorry I didn't reply earlier.

I agree that having a function, as opposed to a set of
points, would make the implementation much neater, but alas
the problem I had in mind is to obtain a phase diagram for a
binary mixture from the the Gibb's free energy. The material
system minimizes the energy, and if a binary mixture of the
two has a lower energy than a single phase then you'll get
two phases (the system's energy lies on the common tangent,
it being the weighted sum of the energy of the two phases).

Also the slope of the system approaches infinity as you
approach pure substances (i.e. the chemical potential of B
in pure A is infinite).

For an implementation with discreet points I was thinking of
searching for the minimum of both curves, and then scan both
sides with a tangent. If the tangent is lower then the other
curves at all points I continue searching, if not I've
intersected the other curve (and have a close approximation
of the common tangent).

Anyways thanks for all your help, I just thought this
problem was neat.

Re: Common tangent

Bruno Luong — Wed, 28 Nov 2007 17:58:51 -0500

"John D'Errico" <woodchips@rochester.rr.com> wrote in
message <fik8j5$jpn$1@fred.mathworks.com>...

>
> Are you kidding? I'm trying to suggest that
> an optimization will be fraught with problems.
>

Sorry for miss-reading John. It seems that you gave a lot of
hints about chosing the metric for calcution of distance
between two tangents. The metric must be explicitely defined
in the optimization framework, and it is extremely
important, I agree. But how is the impact of metric on the
performance of a zero solver of multivariable function?

Bruno

Re: Common tangent

John D'Errico — Wed, 28 Nov 2007 17:30:13 -0500

"Bruno Luong" <b.luong@fogale.fr> wrote in message
<fik01e$csg$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in
> message <fijhn9$bfi$1@fred.mathworks.com>...
> >
> > Also in the event of the optimization, recognize
> > that while an optimizer can solve the problem,
> > this may well have multiple local minima, or it
> > may have no true solution at all. You will need
> > good starting values, or you will need to start
> > off the optimizer at multiple points, taking the
> > best overall solution.
> >
>
> John,
>
> Why you are suggesting optimization tool for such problem
> with all the eventual drawbacks (e.g., metric tbd, i.e.,
> closest notion tbd, local minima, hard to find all the
> solutions, hard to distinguish whereas a numerical solution
> is a real solution)?
>
> It seems to me optimization is a too complex tool and not
> suitable for such problem. I would avoid it all together.
>
> There is much better way to find intersection of two curves
> in the plane.
>
> Bruno

Are you kidding? I'm trying to suggest that
an optimization will be fraught with problems.

John

Re: Common tangent

Bruno Luong — Wed, 28 Nov 2007 17:07:45 -0500

A little program for fun. Zeros solver is dirty written, one
can do much better.

Bruno

% Input function
x=[-5:0.5:5];
f=sin(x) + 0.01*x.^3;
g=sin(x/2+1) - 2;

%
% Call function
%
commontangent(x, f, g);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function commontangent(x, f, g)
%
% Solve and graphic output for common tangent
%

% Spline
F=spline(x,f);
G=spline(x,g);
% Derivative
DF=splinederive(F);
DG=splinederive(G);
% Constant term
AF=coef0(F,DF);
AG=coef0(G,DG);

% fine grid
xx=linspace(min(x),max(x),100);

af=ppval(AF,xx); bf=ppval(DF,xx);
ag=ppval(AG,xx); bg=ppval(DG,xx);

cf=[af./sqrt(1+bf.^2); bf; xx];
cg=[ag./sqrt(1+bg.^2); bg; xx];

%
% Solve for common tangent; dirty way
%
c=poly2poly(cf, cg);

%
% Graphic output
%
figure(1);
clf;

subplot(2,1,1);
hf=plot(x,f,'b+',...
        xx,ppval(F,xx),'b',...
        x,g,'g+',...
        xx,ppval(G,xx),'g');
hold on;

for n=1:size(c,2)
    cn=c(:,n);
    b=cn(2);
    a=cn(1)*sqrt(1+b^2);
    x2=cn([3 6]);
    ht=plot(x2, polyval([b a], x2), 'ko-');
end
h=[hf(1) hf(3) ht(1)];
legend(h, 'f', 'g', 'common tangents');

subplot(2,1,2);
h=plot(cf(1,:),cf(2,:),'b',...
       cg(1,:),cg(2,:),'g',...
       c(1,:), c(2,:), 'k.');
legend(h, 'f-tangent', 'g-tangent', 'common tangents');

end

% derivative of a spline
function d=splinederive(pp)
d=pp;
d.order=pp.order-1;
order=d.order:-1:1;
d.coefs=pp.coefs(:,1:d.order).*repmat(order,pp.pieces,1);
end

% constant coefficient of the tangent
function A=coef0(F,DF)
A=F;
z=zeros(DF.pieces,1);
P=[DF.coefs z] + ...
  [z repmat(DF.breaks(1:end-1)',1,DF.order).*DF.coefs];
A.coefs=F.coefs-P;
end

% intersection of two line segments
function c=seg2seg(s1, s2)

M=[s1(1:2,2)-s1(1:2,1) -s2(1:2,2)+s2(1:2,1)];
rhs=s2(1:2,1)-s1(1:2,1);
sol=M\rhs;
if all(sol>=0 & sol<=1)
    c=[s1*[1-sol(1) sol(1)]'; ...
       s2*[1-sol(2) sol(2)]'];
else
    c=[];
end

end

% intersection of a q segment and a polygone
function c=seg2poly(s1, P)
c=[];
for i=2:size(P,2)
    c=[c seg2seg(s1, P(:,i-1:i))]; %#ok
end
end

% intersection of two polygones
function c=poly2poly(P1, P2)
c=[];
for i=2:size(P1,2)
    c=[c seg2poly(P1(:,i-1:i), P2)];%#ok
end
end

Re: Common tangent

Bruno Luong — Wed, 28 Nov 2007 15:04:14 -0500

"John D'Errico" <woodchips@rochester.rr.com> wrote in
message <fijhn9$bfi$1@fred.mathworks.com>...
>
> Also in the event of the optimization, recognize
> that while an optimizer can solve the problem,
> this may well have multiple local minima, or it
> may have no true solution at all. You will need
> good starting values, or you will need to start
> off the optimizer at multiple points, taking the
> best overall solution.
>

John,

Why you are suggesting optimization tool for such problem
with all the eventual drawbacks (e.g., metric tbd, i.e.,
closest notion tbd, local minima, hard to find all the
solutions, hard to distinguish whereas a numerical solution
is a real solution)?

It seems to me optimization is a too complex tool and not
suitable for such problem. I would avoid it all together.

There is much better way to find intersection of two curves
in the plane.

Bruno

Re: Common tangent

Bruno Luong — Wed, 28 Nov 2007 15:04:11 -0500

Re: Common tangent

Bruno Luong — Wed, 28 Nov 2007 15:04:09 -0500

Re: Common tangent

John D'Errico — Wed, 28 Nov 2007 10:59:53 -0500

"Bruno Luong" <brunoluong@yahoo.com> wrote in message
<fij6n6$9h7$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
> wrote in message <fiivds$lqs$1@fred.mathworks.com>...
> >
> > As John intimated, if you only possess f and g in the
> form of discrete
> > vectors, you cannot expect to find precise solutions to
> the problem but would
> > have to settle for solutions to finite difference
> approximations.
>
> After formalization, this problem is equivalent to be
> finding two abscissas so that two coefficients that describe
> the tangent at respective points are matched. This is like
> finding an intersection of two parametric curves in R^2
> (each axis of the plane corresponds to a coefficient of the
> tangent).
>
> Well, first the derivative must be computed one way or
> another, finite difference would provide the derivative, but
> only at discrete points.
>
> IMHO the "tricky" part is to be able to calculate the
> derivative - not only at discrete point - but at any point.
> The same applied for the input functions. And it's better if
> one can provide a continuous functions and its derivatives,
> so that the two parametric curves are continuous, and they
> intersection can be solved.
>
> If one can parametrize the input functions by cubic-spline,
> its derivative is continuous (even C^1 IIRC). Both are
> piecewise polynomials.
>
> Next, it is just a question of solving it. There is
> certainly a little bit of work, but I can't see any major
> difficulty to implement an algorithm to solve the problem.

Yes. It will either be a problem of comparing all
pairs of tangent lines, taking the two which are
"closest" under some metric, or an optimization,
to find the two points x1 and x2, one for each
continuous curve. Fminsearch will probably be
adequate for the optimization task, since this is
only a two variable problem. Of course, fsolve
will also suffice. You can formulate it for either
solver.

In the latter case, you will need continuous
functions, so it seems silly to discretize the
problem with vectors of points, which then
need to be interpolated by splines. Keep them
as functions to be evaluated if at all possible.
Of course, if they are indeed functions, then
you need to differentiate them accurately. You
might need to use a tool like my derivest, from
the file exchange. So perhaps a pair of spline
interpolants might be a good choice, since they
will be easy and efficient to interpolate.

Also in the event of the optimization, recognize
that while an optimizer can solve the problem,
this may well have multiple local minima, or it
may have no true solution at all. You will need
good starting values, or you will need to start
off the optimizer at multiple points, taking the
best overall solution.

Finally, in either event, you will need to choose
some metric to compare two lines. How will you
define two lines as being the same, since in an
optimization, the two lines will generally be
only approximately the same and you need to
minimize the difference? I'd imagine that a
reasonable metric is the integral of the square
of the difference of the two lines, integrated
over the domain of the interval where the
functions will be compared. Knowing the slopes
and intercepts of the two lines, this objective
should be computable directly using a little
algebra.

So while Bruno is correct that it is doable, it
might take a bit of work to do it well.

John

Re: Common tangent

Bruno Luong — Wed, 28 Nov 2007 07:52:06 -0500

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
wrote in message <fiivds$lqs$1@fred.mathworks.com>...
>
> As John intimated, if you only possess f and g in the
form of discrete
> vectors, you cannot expect to find precise solutions to
the problem but would
> have to settle for solutions to finite difference
approximations.

After formalization, this problem is equivalent to be
finding two abscissas so that two coefficients that describe
the tangent at respective points are matched. This is like
finding an intersection of two parametric curves in R^2
(each axis of the plane corresponds to a coefficient of the
tangent).

Well, first the derivative must be computed one way or
another, finite difference would provide the derivative, but
only at discrete points.

IMHO the "tricky" part is to be able to calculate the
derivative - not only at discrete point - but at any point.
The same applied for the input functions. And it's better if
one can provide a continuous functions and its derivatives,
so that the two parametric curves are continuous, and they
intersection can be solved.

If one can parametrize the input functions by cubic-spline,
its derivative is continuous (even C^1 IIRC). Both are
piecewise polynomials.

Next, it is just a question of solving it. There is
certainly a little bit of work, but I can't see any major
difficulty to implement an algorithm to solve the problem.

Bruno

Re: Common tangent

Roger Stafford — Wed, 28 Nov 2007 05:47:40 -0500

"Giuseppe Brunello" <gbrunello3@gatech.edu> wrote in message <fihu0m
$quf$1@fred.mathworks.com>...
> I want to find between two functions f and g their common
> tangent(s). Is there a built in MatLab command that will
> take two vectors (calculated from f and g) and return the
> common tangent(s)?
---------
  If I understand you correctly, Giuseppe, your "common tangents" problem is
equivalent to finding values for arguments, a and b, which satisfy the
equations:

(f(b)-g(a))/(b-a) = f'(b) = g'(a)

  I am far from being knowledgeable about the Optimization Toolbox but it
seems to me that the 'fsolve' function therein could be used for this purpose,
provided you have it on your computer and can compute the two derivative
(gradient) functions, f' and g'.

  As John intimated, if you only possess f and g in the form of discrete
vectors, you cannot expect to find precise solutions to the problem but would
have to settle for solutions to finite difference approximations.

Roger Stafford

Re: Common tangent

John D'Errico — Tue, 27 Nov 2007 22:53:48 -0500

Common tangent

Giuseppe Brunello — Tue, 27 Nov 2007 20:17:26 -0500

I want to find between two functions f and g their common
tangent(s). Is there a built in MatLab command that will
take two vectors (calculated from f and g) and return the
common tangent(s)?