- 締切済み
非線形計画法、アルゴリズムを教えてください。
目的関数 f(x)=∑_(j=1)^m▒〖(∑_(i=0)^n▒〖x_i c_j 〗-A_j)〗^2 →最小値 制約条件 ∑_(i=0)^n▒〖x_i c_j 〗≥0 x_i≥0 アルゴリズムを教えてください。 よろしくお願います。
- apple123456789
- お礼率25% (1/4)
- C・C++・C#
- 回答数1
- ありがとう数1
- みんなの回答 (1)
- 専門家の回答
みんなの回答
- stomachman
- ベストアンサー率57% (1014/1775)
〖 〗ってのは単なるカッコでしょうか、それとも何か特別な演算子? あと、不思議な文字「▒」が表示されるんですが、これ何? ま、こまかいことは無視すれば、不等式の制約条件付きの極値問題。ならば、アルゴリズムとか言う前に「KKT条件」で検索してみなされ。
関連するQ&A
- 線形計画法の解法について!
線形計画法の解き方が判らなくて困っています。 判らないこと 1.制約条件の式と計算値 2.目的関数の式と目的値 線形計画法は変数と制約条件と目的関数が与えられます。 制約条件を満足し、目的関数が最大(最小)となる変数を求めます。 線形計画法の例 変数 x y 制約条件 (A) 10x + 4y ≦ 360 (B) 4x + 5y ≦ 200 (C) 2x + 10y ≦ 300 (D) x ≧ 0 (E) y ≧ 0 目的関数 M = 7x+12y A,B,C,D,Eの条件を満足し目的関数(M)が最大となる変数x,yを求めます。
- ベストアンサー
- 数学・算数
- 線形計画問題の標準形
現在大学で線形計画法を学んでいるのですが,実際に数字を用いて問題を解く事にはなれてきたのですが,証明問題などになるとどの様に回答を行えば良いか回答に繋がるプロセス分かりません. どの様なプロセスで回答をすれば良いかなにかアドバイスがございましたらよろしくお願いします.以下が現在回答に困っている問題ですのでよろしくお願いします. 線形計画法の標準形 目的関数:c^T x →最小 制約条件:Ax =b x≧0 m<nとなる自然数.x ∈ R^n, c ∈ R^n, b ∈ R^mであり,Aはm*n実行列で,rankA = m とし b ≠ 0 とする. 問題1.線形計画問題の制約条件を満たすxのなす集合を実行可能領域Fで表し,Fが空集合でないときFが凸集合であることを示しなさい. Fが凸集合とは x,x' ∈ F ⇒tx + (1 - t)x' ∈ F (∀t ∈ [0,1]) が成立するときをいう. 問題2.Au = b を満たすベクトル u ≠ 0 が存在する事を示せ. 問題3.Ax = 0 を満たすxのなす R^n の線形部分空間はAの核と呼ばれkerAと表す.Ax = bを満たすxのなす R^n の部分集合を J で表すとき J = { x ∈ R^n | x = u + v, v ∈ kerA} となる事を示せ.ただしuは問題2で存在を示したベクトルである.
- 締切済み
- 数学・算数
- 非線形計画法について
非線形計画法を現在勉強しています。 1. どういうときに線形でどういうときに非線形となるのか良く分かりません。 例えば、ある従属変数yを線形関数f=Σcx で表したいときにパラメータcの絶対値の和が定数bより小さくなるという制約のもとで、yとfの二乗誤差を最小化するパラメータcを求める問題を考えます。 この場合、制約条件はcについて線形ですが、最小化したいのは、yとfの二乗誤差なのでこの場合は非線形ということになるのでしょうか?それとも関数fはcに関して線形関数なので、線形計画法で解くことになるのでしょうか? 2. 以下のサイトで勉強しているのですが、このサイトにある楕円型の等高線はおそらく、従属変数yと目的関数fの誤差を表しているのだと思うのですが、なぜ「楕円」になるのですか?二乗誤差を考えるのならば、「円」になるのではと疑問で仕方ありません。 http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/nonlinear/nonlinear.htm#2.2 疑問が晴れずにもやもやしています。 回答もしくはアドバイス、よろしくお願いします。
- 締切済み
- 数学・算数
- 線形計画法の問題です
P:最大化c^Tx(c^Tはcの転置) 条件Ax<=b x>=0 ただし、Aはm*n行列、bはm次元ベクトル、cはn次元ベクトル、xはn次元 変数ベクトルである。ベクトルはすべて列ベクトルとし、c^Tはcの転置を表す。 問題Pは最適解を持つと仮定し、目的関数の最大値をfと表す。また、問題P に関連して、m次元ベクトルuをパラメータとする次の線形計画問題を考える。 P(u):最大化c^Tx-u^T(Ax-b) 条件x>=0 問題P(u)の目的関数の最大値g(u)と表す。ただし、問題P(u)が有界でない 場合はg(u)=無限大と定義する。以下の問いに答えなさい。 1)問題Pの双対問題を書きなさい 2)任意のu>=0に対して、g(u)>=fが成り立つことを示しなさい 3)min{g(u)|u>=0}=fが成り立つことを示しなさい。ただし、線形計画問題 に対する強双対定理を用いて良い。 以上の問題をお願いします。
- 締切済み
- 数学・算数
- 非線形計画問題
min f(x1,x2)=(x1-1)^2+x2^2 subject to x1+x2>=5 2x1+x2>=7 (計画変数x1,x2は非負) (1)KKT条件を示し、最適解x1*,x2*を求め、目的関数の最小値を示せ。 (2)最適解x1*,x2*が存在する鞍点において、制約条件式(x1+x2>=5)の右辺の値がσだけ増加したときの 目的関数の変化量を求めよ。また、このような変化量に対して、λ1*,λ2*がどのような意味をもつか簡潔に述べよ。 という問題です」。 (1)はノーマルな解法で解いたら, x1*=2,x2*=3,目的関数の最小値は10でした。 (2)については変化量を求めたら、5σ^2-10σでした。 ですが、「このような変化量に対して、λ1*,λ2*がどのような意味をもつか簡潔に述べよ。」 ところはわかりませんでした。 そこがわかる方がいらっしゃいましたら、ぜひご教授お願いします!
- ベストアンサー
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 min x1^2+x2^2 s.t. -x1-x2+4<=0 x1>=0 x2>=0 この問題の場合最適解は(x1,x2)=(2,2)であり、その時の目的関数値は8となります。 次に次式のような双対問題を考えます。 g(x)=-x1-x2+4とおき 双対関数 φ(u)=inf{x1^2+x2^2+u*(-x1-x2+4) : x1>=0 , x2>=0} =inf{x1^2-u*x1 : x1>=0}+inf{x2-2-u*x2 : x2>=0}+4*u 上記においてもしu>=0であれば、x1=x2=(u/2). (なぜなら、x1^2-u*x1をx1で微分するとx1=u/2となる。) u<0であるならばx1=x2-0であることに注目しますと。 φ(u)=-(1/2)*u^2+4*u for u>=0 =4u for u<0 となります. 双対関数がu>0の場合は最大がu=4であることに注目すると、その時の目的関数は8であり、主問題と双対問題の最適な目的関数値は一緒となります。 次に主問題を次のように制約を増やした最小化問題を考えます。 min x1^2+x2^2 s.t. -x1-x2+4<=0 -2*x1-3*x2<=0 x1>=0 x2>=0 これの最適解は上記の問題と同じにならないといけないのですが、 例えば、ラグランジュ関数F(x1,x2,λ1,λ2)を次のようにおき各変数で偏微分して最適解を求めると(λ:ラグランジュ乗数)、 F(x1,x2,λ1,λ2)=x1^2+x2^2+λ1*(-x1-x2+4)+λ2*(-2*x1-3*x2) 最適解はx1=12, x2=-8であり、その時の目的関数は208となり、前問と異なった解が得られました。 この原因は明確であり、ラグランジュ関数の中の各制約式が、偏微分して解を得ることで不等式制約ではなく等式制約とみなされたためです。 偏微分して解を求めなければいいのですが、どうしても偏微分でかいを求めたいために、、前門で示した双対問題を導入しましたが、結果は双対問題のほうでも偏微分するので一緒でした。 しかし、双対問題で得られた解。つまりuは主問題のλに相当し、KKT条件より必ず正である必要があるので、双対問題を解き、uが負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり2番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
- 最適化問題の解法
最適化問題の解法に関するご質問です。 (マニアックな質問ですがお付き合いください・・) 定義: X_j(1<=j<=N)(行列サイズ=d×1)、 A_i(1<=i<=N)(対角行列、行列サイズ=d×d)、 B(行列サイズ=d×1)、 i = (1, ... , 1)' 目的関数:min_{X_k} { |B-Σ_[i=1,N]A_i*X_i|^2 +βΣ_[k=1,N]|B*X_k|^2 } 最終的には、X = (X_1, ... ,X_N)を求めたいです。 必要であれば、「制約条件:W_i'*i=1」を使っても構いません。 この制約条件をもとに下記のように式を変形しました。 目的関数:min_{X_k} { Σ_[i=1,N]Σ_[j=1,N]{X_i'*A_i'*A_j*X_j}+βΣ_[k=1,N]{X_k'*B'*B*X_k} } 制約条件:X_i'*i=1 この最適化問題を解くのに頭を抱えています。 解法を導くことができる方、ヒントを持っている方がいらっしゃいましたら、ぜひともご教授お願い致します。 よろしくお願い致します。
- ベストアンサー
- 数学・算数
- 線形計画法の目的関数の最大値の出し方
【制約条件式】 4x+2y≦160 3x+4y≦170 x≧0,y≧0 【目的関数】 Z=20x+15y この目的関数の最大値は900なのですが、 その出し方がわかりません。 途中式を省かず、 上記以外の数字が出た場合は、それがどこから出たのか、なんであるのかという解説までお願いします。
- ベストアンサー
- 数学・算数
お礼
ありがとうございました。