問題タブ [mathematical-optimization]

R に非線形整数最適化を処理するパッケージがあるかどうかを知りたいです。

「基本的に」、次の問題を解決したいと思います。

max f(x) s.t x in (0,10) and x is integer.

一部の分岐アルゴリズムがこの問題の線形バージョンを処理できることは知っていますが、ここでの関数f()はより複雑になる可能性があります。(それが の二次方程式になるかどうかさえ確認できませんf(x)=xQx)。

制限されている限り、すべての可能性をテストする力ずくのソリューションが常にあると思いますが、もっと賢いものはないかと思っていました。

このコードゴルフの質問には、英語で1から99までのすべての整数の長さを大きな数にエンコードするPythonの回答があります。

の長さを取得するにはn、を計算する必要があります3 + (the_big_number / (10**n)) % 10。これはどのように作動しますか？

現在、特定の値を経時的に測定するソフトウェアを実装しています。ユーザーは、28 日間にわたって値を 100 回測定することを選択できます。（例を挙げるだけです）

線形分布は問題ではありませんが、現在、時間範囲でのポイントの対数分布を取得しようとしています。

簡単な実装は、ポイントを反復処理することになるため、指数関数が必要になります。（ここまでできました！）

私の現在のアルゴリズム（C＃）は次のとおりです。

これにより、28 日間で 100 ポイントというかなり「良い」結果が得られます。
最初の 11 ポイントはすべて 0 秒、
12 ポイントは 1 秒、
20 ポイントは 50 秒、
50 ポイントは 390 分、
95 ポイントは 28605 分、
99 ポイントは 37697 分です (つまり、最後のポイントまで 43 時間かかります)。

私の質問は、最初の 20 ～ 30 ポイントを互いにさらに離し、最後の 20 ～ 30 ポイントを少し近づける方法を知っている人はいますか?

最終的には、最初のポイントを少なくとも 1 分ほど離すアルゴリズムを追加する必要があることを理解しています。そのような動作を厳密に数学的アルゴリズムに組み込むことはできないからです。

このようなもの：

ただし、全体的にもう少し良い分布を得たいと思っています。

数学のひび割れからのクールなアイデアは大歓迎です！

私は再びプロジェクトオイラーの課題を楽しんでいますが、12番のソリューションは、~593.275 msランスルーごとに最も遅いソリューションの1つであることに気づきました。~1254.593 msこれは、ランスルーごとに10番の私のソリューションに次ぐものです。3 ms私の他のすべての答えは、最もよく下で実行するよりも少ないです1 ms。

問題12の私のJavaソリューション：

主要（）：

numDivisors（）：

。

ソリューションフォーラムを見回すと、これらの式（n =（p ^ a）（q ^ b）（r ^ c）...＆d（n）=（a + 1）（b + 1）（ c + 1）...）彼らのために働いたが、私は個人的にそれがこれ以上速くなるかどうかわからない。手作業で速くなるかもしれませんが、プログラムではそうではありません。

。

基本的な思考プロセスは次のとおりです。

48 = (2^4)(3^1)48の約数を計算したいと思います。以下の因子ツリーを見ると、 [n =（p ^ a）（q ^ b）（r ^ c）...]と結論付けることができます。

これを知って、式d(48) = (4+1)(1+1)[d（n）=（a + 1）（b + 1）（c + 1）...]を作成し、48に10個の因子があることを決定します。

。

コードを最適化するにはどうすればよいですか？これらの式は最良の解決策ですか？すべての素因数を見つけて、数式を実装するのは、私がすでに実施しているプログラムよりも時間がかかると思います。

どうもありがとう、

ユスティニアヌス

編集：

誰かがリンクを投稿し始める前に、私は運がなくてもSOで同様の質問を見回しました。私は、すでに配置されているものよりも速く実行されるメソッドの実装を考えることができません。

EDIT2：

エラトステネスのふるいでの2回目の試み（問題10の場合）：

で実行され~985.399 msます-他の方法よりもそれほど速くはありませんが、まだ最適化されていません。ただし、機能します。

参照: http://kks.cabal.fi/GoodEnoughSearch

私はかなり多くの論文やサイトを調べてきました。このアルゴリズムが以前に提示された場所や、誰かが似たようなものを作ったが、より優れた、またはより一般的なものを見つけたことはありません。アルゴリズムは非常に単純なので、私が直面したのと同じ種類の問題に直面している人なら誰でも簡単に見つけられるはずです。

私はこのように書かれた数学の問題を抱えています：

これらの種類の方程式を解くのに役立つC＃の構造はありますか？

これを実現するためにforループを記述したり、再帰を使用したりできることは知っていますが、後で実行するためにそのようなステートメントをプリコンパイルするc＃の構造について読んだことを覚えています。

これらの種類の方程式を解くための興味深い方法はありますか？

まず、これは (ContourPlot から) かなり単純な最大化問題のように見えますが、なぜニュートン法で FindMaximum に問題があるのでしょうか?

第二に、どうすれば警告を取り除くことができますか?

第 3 に、これらの警告を取り除くことができない場合、警告が意味のあるものかどうか (つまり、最大化に失敗したかどうか) をどのように判断できますか?

たとえば、次のコードでは、FindMaximum と Newton のメソッドで警告が表示されますが、PrincipalAxis メソッドでは警告が表示されません。

注、おそらく勾配がコンポーネントの1つの方向で0であることが問題であると考えましたが、最初の点を摂動させても同じ警告が表示されます。例を次に示します

この数列に「1 + 1/2 + 1/3 + --- + 1/n = ?」という公式はありますか? k=1からnまでの和(1/k)という形の調和数だと思います。

私は操作を実行しています。CalculateSomeData と呼びましょう。CalculateSomeData は、1..x の番号が付けられた連続する「世代」で動作します。実行全体の世代数は、CalculateSomeData への入力パラメーターによって固定され、先験的に知られています。1 つの世代が完了するまでに 30 分から 2 時間かかります。その変動性の一部は入力パラメータによるものであり、制御することはできません。ただし、その変動の一部は、ハードウェアの容量、他のプロセスからの CPU 負荷、ネットワーク帯域幅の負荷などによるものです。世代ごとに制御できるパラメーターの 1 つは、CalculateSomeData が使用するスレッドの数です。現在、それは修正されており、最適ではない可能性があります。私' 各世代にかかる時間を追跡し、スレッドの数を微調整して、連続する各世代が前の世代の計算時間を改善する (時間を最小化する) アルゴリズムを用意したいと考えています。どのようなアプローチを使用する必要がありますか? 遺伝的アルゴリズムはどの程度適用可能ですか? 直感的には、この範囲はかなり狭くなることがわかります。おそらく、デュアル クアッド コア プロセッサ マシンでは 1 ～ 16 スレッドです。

ポインタ、疑似コードなどは大歓迎です。

に関していくつかの不等式が{x,y}あり、次の方程式を満たします。

xandyは整数でなければならないことに注意してください。

グラフでは次のように表すことができます。青い領域は、上記の不等式を満たす領域です。

問題は、Matlab に許容可能なすべてのペアを見つける関数がある{x,y}かどうかです。この種のことを行うアルゴリズムがあれば、私もそれについて聞いてうれしいです.

もちろん、いつでも使用できるアプローチの 1 つは{x,y}、不等式が満たされるかどうかを確認するために、可能なすべての組み合わせをテストするブルート フォース アプローチです。しかし、これは時間がかかるため、最後の手段です。これを行う賢いアルゴリズムを探しています。または、最良の場合、すぐに使用できる既存のライブラリを探しています。

これらx^2+y^2>=100 and x^2+y^2<=200は単なる例です。実際fにgは、任意の次数の任意の多項式関数にすることができます。

編集: C# コードも歓迎されます。