締切済み

非線形計画法、アルゴリズムを教えてください。

2014/07/18 16:59

目的関数 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)

2014/07/21 01:07 回答No.1

〖〗ってのは単なるカッコでしょうか、それとも何か特別な演算子？あと、不思議な文字「▒」が表示されるんですが、これ何？　ま、こまかいことは無視すれば、不等式の制約条件付きの極値問題。ならば、アルゴリズムとか言う前に「KKT条件」で検索してみなされ。

質問者

お礼 2014/08/22 08:48

ありがとうございました。

関連する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 とする．問題１．線形計画問題の制約条件を満たすxのなす集合を実行可能領域Fで表し，Fが空集合でないときFが凸集合であることを示しなさい． Fが凸集合とは x,x' ∈ F ⇒tx + (1 - t)x' ∈ F (∀t ∈ [0,1]) が成立するときをいう．問題２．Au = b を満たすベクトル u ≠ 0 が存在する事を示せ．問題３．Ax = 0 を満たすxのなす R^n の線形部分空間はAの核と呼ばれkerAと表す．Ax = bを満たすxのなす R^n の部分集合を J で表すとき J = { x ∈ R^n | x = u + v, v ∈ kerA} となる事を示せ．ただしuは問題２で存在を示したベクトルである．
非線形計画法について

非線形計画法を現在勉強しています。１．どういうときに線形でどういうときに非線形となるのか良く分かりません。例えば、ある従属変数ｙを線形関数ｆ＝Σcx　で表したいときにパラメータｃの絶対値の和が定数ｂより小さくなるという制約のもとで、ｙとｆの二乗誤差を最小化するパラメータｃを求める問題を考えます。この場合、制約条件はｃについて線形ですが、最小化したいのは、ｙとｆの二乗誤差なのでこの場合は非線形ということになるのでしょうか？それとも関数ｆはｃに関して線形関数なので、線形計画法で解くことになるのでしょうか？２．以下のサイトで勉強しているのですが、このサイトにある楕円型の等高線はおそらく、従属変数ｙと目的関数ｆの誤差を表しているのだと思うのですが、なぜ「楕円」になるのですか？二乗誤差を考えるのならば、「円」になるのではと疑問で仕方ありません。 http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/nonlinear/nonlinear.htm#2.2 疑問が晴れずにもやもやしています。回答もしくはアドバイス、よろしくお願いします。
非線形計画法

r[j]{j=1,・・,n}とμをパラメーターに持ち、n次の正定値行列 Qである2次計画問題を考える。変数はx={x[1],x[2],・・・,x[n]}´（ただし、´は転置を示す）このとき　　min x´Qx s.t x[1]+・・・+x[n]=1 r[1]x[1]+・・・+r[n]x[n]≧μ この問題の最適解を求めたいのですが、最小化の目的関数をどう処理すればいいのかご指導願います。
線形計画法の問題です

Ｐ：最大化ｃ＾Ｔｘ（ｃ＾Ｔはｃの転置）　　条件Ａｘ＜＝ｂ　　ｘ＞＝０ただし、Ａはｍ＊ｎ行列、ｂはｍ次元ベクトル、ｃはｎ次元ベクトル、ｘはｎ次元変数ベクトルである。ベクトルはすべて列ベクトルとし、ｃ＾Ｔはｃの転置を表す。問題Ｐは最適解を持つと仮定し、目的関数の最大値をｆと表す。また、問題Ｐに関連して、ｍ次元ベクトルｕをパラメータとする次の線形計画問題を考える。Ｐ（ｕ）：最大化ｃ＾Ｔｘ－ｕ＾Ｔ（Ａｘ－ｂ）　　　　条件ｘ＞＝０問題Ｐ（ｕ）の目的関数の最大値ｇ（ｕ）と表す。ただし、問題Ｐ（ｕ）が有界でない場合はｇ（ｕ）＝無限大と定義する。以下の問いに答えなさい。１）問題Ｐの双対問題を書きなさい２）任意のｕ＞＝０に対して、ｇ（ｕ）＞＝ｆが成り立つことを示しなさい３）ｍｉｎ｛ｇ（ｕ）｜ｕ＞＝０｝＝ｆが成り立つことを示しなさい。ただし、線形計画問題に対する強双対定理を用いて良い。以上の問題をお願いします。
非線形計画問題

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*がどのような意味をもつか簡潔に述べよ。」ところはわかりませんでした。そこがわかる方がいらっしゃいましたら、ぜひご教授お願いします！
線形計画法について

線形計画問題で、制約条件: x1+4x2+x3≦2 x2+x2+2x3≦3 x1,x2,x3≧0 目的関数: max(5x1+8x2+6x3) という問題がでたのですが、ご覧の通り3変数の問題なのですが図式解法を用いて解けという指定なのです。 2変数ならすんなりできたのですが、3変数となると上手くいきません。どなたかわかる方いたら是非ご教授願います。
非線形計画法主-双対問題

次のような制約付き最小化問題を考えています。目的関数は非線形です。 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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
最適化問題の解法

最適化問題の解法に関するご質問です。 (マニアックな質問ですがお付き合いください・・) 定義： 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なのですが、その出し方がわかりません。途中式を省かず、上記以外の数字が出た場合は、それがどこから出たのか、なんであるのかという解説までお願いします。
線形計画法？の問題が解けません

　　　　　カロリー　　　タンパク質製品Ａ　　270 kcal　　　　8 g 製品Ｂ　　165 kcal　　　　16 g それぞれ１００ｇにつきという成分表が与えられています。これだけで、１日あたりの栄養を 2500 kcal、タンパク質を 100 g 確保したい。総重量を最小にするにはどうしたらよいか。という問題なのですけどわかりません。求める重量を製品Ａは x 　　　　　　　　製品Ｂは y　とおいて目的関数　　P = x + y 制約式　　　270x + 165y >= 2500 　　　　　　　　8x + 16y >= 100 として、グラフで許容領域を書いて求めようと考えたのですが、できませんでした。まず、グラフが書けませんでした。割り切れない数値でごちゃごちゃしてしまいました。それで、この答え（できれば計算式も）を教えてくれませんか。お願いします。　　
線形計画法の解について！

線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。問題は、以下のとおりです。（線形計画法とシャドウ価格）次の線形計画法の解、各制約のシャドウ価格を求めなさい。制約条件 2x＋y≦7, x＋3y≦6, x≧0,y≧0 のもとで、目的関数 Z＝x＋y を最大化せよ。
非線形の最適化問題の質問です。

「制約条件：2x+y≦3、x+y≦2、x,y≧0のとき、alogx + (1-a)logy を最大化する解(x,y)を求めよ」という最適化問題の解が(x,y) = (1,1)となるようなaの範囲を求めよ。という問題なのですが、これは目的関数に(-1)をかけて最小化問題とし、キューン・タッカー条件を用いて解けばよいのでしょうか？キューン・タッカー条件を用いて解いてみると、a = 2λ1 + λ2 かつ 1-a = λ1 + λ2 で、λ1、λ2≧0より0≦a≦1という範囲があっけなく出てきたのですが…本当にこれで合っているのか不安です。図形的に考えてみようとも思いましたが、目的関数が複雑すぎて断念しました。どなたかこの問題の正しい解法を教えて頂けないでしょうか？どうぞよろしくお願いします。
線形計画問題をGLPKのですが・・・

現在研究で線形計画・整数計画を扱っており，フリーソフトのGLPKを使っています． GLPKのモデルファイルに制約条件を書く際，変数の取る範囲を両側から指定したい場合(○＜x＜◎など)，どのように表わせばよいのでしょうか．何分英語が苦手で公式マニュアルが理解できないので，どなたかお解りでしたら教えてください．ちなみに実際に書こうとしている制約条件は↓です． s.t. sample{i in part , j in lap : j > t[i] - s , j <= t[i]} : j-c[i]-d[j]*w[i]>= 0; t[i],w[i],j,sは定数でc[i],d[j]です．
非負最小２乗法のコーディング

非負条件の最小２乗法のプログラムを作成したいのですが，参考文献やプログラムがあれば，教えて下さい。考え方のヒントでもよいです。具体的には，関数f[{x}]=|[A]{x}-{b}|^2・・・(1) がxi>=0(i=1,2,..,n)・・・(2)の条件で，最小となる{x}を求めるという問題を解くプログラムを作りたいと考えています。ここで，{x}=(x1,x2,...,xn) 　　　{b}=(b1,b2,...,bm) 　　　[a]はサイズm x nのマトリクス(m>n) であり，[A]および{b}は既知です。条件(2)が無い場合の最小二乗のプログラムは作成できますが，条件(2)を満足させるという条件がある場合には，その条件を具体的にどのようにプログラム化するのか不明であり質問した次第です。宜しくお願いします。
アルゴリズムについて

大学の授業の課題のアルゴリズムについてなのですが、内容的に頭がついて行けず、一切分かりません。問題内容は、最小値を求めるアルゴリズム（必要な箇所を修正して下さい）です。どなたか詳しい方いらっしゃいますでしょうか？よろしくお願いいたします。 M = -9999 データX入力 while X ≠ 9999 Y M < X N 　　M = X 　　データX入力　　Mを出力
線形計画法の問題で、悩んでます。

線形計画法の問題ですが。たとえの問題です。２種類の餌料「Ｘ」と「Ｙ」を牛に与える１日に必要な、ビタミン量を確保したままで、できるだけ価格を安くしたい。Ｘ＝５０円/ｋｇ　Ｙ＝１００円/Ｋｇビタミン量Ｘ　　　Ｙ－－－－－－－－－－－－Ａ　　　　４　　　１Ｂ　　　　２　　　１Ｃ　　　　７　　１０Ｄ　　　　１　　　３－－－－－－－－－－－－餌（ｋｇ)　ビタミン（ｍｇ）ビタミン必要量　　－－－－－－－－－－－－Ａ　　　１２Ｂ　　　１０Ｃ　　　７０Ｄ　　　１５－－－－－－－－－－－－　ヒントは：目的は安くすること、制約条件は必要量。どうとくのか、式だけでも教えていただけないでしょうか？どう、手をつけたらいいのかわかりません。
線形計画問題

最近線形計画法について独学で勉強を始めたのですがいくつかの書籍を調べてもどうしても分からない点があったのでこの場を利用させて頂きます。頭を悩めていますのは制約条件が特殊なためです。問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が分母にきているのです。目的関数で分母に変数を持つものは分数計画問題といるのを拝見した事があるのですが上記のような例は探し方が悪いのか見つける事ができていません。実行可能領域は非有界ですが最小化問題のため上記の例であると2変数なのでグラフにプロットする事でおよそですが解は見つかりました。しかし実際の問題は10変数以上の問題となっていますので解が求められません。その後も実行可能領域を多面体で近似すれば良いのか等の考察を繰り返しましたが問題が複雑になりお手上げの状態です。ちゃんとした解法があるのならお教え頂けるか書籍の案内をして頂きたいです。宜しくお願いします。
max関数を含む関数の最適化

最適化の初学者です。微分不可能関数の最適化に困っています。例えば、次（添付画像）の関数fを最小化する(x_1,x_2,...,x_n)はどう求めたらよいのでしょうか。 f(x_1,x_2,…,x_n)=Σ_{1≦i≦n}{ (max_{1≦j≦n}{x_{j}*r_{i,j}}-x_{i})^2 } ただし、任意のi, jに関してr_{i,j}は与えられているものとします。
線形代数の問題です。至急御願いします！

※バーとは複素共役のことです。標準内積の定義 (x,y∈C) (x,y)=x1y1バー+x2y2バー+…xnynバー (yのみバーがつきます) また標準内積は次の性質を満たす 1.(x1+x2y)=(x1,y)+(x2,y) 2.(λx,y)=λ(x,y)(λ∈C) 3.(x,y)=(y,x)バー 4.||x||≧0,||x||=0⇔x=0 問. 次の(1)～(3)は、上記の4つの条件を実際にみたすことを確かめよ。（１）Ｃ[Ｘ]n∋f=Σ(i=0→n) ai・X^i,g=Σ(i=0→n) bi・X^i (f,g)=Σ(i=0→n) ai・biバー（biのみバー) （２）Ｃ[Ｘ]n∋f,g (f,g)=∫(ｃ^１)f(X)・g(X)バー（g(X)のみバー)dX ここで、c^1={Z∈C||Z|=1} (3)ヒルベルト・シュミット内積 X,Y∈M(m,n;C)に対し、 (X,Y)=Tr(X,tYバー)(tは転置を表す） X,tYバー∈M(m,n;C) A∈M(m,n;C)に対し、Tr(A)=a11+a22+...+amn(数字は添字）(Aの対角成分の和）

非線形計画法、アルゴリズムを教えてください。

みんなの回答

お礼 2014/08/22 08:48

関連するQ&A

線形計画法の解法について！

線形計画問題の標準形

非線形計画法について

非線形計画法

線形計画法の問題です

非線形計画問題

線形計画法について

非線形計画法主-双対問題

最適化問題の解法

線形計画法の目的関数の最大値の出し方

線形計画法？の問題が解けません

線形計画法の解について！

非線形の最適化問題の質問です。

線形計画問題をGLPKのですが・・・

非負最小２乗法のコーディング

アルゴリズムについて

線形計画法の問題で、悩んでます。

線形計画問題

max関数を含む関数の最適化

線形代数の問題です。至急御願いします！

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

非線形計画法、アルゴリズムを教えてください。

みんなの回答

お礼 2014/08/22 08:48

関連するQ&A

線形計画法の解法について！

線形計画問題の標準形

非線形計画法について

非線形計画法

線形計画法の問題です

非線形計画問題

線形計画法について

非線形計画法 主-双対問題

最適化問題の解法

線形計画法の目的関数の最大値の出し方

線形計画法？の問題が解けません

線形計画法の解について！

非線形の最適化問題の質問です。

線形計画問題をGLPKのですが・・・

非負最小２乗法のコーディング

アルゴリズムについて

線形計画法の問題で、悩んでます。

線形計画問題

max関数を含む関数の最適化

線形代数の問題です。至急御願いします！

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

非線形計画法主-双対問題

カテゴリ
一覧

専門家に質問してみよう
専門家登録