非线性规划的拉格朗日算法

XX

大学

智能优化算法课内实验报告书

院系名称 ：

学生姓名 ： 专业名称 ： 班 级 ： 学时

号 ： 间 ：

非线性规划问题的粒子群算法

1.1 背景介绍

1.1.1 非线性规划简介

具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要的分支，非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的机制问题且目标函数和约束条件至少有一个是未知量的非线性函数，目标函数和约束条件都是线性函数的情形则属于线性规划。

非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正式诞生的一个重要标志。在50年代可得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。

非线性规划问题广发存在于科学与工程领域，是一类比较难以解决的优化问题，没有普遍使用的解法。传统的求解该问题的方法（如罚函数，可行方向法，以及变尺度法等）

一般非线性规划

标准型为：

min F(X)

s.t AX<=b Aeq G(X)?0 ?X?beq Ceq(X)=0 VLB?X?VUB

其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步： 1. 首先建立M文件fun.m,定义目标函数F（X）: function f=fun(X); f=F(X);

2. 若约束条件中有非线性约束:G(X)?0或Ceq(X)=0,则建立M文件

nonlcon.m定义函数G(X)与Ceq(X): function [G,Ceq]=nonlcon(X) G=... Ceq=... 3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下：

(1) x=fmincon(‘fun’,X0,A,b) (2) x=fmincon(‘fun’,X0,A,b,Aeq,beq)

(3) x=fmincon(‘fun’,X0,A,b, Aeq,beq,VLB,VUB)

(4) x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’) (5)x=fmincon(‘fun’,X0,

拉格朗日插值绘制龙格现象

一、问题叙述

龙格反例1/(1+x^2)说明高次代数插值会导致误差很大。在区间[-5,5]上取等距结点构造10次拉格朗日插值多项式用计算机绘制图形显示龙格现象。 二、理论分析

1. 拉格朗日插值：假设有（n+1）个拉格朗日插值结点x0?x1??xn ，已知函数值

y0?f(x0),y1?f(x1),,yn?f(xn)

求n次多项式Ln(x)使其满足插值条件f(xj)?yj(j?0,1,,n)

类似于二次插值方法，根据插值结点构造(n+1)个拉格朗日插值基函数

lk(x)?(x?x0)?(x?xk?1)(x?xk?1)?(x?xn)

(xk?x0)?(xk?xk?1)(xk?xk?1)?(xk?xn)?1j?k每一个基函数都是零点多项式lk(xj)??,(j?0,1n)

0j?k?Ln(x)满足插值条件 Ln(xj)?f(xj)拉格朗日插值基函数：lk(x)??j?0j?kn(j?0,1,,n)

(x?xj)(xk?xj)拉格朗日插值多项式：Ln??lj(x)yj

j?0n2. 切比雪夫插值：n阶切比雪夫多项式定义为

1 绪 论

1.1 课题的背景 1.1.1 Matlab简介

MATLAB是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。

MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。

MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且MATLAB也吸收了像Maple等软件的优点，使MATLAB成为一个强大的数学软件。在新

数学建模数与学实验非线性规划

勤工后程院数学教学研1

室

实验的1、目直了观解非性线划规的本基容。

2内掌握、数学用软求件优解化问。题实内验容、非线1规划的基性理本论。、2用学数软求件解线非规性划。 、钢3管订购及运优输模化 4、型验作实。业

2

线性非规划非性线规的划基本概

*念线性规非的基本解划法回返

非现性规划3的基本概 念定 如果目标函义或约数条束中件至少一有个是线非性数函 时最的优问题化叫就做非性线划规题.

问一般形:

m式in f X

gi X 0 i1, ,2.., . ;m s. t. 1() h j X 0 j 1 2,,... l., 其 中X x1 ,x2 , , x n T En f, g,i, h 是定义j在E 上的n实函

数，简记值:f E:n 1E gi,: E n E,1 h j: En E 1其它情况 :求目 标函数的大最或约值条束件小为于于等零的 情，都况通可过其相取反化数为述上般形式.一4

义1定把满足 问题1)(条件的解中X ( n E称)为可行(或可行 点),所有解可行的点合称集为行可集或可行域).记为D.(即 D X | ig

数学建模 非线性规划(xin)

非线性规划 (Nonlinear Programming)第一章 一般的非线性规划问题§1.1 问题概论

(模型) min s .t

f (x)

g i ( x ) 0, i 1,..., m h j ( x ) 0, j 1,..., n1

数学建模 非线性规划(xin)

(两类问题)无约束极值问题与约束极值问题

(一些基本定义)梯度

df df T f ( x) ( ,..., ) dx1 dxn

Hesse矩阵

H ( x)

f11 f m1

f1n f mn

Jaccobi矩阵

f1T F ( x ) f T n 2

数学建模 非线性规划(xin)

§ 1.2 最优解分类 (注：不一定存在)

定义1.2.1 整体(全局)最优解 定义1.2.2 局部最优解 (已有算法基本都是求局部 最优解的)§ 1.3 凸集与凸函数 定义1.3.1 凸集 定义1.3.2 (严格)凸函数 称定义在凸集K上的实值 ，有： 函数f (x)为凸函数，若 x1,x2 K及 01 f ( x1

拉格朗日插值多项式

数值计算方法上机报告

学院：计算机与通信学院班级：计算机科学与技术姓名：柴小辉学号：

拉格朗日插值多项式

05级3班 05240326

拉格朗日插值多项式

尽管满足插值条件Pn(xi)=yi (i=0,1,2,…,n) (1) 的n次插值多项式是唯一的，然而它的表达式却可以有多种形式。如果取满足条件

1 i＝k

lk(xi)= (i=0,1,2,…,n) (2) 0 i≠k

的一组n次的代数多项式l0(x)、l1(x)、…、ln(x)作为上述线性空间的基，容易看出

y0l0(x)+ y1l1(x)+ …+ynln(x)=∑yklk(x) (3)

必是一个不高于n次的代数多项式，而且它在节点x0、x1、…、xn 上的值依次是 y0、y1、…、yn也就是说，由n+1个n次代数多项式y0l0(x)、 y1l1(x)、 …、ynln(x)线性生成的多项式（3），就满足插值条件（1）的n次插值多项式。 满足

拉格朗日多项式插值法浅析

摘要

拉格朗日插值多项式是一种最常见的多项式插值法，也是一种最常用的逼近工具。“学以致用 ”是每一门学科都致力追求的境界，数学自然也不例外。下面，探讨拉格朗日插值法的基本原理、如何构造拉格朗日多项式、拉格朗日多项式的误差界，并用 MATLAB程序来实现这一数学算法的自动化，为复杂的分析研究提供了一条数学算法的捷径。

【关键词】：拉格朗日多项式 算法实现 MATLAB

在科学研究和实际的工程设计中，几乎所有的问题都可以用y?f(x)来表示其某种内在规律的数量关系。但理想化的函数关系在实际工程应用中是很难寻找 的，对于那些没有明显解析式的函数关系表达式则只能通过实验观察的数据，利用多项式对某一函数的进行逼近，使得这个逼近函数能够反映f(x)的特性，而且利用多项式就可以简便的计算相应的函数值。例如我们不知道气温随日期变化的具体函数关系，但是我们可以测量一些孤立的日期的气温值，并假定此气温随日期变化的函数满足某一多项式。这样，利用已经测的数据，应用待定系数法便可以求得一个多项式函数f（x）。应用此函数就可以计算或者说预测其他日期的气温值。一般情况下，多项式的次数越多，需要的数据就越多，而预测也就越

第四章 非线性规划模型

第四章 非线性规划模型

第一节 非线性规划的实例与基本概念

一、非线性规划的实例 例1 化学反应的平衡组成

设现有原料由m种原子组成，各种原子数量依次为b1,b2,,bm,共生成，设生产数量（待求）依次为x1,x2,,xn。设第j种分子n种分子（产品）

中含各种原子的数量依次为

a1j,a2j,amj, j?1,2,n 所有产品中含第i种原子数之和为

ai1x1?ai2x2??ainxn, i?1,2,m 由熟知的质量守恒定律有

ai1x1?ai2x2??ainxn?bi, i?1,2,m

在一定的温度、压力下，每种化合物都具有一定的自由能，根据化学热力学原理，当化学反应达到平衡状态时，系统的总自由能最小。用

fj(x)?fj(x1,x2xn)表示第j种化合物具有的自由能，它的表达式为

n fj(x)?xj(cj?lnxj?ln(?xi))

i?1其中cj是与温度、压力及j有关的常数。总自由能为

数值分析,拉格朗日插值法C语言的实现

实验 一 .拉格朗日插值法C语言的实现

1.实验目的：

进一步熟悉拉格朗日插值法。

掌握编程语言字符处理程序的设计和调试技术。

2.实验要求：

已知：某些点的坐标以及点数。

输入：条件点数以及这些点的坐标 。

输出：根据给定的点求出其对应的拉格朗日插值多项式的值 。

3.程序流程：

（1）输入已知点的个数；

（2）分别输入已知点的X坐标；

（3）分别输入已知点的Y坐标；

（4）通过调用函数lagrange函数，来求某点所对应的函数值。

拉格朗日插值多项式如下：

Ln(xj) yklk(xj) yjj 0,1,……n k 0n

其中lk(x)

(x x0)……(x-xk-1)(x-xk+1) …(x-xn)(xk x0)……(xk-xk-1)(xk-xk+1) …(xk-xn)k 0,1,……,n

程序流程图：

数值分析,拉格朗日插值法C语言的实现

↓

程序如下：

#include <iostream>

#include <conio.h>

#include <malloc.h>

float lagrange(float *x,float *y,float xx,int n) /*拉格朗日插值算法*/