应用matlab求解约束优化问题 姓名：王铎 学号： 2007021271 班级：机械078 上交日期： 2010/7/2 完成日期： 2010/6/29
一．问题分析 f(x)=x1*x2*x3-x1^6+x2^3+x2*x3-x4^2 s.t x1-x2+3x2<=6 x1+45x2+x4=7 x2*x3*x4-50>=0 x2^2+x4^2=14 目标函数为多元约束函数，约束条件既有线性约束又有非线性约束所以应用fmincon函数来寻求优化，寻找函数最小值。由于非线性不等式约束不能用矩阵表示，要用程序表示，所以创建m文件其中写入非线性不等式约束及非线性等式约束，留作引用。 二．数学模型 F(x)为目标函数求最小值 x1 x2 x3 x4 为未知量 目标函数受约束于 x1-x2+3x2<=6 x1+45x2+x4=7 x2*x3*x4-50>=0 x2^2+x4^2=14 三．fmincon应用方法 这个函数的基本形式为 x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon，options) 其中fun为你要求最小值的函数，可以单写一个文件设置函数，也可是m文件。 1.如果fun中有N个变量，如x y z, 或者是X1, X2,X3, 什么的，自己排个顺序，在fun中统一都是用x(1),x(2）....x(n) 表示的。 2. x0, 表示初始的猜测值，大小要与变量数目相同 3. A b 为线性不等约束，A*x <= b， A应为n*n阶矩阵。 4 Aeq beq为线性相等约束，Aeq*x = beq。 Aeq beq同上可求 5 lb ub为变量的上下边界，正负无穷用 -Inf和Inf表示， lb ub应为N阶数组 6 nonlcon 为非线性约束，可分为两部分，非线性不等约束 c，非线性相等约束，ceq 可按下面的例子设置 function [c,ceq] = nonlcon1(x) c = [] ceq = [] 7，最后是options，可以用OPTIMSET函数设置，具体可见OPTIMSET函数的帮助文件。 四．计算程序
约束最优化问题 一实习目的 1.熟练掌握科学与工程计算中常用的基本算法； 2.掌握分析问题，设计算法的能力； 3.掌握模块化程序设计的基本思想，注重模块的“高内聚，低耦合”； 4.采用自顶向下，逐步细化的编程思想完成程序书写； 5.牢固建立“清晰第一，效率第二”的软件设计观念； 6.掌握软件调试，测试的基本技能和方法； 7.提高科技报告的书写质量； 8.在掌握无约束最优化问题求解方法的前提下，对一般情形下的约束最优化问题进行研究，通过实习掌握外点罚函数法、内点罚函数法、乘子法、线性近似规划法和序列二次规划法在求解一般情形下的约束最优化问题的应用。 二问题定义及题目分析 问题1： 要求用外点罚函数法和内点罚函数法解决约束问题： Min f(x)=错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 问题2： 要求用乘子法解决约束问题： Min 错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 (错误！未找到引用源。) 问题3： 要求用线性近似规划法和序列二次规划法解决约束问题: Min 错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 三程序概要设计 1.外点罚函数法 Step1. 给定初始点错误！未找到引用源。,罚参数序列{错误！未找到引用源。}(常取错误！未找到引用源。),精度错误！未找到引用源。，并令k=0；
Step2. 构造增广目标函数错误！未找到引用源。; Step3. 求解无约束优化问题min 错误！未找到引用源。,x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则：惩罚项充分小，或等价地错误！未找到引用源。近似可行）若错误！未找到引用源。，或者错误！未找到引用源。,错误！ 未找到引用源。,则得解错误！未找到引用源。，否则令k=k+1，转 Step2. 2.内点罚函数法： Step1. 给定初始可行解错误！未找到引用源。，罚参数序列{错误！未找到引用源。}(常取错误！未找到引用源。),精度错误！未找到引用源。，并令 k=0； Step2. 构造增广目标函数错误！未找到引用源。; Step3. 求解无约束优化问题min 错误！未找到引用源。,x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则）若错误！未找到引用源。，则得解错误！未找到引用源。，否则令k=k+1，转 Step2. 3.乘子法： Step1. 给定初始点错误！未找到引用源。，初始lagrange乘子错误！未找到引用源。,i错误！未找到引用源。罚参数序列{错误！未找到引用源。}, 精度错误！未找到引用源。，并令k=0； Step2. 构造增广目标函数错误！未找到引用源。 Step3. 求解无约束优化问题min 错误！未找到引用源。，x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则）若错误！未找到引用源。,则得解错误！未找到引用源。，否则令 K=k+1,转Step2. 4.线性近似规划法： Step1. 给定初始点错误！未找到引用源。，步长限制错误！未找到引用源。,缩小系数错误！未找到引用源。。精度错误！未找到引用源。,并令k=0；Step2. 求解线性规划问题：min 错误！未找到引用源。
题目：用外点法求解非线性约束最优化问题 学院信息管理学院 学生姓名余楠学号 81320442 专业数量经济学届别 2013 指导教师易伟明职称教授 二O一三年十二月
用外点法求解非线性约束最优化问题 摘要 约束最优化问题是一类重要的数学规划问题。本文主要研究了用外点罚函数法对约束非线性规划问题进行求解。对于一个约束非线性规划用罚函数求解的基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。本文最后利用c语言编程得到满足允许误差内的最优解。 本文主要对一个约束非线性规划问题的实例，首先利用上述迭代的方法，计算出各迭代点的无约束极值问题的最优解。然后应用c语言编程，得到精确地最优解，需迭代四次次才使得ε≤0.001，得到的最优解为* X=(333 .0)T。 .0, 666 关键词：外点罚函数法非线性规划约束最优化迭代最优解
一、背景描述 线性规划的目标函数和约束条件都是决策变量的线性函数，但如果目标函数或约束条件中含有决策变量的非线性函数，就称为非线性规划。非线性规划与线性规划一样，也是运筹学的一个极为重要的分支，它在经济、管理、计划、统计以及军事、系统控制等方面得到越来越广泛的应用。 非线性规划模型的建立与线性规划模型的建立类似，但是非线性规划问题的求解却是至今为止的一个研究难题。虽然开发了很多求解非线性规划的算法，但是目前还没有适用于求解所有非线性规划问题的一般算法，每个方法都有自己特定的适用范围。 罚函数法是应用最广泛的一种求解非线性规划问题的数值解法，它的基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。这种惩罚体现在求解过程中，对于企图违反约束的那些迭代点，给予很大的目标函数值，迫使这一系列无约束问题的极小值点无限的向可行集（域）逼近，或者一直保持在可行集（域）内移动，直到收敛于原来约束问题的极小值点。 外点法的经济学解释如下：若把目标函数看成“价格”，约束条件看成某种“规定”，采购人员在规定的范围内采购时价格最便宜，但若违反了规定，就要按规定加收罚款。采购人员付出的总代价应是价格和罚款的综合。采购人员的目标是使总代价最小，当罚款规定的很苛刻时，违反规定支付的罚款很高。这就迫使采购人员在规定的范围内采购。数学上表现为罚因子足够大时，无约束极值问题的最优解应满足约束条件，而成为约束问题的最优解。 二、基础知识 2.1 约束非线性优化问题的最优条件 该问题是一个约束非线性优化问题，利用外点罚函数法求解该问题，约束非线性优化问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此有以下几个定理。
项目三 常用无约束最优化方法（一） [实验目的] 编写最速下降法、Newton 法（修正Newton 法）的程序。 [实验学时] 2学时 [实验准备] 1．掌握最速下降法的思想及迭代步骤。 2．掌握Newton 法的思想及迭代步骤； 3．掌握修正Newton 法的思想及迭代步骤。 [实验内容及步骤] 编程解决以下问题：【选作一个】 1．用最速下降法求 22120min ()25[22]0.01T f X x x X ε=+==，，，． 2．用Newton 法求 22121212min ()60104f X x x x x x x =--++-， 初始点 0[00]0.01T X ε==，，． 最速下降法 Matlab 程序： clc;clear; syms x1 x2; X=[x1,x2]; fx=X(1)^2+X(2)^2-4*X(1)-6*X(2)+17; fxd1=[diff(fx,x1) diff(fx,x2)]; x=[2 3]; g=0; e=0.0005; a=1; fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); step=0; while g>e step=step+1; dk=-fan; %点x(k)处的搜索步长
ak=((2*x(1)-4)*dk(1)+(2*x(2)-6)*dk(2))/(dk(1)*dk(2)-2*dk(1)^2-2*dk(2)^2); xu=x+ak*dk; x=xu; %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf(' x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); %计算目标函数点x(k+1)处一阶导数值 fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); end %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf('\n最速下降法\n结果：\n x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); c++程序 #include
实验八 无约束优化问题 一.实验目的 掌握应用matlab 求解无约束最优化问题的方法 二.实验原理及方法 1：标准形式： 元函数 为其中n R R f X f n R x n →∈:) (min 2．无约束优化问题的基本算法一．最速下降法（共轭梯度法）算法步骤：⑴ 给定初始点 n E X ∈0，允许误差0>ε,令k=0； ⑵ 计算() k X f ?； ⑶ 检验是否满足收敛性的判别准则： () ε≤?k X f ， 若满足，则停止迭代，得点k X X ≈*，否则进行⑷； ⑷ 令() k k X f S -?=，从k X 出发，沿k S 进行一维搜索， 即求k λ使得： ()() k k k k k S X f S X f λλλ+=+≥0 min ； ⑸ 令k k k k S X X λ+=+1，k=k+1返回⑵. 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.．牛顿法算法步骤： (1) 选定初始点n E X ∈0，给定允许误差0>ε，令k=0； (2) 求()k X f ?,()() 1 2-?k X f ,检验：若() ε
等式约束优化问题的极值条件 求解等式约束优化问题 )(m i n x f ..t s ()0=x h k ()m k ,,2,1???= 需要导出极值存在的条件，对这一问题有两种处理方法：消元法和拉格朗日乘子法（升维法） 一、消元法（降维法） 1.对于二元函数 ),(min 21x x f ..t s ()0,21=x x h ， 根据等式约束条件，将一个变量1x 表示成另一个变量2x 的函数关系()21x x ?=，然后将这一函数关系代入到目标函数()21,x x f 中消去1x 变成一元函数()2x F 2.对于n 维情况 ()n x x x f ,,,min 21???..t s ()0,,,21=???n k x x x h ),,2,1(l k ???= 由l 个约束方程将n 个变量中的前l 个变量用其余的l n -个变量表示： ()n l l x x x x ,,,2111???=++? ()n l l x x x x ,,,2122???=++? ... ()n l l l l x x x x ,,,21???=++? 将这些函数关系代入到目标函数中，得到()n l l x x x F ,,,21???++ 二、拉格朗日乘子法（升维法） 设T n x x x x ),,,(21???=，目标函数是()x f ，约束条件()0=x h k ),,2,1(l k ???=的l 个等式约束方程。为了求出()x f 的可能极值点T n x x x x ),,,(**2*1*???=，引入拉格朗日乘子k λ),,2,1(l k ???=，并构成一个新的目标函数 ()()x h x f x F l k k k ∑=+=1),(λλ 把()λ,x F 作为新的无约束条件的目标函数来求解它的极值点，满足约束条件 ()0=x h k ),,2,1(l k ???=的原目标函数()x f 的极值点。 ()λ,x F 具有极值的必要条件 ),,2,1(0n i x F i ???==?? ，),,2,1(0l k F k ???==??λ可得n l +
无约束最优化问题及其Matlab 求解 一、教学目标 1. 了解悟约束规划的基本算法最速下降法（共轭梯度法）的基本步骤 2. 掌握用Matlab 求解五约束的一元规划问题、多元规划问题、以及Matlab 求解过程中参数的设置。 3. 针对实际问题能列出其无约束规划方程并用Matlab 求解。 二、 教学手段 1. 用Flashmx 2004制作课件，并用数学软件Matlab 作辅助教学。 2. 采用教学手法上采取讲授为主、讲练结合的方法。 3. 上机实践操作。 三、 教学内容 （一）、求解无约束最优化问题的基本思想 标准形式： ★（借助课件说明过程） （二）、无约束优化问题的基本算法 1．最速下降法（共轭梯度法）算法步骤： ⑴ 给定初始点n E X ∈0，允许误差0>ε,令k=0； ⑵ 计算()k X f ?； ⑶ 检验是否满足收敛性的判别准则： ()ε≤?k X f ， 若满足，则停止迭代，得点k X X ≈*，否则进行⑷； ⑷ 令()k k X f S -?=，从k X 出发，沿k S 进行一维搜索， 即求k λ使得： ()() k k k k k S X f S X f λλλ+=+≥0min ； ⑸ 令k k k k S X X λ+=+1，k=k+1返回⑵. 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢。 ★（借助课件说明过程,由于 算法 在实际中用推导过程比较枯燥，用课件显示搜索过程比较直观） 2. 采用Matlab 软件，利用最速下降法求解无约束优化问题 常用格式如下： （1）x= fminbnd (fun,x1,x2) （2）x= fminbnd (fun,x1,x2 ，options) （3）[x ，fval]= fminbnd （...） （4）[x ，fval ，exitflag]= fminbnd （...） （5）[x ，fval ，exitflag ，output]= fminbnd （...） 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd ()X f n E X ∈min 其中 1:E E f n →
五种最优化方法 1.最优化方法概述 最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3）线性优化与非线性优化（目标函数和约束条件是否线性）； 4）静态规划和动态规划（解是否随时间变化）。 最优化问题的一般形式（有约束条件）： 式中f（X）称为目标函数（或求它的极小，或求它的极大），si（X）称为不等式约束，hj（X）称为等式约束。化过程就是优选X，使目标函数达到最优值。 2.牛顿法 简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法： 3）是一种函数逼近法。 原理和步骤 3.最速下降法（梯度法） 最速下降法简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）沿函数在该点处目标函数下降最快的方向作为搜索方向； 最速下降法算法原理和步骤 4?模式搜索法（步长加速法） 简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的 是探测有利的下降方向，而模式移动的目的则是沿着有利方向加速移动。
模式搜索法步骤 5.评价函数法 简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下： min (f_1(x),f_2(x),…,f_k(x)) .g(x)<=o 传统的多目标优化方法本质是将多目标优化中的各分目标函数, 经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有“线性加权和法”、“极大极小法”、“理想点法”。选取其中一种线性加权 求合法介绍。 线性加权求合法 6.遗传算法 智能优化方法是通过计算机学习和存贮大量的输入-输出模式映射关系，进而达到优化的一种方法，主要有人工神经网络法，遗传算法和模拟退火法等。遗传算法基本概念 1.个体与种群 个体就是模拟生物个体而对问题中的对象 (一般就是问题的解)的一种称呼。种群就是模拟生物种群而由若干个体组成的群体，它一般是整个搜索空间的一个很小的子集。 2.适应度与适应度函数 适应度就是借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度。 适应度函数就是问题中的全体个体与其适应度之间的一个对应关系。该函数就是遗传算法中指导搜索的评价函数。 遗传算法基本流程 的就是对一定数量个体组成的生物种群进行选择、交叉、变异等遗传操作，最终求得最优解或近似最优解。 遗传算法步骤
《最优化方法》1 一、填空题： 1．最优化问题的数学模型一般为：____________________________，其中 ___________称为目标函数，___________称为约束函数，可行域D 可以表示 为_____________________________，若______________________________， 称*x 为问题的局部最优解，若_____________________________________，称*x 为问题的全局最优解。 2．设f(x)= 212121522x x x x x +-+，则其梯度为___________，海色矩阵___________,令,)0,1(,)2,1(T T d x ==则f(x)在x 处沿方向d 的一阶方向导数为___________，几何意义为___________________________________,二阶 方向导数为___________________，几何意义为_________________________ ___________________________________。 3．设严格凸二次规划形式为： 012. .222)(min 21212 12 221≥≥≤+--+=x x x x t s x x x x x f 则其对偶规划为___________________________________________。
4．求解无约束最优化问题：n R x x f ∈),(min ，设k x 是不满足最优性条件的第k 步迭代点，则： 用最速下降法求解时，搜索方向k d =___________ 用Newton 法求解时，搜索方向k d =___________ 用共轭梯度法求解时，搜索方向k d =_______________ ____________________________________________________________。 二．（10分）简答题：试设计求解无约束优化问题的一般下降算法。 三．（25分）计算题 1． （10分）用一阶必要和充分条件求解如下无约束优化问题的最优解： )1(632)(m in 21212131----=x x x x x x x f . 2． （15分）用约束问题局部解的一阶必要条件和二阶充分条件求约束问题： 1)(. .)(min 22 2 1 2 1=-+==x x x c t s x x x f 的最优解和相应的乘子。 四． 证明题（共33分） 1．（10分）设δ++=x r Gx x x f T T 2 1 )(是正定二次函数，证明一维问题
精心整理 五种最优化方法 1.最优化方法概述 1.1最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3 4 1.2 2. 2.1 1 2 3 2.2 3. 3.1 1 2 3 3.2 4.模式搜索法(步长加速法) 4.1简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的是探测有利的下降
方向，而模式移动的目的则是沿着有利方向加速移动。 4.2模式搜索法步骤 5.评价函数法 5.1简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下： min(f_1(x),f_2(x),...,f_k(x)) s.t.g(x)<=0 传统的多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有“线性加权和法”、“极大极小法”、“理想点法”。选取其中一种线性加权求合法介绍。 5.2线性加权求合法 6.遗传算法 智能优化方法是通过计算机学习和存贮大量的输入-输出模式映射关系，进而达到优化的一种方法，主要有人工神经网络法，遗传算法和模拟退火法等。 6.1遗传算法基本概念 1.个体与种群 个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼。 种群就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。 2.适应度与适应度函数 适应度就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。 适应度函数就是问题中的全体个体与其适应度之间的一个对应关系。该函数就是遗传算法中指导搜索的评价函数。 6.2遗传算法基本流程 遗传算法的中心思想就是对一定数量个体组成的生物种群进行选择、交叉、变异等遗传操作,最终求得最优解或近似最优解。 遗传算法步骤 步1在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；
fmincon函数优化问题 fmincon解决的优化模型如下： min F(X) subject to: A*X <= B (线性不等式约束) Aeq*X = Beq (线性等式约束) C(X) <= 0 (非线性不等式约束) Ceq(X) = 0 (非线性等式约束) LB <= X <= UB （参数x的取值范围） x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) fmincon是求解目标fun最小值的内部函数 x0是初值 A b线性不等式约束 Aeq beq线性等式约束 lb下边界 ub上边界 nonlcon非线性约束条件 options其他参数，对初学者没有必须，直接使用默认的即可 优化工具箱提供fmincon函数用于对有约束优化问题进行求解，其语法格式如下：x=fmincon(fun,x0,A,b) x=fmincon(fun,x0,A,b,Aeq,beq) x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub) x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,...) [x,fval]=fmincon(...) [x,fval,exitflag]=fmincon(...) [x,fval,exitflag,output]=fmincon(...)
非线性约束最优化方法 ——乘子法 1.1 研究背景 最优化理论与方法是一门应用性相当广泛的学科，它的最优性主要表现在讨论决策问题的最佳选择性，讨论计算方法的理论性质，构造寻求最佳解的计算方法，以及实际计算能力。伴随着计算数学理论的发展、优化计算方法的进步以及计算机性能的迅速提高，规模越来越大的优化问题得到解决。因为最优化问题广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域，它已受到政府部门、科研机构和产业部门的高度重视。然而，随着人们对模型精度和最优性的要求所得到的优化命题往往具有方程数多、变量维数高、非线性性强等特点，使得相关变量的存储、计算及命题的求解都相当困难，从而导致大规模非线性优化很难实现。因此，寻求高效、可靠的大规模非线性优化算法成为近年来研究的热点。 本文讨论的问题属于非线性约束规划的范畴，讨论了其中的非线性等式约束最优化问题方面的一些问题。 1.2非线性约束规划问题的研究方法 非线性约束规划问题的一般形式为 （NPL ） {}{} m in (),, s.t. ()0,1,2,...,, ()0,1,2,...,n i i f x x R c x i E l c x i I l l l m ∈=∈=≤∈=+++ 其中，(),()i f x c x 是连续可微的. 在求解线性约束优化问题时，可以利用约束问题本身的性质，
但是对于非线性约束规划问题，由于约束的非线性使得求解这类问题比较复杂、困难。因此，我们将约束问题转化为一系列无约束优化问题，通过求解一系列无约束优化问题，来得到约束优化问题的最优解。我们用到的几类主要的方法有:罚函数法、乘子法以及变尺度法。 传统上我们所提出的非线性约束最优化方法一般都遵循下列三个基本思路之一 1 借助反复的线性逼近把线性方法扩展到非线性优化问题中来 2 采用罚函数把约束非线性问题变换到一系列无约束问题 3 采用可变容差法以便同时容纳可行的和不可行的X 矢量 其中源于思路2 的乘子罚函数法具有适合于等式及不等式约束不要求初始点为严格内点，甚至不要求其为可行点对自由度的大小无任何要求等特点。 1.3乘子法 罚函数法的主要缺点在于需要惩罚因子趋于无穷大，才能得到约束问题的极小点，这会使罚函数的Hesse矩阵变得病态，给无约束问题的数值求解带来很大问题，为克服这一缺点，Hestenes和Powell 于1964年各自独立地提出乘子法。所谓乘子法是：由问题的Lagrange 函数出发，考虑它的精确惩罚，从而将约束优化问题化为单个函数的无约束优化问题，它同精确罚函数法一样，具有较好的收敛速度和数值稳定性，且避免了寻求精确罚函数法中关于罚参数阈值的困难，它们一直是求解约束优化问题的主要而有效的算法。 考虑如下非线性等式约束优化问题：
数学规划课程设计 题目外点法求约束最优化问题 姓名 学号 成绩
摘要 罚函数是应用最广泛的一种求解式的数值解法，基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。（这种惩罚体现在求解过程中，对于企图违反约束的那些迭代点，给予很大的目标函数值，迫使这一系列无约束问题的极小值或者无限地向可行解（域）逼近，或者一直保持在可行集（域）内移动，直到收敛于原来约束问题的极小值点。） 本文....... 外点法可用于求解不等式约束优化问题，又可用于求解等式约束优化问题，主要特点是惩罚函数定义在可行域的外部，从而在求解系列无约束优化问题的过程中，从可行域外部逐渐逼近原约束优化问题最优解。 关键词：罚函数法、约束最优化问题、外点法
一、预备知识（基本理论） 看下是否还有定理、定义等等，可以加一些 外点惩罚函数法的一般形式 考虑不等式约束优化设计时：对 ) ,2,1(,0)(. .), (min m u X g t s R x X f u n =≥∈ 构造一般形式的外点惩罚函数为： []2 1 } )(,0{min )(),(∑=+=m u u k k X g r X f r X P 其中： （1）当满足所有约束条件时惩罚项为0，即 []{}0 )(,0min 2 1 =∑=m u u k X g r （2）当 X 违反某一约束条件，即0 )(
分数: ___________ 任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业四 学生姓名： 学号： 提交时间：
一、问题重述 形如下式的寻优问题称为无约束最优化问题，这类问题的最优解称为约束最优解。 min f(x).. (x)0,i 1,...p h (x)0,j 1,...q 0,0i j s t g p q ??≤=?? ==? ?>>? 约束优化问题的最优性条件是，在满足灯饰和不等式约束条件下，其目标函数值最小的点所必须满足的条件。 约束优化设计问题求解方式有两种，间接法和直接法。直接法是在满足不等式约束的可行设计区域内直接搜索问题的最优解和最小值，常用的方法有随机方向法、复合形法。间接法是将优化问题转化为一系列无约束优化问题来求解，常用的方法有内惩罚函数法、外惩罚函数法以及混合惩罚函数法。 本次作业以为例，介绍无约束最优化问题的寻优方法。 二、算法原理 复合形法是求解约束非线性寻优问题的一种重要的直接方法。 复合形法的核心在于可行域内构造的不断逼近最优点的复合形。每次迭代，计算各顶点的目标函数值，找到目标函数值最大的顶点(称最坏点)，然后按相应的原则求出目标函数可行的下降点，以此代替最坏点，构成新的复合形。复合形每改变一次，各个顶点就向最优点移动一步，直至满足终止条件，找到最优点。 复合形法的顶点数K 通常取12n K n +≤≤，其中n 表示搜索环境的维度。初始图形的顶点是由设计者确定或者随机产生的，但一定要保证在可行域内。如果随机产生的初始点没有在可行域内，可以通过以下步骤将其调入可行域内。 （1）计算在可行域内点的初始点集中心X (s); （2）将可行域外的点向X (s)靠拢，每次前进间距的一半，直至进入可行域内。 复合行法的终止条件可以有以下几种形式，满足终止条件后，可将最后复合形的好点及其函数值作为最优解输出。 （1）各顶点与好点函数值之差的均方根小于误差限； （2）各顶点与好点的函数之差平和小于误差限； （3）各顶点与好点函数值差的绝对值之和小于误差限。
第三章无约束最优化方法 本章内容及教学安排 第一节概述 第二节迭代终止原则 第三节常用的一维搜索方法 第四节梯度法 第五节牛顿法 第六节共轭方向法 第七节变尺度法 第八节坐标轮换法 第九节鲍威尔方法 第一节概述 优化问题可分为 无约束优化问题 有约束优化问题 无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题 迭代法的基本思想：
所以迭代法要解决三个问题 1、如何选择搜索方向 2、如何确定步长
3、如何确定最优点（终止迭代） 第二节 迭代终止准则 1）1K K X X ε+-≤ 111/2 21K K K K n i i i X X X X ε++=??-=-≤???? ∑（） 2） 11()()()() () K K K K K f X f X f X f X or f X ε ε ++-≤-≤ 3）(1)()K f X ε+?≤ 第三节 常用的一维搜索方法 本节主要解决的是如何确定最优步长的问题。 从初始点(0)X 出发，以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下： (1)(0)00(2)(1)11(1)() K K k k X X S X X S X X S ααα+=+=+= + 现在假设K S 已经确定，需要确定的是步长k α，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题，变成求一个变量即步长的最优值的一维问题了。即 (1)()min ()min ()min ()K K K k k f X f X S f αα+=+= 由此可见，最佳步长*K α由一维搜索方法来确定 求*k α，使得()()()()()()min K K K K f f X S αα=+→ 一、一维搜索区间的确定 区间[,]a b 应满足 ()(*)()f a f f b α><
Chin.Quart.J.of Math. 2009,24(3):469—474 Feasible SQP Descent Method for Inequality Constrained Optimization Problems and Its Convergence ZHANG He-ping1,YE Liu-qing2 (1.Department of Mathematics,Luohe Vocational Technology College,Luohe462000,China;2.Depart-ment of Mathematics,Jiaozuo Teachers College,Jiaozuo454002,China) Abstract:In this paper,the new SQP feasible descent algorithm for nonlinear constrained optimization problems presented,and under weaker conditions of relative,we proofed the new method still possesses global convergence and its strong convergence.The numerical results illustrate that the new methods are valid. Key words:nonlinearly constrained optimization;SQP;the generalized projection;line search;global convergence;strong convergence. 2000MR Subject Classi?cation:90C30,49M37 CLC number:O221.2Document code:A Article ID:1002–0462(2009)03–0469–06 §1.Introduction and Preparation Concept Nonlinear inequality constrained optimization problems (P)min f0(x); s.t.f j(x)≤0,j∈I={1,2,···,m} During the research of method for nonlinear inequality constrained optimization,Due to the rapid convergence-type methods(such as sequential quadratic programming,sequential quadratic programming,Jane recorded as SQP)can calculate the solution to meet the optimization in the shortest possible time and with less the amount of calculation under a certain accuracy solution, Received date:2009-03-10 Foundation item:Supported by the NNSF of China(10231060);Supported by the Soft Science Foundation of Henan Province(082400430820) Biographies:ZHANG He-ping(1965-),male,native of Hebi,Henan,an associate professor of Luohe Vo-cational Technology College,M.S.D.,engages in nonlinear programming;YE Liu-qing(1965-),male,native of Runan,Henan,a professor of Jiaozuo Teachers College,M.S.D.,engages in nonlinear programming.
分数: ___________任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间：
一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差，而且寻优的效率特别低下。