1

y切片と角度qで定義されるN本の線があります。制約は、すべてのN本の線が1点で交差する必要があるということです。最終的に制約を取得するために私が思いつくことができる方程式は次のとおりです。

Y = tan(q(1))X + y(1)
Y = tan(q(2))X + y(2)
...

手作業で、N = 3または4の場合に制約を取得できますが、Nが4より大きい場合に1つの制約を取得するのに問題があります。N= 3または4の場合、Xについて上記の方程式を解くと、次のようになります。 2つの方程式を設定すると、それらを互いに等しく設定できます。N> 4の場合、Xに等しい2つ以上の方程式が得られ、それらを1つの制約に凝縮する方法がわかりません。それらを1つの制約に凝縮できず、動的に作成される（渡されるNに応じて）複数の制約を使用して最適化問題を解決できる場合も、問題ありません。

私が何をしているのかをよりよく理解するために、N=3の制約を取得する方法を示します。次の3つの方程式から始めます。

Y = tan(q(1))X + y(1)
Y = tan(q(2))X + y(2)
Y = tan(q(3))X + y(3)

次に、それらを互いに等しく設定し、次の方程式を取得します。

tan(q(1))X + y(1) = tan(q(2))X + y(2)
tan(q(2))X + y(2) = tan(q(3))X + y(3)

次に、Xを解いて、この制約を取得します。

(y(2) - y(1)) / (tan(q(1)) - tan(q(2))) = (y(3) - y(2)) / (tan(q(2)) - tan(q(3)))

Xを解くための2つの方程式があることに注意してください。N>4の場合、2を超えることになります。これは、制約を動的に作成し、MATLABで複数の制約を処理する最適化関数を呼び出すことができれば問題ありません。はるかに1つを見つけていません。

4

1 に答える 1

1

q上記の方程式も成り立つ一方で、「実際の」問題が最小化されるように最適化アルゴリズムを調整する必要があるとあなたは言います。

5番目のEuclidaxoimqは、2つの線が等しいが、対応する線が等しくない場合を除いて、すべての線が常に他のすべての線と交差することを保証することに注意してくださいy0。この最後のケースは（浮動小数点のコンテキストでは）非常にまれなので、ここではスキップしますが、堅牢性を高めるために、最終的には含める必要があります。

さて、まず、行列の観点から考えてみましょう。制約は、行列方程式によって定式化できます。

y = tan(q)*x + y0

ここqで、、yおよびy0は[Nx1]行列でxあり、未知のスカラーです。y = c*ones(N,1)たとえば、同じ定数のみを含む行列に注意してください。これは実際には非線形制約です。つまり、次のように表現することはできません。

A*q <= b   or   A*q == b

いくつAかの計画行列とbいくつかの解ベクトルを使用します。したがって、この非線形制約を定義する関数を作成する必要があります。この関数は、のようなオプティマイザーに渡すことができますfmincon。ドキュメントから：

x = fmincon（fun、x0、A、b、Aeq、beq、lb、ub、nonlcon）は、nonlconで定義された非線形不等式c（x）または等式ceq（x）に最小化を適用します。fminconは、c（x）≤0およびceq（x）= 0になるように最適化します。境界が存在しない場合は、lb=[]および/またはub=[]に設定します。

あなたは実際に正しい方向に進んでいたことに注意してください。線のx任意のペアの交点の位置を次の方程式で解くことができます。q(n),y0(n)q(m),y0(m)

x(n,m) = (y0(n)-y0(m)) / (q(m)-q(n))

関数は、考えられるすべてのペアnonlconを見つけて、それらがすべて等しいかどうかを確認する必要があります。あなたはこれを次のように便利に行うことができます：xn,m

function [c, ceq] = nonlcon(q, y0)
    % not using inequalities
    c = -1; % NOTE: setting it like this will always satisfy this constraint

    % compute tangents 
    tanq = tan(q);

    % compute solutions to x for all pairs 
    x = bsxfun(@minus, y0, y0.') ./ -bsxfun(@minus, tanq, tanq.');

    % equality contraints: they all need to be equal 
    ceq = diff(x(~isnan(x))); % NOTE: if all(ceq==0), converged.

end

実際に明示的に解いているわけではないことに注意してくださいq（または交差点のy座標がまったく必要ありません）-それがすべてfminconの仕事です。

定義するだけで十分な場合もあるため、いくつかの実験を行う必要があります

x = x(~isnan(x));
ceq = norm(x-x(1)); % e.g., only 1 equality constraint

これはより高速になります（計算する導関数が少なくなります）が、他の問題は本当に必要です

x = x(~isnan(x));
ceq = x-x(1); % e.g., N constraints

または同様のトリック。オプティマイザがそれぞれのケースを見つけるのがどれほど難しいかは、問題の残りの部分に本当に依存します。

于 2012-11-05T14:42:41.293 に答える