大域的最適化アルゴリズムとその化学相平衡問題への応用

全局优化算法及其在化学相平衡问题中的应用

基本信息

批准号：
01F00040
负责人：
久野誉人
金额：
$ 1.41万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

化学プロセスで解決の求められることの多い非線形0-1型混合整数計画問題は,0-1変数を固定すれば通常の凸計画問題に帰着するものの,正しい解を求めるためには,0-1変数の数の巾乗個もの凸計画問題の中から大域的に最適な解を与えるものを見つけ出さなければならない.このため,従来は発見的に精度保障のない近似解を求めるほか術がないとされてきたが,この多極値非凸最適化問題に対して厳密な最適解を生成する分枝カットアルゴリズムを構築した.対象となる問題を凸計画問題に連続緩和したときの最適解が,その実行可能領域における,ある1次関数の最小点に一致することを明かにした.これをもとに,緩和問題の最適解を離接切除平面によって効果的に除去する方法を考案した.離接切除平面は,0-1変数で離接が生じることを利用して各0-1変数の定めるアフィン空間に子問題を射影し,これを解くことによって生成する.しかし,射影された問題は非線形計画問題であり,アルゴリズムの各反復でこれを解くことは全体として効率的でない.そこで,この問題をさらに線形計画問題に緩和し,その双対問題を用いて切除平面が子問題に対して常に妥当となるように調整を行なった.同時に,残りの0-1変数の整数性も利用し,解を与えない領域をなるべく深く除去するように切除平面の強化を行なった.以上の方法で生成される離接切除平面は,必ずしも離接集合に対する凸包のファセットとはならない.しかし,予備実験では典型的な2つの化学設計問題に対して十分な効果のあることが確認できた.

化学过程中经常寻求解决的非线性0-1混合整数规划问题，通过固定0-1变量来简化为普通的凸规划问题，但为了找到正确的解决方案，必须在凸规划问题中找到全局最优解，该问题是变量数量的幂。因此，传统上，唯一的选择是使用启发式方法来找到不保证准确性的近似解。然而，我们开发了一种分支切割算法，可以为这个多极端非凸优化问题生成精确的最优解。当目标问题相继松弛为凸规划问题时，最优解为我们发现它与基于此，我们设计了一种利用析取切平面来有效消除松弛问题最优解的方法。通过将子问题投影到由每个 0-1 变量定义的仿射空间并利用 0-1 变量中发生析取的事实来求解它，从而生成表面。但是，投影问题是非线性规划方法。，并且在算法的每次迭代中求解它整体效率不高，因此，我们进一步将这个问题放松为线性规划问题，并使用其对偶问题来确保子问题的切割平面始终恒定。同时，我们利用剩余0-1变量的整数性质来强化切割面，以便尽可能深地去除未给出解的区域，生成的析取切割面不一定是切面。然而，初步实验证实该方法对于两个典型的化学设计问题足够有效。