We discuss the convergence of cutting plane algorithms for a class of nonconvex programs called the Generalized Lattice Point Problems (GLPP). A set of sufficient conditions which guarantee finite convergence are pres...
详细信息
We discuss the convergence of cutting plane algorithms for a class of nonconvex programs called the Generalized Lattice Point Problems (GLPP). A set of sufficient conditions which guarantee finite convergence are presented. Although these conditions are usually difficult to enforce in a practical implementation, they do illustrate the various factors that must be involved in a convergent rudimentary cutting plane algorithm. A striking example of nonconvergence (in which no subsequence converges to a feasible solution, even when seemingly strong cutting planes are used), is presented to show the effect of neglecting one such factor. We give an application of our analysis to problems with multiple choice constraints and finally discuss a modification of cutting plane algorithms so as to make finite convergence more readily implementable.
In the present paper, which is part III of our review concerning the theory of Φ-conjugate functions, we consider Lagrangians, duality theorems are proved and the connection to saddle point theorems is shown. By a fu...
详细信息
In the present paper, which is part III of our review concerning the theory of Φ-conjugate functions, we consider Lagrangians, duality theorems are proved and the connection to saddle point theorems is shown. By a fundamental inequality, duality theorems are proved and the connection to saddle point theorems is shown. By a fundamental inequality, duality theorems can be obtained, where results are modified given in part I and part II of our paper.
In this paper, we consider a general family of nonconvex programming problems. All of the objective functions of the problems in this family are identical, but their feasibility regions depend upon a parameter ϑ. This...
详细信息
In this paper, we consider a general family of nonconvex programming problems. All of the objective functions of the problems in this family are identical, but their feasibility regions depend upon a parameter ϑ. This family of problems is called a parametric nonconvex program (PNP). Solving (PNP) means finding an optimal solution for every program in the family. A prototype branch-and-bound algorithm is presented for solving (PNP). By modifying a prototype algorithm for solving a single nonconvex program, this algorithm solves (PNP) in one branch-and-bound search. To implement the algorithm, certain compact partitions and underestimating functions must be formed in an appropriate manner. We present an algorithm for solving a particular (PNP) which implements the prototype algorithm by forming compact partitions and underestimating functions based upon rules given by Falk and Soland. The programs in this (PNP) have the same concave objective function, but their feasibility regions are described by linear constraints with differing right-hand sides. Computational experience with this algorithm is reported for various problems.
This note presents a new convergence property for each of two branch-and-bound algorithms for nonconvex programming problems (Falk-Soland algorithms and Horst algorithms). For each algorithm, it has been shown previou...
详细信息
This note presents a new convergence property for each of two branch-and-bound algorithms for nonconvex programming problems (Falk-Soland algorithms and Horst algorithms). For each algorithm, it has been shown previously that, under certain conditions, whenever the algorithm generates an infinite sequence of points, at least one accumulation point of this sequence is a global minimum. We show here that, for each algorithm, in fact, under these conditions, every accumulation point of such a sequence is a global minimum.
This paper presents a branch-and-bound algorithm for minimizing the sum of a convex function in x, a convex function in y and a bilinear term in x and y over a closed set. Such an objective function is called biconvex...
详细信息
This paper presents a branch-and-bound algorithm for minimizing the sum of a convex function in x, a convex function in y and a bilinear term in x and y over a closed set. Such an objective function is called biconvex with biconcave functions similarly defined. The feasible region of this model permits joint constraints in x and y to be expressed. The bilinear programming problem becomes a special case of the problem addressed in this paper. We prove that the minimum of a biconcave function over a nonempty compact set occurs at a boundary point of the set and not necessarily an extreme point. The algorithm is proven to converge to a global solution of the nonconvex program. We discuss extensions of the general model and computational experience in solving jointly constrained bilinear programs, for which the algorithm has been implemented.
For fractional programs involving several ratios in the objective function, a dual is introduced with the help of Farkas' lemma. Often the dual is again a generalized fractional program. Duality relations are esta...
详细信息
For fractional programs involving several ratios in the objective function, a dual is introduced with the help of Farkas' lemma. Often the dual is again a generalized fractional program. Duality relations are established under weak assumptions. This is done in both the linear case and the nonlinear case. We show that duality can be obtained for these nonconvex programs using only a basic result on linear (convex) inequalities.
作者：
HORST, RProfessor
Fachbereich Mathematik Fachhochschule Darmstadt Darmstadt West Germany
In this note, we introduce a new class of generalized convex functions and show that a real functionf which is continuous on a compact convex subsetM of ℝn and whose set of global minimizers onM is arcwise-connected h...
详细信息
In this note, we introduce a new class of generalized convex functions and show that a real functionf which is continuous on a compact convex subsetM of ℝn and whose set of global minimizers onM is arcwise-connected has the property that every local minimum is global if, and only if,f belongs to that class of functions.
In this paper, we propose a feasible-direction method for large-scale nonconvex programs, where the gradient projection on a linear subspace defined by the active constraints of the original problem is determined by d...
详细信息
In this paper, we propose a feasible-direction method for large-scale nonconvex programs, where the gradient projection on a linear subspace defined by the active constraints of the original problem is determined by dual decomposition. Results are extended for dynamical problems which include distributed delays and constraints both in state and control variables. The approach is compared with other feasible-direction approaches, and the method is applied to a power generation problem. Some computational results are included.
A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed co...
详细信息
A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed convex polytopes contains the feasible region. No geometric tolerance parameters are required.
A method is described for globally minimizing concave functions over convex sets whose defining constraints may be nonlinear. The algorithm generates linear programs whose solutions minimize the convex envelope of the...
详细信息
A method is described for globally minimizing concave functions over convex sets whose defining constraints may be nonlinear. The algorithm generates linear programs whose solutions minimize the convex envelope of the original function over successively tighter polytopes enclosing the feasible region. The algorithm does not involve cuts of the feasible region, requires only simplex pivot operations and univariate search computations to be performed, allows the objective function to be lower semicontinuous and nonseparable, and is guaranteed to converge to the global solution. Computational aspects of the algorithm are discussed.
暂无评论