Global convergence analysis of the aggregate constraint homotopy method for nonlinear programming problems with both inequality and equality constraints

In this paper, we construct appropriate aggregate mappings and a new aggregate constraint homotopy (ACH) equation by converting equality constraints to inequality constraints and introducing two variable parameters. Then, we propose an ACH method for nonlinear programming problems with inequality and equality constraints. Under suitable conditions, we obtain the global convergence of this ACH method, which makes us prove the existence of a bounded smooth path that connects a given point to a Karush–Kuhn–Tucker point of nonlinear programming problems. The numerical tracking of this path can lead to an implementable globally convergent algorithm. A numerical procedure is given to implement the proposed ACH method, and the computational results are reported.     

A constraint shifting homotopy method for general non-linear programming

In this article, a constraint shifting homotopy method (CSHM) is proposed for solving non-linear programming with both equality and inequality constraints. A new homotopy is constructed, and existence and global convergence of a homotopy path determined by it are proven. All problems that can be solved by the combined homotopy interior point method (CHIPM) can also be solved by the proposed method. In contrast to the combined homotopy infeasible interior point method (CHIIPM), it needs a weaker regularity condition. And the starting point in the proposed method is not necessarily a feasible point or an interior point, so it is more convenient to be implemented than CHIPM and CHIIPM. Numerical results show that the proposed algorithm is feasible and effective.     

解约束非凸规划问题的同伦方法的收敛性定理

本文在利用组合内点同伦方法求解约束非凸规划问题时,得到了一些新的收敛性定理.证明了同伦映射为正则映射的条件下,选取合适的同伦方程,用此同伦方法得到的K-K-T点一定是问题局部最优解.     

求解一类非线性规划的连续同伦方法(英文)

In this paper we present a homotopy continuation method for finding the Karush-Kuhn-Tucker point of a class of nonlinear non-convex programming problems. Two numerical examples are given to show that this method is effective. It should be pointed out that we extend the results of Lin et al. （see Appl. Math. Comput., 80（1996）, 209-224） to a broader class of non-convex programming problems.     

解非凸规划问题动边界组合同伦方法

本文给出了一个新的求解非凸规划问题的同伦方法,称为动边界同伦方程,并在较弱的条件下,证明了同伦路径的存在性和大范围收敛性．与已有的拟法锥条件、伪锥条件下的修正组合同伦方法相比,同伦构造更容易,并且不要求初始点是可行集的内点,因此动边界组合同伦方法比修正组合同伦方法及弱法锥条件下的组合同伦内点法和凝聚约束同伦方法更便于应用．     

A homotopy interior point method for semi-infinite programming problems

This paper presents a homotopy interior point method for solving a semi-infinite programming (SIP) problem. For algorithmic purpose, based on bilevel strategy, first we illustrate appropriate necessary conditions for a solution in the framework of standard nonlinear programming (NLP), which can be solved by homotopy method. Under suitable assumptions, we can prove that the method determines a smooth interior path from a given interior point to a point w ^*, at which the necessary conditions are satisfied. Numerical tracing this path gives a globally convergent algorithm for the SIP. Lastly, several preliminary computational results illustrating the method are given.     

A nonmonotonic trust region algorithm for a class of semi-infinite minimax programming

Based on the discretization methods for solving semi-infinite programming problems, this paper presents a new nonmonotonic trust region algorithm for a class of semi-infinite minimax programming problem. Under some mild assumptions, the global convergence of the proposed algorithm is given. Numerical tests are reported that show the efficiency of the proposed method.     

连续化方法求解一般无界非凸规划的K-K-T点

给出了求解无界非凸规划的K-K-T系统的一种连续化方法,在适当的条件下,得到了连接可行域内部任意给定的点和非凸规划的K-K-T点的同伦路径存在性的构造性证明,从而构建了可数值实现的全局收敛性算法.数值算例进一步验证了本文结果的有效性.     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.     

An interior point algorithm for semi-infinite linear programming

We consider the generalization of a variant of Karmarkar's algorithm to semi-infinite programming. The extension of interior point methods to infinite-dimensional linear programming is discussed and an algorithm is derived. An implementation of the algorithm for a class of semi-infinite linear programs is described and the results of a number of test problems are given. We pay particular attention to the problem of Chebyshev approximation. Some further results are given for an implementation of the algorithm applied to a discretization of the semi-infinite linear program, and a convergence proof is given in this case.     

An Approximation Approach to Non-strictly Convex Quadratic Semi-infinite Programming

We present in this paper a numerical method for solving non-strictly-convex quadratic semi-infinite programming including linear semi-infinite programming. The proposed method transforms the problem into a series of strictly convex quadratic semi-infinite programming problems. Several convergence results and a numerical experiment are given.     

An Approximation Approach to Non-strictly Convex Quadratic Semi-infinite Programming

We present in this paper a numerical method for solving non-strictly-convex quadratic semi-infinite programming including linear semi-infinite programming. The proposed method transforms the problem into a series of strictly convex quadratic semi-infinite programming problems. Several convergence results and a numerical experiment are given.     

Semi-Infinite Programming Approach to Continuously-Constrained Linear-Quadratic Optimal Control Problems

Consider the class of linear-quadratic (LQ) optimal control problems with continuous linear state constraints, that is, constraints imposed on every instant of the time horizon. This class of problems is known to be difficult to solve numerically. In this paper, a computational method based on a semi-infinite programming approach is given. The LQ optimal control problem is formulated as a positive-quadratic infinite programming problem. This can be done by considering the control as the decision variable, while taking the state as a function of the control. After parametrizing the decision variable, an approximate quadratic semi-infinite programming problem is obtained. It is shown that, as we refine the parametrization, the solution sequence of the approximate problems converges to the solution of the infinite programming problem (hence, to the solution of the original optimal control problem). Numerically, the semi-infinite programming problems obtained above can be solved efficiently using an algorithm based on a dual parametrization method.     

A relaxed cutting plane method for semi-infinite semi-definite programming

In this paper, we develop two discretization algorithms with a cutting plane scheme for solving combined semi-infinite and semi-definite programming problems, i.e., a general algorithm when the parameter set is a compact set and a typical algorithm when the parameter set is a box set in the m-dimensional space. We prove that the accumulation point of the sequence points generated by the two algorithms is an optimal solution of the combined semi-infinite and semi-definite programming problem under suitable assumption conditions. Two examples are given to illustrate the effectiveness of the typical algorithm.     

A New Quadratic Semi-infinite Programming Algorithm Based on Dual Parametrization

The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

Interior-point algorithms for semi-infinite programming

In order to study the behavior of interior-point methods on very large-scale linear programming problems, we consider the application of such methods to continuous semi-infinite linear programming problems in both primal and dual form. By considering different discretizations of such problems we are led to a certain invariance property for (finite-dimensional) interior-point methods. We find that while many methods are invariant, several, including all those with the currently best complexity bound, are not. We then devise natural extensions of invariant methods to the semi-infinite case. Our motivation comes from our belief that for a method to work well on large-scale linear programming problems, it should be effective on fine discretizations of a semi-infinite problem and it should have a natural extension to the limiting semi-infinite case.Research supported in part by NSF, AFORS and ONR through NSF grant DMS-8920550.     

A constraint shifting homotopy method for convex multi-objective programming

In this paper, a constraint shifting combined homotopy method for solving multi-objective programming problems with both equality and inequality constraints is presented. It does not need the starting point to be an interior point or a feasible point and hence is convenient to use. Under some assumptions, the existence and convergence of a smooth path to an efficient solution are proven. Simple numerical results are given.     

Analytical solutions for the fractional nonlinear cable equation using a modified homotopy perturbation and separation of variables methods

In this paper, we first introduce a new homotopy perturbation method for solving a fractional order nonlinear cable equation. By applying proposed method the nonlinear equation it is changed to linear equation for per iteration of homotopy perturbation method. Then, we solve obtained problems with separation method. In examples, we illustrate that the exact solution is obtained in one iteration by convenience separating of source term in given equation.     

A constraint shifting homotopy method for convex multi-objective programming

In this paper, a constraint shifting combined homotopy method for solving multi-objective programming problems with both equality and inequality constraints is presented. It does not need the starting point to be an interior point or a feasible point and hence is convenient to use. Under some assumptions, the existence and convergence of a smooth path to an efficient solution are proven. Simple numerical results are given.     

Feasible Method for Generalized Semi-Infinite Programming

In this paper, we analyze the outer approximation property of the algorithm for generalized semi-infinite programming from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). A simple bound on the regularization error is found and used to formulate a feasible numerical method for generalized semi-infinite programming with convex lower-level problems. That is, all iterates of the numerical method are feasible points of the original optimization problem. The new method has the same computational cost as the original algorithm from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). We also discuss the merits of this approach for the adaptive convexification algorithm, a feasible point method for standard semi-infinite programming from Floudas and Stein (SIAM J. Optim. 18:1187–1208, 2007).