The tremendous performance gain of heterogeneous networks(Het Nets) is at the cost of complicated resource allocation. Considering information security, the resource allocation for Het Nets becomes much more challengi...The tremendous performance gain of heterogeneous networks(Het Nets) is at the cost of complicated resource allocation. Considering information security, the resource allocation for Het Nets becomes much more challenging and this is the focus of this paper. In this paper, the eavesdropper is hidden from the macro base stations. To relax the unpractical assumption on the channel state information on eavesdropper, a localization based algorithm is first given. Then a joint resource allocation algorithm is proposed in our work, which simultaneously considers physical layer security, cross-tier interference and joint optimization of power and subcarriers under fairness requirements. It is revealed in our work that the considered optimization problem can be efficiently solved relying on convex optimization theory and the Lagrangian dual decomposition method is exploited to solve the considered problem effectively. Moreover, in each iteration the closed-form optimal resource allocation solutions can be obtained based on the Karush-Kuhn-Tucker(KKT) conditions. Finally, the simulation results are given to show the performance advantages of the proposed algorithm.展开更多
In this paper we consider domain decomposition methods with polynomial Lagrangian multipliers to two-dimentional elliptic problems, and construct a kind of simple preconditioners for the corresponding interface equat...In this paper we consider domain decomposition methods with polynomial Lagrangian multipliers to two-dimentional elliptic problems, and construct a kind of simple preconditioners for the corresponding interface equation. It will be shown that condition number of the resulting preconditioned interface matrix is almost optimal (namelys it has only logarithmic growth with dimension of the local interface space).展开更多
With time-based competition and rapid technology advancements, effective manufacturing scheduling and supply chain coordination are critical to quickly respond to changing market conditions. These problems, however, a...With time-based competition and rapid technology advancements, effective manufacturing scheduling and supply chain coordination are critical to quickly respond to changing market conditions. These problems, however, are difficult in view of inherent complexity and various uncertainties involved. Based on a series of results by the authors, decomposition and coordination by using Lagrangian relaxation is identified in this paper as an effective way to control complexity and uncertainty. A manufacturing scheduling problem is first formulated within the job shop context with uncertain order arrivals, processing times, due dates, and part priorities as a separable optimization problem. A solution methodology that combines Lagrangian relaxation, stochastic dynamic programming, and heuristics is developed. Method improvements to effectively solve large problems are also highlighted. To extend manufacturing scheduling within a factory to coordinate autonomic members across chains of suppliers, a decentralized supply chain model is established in the second half of this paper. By relaxing cross-member constraints, the model is decomposed into member-wise subproblems, and a nested optimization structure is developed based on the job shop scheduling results. Coordination is performed through the iterative updating of cross-member prices without accessing other members' private information or intruding their decision-making authorities, either with or without a coordinator. Two examples are presented to demonstrate the effectiveness of the method. Future prospects to overcome problem inseparability and improve computing efficiency are then discussed.展开更多
Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regressio...Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regression.This class of problems can be modeled as mixed-integer programs with special structures and are in general NP-hard.In the past few years,based on new reformulations,approximation and relaxation techniques,promising exact and approximate methods have been developed.We survey in this paper these recent developments for this challenging class of mathematical programming problems.展开更多
uv-decomposition method for solving a mathematical program with equilibrium constraints （MPEC） problem with linear complementarity constraints is presented. The problem is first converted into a nonlinear programmin...uv-decomposition method for solving a mathematical program with equilibrium constraints （MPEC） problem with linear complementarity constraints is presented. The problem is first converted into a nonlinear programming one. The structure of subdifferential a corresponding penalty function and results of its uv-decomposition are given. A conceptual algorithm for solving this problem with a superUnear convergence rate is then constructed in terms of the obtained results.展开更多
To address large scale industrial processes,a novel Lagrangian scheme is proposed to decompose a refinery scheduling problem with operational transitions in mode switching into a production subproblem and a blending a...To address large scale industrial processes,a novel Lagrangian scheme is proposed to decompose a refinery scheduling problem with operational transitions in mode switching into a production subproblem and a blending and delivery subproblem.To accelerate the convergence of Lagrange multipliers,some auxiliary constraints are added in the blending and delivery subproblem.A speed-up scheme is presented to increase the efficiency for solving the production subproblem.An initialization scheme of Lagrange multipliers and a heuristic algorithm to find feasible solutions are designed.Computational results on three cases with different lengths of time horizons and different numbers of orders show that the proposed Lagrangian scheme is effective and efficient.展开更多
This paper investigates the relay selection and resource allocation problem in multiuser orthogonal frequency division multiplexing （OFDM） based cooperative cellular networks, in which user nodes could relay informa...This paper investigates the relay selection and resource allocation problem in multiuser orthogonal frequency division multiplexing （OFDM） based cooperative cellular networks, in which user nodes could relay information for each other using the decode-and-forward （DF） protocol to achieve spatial diversity gain. Specifically, the paper proposes an optimal joint relay selection and resource allocation （0RSRA） algorithm whose objective is to maximize system total achievable data rate with the constraints of each user＇ s individual quality of service （QoS） requirement and transmission power. Due to being a mixed binary integer programming （MBIP） problem, a novel two-level Lagrangian dual-primal decomposition and subgradient projection approach is proposed to not only select the appropriate cooperative relay nodes, but also allocate subcarries and power optimally. Simulation re- suits demonstrate that our proposed scheme can efficiently enhance overall system data rate and guarantee each user＇ s QoS requirement. Meanwhile, the fairness among users can be improved dramatically.展开更多
The manuscript presents an augmented Lagrangian—fast projected gradient method (ALFPGM) with an improved scheme of working set selection, pWSS, a decomposition based algorithm for training support vector classificati...The manuscript presents an augmented Lagrangian—fast projected gradient method (ALFPGM) with an improved scheme of working set selection, pWSS, a decomposition based algorithm for training support vector classification machines (SVM). The manuscript describes the ALFPGM algorithm, provides numerical results for training SVM on large data sets, and compares the training times of ALFPGM and Sequential Minimal Minimization algorithms (SMO) from Scikit-learn library. The numerical results demonstrate that ALFPGM with the improved working selection scheme is capable of training SVM with tens of thousands of training examples in a fraction of the training time of some widely adopted SVM tools.展开更多
Single Stage Capacitated Warehouse Location Problem (SSCWLP) has been attempted by few researchers in the past. These are Geoffrion and Graves [1], Sharma [2], Sharma [3] and Sharma and Berry [4]. In this paper we giv...Single Stage Capacitated Warehouse Location Problem (SSCWLP) has been attempted by few researchers in the past. These are Geoffrion and Graves [1], Sharma [2], Sharma [3] and Sharma and Berry [4]. In this paper we give a “vertical decomposition” approach to solve SSCWLP that uses Lagrangian relaxation. This way SSCWLP is broken into two versions of capacitated plant location problem (the CPLP_L and CPLP_R) by relaxing the flow balance constraints. For CPLP_R, we use well known Lagrangian relaxations given in literature (Christofides and Beasley [5] and Nauss [6]);and adopt them suitably for solving CPLP_L. We show theoretically in this paper that SSCWLP can be more efficiently solved by techniques of vertical decomposition developed in this paper than the method available in literature (Sharma and Berry [4]). Encouraging computational study is reported in this paper.展开更多
In this paper, the discrete mean-variance model is considered for portfolio selection under concave transaction costs. By using the Cholesky decomposition technique, the convariance matrix to obtain a separable mixed ...In this paper, the discrete mean-variance model is considered for portfolio selection under concave transaction costs. By using the Cholesky decomposition technique, the convariance matrix to obtain a separable mixed integer nonlinear optimization problem is decomposed. A brand-and-bound algorithm based on Lagrangian relaxation is then proposed. Computational results are reported for test problems with the data randomly generated and those from the US stock market.展开更多
A vu-decomposition method for solving a second-order cone problem is presented in this paper. It is first transformed into a nonlinear programming problem. Then, the structure of the Clarke subdifferential correspondi...A vu-decomposition method for solving a second-order cone problem is presented in this paper. It is first transformed into a nonlinear programming problem. Then, the structure of the Clarke subdifferential corresponding to the penalty function and some results of itsvu-decomposition are given. Under a certain condition, a twice continuously differentiable trajectory is computed to produce a second-order expansion of the objective function. A conceptual algorithm for solving this problem with a superlinear convergence rate is given.展开更多
基金supported by the National Natural Science Foundation of China under Grant No.61371075the 863 project SS2015AA011306
文摘The tremendous performance gain of heterogeneous networks(Het Nets) is at the cost of complicated resource allocation. Considering information security, the resource allocation for Het Nets becomes much more challenging and this is the focus of this paper. In this paper, the eavesdropper is hidden from the macro base stations. To relax the unpractical assumption on the channel state information on eavesdropper, a localization based algorithm is first given. Then a joint resource allocation algorithm is proposed in our work, which simultaneously considers physical layer security, cross-tier interference and joint optimization of power and subcarriers under fairness requirements. It is revealed in our work that the considered optimization problem can be efficiently solved relying on convex optimization theory and the Lagrangian dual decomposition method is exploited to solve the considered problem effectively. Moreover, in each iteration the closed-form optimal resource allocation solutions can be obtained based on the Karush-Kuhn-Tucker(KKT) conditions. Finally, the simulation results are given to show the performance advantages of the proposed algorithm.
基金This work was supported partly by the Natural Science Foundation of China (No. 19801030).
文摘In this paper we consider domain decomposition methods with polynomial Lagrangian multipliers to two-dimentional elliptic problems, and construct a kind of simple preconditioners for the corresponding interface equation. It will be shown that condition number of the resulting preconditioned interface matrix is almost optimal (namelys it has only logarithmic growth with dimension of the local interface space).
基金This work was supported in part by the National Science Foundation under DMI-0223443by a contract from the United Technologies Research Center,USA.
文摘With time-based competition and rapid technology advancements, effective manufacturing scheduling and supply chain coordination are critical to quickly respond to changing market conditions. These problems, however, are difficult in view of inherent complexity and various uncertainties involved. Based on a series of results by the authors, decomposition and coordination by using Lagrangian relaxation is identified in this paper as an effective way to control complexity and uncertainty. A manufacturing scheduling problem is first formulated within the job shop context with uncertain order arrivals, processing times, due dates, and part priorities as a separable optimization problem. A solution methodology that combines Lagrangian relaxation, stochastic dynamic programming, and heuristics is developed. Method improvements to effectively solve large problems are also highlighted. To extend manufacturing scheduling within a factory to coordinate autonomic members across chains of suppliers, a decentralized supply chain model is established in the second half of this paper. By relaxing cross-member constraints, the model is decomposed into member-wise subproblems, and a nested optimization structure is developed based on the job shop scheduling results. Coordination is performed through the iterative updating of cross-member prices without accessing other members' private information or intruding their decision-making authorities, either with or without a coordinator. Two examples are presented to demonstrate the effectiveness of the method. Future prospects to overcome problem inseparability and improve computing efficiency are then discussed.
基金supported by the National Natural Science Foundation of China grants(Nos.11101092,10971034)the Joint National Natural Science Foundation of China/Research Grants Council of Hong Kong grant(No.71061160506)the Research Grants Council of Hong Kong grants(Nos.CUHK414808 and CUHK414610).
文摘Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regression.This class of problems can be modeled as mixed-integer programs with special structures and are in general NP-hard.In the past few years,based on new reformulations,approximation and relaxation techniques,promising exact and approximate methods have been developed.We survey in this paper these recent developments for this challenging class of mathematical programming problems.
基金Project supported by the National Natural Science Foundation of China(Nos.10372063,10771026 and 10471015)
文摘uv-decomposition method for solving a mathematical program with equilibrium constraints （MPEC） problem with linear complementarity constraints is presented. The problem is first converted into a nonlinear programming one. The structure of subdifferential a corresponding penalty function and results of its uv-decomposition are given. A conceptual algorithm for solving this problem with a superUnear convergence rate is then constructed in terms of the obtained results.
基金Supported by the National Natural Science Foundation of China(61273039,21276137)the National Science Fund for Distinguished Young Scholars of China(61525304)
文摘To address large scale industrial processes,a novel Lagrangian scheme is proposed to decompose a refinery scheduling problem with operational transitions in mode switching into a production subproblem and a blending and delivery subproblem.To accelerate the convergence of Lagrange multipliers,some auxiliary constraints are added in the blending and delivery subproblem.A speed-up scheme is presented to increase the efficiency for solving the production subproblem.An initialization scheme of Lagrange multipliers and a heuristic algorithm to find feasible solutions are designed.Computational results on three cases with different lengths of time horizons and different numbers of orders show that the proposed Lagrangian scheme is effective and efficient.
基金Supported by the National Natural Science Foundation for Distinguished Young Scholar （ No. 61001115 ） and the Beijing Municipal Natural Science Foundation （ No. 4102044）.
文摘This paper investigates the relay selection and resource allocation problem in multiuser orthogonal frequency division multiplexing （OFDM） based cooperative cellular networks, in which user nodes could relay information for each other using the decode-and-forward （DF） protocol to achieve spatial diversity gain. Specifically, the paper proposes an optimal joint relay selection and resource allocation （0RSRA） algorithm whose objective is to maximize system total achievable data rate with the constraints of each user＇ s individual quality of service （QoS） requirement and transmission power. Due to being a mixed binary integer programming （MBIP） problem, a novel two-level Lagrangian dual-primal decomposition and subgradient projection approach is proposed to not only select the appropriate cooperative relay nodes, but also allocate subcarries and power optimally. Simulation re- suits demonstrate that our proposed scheme can efficiently enhance overall system data rate and guarantee each user＇ s QoS requirement. Meanwhile, the fairness among users can be improved dramatically.
文摘The manuscript presents an augmented Lagrangian—fast projected gradient method (ALFPGM) with an improved scheme of working set selection, pWSS, a decomposition based algorithm for training support vector classification machines (SVM). The manuscript describes the ALFPGM algorithm, provides numerical results for training SVM on large data sets, and compares the training times of ALFPGM and Sequential Minimal Minimization algorithms (SMO) from Scikit-learn library. The numerical results demonstrate that ALFPGM with the improved working selection scheme is capable of training SVM with tens of thousands of training examples in a fraction of the training time of some widely adopted SVM tools.
文摘Single Stage Capacitated Warehouse Location Problem (SSCWLP) has been attempted by few researchers in the past. These are Geoffrion and Graves [1], Sharma [2], Sharma [3] and Sharma and Berry [4]. In this paper we give a “vertical decomposition” approach to solve SSCWLP that uses Lagrangian relaxation. This way SSCWLP is broken into two versions of capacitated plant location problem (the CPLP_L and CPLP_R) by relaxing the flow balance constraints. For CPLP_R, we use well known Lagrangian relaxations given in literature (Christofides and Beasley [5] and Nauss [6]);and adopt them suitably for solving CPLP_L. We show theoretically in this paper that SSCWLP can be more efficiently solved by techniques of vertical decomposition developed in this paper than the method available in literature (Sharma and Berry [4]). Encouraging computational study is reported in this paper.
基金supported by the National Natural Science Foundation of China (Grant Nos.70671064,70518001)
文摘In this paper, the discrete mean-variance model is considered for portfolio selection under concave transaction costs. By using the Cholesky decomposition technique, the convariance matrix to obtain a separable mixed integer nonlinear optimization problem is decomposed. A brand-and-bound algorithm based on Lagrangian relaxation is then proposed. Computational results are reported for test problems with the data randomly generated and those from the US stock market.
基金Project supported by the National Natural Science Foundation of China (No. 10771026)the Foundation of Dalian University of Technology (Nos. MXDUT73008 and MXDUT98009)
文摘A vu-decomposition method for solving a second-order cone problem is presented in this paper. It is first transformed into a nonlinear programming problem. Then, the structure of the Clarke subdifferential corresponding to the penalty function and some results of itsvu-decomposition are given. Under a certain condition, a twice continuously differentiable trajectory is computed to produce a second-order expansion of the objective function. A conceptual algorithm for solving this problem with a superlinear convergence rate is given.
基金Supported by the National Natural Sciences Foundation of China (70432001) andGraduated Student Innovation Foundation of Fudan University (CQH1019008)
