An Effective Algorithm for Quadratic Optimization with Non-Convex Inhomogeneous Quadratic Constraints

This paper considers the NP (Non-deterministic Polynomial)-hard problem of finding a minimum value of a quadratic program (QP), subject to m non-convex inhomogeneous quadratic constraints. One effective algorithm is proposed to get a feasible solution based on the optimal solution of its semidefinite programming (SDP) relaxation problem.

Global optimality conditions for quadratic 0-1 programming with inequality constraints

Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.

Global Optimization of a Class of Nonconvex Quadratically Constrained Quadratic Programming Problems

In this paper we study a Class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.

A Chance Constrained Optimal Reserve Scheduling Approach for Economic Dispatch Considering Wind Penetration

The volatile wind power generation brings a full spectrum of problems to power system operation and management, ranging from transient system frequency fluctuation to steady state supply and demand balancing issue. In this paper, a novel wind integrated power system day-ahead economic dispatch model, with the consideration of generation and reserve cost is modelled and investigated. The proposed problem is first formulated as a chance constrained stochastic nonlinear programming U+0028 CCSNLP U+0029, and then transformed into a deterministic nonlinear programming U+0028 NLP U+0029. To tackle this NLP problem, a three-stage framework consists of particle swarm optimization U+0028 PSO U+0029, sequential quadratic programming U+0028 SQP U+0029 and Monte Carlo simulation U+0028 MCS U+0029 is proposed. The PSO is employed to heuristically search the line power flow limits, which are used by the SQP as constraints to solve the NLP problem. Then the solution from SQP is verified on benchmark system by using MCS. Finally, the verified results are feedback to the PSO as fitness value to update the particles. Simulation study on IEEE 30-bus system with wind power penetration is carried out, and the results demonstrate that the proposed dispatch model could be effectively solved by the proposed three-stage approach. © 2017 Chinese Association of Automation.

A Quadratically Approximate Framework for Constrained Optimization,Global and Local Convergence

This paper presents a quadratically approximate algorithm framework （QAAF） for solving general constrained optimization problems, which solves, at each iteration, a subproblem with quadratic objective function and quadratic equality together with inequality constraints. The global convergence of the algorithm framework is presented under the Mangasarian-Fromovitz constraint qualification （MFCQ）, and the conditions for superlinear and quadratic convergence of the algorithm framework are given under the MFCQ, the constant rank constraint qualification （CRCQ） as well as the strong second-order sufficiency conditions （SSOSC）. As an incidental result, the definition of an approximate KKT point is brought forward, and the global convergence of a sequence of approximate KKT points is analysed.

Exact Computable Representation of Some Second-Order Cone Constrained Quadratic Programming Problems

Solving the quadratically constrained quadratic programming(QCQP)problem is in general NP-hard.Only a few subclasses of the QCQP problem are known to be polynomial-time solvable.Recently,the QCQP problem with a nonconvex quadratic objective function over one ball and two parallel linear constraints is proven to have an exact computable representation,which reformulates the original problem as a linear semidefinite program with additional linear and second-order cone constraints.In this paper,we provide exact computable representations for some more subclasses of the QCQP problem,in particular,the subclass with one secondorder cone constraint and two special linear constraints.

Robust Solutions of Uncertain Complex-valued Quadratically Constrained Programs

In this paper, we discuss complex convex quadratically constrained optimization with uncertain data. Using S-Lemma, we show that the robust counterpart of complex convex quadratically constrained optimization with ellipsoidal or intersection-of-two-ellipsoids uncertainty set leads to a complex semidefinite program. By exploring the approximate S-Lemma, we give a complex semidefinite program which approximates the NP-hard robust counterpart of complex convex quadratic optimization with intersection-of-ellipsoids uncertainty set.

Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs:Algorithms and Approximation Bounds

This paper develops new semidefinite programming(SDP)relaxation techniques for two classes of mixed binary quadratically constrained quadratic programs and analyzes their approximation performance.The first class of problems finds two minimum norm vectors in N-dimensional real or complex Euclidean space,such that M out of 2M concave quadratic constraints are satisfied.By employing a special randomized rounding procedure,we show that the ratio between the norm of the optimal solution of this model and its SDP relaxation is upper bounded by 54πM2 in the real case and by 24√Mπin the complex case.The second class of problems finds a series of minimum norm vectors subject to a set of quadratic constraints and cardinality constraints with both binary and continuous variables.We show that in this case the approximation ratio is also bounded and independent of problem dimension for both the real and the complex cases.

解带有二次约束非凸二次规划问题的一个分枝缩减方法(英文)

在这篇论文里,有机地把外逼近方法与分枝定界技术结合起来,提出了解带有二次约束非凸二次规划问题的一个分枝缩减方法;给出了原问题的一个新的线性规划松弛,以便确定它在超矩形上全局最优值的一个下界;利用超矩形的一个深度二级剖分方法,以及超矩形的缩减和删除技术,提高算法的收敛速度;证明了在知道原问题可行点的条件下,该算法在有限步里就可以获得原问题的一个全局最优化解,并且用一个例子说明了该算法是有效的.

逐步二次规划法在约束潮流中的运用

约束潮流就是当系统的结构、参数及负荷情况给定时,通过选取控制变量,找到能够满足所有运行限制的潮流分布。文中运用最优潮流算法计算约束潮流,将有功、无功出力以及电压值作为控制变量,并使用逐步二次规划法对其进行求解。给出了有关的数学模型和计算流程,介绍了处理Maratos效应的一种的灵敏度算法。中国电科院8机22节点系统和IEEE-118节点系统的计算结果证明了使用SQP方法计算约束潮流的有效性。

多重二次背包问题的量子进化求解算法

多重二次背包问题是二次背包与多重背包两种NP(Non-Deterministic Polynomial,非确定多项式)难问题融合后的一种新问题,由于其决策变量间具有高耦合性,已有的启发式算法求解效率和精度不够理想.针对这一问题提出一种量子进化求解算法,这种算法的量子观测操作能将部分约束处理与观测一步完成,解码效率高且不易陷入局部极值.算法中的量子更新采用自适应调节整体更新方式,相比传统查表方式更简洁和高效.算法还设计了一种局部和全局修补算子以保证解的可行性.另外,设计的交换算子能增强算法在约束边界的搜索性能.标准算例测试实验的结果表明文中提出的求解算法比传统算法的精度和效率更高.

带有界约束非凸二次规划问题的整体优化方法

通过研究带有界约束非凸二次规划问题 ,给出了求解该问题的整体最优解的分枝定界方法及其收敛性 ;提出了定界的紧、松驰策略 ,把球约束二次规划问题作为子问题来确定原问题的整体最优值下界和上界 ,应用分枝定界方法达到了对原问题的求解。

带有二次约束二次规划问题的分枝定界方法

提出了一种解带有二次约束二次规划问题的新的分枝定界算法对该算法进行了收敛性分析。这种方法是用新的线性规划松弛定界技术确定最优值的下界,并且把分枝定界技术和外逼近方法有机地结合起来。

求解约束优化问题的动态邻域粒子群算法

粒子群算法(PSO)求解约束优化问题存在较严重的早熟收敛现象,为了有效抑制早熟收敛,提出了基于改进的约束自适应方法的动态邻域粒子群算法(IPSO)。算法采用动态邻域策略提高算法的全局搜索能力,设计了一种改进的自适应约束处理方法,根据迭代代数线性增加搜索偏向系数,在早期偏向于搜索可行解,在后期偏向于搜索最优解,并引入序列二次规划增强算法的局部搜索能力。通过基准测试函数实验对比分析,表明该算法对于约束优化问题具有较好的全局收敛性。

铁路网上技术直达列车编组计划优化的二次0-1规划法

以文献[1]的构模原理为基础,构造了任意结构的路网上双方向技术直达列车编组计划综合优化的二次0-1规划模型,然后给出了这类模型的若干理论结果,并在此基础上介绍了模型的解法、计算试验结果及分析。

边界约束非凸二次规划问题的分枝定界方法

本文是研究带有边界约束非凸二次规划问题.我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分别引用了它们的一个求整体最优解的有效算法.我们提出了几种定界的紧、松弛策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法.最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想.

线性约束两分块非凸优化的ADMM-SQP算法

基于乘子交替方向法(ADMM)和序列二次规划(SQP)方法思想,致力于研究线性约束两分块非凸优化的新型高效算法.首先,以SQP思想为主线,在其二次规划(QP)子问题的求解中引入ADMM思想,将QP分解为两个相互独立的小规模QP求解·其次,借助增广拉格朗日函数和Armijo线搜索产生原始变量新迭代点.最后,以显式解析式更新对偶变量·因此,构建了一个新型ADMM-SQP算法·在较弱条件下,分析了算法通常意义下的全局收敛性,并对算法进行了初步的数值试验.

输入受限LQ控制的参变量变分原理和算法

在最优控制理论中根据模拟理论思想发展了塑性力学和接触力学中的参变量变分原理,并建立了控制输入受限的线性二次(linear quadratic,LQ)最优控制问题的求解新方程—耦合的Hamilton正则方程与线性互补方程.通过将连续时间离散成一系列等间距时间区段,在离散时域内采用参数二次规划方法给出数值求解输入受限的LQ最优控制问题的新算法.数值仿真验证了该算法在求解控制输入受限的LQ最优控制问题中的有效性,并且该算法具有较快的收敛性,在大步长下具有较高的计算精度.

一类积极集SQP滤子方法

积极集策略是在约束最优化问题中减少约束条件个数的一个有效手段.基于此策略,结合序列二次规划(SQP)方法,并利用滤子以避免罚函数的使用,提出了一类积极集SQP滤子方法,并在合理条件下证明了算法的全局收敛性.数值结果表明算法是有效的.

基于序列二次规划算法的机械弹性车轮的结构优化

在保证结构与实际车轮模型结构相同的条件下,建立机械弹性车轮的有限元模型,实现了车轮受力时的结构协调性和弹簧的回位功能。利用ANSYS软件对车轮进行了有限元分析,得出车轮的径向刚度。根据结构优化问题的特点,以轮辐的每段长度作为设计变量,轮胎径向刚度为优化目标,利用序列二次规划(SQP)算法,对车轮结构进行优化设计。结果表明:基于SQP算法的机械弹性车轮的结构优化,在允许范围内有效的增大了车轮的径向刚度。