检索结果-内蒙古大学图书馆

SOLVING QUADRATIC programming BY CUTTING PLANES

SIAM JOURNAL ON OPTIMIZATION 2019年第2期29卷 1076-1105页

作者： Bonami, Pierre Lodi, Andrea Schweiger, Jonas Tramontani, Andrea IBM Spain CPLEX Optimizat Madrid Spain Polytech Montreal Canada Excellence Res Chair CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Zuse Inst Berlin Berlin Germany

We propose new cutting planes for strengthening the linear relaxations that appear in the solution of nonconvex quadratic problems with linear constraints. By a famous result of Motzkin and Straus, these problems are connected to the clique number of a graph. Our cuts are derived in the context of a spatial branch-and-bound algorithm where linearization variables are introduced to represent products. Their validity is based on the result of Motzkin and Straus, in that it depends on the clique number of certain graphs. For convenience, we derive our cuts for the special case of the so-called standard quadratic programs, where the only (linear) constraint imposes that variables must belong to a simplex. We specifically consider cuts that correspond to carefully constructed complete bipartite graphs. We study the relation between these cuts and the classical ones obtained at the first level of the reformulation-linearization technique. By studying this relation, we derive a new type of valid inequalities that generalizes both types of cuts, and thus leading to a large family of cutting planes to strengthen the linear relaxation. We present extensive computational results using the different cutting planes we propose within the spatial branch and bound implemented by the commercial solver CPLEX. We show that our cuts allow us to obtain a significantly better bound than reformulation-linearization cuts and reduce computing times for global optimality. Finally, we formally establish the scaling necessary for using the proposed cuts to solve nonconvex quadratic problems with linear constraints, e.g., quadratic knapsack problems.

关键词： nonconvex programming standard quadratic programming global optimization cutting planes reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

CONSTRUCTION OF TEST PROBLEMS FOR A CLASS OF REVERSE CONVEX-PROGRAMS

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1994年第2期81卷 343-354页

作者： MOSHIRVAZIRI, K UNIV CALIF LOS ANGELES LOS ANGELES CA 90024 USA

A method of constructing test problems with known global solution for a class of reverse convex programs or linear programs with an additional reverse convex 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.

关键词： REVERSE CONVEX programming nonconvex programming NONLINEAR programming LINEAR programming TEST PROBLEMS GLOBAL OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

A DISJUNCTIVE CUTTING PLANE ALGORITHM FOR BILINEAR programming

引用

SIAM JOURNAL ON OPTIMIZATION 2024年第4期34卷 3286-3313页

作者： Rahimian, Hamed Mehrotra, Sanjay Clemson Univ Dept Ind Engn Clemson SC 29634 USA Northwestern Univ Dept Ind Engn & Management Sci Evanston IL 60208 USA

In this paper, we present and analyze a finitely convergent disjunctive cutting plane algorithm to obtain an \epsilon -optimal solution or detect the infeasibility of a general nonconvex continuous bilinear program. While the cutting planes are obtained like Saxena, Bonami, and Lee [Math. Prog., the algorithm that guarantees finite convergence is exploring near-optimal extreme point solutions to a current relaxation at each iteration. In this sense, the presented algorithm and its analysis extend the work Owen and Mehrotra [Math. Prog., 89 (2001), pp. 437--448] for solving mixed-integer linear programs to the general bilinear programs.

关键词： rogramming nonconvex programming disjunctive programming global optimization cutting planes

来源：评论

学校读者我要写书评

暂无评论

Cooperative MIMO relay beamforming in overloaded DS/CDMA multicast networks

引用

IET COMMUNICATIONS 2017年第3期11卷 344-354页

作者： Mehrizi, Sajad Mahboobi, Behrad Islamic Azad Univ Sci & Res Branch Dept Engn Tehran Iran

A new beamforming scheme is proposed for multi-input multi-output (MIMO) non-regenerative relays in an overloaded synchronous direct sequence code division multiple access (DS-CDMA) network in which the number of users is larger than the processing gain. In this scheme, several transmitters multicast their data to their groups of receivers through MIMO relays and DS-CDMA technique is utilised to decrease the level of multiple access interference (MAI) at the relays and the receivers. At the relays, the data of transmitters are despread, beamformed and re-spread. The aim of the beamformer is to minimise the total relays transmission power subject to the signal to interference and noise ratio (SINR) constraints at the receivers. This optimisation problem is an indefinite quadratic (non-convex) programming. Semi-definite programming (SDP) and second-order cone programming (SOCP) are two existing methods to solve the problem. However, they, respectively, suffer from high computational complexity and performance degradation when the number of antennas or users increase. To effectively mitigate these deficiencies, we propose a novel DC (difference of two convex functions) programming method. Our simulation results demonstrate the computational advantage of the proposed DC programming over SDP, while a better performance over SOCP is achieved. Moreover, the superiority of the proposed MIMO-CDMA scheme over other multiplexing schemes is shown by several scenarios.

关键词： cooperative communication MIMO communication relay networks (telecommunication) array signal processing code division multiple access spread spectrum communication radiofrequency interference concave programming computational complexity cooperative MIMO relay beamforming overloaded synchronous DS-CDMA multicast networks multiinput multioutput nonregenerative relays direct sequence code division multiple access network multiple-access interference total relay transmission power minimization SINR constraint optimisation problem indefinite quadratic programming nonconvex programming computational complexity antenna number DC programming method difference-of-two convex functions SDP SOCP MIMO-CDMA scheme

来源：评论

学校读者我要写书评

暂无评论

INEXACT INTERIOR-POINT METHOD FOR PDE-CONSTRAINED NONLINEAR OPTIMIZATION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2014年第3期36卷 A1251-A1276页

作者： Grote, Marcus J. Huber, Johannes Kourounis, Drosos Schenk, Olaf Univ Basel Dept Math & Comp Sci CH-4051 Basel Switzerland Univ Svizzera Italiana Inst Computat Sci CH-6900 Lugano Switzerland

Starting from the inexact interior-point framework from Curtis, Schenk, and Wachter [SIAM J. Sci. Comput., 32 (2012), pp. 3447-3475], we propose an effective Schur-complement slack-control preconditioner for the full Lagrangian Hessian matrix needed at each Newton iteration. Together they yield a scalable, robust, and highly parallel method for the numerical solution of large-scale nonconvex PDE-constrained optimization problems with inequality constraints. Because it uses the full Hessian matrix, modifying it whenever needed, the method not only is globally convergent, but also converges fast locally. Our preconditioner is not tailored to any particular class of PDEs or constraints, but instead judiciously exploits the sparsity structure of the Hessian. Numerical examples from PDE-constrained optimal control, parameter estimation, and full-waveform inversion demonstrate the robustness and efficiency of the method, even in the presence of active inequality constraints.

关键词： PDE-constrained optimization nonconvex programming inequality constraints inexact interior-point method preconditioning KKT system optimal control seismic imaging full-waveform inversion

来源：评论

学校读者我要写书评

暂无评论

A MATRIX-FREE ALGORITHM FOR EQUALITY CONSTRAINED OPTIMIZATION PROBLEMS WITH RANK-DEFICIENT JACOBIANS

引用

SIAM JOURNAL ON OPTIMIZATION 2009年第3期20卷 1224-1249页

作者： Curtis, Frank E. Nocedal, Jorge Waechter, Andreas NYU Courant Inst Math Sci New York NY 10003 USA Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA

We present a line search algorithm for large-scale constrained optimization that is robust and efficient even for problems with (nearly) rank-deficient Jacobian matrices. The method is matrix-free (i.e., it does not require explicit storage or factorizations of derivative matrices), allows for inexact step computations, and is applicable for nonconvex problems. The main components of the approach are a trust region subproblem for handling ill-conditioned or inconsistent linear models of the constraints and a process for attaining a sufficient reduction in a local model of a penalty function. We show that the algorithm is globally convergent to first-order optimal points or to stationary points of an infeasibility measure. Numerical results are presented.

关键词： large-scale optimization constrained optimization nonconvex programming trust regions inexact linear system solvers Krylov subspace methods

来源：评论

学校读者我要写书评

暂无评论

JOINTLY CONSTRAINED BICONVEX programming

引用

MATHEMATICS OF OPERATIONS RESEARCH 1983年第2期8卷 273-286页

作者： ALKHAYYAL, FA FALK, JE GEORGE WASHINGTON UNIV DEPT OPERAT RESWASHINGTONDC 20052

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.

关键词： biconvex functions. Bilinear programming branch and bound algorithm global convergence nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

nonconvex sensitivity-based generalized Benders decomposition

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第1期86卷 37-60页

作者： Lin, Jia-Jiang Xu, Feng Luo, Xiong-Lin China Univ Petr Dept Automat Beijing 102249 Peoples R China

This paper considers general separable pseudoconvex optimization problems with continuous complicating variables in which primal and projected problems are both pseudoconvex problems. A novel decomposition method based on generalized Benders decomposition, named nonconvex sensitivity-based generalized Benders decomposition, is developed and proved strictly to obtain optimal solutions of general separable pseudoconvex optimization problems of interest without constructing surrogate models. By the use of a reformulation strategy (introducing an extra equality constraint and constructing several subproblems), the algorithm handles the nonconvexity by direct manipulations of consistent linear Benders cuts and the check of optimality conditions and approximating the feasible region of complicating variables by supporting hyperplanes. The master problems of the new algorithm are always linear programming problems and the solution of the algorithm contains sensitivity information about complicating variables. Moreover, the new algorithm could also be used as a tool to check the nonconvexity of an optimization problem. Two cases are given to confirm the validity and applicability of the proposed algorithm.

关键词： nonconvex programming Separable pseudoconvexity Benders decomposition Optimality conditions Sensitivity analysis

来源：评论

学校读者我要写书评

暂无评论

Integer programming Formulations for Approximate Packing Circles in a Rectangular Container

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2014年第1期2014卷 1-6页

作者： Litvinchev, Igor Ozuna Espinosa, Edith Lucero Russian Acad Sci Ctr Comp Complex Syst Dept Moscow 119333 Russia Nuevo Leon State Univ Fac Mech & Elect Engn Monterrey 66450 NL Mexico

A problem of packing a limited number of unequal circles in a fixed size rectangular container is considered. The aim is to maximize the (weighted) number of circles placed into the container or minimize the waste. This problem has numerous applications in logistics, including production and packing for the textile, apparel, naval, automobile, aerospace, and food industries. Frequently the problem is formulated as a nonconvex continuous optimization problem which is solved by heuristic techniques combined with local search procedures. New formulations are proposed for approximate solution of packing problem. The container is approximated by a regular grid and the nodes of the grid are considered as potential positions for assigning centers of the circles. The packing problem is then stated as a large scale linear 0-1 optimization problem. The binary variables represent the assignment of centers to the nodes of the grid. Nesting circles inside one another is also considered. The resulting binary problem is then solved by commercial software. Numerical results are presented to demonstrate the efficiency of the proposed approach and compared with known results.

关键词： INTEGER programming CONTAINERS LOGISTICS HEURISTIC algorithms nonconvex programming MATHEMATICAL optimization

来源：评论

学校读者我要写书评

暂无评论

Efficient Method for Flexibility Analysis of Large-Scale nonconvex Heat Exchanger Networks

引用

INDUSTRIAL & ENGINEERING CHEMISTRY RESEARCH 2015年第43期54卷 10757-10767页

作者： Li, Jilong Du, Jian Zhao, Zongchang Yao, Pingjing Dalian Univ Technol Dept Chem Engn State Key Lab Fine Chem Dalian 116024 Liaoning Peoples R China Chinese Acad Sci Shenyang Inst Automat Shenyang 110016 Liaoning Peoples R China

A novel method is proposed for flexibility analysis of nonconvex heat exchanger networks. In this method, the direction matrix is introduced to describe the deviation direction of the uncertain parameter. Then by searching the critical directions that restrict the process flexibility with the simulated annealing algorithm, the flexibility index can be obtained. Since the directions are no longer limited to the vertices, this method can well deal with the nonconvex problems. Moreover, for large-scale problems, a decoupling strategy is developed to enhance the efficiency. On the basis of this, the entire network is decomposed into several independent subnetworks, and the one with the lowest flexibility decides the global flexibility index. Two examples are studied, and the results well demonstrate the various aspects dealt with in this work.

关键词： FLEXIBILITY (Mechanics) HEAT exchangers SIMULATED annealing (Mathematics) DECOMPOSITION (Chemistry) nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：