In this paper, global optimization of linear programs with an additional reverse convex constraint is considered. This type of problem arises in many applications such as engineering design, communications networks, a...
详细信息
In this paper, global optimization of linear programs with an additional reverse convex constraint is considered. This type of problem arises in many applications such as engineering design, communications networks, and many management decision support systems with budget constraints and economies-of-scale. The main difficulty with this type of problem is the presence of the complicated reverse convex constraint., which destroys the convexity and possibly the connectivity of the feasible region, putting the problem in a class of difficult and mathematically intractable problems. We present a cutting plane method within the scope of a branch-and-bound scheme that efficiently partitions the polytope associated with the linear constraints and systematically fathoms these portions through the use of the bounds. An upper bound and a lower bound for the optimal value is found and improved at each iteration. The algorithm terminates when all the generated subdivisions have been fathomed.
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.
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.
It has recently been established by Wang and Xia that local minimizers of perimeter within a ball subject to a volume constraint must be spherical caps or planes through the origin. This verifies a conjecture of the a...
详细信息
It has recently been established by Wang and Xia that local minimizers of perimeter within a ball subject to a volume constraint must be spherical caps or planes through the origin. This verifies a conjecture of the authors and is in contrast to the situation of area-minimizing surfaces with prescribed boundary where singularities can be present in high dimensions. This result lends support to the more general conjecture that volume-constrained minimizers in arbitrary convex sets may enjoy better regularity properties than their boundary-prescribed cousins. Here, we show the importance of the convexity condition by exhibiting a simple example, given by the Simons cone, of a singular volume-constrained locally area-minimizing surface within a nonconvex domain that is arbitrarily close to the unit ball.
We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An i...
详细信息
We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An important class of algorithms for the linearly constrained minimization of nonconvex cost functions utilize the branch and bound approach, using convex underestimating cost functions to compute the lower *** suggest instead the use of the surrogate dual problem to bound subproblems. We show that the success of the surrogate dual in fathoming subproblems in a branch and bound algorithm may be determined without directly solving the surrogate dual itself, but that a simple test of the feasibility of a certain linear system of inequalities will suffice. This test is interpreted geometrically and used to characterize the extreme points and extreme rays of the optimal value function's level sets.
As is well known, a saddle point for the Lagrangian function, if it exists, provides a solution to a convex programming problem; then, the values of the optimal primal and dual objective functions are equal. However, ...
详细信息
As is well known, a saddle point for the Lagrangian function, if it exists, provides a solution to a convex programming problem; then, the values of the optimal primal and dual objective functions are equal. However, these results are not valid for nonconvex problems. In this paper, several results are presented on the theory of the generalized Lagrangian function, extended from the classical Lagrangian and the generalized duality program. Theoretical results for convex problems also hold for nonconvex problems by extension of the Lagrangian function. The concept of supporting hypersurfaces is useful to add a geometric interpretation to computational algorithms. This provides a basis to develop a new algorithm.
Problems that can be reduced to polynomial and parametrized linear matrix inequalities are considered. Such problems arise, for example, in control theory. Well-known methods for their solution based on a search for n...
详细信息
Problems that can be reduced to polynomial and parametrized linear matrix inequalities are considered. Such problems arise, for example, in control theory. Well-known methods for their solution based on a search for nonnegative polynomials scale poorly and require significant computational resources. An approach based on systematic transformations of the problem under study to a form that can be addressed with simpler methods is presented.
Optimization problems that involve products of convex functions in the objective function or in the constraints arise in a variety of applications. These problems are difficult global optimization problems. During the...
详细信息
Optimization problems that involve products of convex functions in the objective function or in the constraints arise in a variety of applications. These problems are difficult global optimization problems. During the past 15 years, however, a number of practical algorithms have been proposed for globally solving these types of problems. In this article, we present and validate a branch-and-reduce algorithm for finding a global optimal solution to a convex program that contains an additional constraint on the product of several convex functions. To globally solve this problem, the algorithm instead globally solves an equivalent master problem. At any stage of the algorithm, a disconnected set consisting of a union of simplices is constructed. This set is guaranteed to contain a portion of the boundary of the feasible region of the master problem where a global optimal solution lies. The algorithm uses a new branch-and-reduce scheme to iteratively reduce the sizes of these sets until a global optimal solution is found. Several potential computational advantages of the algorithm are explained, and a numerical example is solved.
This paper proposes prediction-and-sensing-based spectrum sharing, a new spectrum-sharing model for cognitive radio networks, with a time structure for each resource block divided into a spectrum prediction-and-sensin...
详细信息
This paper proposes prediction-and-sensing-based spectrum sharing, a new spectrum-sharing model for cognitive radio networks, with a time structure for each resource block divided into a spectrum prediction-and-sensing phase and a data transmission phase. Cooperative spectrum prediction is incorporated as a sub-phase of spectrum sensing in the first phase. We investigate a joint design of transmit beamforming at the secondary base station (BS) and sensing time. The primary design goal is to maximize the sum rate of all secondary users (SUs) subject to the minimum rate requirement for all SUs, the transmit power constraint at the secondary BS, and the interference power constraints at all primary users. The original problem is difficult to solve since it is highly nonconvex. We first convert the problem into a more tractable form, then arrive at a convex program based on an inner approximation framework, and finally propose a new algorithm to successively solve this convex program. We prove that the proposed algorithm iteratively improves the objective while guaranteeing convergence at least to local optima. Simulation results demonstrate that the proposed algorithm reaches a stationary point after only a few iterations with a substantial performance improvement over existing approaches.
We consider the Boltzmann equation in a general non-convex domain with the diffuse boundary condition. We establish optimal BV estimates for such solutions. Our method consists of a new W (1,1)-trace estimate for the ...
详细信息
We consider the Boltzmann equation in a general non-convex domain with the diffuse boundary condition. We establish optimal BV estimates for such solutions. Our method consists of a new W (1,1)-trace estimate for the diffuse boundary condition and a delicate construction of an -tubular neighborhood of the singular set.
暂无评论