最优化外点法

——电子工程学院

最优化方法及应用（2）

上机报告

外点法求最优解

题 目：

xxxxxxx

任课老师：

xxxxxxx

姓 名：

xxxxxxx

学 号:

02951

班 级：

外点法 一、问题描述： Min x1x2

s.t x122第1页 / 共5页

x210

二、问题分析

实现方法：外点法（C语言）。 外点法算法基本步骤：

1.构建函数F(X,Mk)f(X)Mka(X). 2.输入初始点X.

3.用最速下降法求min[F(X,Mk)]得到较优点Xk.

4.若Mka(X)，则Xk就是所求最优点，打印结果。否则转5. 5.MkMk1，k=k+1，转3.

三、代码

// WaiDianFa.cpp : Defines the entry point for the console application. //

#include \"stdafx.h\"

#define _accuracy 0.0001 //f()

float f(float x1,float x2){ return x1*x1+x2*x2; } //F()

float F(float x1,float x2,int M){ float sum; sum = (x1+x2-1>=0)?(x1*x1+x2*x2):(x1*x1+x2*x2+M*(x1+x2-1)*(x1+x2-1)); return sum; }

//grad()

void grad(float x[2],float g[2],int m){ if(x[0]+x[1]-1>=0){ g[0] = 2*x[0]; g[1] = 2*x[1]; } else{ g[0] = 2*x[0]+m*2*(x[0]+x[1]-1); g[1] = 2*x[1]+m*2*(x[0]+x[1]-1);

外点法 } } //

void plusx(float x1[2],float x0[2],float g[2],float t){ x1[0] = x0[0]+t*g[0]; x1[1] = x0[1]+t*g[1]; }

//gold()

void gold(float &a,float &b,float x[2],float g[2],int M){ float t1,t2; float x1[2],x2[2]; t2=a+(float)0.382*(b-a); plusx(x2,x,g,t2); t1=a+b-t2; plusx(x1,x,g,t1); float f1,f2; f1=F(x1[0],x1[1],M); f2=F(x2[0],x2[1],M); if(f1f2) b=t1; else {a=t2;b=t1;} } //

void linesearch(float Xk1[2],float Xk0[2],float g[2],int M){ float mina,maxb,Lanbuda; /* searchRange(mina,maxb,Xk0,g);*/ mina = -100; maxb =100; while (maxb-mina>_accuracy) { gold(mina,maxb,Xk0,g,M); } Lanbuda = (mina+maxb)/2; plusx(Xk1,Xk0,g,Lanbuda); }

void find_min(float x[2],int M){ int k =0; float x1[2]={x[0],x[1]}; float g[2]; float f0,f1;

第2页 / 共5页

外点法 f0 = F(x[0],x[1],M); grad(x,g,M); while (1) { if(0.01>g[0]*g[0]+g[1]*g[1]) break; if(++k>1000) break; // if (g[0]*g[0]+g[1]*g[1]==0) break; linesearch(x1,x,g,M); f1 = F(x1[0],x[1],M); grad(x1,g,M); x[0] = x1[0]; x[1] = x1[1]; f0 = f1; } printf(\"M=%d:\X=[%.3f,%.3f]\\ printf(\"minf(X)=%.3f\\n\}

int main(int argc, char* argv[]) { float x[2] = {-10,-10}; const int C = 10; int M = 1; float threshold = M*(x[0]+x[1]-1)*(x[0]+x[1]-1); while (threshold>_accuracy) { find_min(x,M); M *= C; threshold = M*(x[0]+x[1]-1)*(x[0]+x[1]-1); } printf(\"root:\X=[%.3f,%.3f]\\ printf(\"minf(X)=%.3f\\n\ return 0; }

第3页 / 共5页

外点法 四、运行结果及分析

运行结果： 函数

Min x1x2s.t x122第4页 / 共5页

x210

精度：ε=0.001 起始X=[-10，-10]

在第四次迭代时（M=1000），已经找到最优解了。