具有性能约束布局问题的优化理论及双层规划模型的启发式并行算法

The project will reaearch a kind of packing optimization problem with performance constraints. The main object of this item is to overcome optimization variables'on-off nature and to solve the difficulty of enormous calculation work for combinatorial optimization problem. The main research contents is to build a bilevel programming model based on satellite module layout problem. Firstly, upper level programming chooses the suitable packing schemes in the nonisomorphic items. It is a combinatorial optimization with limit discrete variables. Secondly, lower level programming is to find out local optimal solutions in the isomorphic items which is a indifferentiable nolinear constraint optimization with continuous variants. In the upper level programming, the number of nonisomorphic packing schemes equivalence classes is increasing by exponent, we will give a heuristic cutting rules to get rid of unreasonable equivalence classes and construct the parallel algorithm to solve the remained items. For the lower level programming, we will study its optimal conditions by directionally differentiable， semi-directionally differentiable，invexity and pre-invexity,etc. Combining feasible decreasing direction with neighborhood search mechanism, optimization algorithm will be done and numerical computation will be completed by parallel machine.

本项目研究一类具有性能约束的布局优化问题，目标是克服该类问题优化变量的时断时续性，并且解决组合优化计算量过大的难题。主要研究内容是以卫星舱布局为背景，建立双层规划模型。上层规划对不同构的布局方案进行优化，是有限多个离散变量优化问题；下层规划在同构的布局方案中寻求最优解，是连续变量的不可微非线性约束规化问题。上层规划的不同构布局方案等价类的数量随着图元个数增加呈指数型增长，可以制定启发式删减原则，将尽可能多的不合理的布局等价类删掉，对保留下的布局方案等价类拟采用并行算法求解；下层规划中，拟利用不可微优化理论中的方向可微、半方向可微、不变凸性和预不变凸性等研究最优性条件，结合邻域搜索机制给出可行的下降方向，进一步构造优化算法，最终在并行机上进行数值计算。

本项目针对卫星舱三维布局优化问题和微生物发酵生产1,3-PD两类实际问题建立了双层规划模型。上层规划是关于离散变量的优化问题，而下层规划是关于连续变量的半无限优化问题。利用非光滑优化和凸分析等相关理论可以证明，在布局问题的下层规划中目标函数是连续且方向可微的，进一步可证明其次微分是外半连续的。在此基础上，构造了优化算法的下降方向，同时以最优性函数为终止准则。对于微生物发酵问题利用常微分方程的基本理论，讨论了非线性动力系统的性质。证明了系统中的各个函数关于参数向量u是Lipschitz连续，并且是线性增长的，从而得到动力系统解的存在唯一性。给出了系统参数的鲁棒性的定量定义，证明了以鲁棒性为目标的参数辨识模型存在最优解。由于两类问题的计算量非常巨大，我们构造了多种并行优化算法进行求解，并获得了较好的数值结果。. 在进行上述各种问题的研究过程中，本人指导研究生完成了多篇论文，12篇论文已发表，2篇论文已投稿，1篇论文正在撰写中。