系统优化与调度中期作业作业

MidtermProjectGiveanon-quadraticnonlinearobjectivefunctionandlinearinequalityconstraints(atleasttwo).Selectacomputationalmethod(primalordual)forconstrainedoptimizationyoulearnintheclass.Showyourcomputationalresultsandcorrespondinganalysis.Submitthetypedreport.Attachyourprogram.中期作业一、问题描述已知目标函数为线性约束条件为求目标函数的极小值。二、算法描述可行方向法是解决具有约束条件最优化问题的一类基本方法，包括有卓坦狄克可行方向法、罗森梯度投影法、既约梯度法和弗兰克－沃尔夫方法等。可行方法也是一种下降迭代算法，但由于考虑到存在约束条件，故所要求的搜索方向不仅是下降的而且是可行的。可行性方向法的基本思想是从一个可行点出发，沿下降的可行方法进行搜索，以获得目标函数逐步下降的可行点列{x(k)},从而逼近目标函数最优点。在本文中，使用卓坦狄克提出的可行方向法，来求解该问题。设n元目标函数为（1）线性约束为（2）式中，为可微函数；A为矩阵；E为矩阵；b和e分别为m维和维列向量。设n元目标函数为（1）线性约束为（2）式中，为可微函数；A为矩阵；E为矩阵；b和e分别为m维和维列向量。设点是一个可行点，则在点处有（3）其中根据定理推证可以证明，在处的可行方向d应满足（4）为了使可行方向d为下降方向，非零向量d还应满足（5）为了使d的某种度量有界，应增加规范化条件（约束条件），常用的规范化条件为（6）（7）采用上式的规范化条件，则仅对可行方向d加上一组线性条件，容易处理。因此，卓坦狄克可行方向法把确定搜索方向d归结为求线性规划问题，即（8）上式中，显然d＝0为可行解。由此可知，目标函数的最优值必定小于零或等于零。如果目标函数的最优值小于零，则可得到下降方向d。在确定了可行点的下降可行方向后，还必须解决确定最优步长的问题。最优步长的取值原则，除了保持迭代点的可行性外，还应使目标函数值尽可能减小。为此，应在不违反约束条件下可沿可行方向进行一维搜索来确定最优步长，即（9）在点处，把不等式约束分为起作用的约束和不起作用的约束，它们对应的系数矩阵分别为A1和A2，即（10）这样，式（9）中的第一个约束可写为（11）由于为可行方向，，以及，因此（12）约束条件（11）可简化为（13）这样，式（9）可简化为（14）根据式（14）的约束条件，容易求出步长的上限。令（15）由式（10）可知，，即，因此式（14）的约束条件可写为（16）由此可得（17）此时，式（9）最终可简化为（18）综上可述，对于具有线性约束条件的目标函数，如果给定了一个可行点后，则可通过求解式（8）得到下降可行方向，再通过求解式（18）来确定沿该方向进行一维搜索的步长。线性约束情况的可行方向法的计算步骤如下：（1）给定初始可行点，置k＝1；（2）在点处将A分解为A1和A2，将b分解为b1和b2，且满足计算函数梯度。（3）求解线性规划问题mins.t得到下降可行方向d(k)。（4）如果，则停止计算，点为库恩－图克点（当目标函数的最优值为零时