SQP Feasible Algorithm On Solving The Nonlinear Programming

The nonlinear programming problem is a hotspot problem that people careabout all the time. Because the objective function and the constraint function arenonlinear, there are not unitized method to solve nonlinear programming.Quadratic programming is the closest to linear programming. in thenonlinear programming When the symmetrical matrix of the objective function ofthe quadratic programming is positive or half-positive , the quadraticprogramming exists an unique solution x^* (global optimal solution). Therefore,people consider to make use of the above property to solve the nonlinearprogramming problem. This is the sequence quadratic programming method (i.e.SQP).We will discuss the fundamental idea of the sequence quadraticprogramming method in the following. We can construct a sub-problem at eachiteration point x_k and let the solution of this problem as the searching directiond_k. we can make the one-dimension searching along with this direction,namely x_k+1 =x_k+δ_kd_k and repeat this iteration processuntil x_k+1( k =0,1,2,)approaches the approximate constraint optimal point ofthe original problem.Since Wilson's research about sequence quadratic programming came outas well as Han and Powell successfully improve this work , Sequence quadraticprogramming method get extensive development. The method of constructingnonlinear programming to solve quadratic programming has many newprogresses ([1-11]). Most early sequence quadratic programming methods havetwo disadvantages: firstly, because it need to solve many quadratic programmingsub-problems at each iteration, the amount of calculation is large. Secondly, fromthe actual effect, sequence quadratic programming methods is extremely effectivefor the constraint optimization. But the point obtained from the calculation oncomputer usually is not feasible in sequence quadratic programming method. Theoptimization which is relevant with engineering design is constrained byobjective factors, so it often require the solution of the problem is feasible. That isthe serious disadvantage of sequence quadratic programming method.In order to overcome the disadvantage of sequence quadraticprogramming method, Panier and Tits presented a amendment about sequencequadratic programming method in 1987 [12]. The amendment guarantees that theiteration point is always in feasible region. But there are still two disadvantages in[12]: firstly, the method needs three different quadraticsub-programming (Q P0 )(QP )(LS ), at each iteration and "one rank" directionsometimes (it presented a complex quadratic programming problem, so theamount of the calculation is large at each step. The convergence rate is two stepssuperlinearity convergence). From then on, there are many researchers who makeamendment of sequence quadratic programming method in theory and application[1-11].Gao Ziyou ([7,8])make use of the following quadratic programming:()()0,1,2,,(),..min 012fxfxdimfxddHds tiiTTT+?≤=? +Where H is a symmetry positive matrix. It presented a sequence quadraticprogramming method that contains equality and inequality constraint. Because(1.4) may have no solution at point x . In order to solve this question, we dealwith it specially. Thus the amount of calculation increases.Kostreva and CHEN ([9.10]) presented another superlinearity algorithm:fxfxhvhjmstfxhvhhhHhjTjjTT()()1,2,..(),min0000012+?≤=?≤+where H is a symmetry positive matrix, vj > 0, (j=0,1,m). The searchdirection h is obtained from solving the quadratic sub-problem. It is a feasiblegradient direction. In order to avoid the Marotos effect, h could be modifiedonly one time. So than we need only solving two quadratic sub-problem. Thismethod is two step superlinearity convergence and it needs thatf j > 0, (j=0,1,m)are three order continuous differentiable. Zhu and Zhang[11] make use of the nonlinear programming with inequality constraint toconstruct a new sequence quadratic programming method. We need only solvingone quadratic sub-problem at each iteration and modify the feasible directionautomatically in order to avoid the Marotos effect. The method could retain theglobal convergence under the weak condition. We extend the work of Zhu andZhang ([11]) to the nonlinear programming with equality and inequalityconstraint and obtain a better sequence quadratic programming method comparedwith Gao Ziyou [8].We give the following algorithm:AlgorithmStep1. (initialization) Let x 0 ∈Xand a symmetric positive definite matrixB 0 = B( x0)∈Rn×nChoose ε ,ν ,β,ξ∈ (0,1),δ>2,α∈(0,12 ),τ∈(2,3),and Let k :=0;Step 2. Compute z 0k = z0( xk);d0k=d0k(xk),u^k=u^xk by solving the QPproblem(3.4)at x k. if d 0 k=0,stop. Otherwise, continue.Step3. Let J k = J( xk)=I(xk)∪J,Ak=(gj(xk);j∈Jk),if det( Ak TAk)=0,go to Step 5, else computeQ k = ( AkTAk)?1 AkT,d k = d0k ?QkT(|| d0k||τ e+^fk),^f k = (fj(xk+d0k )?z0k,j∈Jk),Where (1,1,,1)||e = ∈RJk. Ifg 0 ( xk )Td0k≤ min{?ξ ||d0k||δ ,?ξ||dk||δ},(3.5)continue,else go to Step 5.Step4. Do the finite attempted linear search. Let λ = 1 ,(1) iff 0 ( xk + λ dk)≤f0(xk)+αλg0(xk)Td0k, ( 2.6)f j ( xk+ λ dk)≤0,j∈I , ( 2.7)f j ( xk+ λ dk)=0,j∈J , ( 2.8)let λ k =λ go to Step 6, else go to(2);(2)Let λ = βλ。if λ < ε,go to Step 5,else repeat(1) of Step 4;Step 5. Compute λ k,the first numberλ in the sequence {1 ,β ,β2,}satisfyingf 0 ( xk + λ d0k)≤f0(xk)+νλg0(xk)Td0k, (2.9)f j ( xk+ λ dk)≤0,j∈I, (2.10)f j ( xk+ λ d0 k)=0,j∈J, (2.11)And let d k = d0k;Step6. Obtain B k+1 by updating the positive definite matrix Bk usingquasi-Newton formulas. set x k +1 =xk+λkdk and k = k+1. Go back to Step 2.Theorem 2.1 (Convergence of algorithm) The above algorithm stops atKKT point of Problem (2.1) by finite steps, or generates an infinite sequence,which accumulation point is KKT point of Problem (2.1).