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

Fix and bound: an efficient approach for solving large-scale quadratic programming problems with box constraints

MATHEMATICAL programming COMPUTATION 2025年第2期17卷 231-263页

作者： Locatelli, Marco Piccialli, Veronica Sudoso, Antonio M. Univ Parma Dipartimento Ingn & Architettura 181-AParco Area Sci I-43124 Parma Italy Sapienza Univ Roma Dipartimento Ingn Informat Automat & Gestionale A Via Ariosto 25 I-00185 Rome Italy

In this paper, we propose a branch-and-bound algorithm for solving nonconvex quadratic programming problems with box constraints (BoxQP). Our approach combines existing tools, such as semidefinite programming (SDP) bounds strengthened through valid inequalities, with a new class of optimality-based linear cuts which leads to variable fixing. The most important effect of fixing the value of some variables is the size reduction along the branch-and-bound tree, allowing to compute bounds by solving SDPs of smaller dimension. Extensive computational experiments over large dimensional (up to n=200\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n=200$$\end{document}) test instances show that our method is the state-of-the-art solver on large-scale BoxQPs. Furthermore, we test the proposed approach on the class of binary QP problems, where it exhibits competitive performance with state-of-the-art solvers.

关键词： nonconvex quadratic programming Global optimization Semidefinite programming Branch-and-bound Variable fixing

来源：评论

学校读者我要写书评

暂无评论

KRONECKER PRODUCT CONSTRAINTS WITH AN APPLICATION TO THE TWO-TRUST-REGION SUBPROBLEM

引用

SIAM JOURNAL ON OPTIMIZATION 2017年第1期27卷 368-378页

作者： Anstreicher, Kurt M. Univ Iowa Dept Management Sci Iowa City IA 52242 USA

We consider semidefinite optimization problems that include constraints of the form G(x) >= 0 and H(x) >= 0, where the components of the symmetric matrices G(.) and H(.) are affine functions of x is an element of R-n. In such a case we obtain a new constraint K(x, X) >= 0, where the components of K(.,.) are affine functions of x and X, and X is an n x n matrix that is a relaxation of xx(T). The constraint K(x, X) >= 0 is based on the fact that G(x) circle times H(x) >= 0, where circle times denotes the Kronecker product. This construction of a constraint based on the Kronecker product generalizes the construction of a reformation-linearization technique (RLT) constraint from two linear inequality constraints, and also the construction of a second-order coneRLT constraint from one linear inequality constraint and a second-order cone constraint. We show how the Kronecker product constraint obtained from two second-order cone constraints can be efficiently used to computationally strengthen the semidefinite programming relaxation of the two-trust-region subproblem.

关键词： semidefinite programming semidefinite optimization nonconvex quadratic programming trust region subproblem

来源：评论

学校读者我要写书评

暂无评论

An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs

引用

JOURNAL OF GLOBAL OPTIMIZATION 2010年第4期48卷 595-632页

作者： Dinh, Tao Pham Canh, Nam Nguyen Le Thi, Hoai An Natl Inst Appl Sci Rouen Lab Modelling Optimizat & Operat Res LMI F-76801 St Etienne France Metz Univ Informat Dept UFR MIM Lab Theoret & Appl Comp Sci LITA F-57045 Metz France

This paper addresses a new continuous approach based on the DC (Difference of Convex functions) programming and DC algorithms (DCA) to Binary quadratic programs (BQP) which play a key role in combinatorial optimization. DCA is completely different from other avalaible methods and featured by generating a convergent finite sequence of feasible binary solutions (obtained by solving linear programs with the same constraint set) with decreasing objective values. DCA is quite simple and inexpensive to handle large-scale problems. In particular DCA is explicit, requiring only matrix-vector products for Unconstrained Binary quadratic programs (UBQP), and can then exploit sparsity in the large-scale setting. To check globality of solutions computed by DCA, we introduce its combination with a customized Branch-and-Bound scheme using DC/SDP relaxation. The combined algorithm allows checking globality of solutions computed by DCA and restarting it if necessary and consequently accelerates the B&B approach. Numerical results on several series test problems provided in OR-Library (Beasley in J Global Optim, 8:429-433, 1996), show the robustness and efficiency of our algorithm with respect to standard methods. In particular DCA provides I mu-optimal solutions in almost all cases after only one restarting and the combined DCA-B&B-SDP always provides (I mu-)optimal solutions.

关键词： DC programming DC algorithms (DCA) nonconvex quadratic programming Exact penalty DC relaxation Branch-and-bound (B&B) Semidefinite programming (SDP) Binary quadratic programming (BQP)

来源：评论

学校读者我要写书评

暂无评论

Generalization performance of ν-support vector classifier based on conditional value-at-risk minimization

引用

NEUROCOMPUTING 2009年第10-12期72卷 2351-2358页

作者： Takeda, Akiko Keio Univ Dept Adm Engn Kohoku Ku Kanagawa 2238522 Japan

We extend the conditional geometric score (CGS) classifier of Gotoh and Takeda for binary linear classification to a nonlinear one, which we call the beta-support vector classifier (SVC), and investigate the equivalence between the beta-SVC and the (extended) nu-SVC. The CGS classifier has recently been found to be equivalent to the extended nu-SVC of Perez-Cruz et al. and, especially in the convex case, equivalent to the nu-SVC of Scholkopf et A. The CGS problem is to minimize a risk measure known as the conditional value-at-risk (beta-CVaR). In this paper, we discuss theoretical aspects, mainly generalization performance, of the beta-SVC. The formula of a generalization error bound includes the beta-CVaR or a related quantity. It implies that the minimum beta-CVaR leads to a small generalization error bound of the beta-SVC. The viewpoint of CVaR minimization is useful to ensure the validity of not only the beta-SVC but also the (extended) nu-SVC. (c) 2009 Elsevier B.V. All rights reserved.

关键词： Support vector machines Conditional value-at-risk nonconvex quadratic programming Extended nu-SVM

来源：评论

学校读者我要写书评

暂无评论

Global optimization approach to unequal sphere packing problems in 3D

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2002年第3期114卷 671-694页

作者： Sutou, A Dai, Y Cent Res Lab Enterprise Server Syst Res Dept Res Staff Tokyo Japan Univ Illinois Dept Bioengn Chicago IL USA

The problem of the unequal sphere packing in a 3-dimen-sional polytope is analyzed. Given a set of unequal spheres and a poly-tope, the double goal is to assemble the spheres in such a way that (i) they do not overlap with each other and (ii) the sum of the volumes of the spheres packed in the polytope is maximized. This optimization has an application in automated radiosurgical treatment planning and can be formulated as a nonconvex optimization problem with quadratic constraints and a linear objective function. On the basis of the special structures associated with this problem, we propose a variety of algorithms which improve markedly the existing simplicial branch-and-bound algorithm for the general nonconvex quadratic program. Further, heuristic algorithms are incorporated to strengthen the efficiency of the algorithm. The computational study demonstrates that the proposed algorithm can obtain successfully the optimization up to a limiting size.

关键词： nonconvex quadratic programming unequal sphere packing problem simplicial branch-and-bound algorithm LP relaxation heuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic Output Feedback Control of the Liouville Equation for Discrete-Time SISO Linear Systems

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第10期64卷 4268-4275页

作者： Bakolas, Efstathios Univ Texas Austin Dept Aerosp Engn & Engn Mech Austin TX 78712 USA

In this paper, we address the so-called Liouville control problem for discrete-time SISO linear systems in the class of Gaussian distributions. In particular, we propose a systematic procedure for the characterization of a dynamic output feedback policy that will transfer the output of the system. which is a known Gaussian random variable, to a goal Gaussian distribution after a finite number of stages. In the proposed approach, the Liouville control problem is reduced to two decoupled (finite-dimensional) quadratic programs, one of which is subject to a single affine constraint, which is a convex program, whereas the other one is subject to a single quadratic equality constraint. Despite the fact that the second optimization problem is not convex, one can characterize its exact solution via a systematic procedure without resorting to convex relaxation techniques. which may yield suboptimal or even infeasible solutions to the original (nonconvex) optimization problem. Finally, we present numerical simulations that illustrate the key ideas of this paper.

关键词： Affine output feedback control discrete-time linear systems Liouville control problem nonconvex quadratic programming output covariance control

来源：评论

学校读者我要写书评

暂无评论

A new semidefinite programming bound for indefinite quadratic forms over a simplex

引用

JOURNAL OF GLOBAL OPTIMIZATION 1999年第4期14卷 357-364页

作者： Nowak, I Humboldt Univ D-10099 Berlin Germany

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.

关键词： global optimization nonconvex quadratic programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Dual bounds and optimality cuts for all-quadratic programs with convex constraints

引用

JOURNAL OF GLOBAL OPTIMIZATION 2000年第4期18卷 337-356页

作者： Nowak, I Humboldt Univ D-10099 Berlin Germany

A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.

关键词： global optimization nonconvex quadratic programming Lagrangian relaxation optimality cuts duality gap

来源：评论

学校读者我要写书评

暂无评论

On the Lower Semicontinuity of the Value Function and Existence of Solutions in Quasiconvex Optimization

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2022年第2期195卷 390-417页

作者： Flores-Bazan, Fabian Thiele, Filip Univ Concepcion Dept Ingn Matemat Concepcion Chile

This paper provides sufficient conditions ensuring the lower semicontinuity of the value function psi(a) := inf {f(x) : g(1)(x) <= a(1), ..., g(m)(x) <= a(m)}, a = (a(1), ..., a(m)), at 0, under quasiconvexity assumptions on f and g(i), although there are results where convexity of some g(i) will be required. In some situations, our conditions will imply also the existence of points where the value psi(0) is achieved. In convex optimization, it is known that zero duality gap is equivalent to the lower semicontinuity of psi at 0. Here, the dual problem is defined in terms of the linear Lagrangian. We recall that convexity of the closure of the set (f , g(1), ..., g(m))(R-n) + R-+(1+m) m and lower semicontinuity of psi at 0 imply zero duality gap. In addition, our results provide much more information than those existing in the literature. Several examples showing the applicability of our approach and the non applicability of any other result elsewhere are exhibited. Furthermore, we identify a suitable large class of functions (quadratic linear fractional) to which f and g(i) could belong to and our results apply.

关键词： Zero duality gap Lagrangian duality Quasiconvex programming nonconvex quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Enhancing RLT relaxations via a new class of semidefinite cuts

引用

JOURNAL OF GLOBAL OPTIMIZATION 2002年第1-4期22卷 233-261页

作者： Sherali, HD Fraticelli, BMP Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.

关键词： Reformulation-Linearization Technique (RLT) semidefinite programming (SDP) semidefinite cuts valid inequalities nonconvex quadratic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：