2016年大連理工大學(xué)優(yōu)化方法上機(jī)大作業(yè).doc

2016年大連理工大學(xué)優(yōu)化方法上機(jī)大作業(yè)學(xué)院：專業(yè)：班級：學(xué)號：姓名：上機(jī)大作業(yè)1：1.最速下降法：function f = fun(x) f = (1-x(1)2 + 100*(x(2)-x(1)2)2; endfunction g = grad(x) g = zeros(2,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)2-x(2); g(2) = 200*(x(2)-x(1)2); end function x_star = steepest(x0,eps) gk = grad(x0); res = norm(gk); k = 0; while res > eps && k<=1000 dk = -gk; ak =1; f0 = fun(x0); f1 = fun(x0+ak*dk); slope = dot(gk,dk); while f1 > f0 + 0.1*ak*slope ak = ak/4; xk = x0 + ak*dk; f1 = fun(xk); end k = k+1; x0 = xk; gk = grad(xk);res = norm(gk); fprintf(-The %d-th iter, the residual is %fn,k,res); end x_star = xk; end>> clear>> x0=0,0;>> eps=1e-4;>> x=steepest(x0,eps)2.牛頓法：function f = fun(x) f = (1-x(1)2 + 100*(x(2)-x(1)2)2; endfunction g = grad2(x) g = zeros(2,2); g(1,1)=2+400*(3*x(1)2-x(2); g(1,2)=-400*x(1); g(2,1)=-400*x(1); g(2,2)=200; end function g = grad(x) g = zeros(2,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)2-x(2); g(2) = 200*(x(2)-x(1)2); end function x_star = newton(x0,eps) gk = grad(x0); bk = grad2(x0)(-1); res = norm(gk); k = 0; while res > eps && k<=1000 dk=-bk*gk; xk=x0+dk; k = k+1; x0 = xk; gk = grad(xk); bk = grad2(xk)(-1); res = norm(gk); fprintf(-The %d-th iter, the residual is %fn,k,res); end x_star = xk; end>> clear>> x0=0,0;>> eps=1e-4;>> x1=newton(x0,eps)-The 1-th iter, the residual is 447.213595-The 2-th iter, the residual is 0.000000x1 = 1.0000 1.00003.BFGS法：function f = fun(x) f = (1-x(1)2 + 100*(x(2)-x(1)2)2; endfunction g = grad(x) g = zeros(2,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)2-x(2); g(2) = 200*(x(2)-x(1)2); end function x_star = bfgs(x0,eps) g0 = grad(x0); gk=g0; res = norm(gk); Hk=eye(2); k = 0; while res > eps && k<=1000 dk = -Hk*gk; ak =1; f0 = fun(x0); f1 = fun(x0+ak*dk); slope = dot(gk,dk); while f1 > f0 + 0.1*ak*slope ak = ak/4; xk = x0 + ak*dk; f1 = fun(xk); end k = k+1; fa0=xk-x0; x0 = xk; go=gk;gk = grad(xk);y0=gk-g0;Hk=(eye(2)-fa0*(y0)/(fa0)*(y0)*(eye(2)-(y0)*(fa0)/(fa0)*(y0)+(fa0*(fa0)/(fa0)*(y0);res = norm(gk); fprintf(-The %d-th iter, the residual is %fn,k,res); end x_star = xk; End>> clear>> x0=0,0;>> eps=1e-4;>> x=bfgs(x0,eps)4.共軛梯度法： function f = fun(x) f = (1-x(1)2 + 100*(x(2)-x(1)2)2; endfunction g = grad(x) g = zeros(2,1); g(1)=2*(x(1)-1)+400*x(1)*(x(1)2-x(2); g(2) = 200*(x(2)-x(1)2); end function x_star =CG(x0,eps) gk = grad(x0);res = norm(gk); k = 0; dk = -gk; while res > eps && k<=1000 ak =1; f0 = fun(x0); f1 = fun(x0+ak*dk); slope = dot(gk,dk); while f1 > f0 + 0.1*ak*slope ak = ak/4; xk = x0 + ak*dk; f1 = fun(xk); end k = k+1; x0 = xk; g0=gk; gk = grad(xk);res = norm(gk);p=(gk/g0)2;dk1=dk;dk=-gk+p*dk1;fprintf(-The %d-th iter, the residual is %fn,k,res); end x_star = xk; end>> clear>> x0=0,0;>> eps=1e-4;>> x=CG(x0,eps)上機(jī)大作業(yè)2：function f= obj(x)f=4*x(1)-x(2)2-12;endfunction h,g =constrains(x)h=x(1)2+x(2)2-25;g=zeros(3,1);g(1)=-10*x(1)+x(1)2-10*x(2)+x(2)2+34;g(2)=-x(1);g(3)=-x(2);endfunction f=alobj(x) %拉格朗日增廣函數(shù)%N_equ等式約束個數(shù)?%N_inequ不等式約束個數(shù)N_equ=1;N_inequ=3;global r_al pena;%全局變量h_equ=0;h_inequ=0;h,g=constrains(x);%等式約束部分?for i=1:N_equ h_equ=h_equ+h(i)*r_al(i)+(pena/2)*h(i).2;end %不等式約束部分for i=1:N_inequ h_inequ=h_inequ+(0.5/pena)*(max(0,(r_al(i)+pena*g(i).2-r_al(i).2);end%拉格朗日增廣函數(shù)值f=obj(x)+h_equ+h_inequ;function f=compare(x) global r_al pena N_equ N_inequ;N_equ=1;N_inequ=3;h_inequ=zeros(3,1);h,g=constrains(x);%等式部分for i=1:1 h_equ=abs(h(i); end%不等式部分 for i=1:3h_inequ=abs(max(g(i),-r_al(i+1)/pena);endh1 = max(h_inequ);f= max(abs(h_equ),h1); %sqrt(h_equ+h_inequ);function x,fmin,k =almain(x_al)%本程序為拉格朗日乘子算法示例算法%函數(shù)輸入：% x_al:初始迭代點% r_al：初始拉格朗日乘子N-equ:等式約束個數(shù)N_inequ:不等式約束個數(shù)?%函數(shù)輸出% X：最優(yōu)函數(shù)點FVAL:最優(yōu)函數(shù)值%=程序開始=global r_al pena ; %參數(shù)（全局變量）pena=10; %懲罰系數(shù)r_al=1,1,1,1;c_scale=2; %乘法系數(shù)乘數(shù)cta=0.5; %下降標(biāo)準(zhǔn)系數(shù)e_al=1e-4; %誤差控制范圍max_itera=25;out_itera=1; %迭代次數(shù)%=算法迭代開始=while out_itera<max_itera x_al0=x_al; r_al0=r_al; %判斷函數(shù)? compareFlag=compare(x_al0); %無約束的擬牛頓法BFGS X,fmin=fminunc(alobj,x_al0); x_al=X; %得到新迭代點 %判斷停止條件? if compare(x_al)<e_al disp(we get the opt point); break end %c判斷函數(shù)下降度? if compare(x_al)<cta*compareFlag pena=1*pena; %可以根據(jù)需要修改懲罰系數(shù)變量 else pena=min(1000,c_scale*pena); %乘法系數(shù)最大1000 disp(pena=2*pena); end %?更新拉格朗日乘子 h,g=constrains(x_al); for i=1:1 %等式約束部分 r_al(i)= r_al0(i)+pena*h(i); end for i=1:3 %不等式約束部分 r_al(i+1)=max(0,(r_al0(i+1)+pena*g(i); end out_itera=out_itera+1;end%+迭代結(jié)束+disp(the iteration number);k=out_itera;disp(the value of constrains); compare(x_al)disp(the opt point); x=x_al; fmin=obj(X);>> clear>> x_al=0,0;>> x,fmin,k=almain(x_al)上機(jī)大作業(yè)3： 1、>> clear all n=3; c=-3,-1,-3; A=2,1,1;1,2,3;2,2,1;-1,0,0;0,-1,0;0,0,-1;b=2,5,6,0,0,0;cvx_begin variable x(n) minimize( c*x) subject to A*x<=bcvx_end Calling SDPT3 4.0: 6 variables, 3 equality constraints- num. of constraints = 3 dim. of linear var = 6* SDPT3: Infeasible path-following algorithms* version predcorr gam expon scale_data NT 1 0.000 1 0 it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime- 0|0.000|0.000|1.1e+01|5.1e+00|6.0e+02|-7.000000e+01 0.000000e+00| 0:0:00| chol 1 1 1|0.912|1.000|9.4e-01|4.6e-02|6.5e+01|-5.606627e+00 -2.967567e+01| 0:0:01| chol 1 1 2|1.000|1.000|1.3e-07|4.6e-03|8.5e+00|-2.723981e+00 -1.113509e+01| 0:0:01| chol 1 1 3|1.000|0.961|2.3e-08|6.2e-04|1.8e+00|-4.348354e+00 -6.122853e+00| 0:0:01| chol 1 1 4|0.881|1.000|2.2e-08|4.6e-05|3.7e-01|-5.255152e+00 -5.622375e+00| 0:0:01| chol 1 1 5|0.995|0.962|1.6e-09|6.2e-06|1.5e-02|-5.394782e+00 -5.409213e+00| 0:0:01| chol 1 1 6|0.989|0.989|2.7e-10|5.2e-07|1.7e-04|-5.399940e+00 -5.400100e+00| 0:0:01| chol 1 1 7|0.989|0.989|5.3e-11|5.8e-09|1.8e-06|-5.399999e+00 -5.400001e+00| 0:0:01| chol 1 1 8|1.000|0.994|2.8e-13|4.3e-11|2.7e-08|-5.400000e+00 -5.400000e+00| 0:0:01| stop: max(relative gap, infeasibilities) < 1.49e-08- number of iterations = 8 primal objective value = -5.39999999e+00 dual objective value = -5.40000002e+00 gap := trace(XZ) = 2.66e-08 relative gap = 2.26e-09 actual relative gap = 2.21e-09 rel. primal infeas (scaled problem) = 2.77e-13 rel. dual " " " = 4.31e-11 rel. primal infeas (unscaled problem) = 0.00e+00 rel. dual " " " = 0.00e+00 norm(X), norm(y), norm(Z) = 4.3e+00, 1.3e+00, 1.9e+00 norm(A), norm(b), norm(C) = 6.7e+00, 9.1e+00, 5.4e+00 Total CPU time (secs) = 0.71 CPU time per iteration = 0.09 termination code = 0 DIMACS: 3.6e-13 0.0e+00 5.8e-11 0.0e+00 2.2e-09 2.3e-09- -Status: SolvedOptimal value (cvx_optval): -5.42、>> clear all n=2; c=-2,-4; G=0.5,0;0,1; A=1,1;-1,0;0,-1; b=1,0,0;cvx_begin variable x(n) minimize( x*G*x+c*x) subject to A*x<=bcvx_end Calling SDPT3 4.0: 7 variables, 3 equality constraints For improved efficiency, SDPT3 is solving the dual problem.- num. of constraints = 3 dim. of socp var = 4, num. of socp blk = 1 dim. of linear var = 3* SDPT3: Infeasible path-following algorithms* version predcorr gam expon scale_data NT 1 0.000 1 0 it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime- 0|0.000|0.000|8.0e-01|6.5e+00|3.1e+02| 1.000000e+01 0.000000e+00| 0:0:00| chol 1 1 1|1.000|0.987|4.3e-07|1.5e-01|1.6e+01| 9.043148e+00 -2.714056e-01| 0:0:00| chol 1 1 2|1.000|1.000|2.6e-07|7.6e-03|1.4e+00| 1.234938e+00 -5.011630e-02| 0:0:00| chol 1 1 3|1.000|1.000|2.4e-07|7.6e-04|3.0e-01| 4.166959e-01 1.181563e-01| 0:0:00| chol 1 1 4|0.892|0.877|6.4e-08|1.6e-04|5.2e-02| 2.773022e-01 2.265122e-01| 0:0:00| chol 1 1 5|1.000|1.000|1.0e-08|7.6e-06|1.5e-02| 2.579468e-01 2.427203e-01| 0:0:00| chol 1 1 6|0.905|0.904|3.1e-09|1.4e-06|2.3e-03| 2.511936e-01 2.488619e-01| 0:0:00| chol 1 1 7|1.000|1.000|6.1e-09|7.7e-08|6.6e-04| 2.503336e-01 2.496718e-01| 0:0:00| chol 1 1 8|0.903|0.903|1.8e-09|1.5e-08|1.0e-04| 2.500507e-01 2.499497e-01| 0:0:00| chol 1 1 9|1.000|1.000|4.9e-10|3.5e-10|2.9e-05| 2.500143e-01 2.499857e-01| 0:0:00| chol 1 1 10|0.904|0.904|4.7e-11|1.3e-10|4.4e-06| 2.500022e-01 2.499978e-01| 0:0:00| chol 2 2 11|1.000|1.000|2.3e-12|9.4e-12|1.2e-06| 2.500006e-01 2.499994e-01| 0:0:00| chol 2 2 12|1.000|1.000|4.7e-13|1.0e-12|1.8e-07| 2.500001e-01 2.499999e-01| 0:0:00| chol 2 2 13|1.000|1.000|2.0e-12|1.0e-12|4.2e-08| 2.500000e-01 2.500000e-01| 0:0:00| chol 2 2 14|1.000|1.000|2.6e-12|1.0e-12|7.3e-09| 2.500000e-01 2.500000e-01| 0:0:00| stop: max(relative gap, infeasibilities) < 1.49e-08- number of iterations = 14 primal objective value = 2.50000004e-01 dual objective value = 2.49999996e-01 gap := trace(XZ) = 7.29e-09 relative gap = 4.86e-09 actual relative gap = 4.86e-09 rel. primal infeas (scaled problem) = 2.63e-12 rel. dual " " " = 1.00e-12 rel. primal infeas (unscaled problem) = 0.00e+00 rel. dual " " " = 0.00e+00 norm(X), norm(y), norm(Z) = 3.2e+00, 1.5e+00, 1.9e+00 norm(A), norm(b), norm(C) = 3.9e+00, 4.2e+00, 2.6e+00 Total CPU time (secs) = 0.36 CPU time per iteration = 0.03 termination code = 0 DIMACS: 3.7e-12 0.0e+00 1.3e-12 0.0e+00 4.9e-09 4.9e-09- -Status: SolvedOptimal value (cvx_optval): -3