We present a branch and cut algorithm that yields in finite time, a globally epsilon-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming probl...
详细信息
We present a branch and cut algorithm that yields in finite time, a globally epsilon-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node df the tree is flexible enough to be used at other nodes. Computational results are reported that include standard test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality.
A strong convergence theorem is proven to hold for the general algorithm of the branch and bound type for solving nonconvex programming problems given in [1].
A strong convergence theorem is proven to hold for the general algorithm of the branch and bound type for solving nonconvex programming problems given in [1].
In this paper, the principal-agent bilevel programming problem with integral operator is considered, in which the upper-level object is the agent that maximizes its expected utility with respect to an agreed compensat...
详细信息
In this paper, the principal-agent bilevel programming problem with integral operator is considered, in which the upper-level object is the agent that maximizes its expected utility with respect to an agreed compensation contract. The constraints are the principal's participation and the agent's incentive compatibility. The latter is a lower-level optimization problem with respect to its private action. To solve an equivalent single-level nonconvex programming problem with integral operator, a modified homotopy method for solving the Karush-Kuhn-Tucker system is proposed. This method requires only an interior point and, not necessarily, a feasible initial approximation for the constraint shifting set. Global convergence is proven under some mild conditions. Numerical experiments were performed by our homotopy method as well as by fmincon in Matlab, LOQO and MINOS. The experiments showed that: designing a piecewise linear contract is much better than designing a piecewise constant contract and only needs to solve a much lower-dimensional optimization problem and hence needs much less computation time;the optimal value of the principal-agent model with designing piecewise linear contract tends to a limitation, while the discrete segments gradually increase;and finally, the proposed modified homotopy method is feasible and effective.
Full-duplex (ED) systems have emerged as an essential enabling technology to further increase the data rate of wireless communication systems. The key idea of ED is to serve multiple users over the same bandwidth with...
详细信息
Full-duplex (ED) systems have emerged as an essential enabling technology to further increase the data rate of wireless communication systems. The key idea of ED is to serve multiple users over the same bandwidth with a base station (BS) that can simultaneously transmit and receive the signals. The most challenging issue in designing an ED system is to address both the harmful effects of residual self-interference caused by the transmit-to-receive antennas at the BS as well as the co-channel interference from an uplink user (ULU) to a downlink user (DLU). An efficient solution to these problems is to assign the ULUs/DLUs in different groups/slots, with each user served in multiple groups. Hence, this paper studies the joint design of transmit beamformers, ULUs/DLUs group assignment, and time allocation for each group. The specific aim is to maximize the sum rate under the ULU/DLU minimum throughput constraints. The utility function of interest is a difficult nonconcave problem, and the involved constraints are also nonconvex, and so this is a computationally troublesome problem. To solve this optimization problem, we propose a new path-following algorithm for computational solutions to arrive at least the local optima. Each iteration involves only a simple convex quadratic program. We prove that the proposed algorithm iteratively improves the objective while guaranteeing convergence. Simulation results confirm the fast convergence of the proposed algorithm with substantial performance improvements over existing approaches.
Based on a review of existing algorithms, a general branch-and-bound concept in global optimization is presented. A sufficient and necessary convergence condition is established, and a broad class of realizations is d...
详细信息
Based on a review of existing algorithms, a general branch-and-bound concept in global optimization is presented. A sufficient and necessary convergence condition is established, and a broad class of realizations is derived that include existing and several new approaches for concave minimization problems.
This technical note develops a neural dynamical approach to nonlinear programming (NP) problems, whose equilibrium points coincide with Karush-Kuhn-Tucker points of the NP problem. A rigorous analysis on the global co...
详细信息
This technical note develops a neural dynamical approach to nonlinear programming (NP) problems, whose equilibrium points coincide with Karush-Kuhn-Tucker points of the NP problem. A rigorous analysis on the global convergence and the convergence rate of the proposed neural dynamical approach is carried out under the condition that the associated Lagrangian function is convex. Analysis results show that the proposed neural dynamical approach can solve general convex programming problems and a class of nonconvex programming problems. Two nonconvex programming examples are provided to demonstrate the performance of the developed neural dynamical approach.
We consider the problem of finding a global extremum for a nonconvex function by constructing another smoothed function, which has a better “behavior” than the original one. Then, operating only with the smoothed fu...
详细信息
We consider the problem of finding a global extremum for a nonconvex function by constructing another smoothed function, which has a better “behavior” than the original one. Then, operating only with the smoothed function, we find the global extremum for the original function.
This paper presents a novel recurrent neural network for solving nonlinear optimization problems with inequality constraints. Under the condition that the Hessian matrix of the associated Lagrangian function is positi...
详细信息
This paper presents a novel recurrent neural network for solving nonlinear optimization problems with inequality constraints. Under the condition that the Hessian matrix of the associated Lagrangian function is positive semidefinite, it is shown that the proposed neural network is stable at a Karush-Kuhn-Tucker point in the sense of Lyapunov and its output trajectory is globally convergent to a minimum solution. Compared with variety of the existing projection neural networks, including their extensions and modification, for solving such nonlinearly constrained optimization problems, it is shown that the proposed neural network can solve constrained convex optimization problems and a class of constrained nonconvex optimization problems and there is no restriction on the initial point. Simulation results show the effectiveness of the proposed neural network in solving nonlinearly constrained optimization problems.
In this paper a bisecting search algorithm is developed for solving the problem (P) of optimizing a linear function over the set of weakly-efficient solutions of a multiple objective linear program. We show that probl...
详细信息
In this paper a bisecting search algorithm is developed for solving the problem (P) of optimizing a linear function over the set of weakly-efficient solutions of a multiple objective linear program. We show that problem (P) can arise in a variety of practical situations. The algorithm for solving problem (P) is guaranteed to find an optimal or approximately-optimal solution for the problem in a finite number of steps. Using a Fortran computer code called Conmin as an aid, we have solved ten test problems using our proposed algorithm. This preliminary computational experience seems to indicate that the algorithm is quite practical for relatively small problems.
The variational inequality problem in Euclidian space is formulated as a nonconvex, nondifferentiable optimization problem. We show that any stationary point is optimal, and we propose a solution algorithm that decrea...
详细信息
The variational inequality problem in Euclidian space is formulated as a nonconvex, nondifferentiable optimization problem. We show that any stationary point is optimal, and we propose a solution algorithm that decreases the nondifferential objective monotonically. Application to the asymmetric traffic assignment problem is considered.
暂无评论