A NEW EXCHANGE METHOD FOR CONVEX SEMI-INFINITE PROGRAMMING

作者：Zhang Liping; Wu Soon Yi^*; Lopez Marco A

来源：SIAM Journal on Optimization, 2010, 20(6): 2959-2977.

DOI：10.1137/090767133

• convex semi-infinite programming
• exchange methods
• adding-dropping rules
• complex approximation theory
• filter design

In this paper we propose a new exchange method for solving convex semi-infinite programming (CSIP) problems. We introduce a new dropping-rule in the proposed exchange algorithm, which only keeps those active constraints with positive Lagrange multipliers. Moreover, we exploit the idea of looking for eta-infeasible indices of the lower level problem as the adding-rule in our algorithm. Hence the algorithm does not require to solve a maximization problem over the index set at each iteration; it only needs to find some points such that a certain computationally-easy criterion is satisfied. Under some reasonable conditions, the new adding-dropping rule guarantees that our algorithm provides an approximate optimal solution for the CSIP problem in a finite number of iterations. In the numerical experiments, we apply the proposed algorithm to solve some test problems from the literature, including some medium-sized problems from complex approximation theory and FIR filter design. We compare our algorithm with an existing central cutting plane algorithm and with the semi-infinite solver fseminf in MATLAB toolbox, and we find that our algorithm solves the CSIP problem much faster. For the FIR filter design problem, we show that our algorithm solves the problem better than some algorithms that were technically established for the problem.

• 出版日期2010
• 单位清华大学