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

《2016年大連理工大學(xué)優(yōu)化方法上機(jī)大作業(yè).doc》由會員分享，可在線閱讀，更多相關(guān)《2016年大連理工大學(xué)優(yōu)化方法上機(jī)大作業(yè).doc（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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; 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 = 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 %f\n,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; end function 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 %f\n,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.000000 x1 = 1.0000 1.0000 3.BFGS法： function f = fun(x) f = (1-x(1))^2 + 100*(x(2)-x(1)^2)^2; 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 = 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 %f\n,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; 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 =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 %f\n,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; end function [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); end function 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:3 h_inequ=abs(max(g(i),-r_al(i+1)/pena)); end h1 = 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> 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<=b cvx_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: Solved Optimal value (cvx_optval): -5.4 2、 >> 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<=b cvx_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: Solved Optimal value (cvx_optval): -3