Research On Effective Numerical Algorithms For Semi-infinite Programming

Semi-infinite programming (SIP) not only has been applied widely and directly inengineering design, optimal control, information technology, economic balance and otherfields, but also plays an important role in some academic aspects, such as Chebyshevapproximation theory, mathematical physics, fuzzy set, the robust optimization and soon. Therefore, the research of efective numerical algorithms on semi-infinite program-ming has strong application value, and has aroused great attention from scholars in theworld. Many scholars propose various algorithms solving semi-infinite programming us-ing smooth nonlinear programming technology, many of which are designed based on thepenalty function method in nonlinear programming. Penalty function method has manyadvantages, such as allowing arbitrary initial point, simple structure and getting con-vergence under the proper conditions. However, it is not easy to adjust for the penaltyparameter. Meanwhile, iteration points and the final optimal solutions often may notmeet the requirements of feasibility. Recently, based on ideas of the two stage method[Polak,1978], penalty function methods and feasible direction methods, Prof. Jian hasproposed a strongly sub-feasible direction method. This method allows arbitrary initialpoints, and guarantees the feasibility of constraints is monotonously increasing. Oncea certain iterate gets into the feasible set, the algorithm will become feasible directionalgorithm.In recent years, strongly sub-feasible direction methods, sequential quadratic pro-gramming (SQP), sequential quadratically constrained quadratic programming (SQCQP)and norm-relaxed technique have been combined fully, and have concluded that a se-ries of achievements, such as a strongly sub-feasible norm-relaxed SQP algorithm, thea strongly sub-feasible norm-relaxed SQCQP algorithm etc. In addition, a new typeof strongly sub-feasible direction algorithms are proposed utilizing penalty method toimprove the line search of strong sub-feasible direction method. These algorithms havemany advantages of good convergence and numerical instability, part of which has beenapplied in the cable force optimization of cable-stayed bridge and FIR QMF Bank de-sign. Therefore, how to apply these good ideas in the algorithms above to constructnumerical algorithms for semi-infinite programming, to form a new system of solvingsemi-infinite programming, has certain theoretical significance and application value. This dissertation firstly proposes three new algorithms for the discretized semi-infiniteoptimization problems, including a strongly sub-feasible norm-relaxed SQP algorithm, astrongly sub-feasible norm-relaxed SQCQP algorithm and a new penalty function basedstrongly sub-feasible SQP algorithm. Secondly, a new discretization method based two-stage SQP algorithm solving semi-infinite programming is proposed. The inner iterationitself is a new two-stage SQP algorithm for the discretized problems from semi-infiniteprogramming. Finally, two algorithm frameworks solving semi-infinite programming areproposed using discretization method and local reduction method, respectively. More-over, the global convergence of the first algorithm framework is proved.Chapter1firstly presents the research background of this dissertation, and brieflyexpounds the research history and present situation of semi-infinite programming. Sec-ondly, it introduces the basic algorithm of semi-infinite programming such as discretiza-tion method, local reduction method, exchange method, and other algorithms, fromthe main ideas, steps of algorithms and the related theory. Finally, the design basis ofalgorithms in this dissertation is analyzed, and the main research content and structurearrangement are presented.Combining the ideas of the norm-relaxed feasible SQP algorithm and strongly sub-feasible direction methods, chapter2presents a strongly sub-feasible norm-relaxed SQPalgorithm for the discretized semi-infinite optimization problems. This algorithm allowsarbitrary initial points. At each iteration, the main search direction is obtained bysolving only one direction finding subproblem, in which the constraint index set beingupdated can reduce the number of constraints. Based on the properties of strongly sub-feasible direction methods, the existing technique of updating constraint index sets isimproved. It not only guarantees the global convergence of the proposed algorithm, butalso reduces the computational cost greatly and avoids the numerical difculty causedby overmuch constraints of the discretized semi-infinite optimization problems. Somepreliminary numerical results show that the proposed algorithm is efective. In addition,an high order correction direction is introduced to improve the algorithm above, andmake it obtain the superlinear convergence. Finally, based on the technique of updatingconstraints index sets, the algorithm above is extended to solve the discretized minimaxsemi-infinite optimization problems.Chapter3presents a strongly sub-feasible norm-relaxed SQCQP algorithm for the discretized semi-infinite optimization problems. The algorithm is suitable for semi-infinite programming in which the nonlinear degree of constraints is high. By updatingconstraints index sets of the QCQP subproblem and designing correction technique ofsecond order Hessian matrix of constraints function, the proposed algorithm not onlyreduces the number of constraints and the computational cost of QCQP subproblemgreatly, but also keeps the advantage of previous strongly sub-feasible norm-relaxedSQCQP algorithm in nonlinear programming. The proposed algorithm can start fromarbitrary initial point, and ensure that the iterates get into the feasible set after afinite number of iterations. Without any other correction direction, under some properconditions, the global and superlinear convergence properties are proved. Numericalnumerical results show that the proposed algorithm is stable and efective.Chapter4presents a new penalty function based strongly sub-feasible SQP algo-rithm for the discretized semi-infinite optimization problems. The algorithm has thefollowing features: initial point is chosen arbitrarily; according to the degree of iter-ation points deviating from the feasible region, two search direction subproblems areconstructed, which forms are unified. When the iteration point away from the feasibleregion, penalty functions is used to construct the line search, otherwise, the idea ofstrongly sub-feasible direction method is used to construct the line search. This searchis more relaxed than strongly sub-feasible direction methods. At each iteration, onlyone QP subproblem is solved to obtain a search direction. Only a few constraints arechosen, which can reduce the computation cost greatly. Under some weak conditions,the proposed algorithm possesses global convergence. Numerical numerical results showthat the proposed algorithm is efective.Combining the discretization method, Chapter5presents a new two-stage SQP algo-rithm for semi-infinite programming. Firstly, the inner iteration algorithm is proposed,which is really a new two-stage SQP algorithm for the discretized problems from semi-infinite programming. The algorithm allows arbitrary starting point, and the structureof QP subproblem is simple, in which only a few of constraints are chosen to obtainthe search direction. This can reduce the computation cost greatly. The line searchis constructed using two-stage methods. Nextly, under some proper conditions, theglobal convergence is proved. Some preliminary numerical results show that the inneriteration algorithm is efective. Finally, combining the discretization method, a new two-stage SQP algorithm for semi-infinite programming is proposed, the correspondingconvergence result is given.On the basis of the proposed algorithms in the previous chapters, chapter6presentstwo new algorithm frameworks solving semi-infinite programming. Firstly, a new dis-cretization method based algorithm framework is proposed, in which the proposed al-gorithms in the previous chapters are suitable for the inner iteration. Nextly, the globalconvergence is proved. Finally, combining the idea of local reduction, a new two-stagealgorithm framework is proposed. The first phase is computing an approximate solutionof semi-infinite programming using the proposed algorithms in the previous chapters.The second phase is solving the local reduction problem of semi-infinite programming,using the approximate solution as its initial point, and obtain an optimal solution ofSIP.Chapter7summaries the main work of this dissertation, and proposes some problemsneeded to be studied.Finally, it should be pointed out that, the proposed four algorithms solving thediscretized semi-infinite optimization problems can obtain the approximate solution ofsemi-infinite programming, and can be directly used when the accuracy is not high.The basis of theory see first quarter in chapter6. When the accuracy requirement ishigh, the approximate solution can be an initial point of another method to further con-struct algorithms solving semi-infinite programming, such as the local reduction basedtwo-stage algorithm framework solving semi-infinite programming in second quarter inchapter6.