A global optimization algorithm is proposed in order to locate the global minimum of the special reverse convex programming which is both nonconvex and nonlinear. Three new strategies are adopted in this paper. Some o...
详细信息
A global optimization algorithm is proposed in order to locate the global minimum of the special reverse convex programming which is both nonconvex and nonlinear. Three new strategies are adopted in this paper. Some of them can be used to solve general reverse convex programming. Global solution locating is to identify the location of the Solution. The linear relaxation method is used to obtain the lower bound of the optimum of the primal programming, and in this paper the relaxed programming is a kind of linear programming, which can be solved by standard simplex algorithm. The final strategy is upper bound updating method, which provides a better upper bound than the standard branch and bound method. According to the strategies, a global optimization algorithm is derived based on branch and bound theory. It is proved that the algorithm possesses global convergence. Finally, a numerical experiment is given to illustrate the feasibility and the smaller computational effort. (C) 2007 Elsevier Ltd. All rights reserved.
In this paper, an efficient algorithm is proposed for globally solving special reverse convex programming problems with more than one reverseconvex constraints. The proposed algorithm provides a nonisolated global op...
详细信息
In this paper, an efficient algorithm is proposed for globally solving special reverse convex programming problems with more than one reverseconvex constraints. The proposed algorithm provides a nonisolated global optimal solution which is also stable under small perturbations of the constraints, and it turns out that such an optimal solution is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and the numerical experiment is given to illustrate the feasibility of the presented algorithm. (C) 2008 Elsevier B.V. All rights reserved.
It is well known that each convex function f:Rn?R is supremally generated by affine functions. More precisely, each convex function f:Rn?R is the upper envelope of its affine minorants. In this paper, we propose an al...
详细信息
It is well known that each convex function f:Rn?R is supremally generated by affine functions. More precisely, each convex function f:Rn?R is the upper envelope of its affine minorants. In this paper, we propose an algorithm for solving reverse convex programming problems by using such a representation together with a generalized cutting-plane method. Indeed, by applying this representation, we solve a sequence of problems with a smaller feasible set, in which the reverseconvex constraint is replaced by a still reverseconvex but polyhedral constraint. Moreover, we prove that the proposed algorithm converges, under suitable assumptions, to an optimal solution of the original problem. This algorithm is coded in MATLAB language and is evaluated by some numerical examples.
The cognitive beamforming problems are naturally formulated as indefinite quadratic (nonconvex) optimization programs. The typical methods for solving such optimization problems are to transform them into convex semi-...
详细信息
ISBN:
(纸本)9781424470587
The cognitive beamforming problems are naturally formulated as indefinite quadratic (nonconvex) optimization programs. The typical methods for solving such optimization problems are to transform them into convex semi-definite programs (SDPs) with additional rank-one (nonconvex and discontinuous) constraints. The rank-one constraints are then dropped to obtain solvable SDP relaxed problems and randomization techniques are employed for seeking the feasible solutions to the original nonconvex optimization problems. In many practical cases, these approaches fail to deliver satisfactory solutions, i.e., their solutions are very far from the optimal ones. In contrast, in this paper the rank-one constraints are equivalently expressed as reverseconvex constraints and are incorporated into the optimization problems. Then, we propose an efficient iterative algorithm for solving the nonsmooth reverseconvex optimization problems. Our simulations show that our proposed approach yields nearly global optimal solutions with much less computational load as compared to the conventional one.
This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas (1974, 1979) to hold for facial disjunctive programs. Sequential convexifiability means that the c...
详细信息
This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas (1974, 1979) to hold for facial disjunctive programs. Sequential convexifiability means that the convex hull of a nonconvex set defined by a collection of constraints can be generated by imposing the constraints one by one, sequentially, and generating each time the convex hull of the resulting set. Here we extend the class of problems considered to disjunctive programs with infinitely many terms, also known as reverseconvex programs, and give necessary and sufficient conditions for the solution sets of such problems to be sequentially convexifiable. We point out important classes of problems in addition to facial disjunctive programs (for instance, reverseconvex programs with equations only) for which the conditions are always satisfied. Finally, we give examples of disjunctive programs for which the conditions are violated, and so the procedure breaks down.
A kind of general convexification and concavification methods is proposed for solving some classes of global optimization problems with certain monotone properties. It is shown that these minimization problems can be ...
详细信息
A kind of general convexification and concavification methods is proposed for solving some classes of global optimization problems with certain monotone properties. It is shown that these minimization problems can be transformed into equivalent concave minimization problem or reverse convex programming problem or canonical D.C. programming problem by using the proposed convexification and concavification schemes. The existing algorithms then can be used to find the global solutions of the transformed problems.
A cutting plane method, using the idea of Tuy cuts, has been suggested in earlier papers as a possible means of solving reverseconvex programs. However, the method is fraught with theoretical and numerical difficulti...
详细信息
A cutting plane method, using the idea of Tuy cuts, has been suggested in earlier papers as a possible means of solving reverseconvex programs. However, the method is fraught with theoretical and numerical difficulties. Stringent sufficient conditions for convergence in n dimensions are given. However, examples of nonconvergence are given and reasons for this nonconvergence are developed. A result of the discussion is a convergent algorithm which combines the idea of the cutting plane method with vertex enumeration procedures in order to numerically improve upon the edge search procedure of Hillestad.
The discrete moment problem is a foundational problem in distribution-free robust optimization, where the goal is to find a worst-case distribution that satisfies a given set of moments. This paper studies the discret...
详细信息
The discrete moment problem is a foundational problem in distribution-free robust optimization, where the goal is to find a worst-case distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional shape constraints that guarantee the worst-case distribution is either log-concave (LC), has an increasing failure rate (IFR), or increasing generalized failure rate (IGFR). These classes of shape constraints have not previously been studied in the literature, in part due to their inherent nonconvexities. Nonetheless, these classes are useful in practice, with applications in revenue management, reliability, and inventory control. We characterize the structure of optimal extreme point distributions under these constraints. We show, for example, that an optimal extreme point solution to a moment problem with m moments and LC shape constraints is piecewise geometric with at most m pieces. This optimality structure allows us to design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. We also leverage this structure to study a robust newsvendor problem with shape constraints and compute optimal solutions.
Optical wireless communication is a promising technology for underwater broadband access networks, which are particularly important for high-resolution environmental monitoring applications. This paper focuses on a de...
详细信息
Optical wireless communication is a promising technology for underwater broadband access networks, which are particularly important for high-resolution environmental monitoring applications. This paper focuses on a deep-sea monitoring system, where an underwater optical wireless network is deployed on the seafloor. We model such an optical wireless network as a general queueing network and formulate an optimal relay placement problem, whose objective is to maximize the stability region of the whole system, i.e., the supremum of the traffic volume that the network is capable of accommodating. The formulated optimization problem is further shown to be non-convex, so that its global optimization is non-trivial. In this paper, we develop a global optimization method for this problem and we provide an efficient algorithm to compute an optimal solution. Through numerical evaluations, we show that a significant performance gain can be obtained by using the derived optimal solution.
A method of constructing test problems with known global solution for a class of reverseconvex programs or linear programs with an additional reverseconvex constraint is presented. The initial polyhedron is assumed ...
详细信息
A method of constructing test problems with known global solution for a class of reverseconvex programs or linear programs with an additional reverseconvex constraint is presented. The initial polyhedron is assumed to be a hypercube. The method then systematically generates cuts that slice the cube in such a way that a prespecified global solution on its edge remains intact. The proposed method does not require the solution of linear programs or systems of linear equations as is often required by existing techniques.
暂无评论