On the lower bound for a quadratic problem on the Stiefel manifold

We study the problem of finding the global minimum of a homogeneous quadratic function of special kind over the Stiefel manifold. For two variants of this problem, a low bound is proposed that is the dual Lagrange bound in the quadratic statement obtained using a family of redundant restrictions. The dual bound is proved to be exact in the case where the problem is considered over Boolean variables. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 95–103, September–October 2008.     

New quadratic models for the maximum weighted cut problem

New quadratic models are proposed to improve the upper-bound estimates in the maximum weighted cut problem. They are found by two original methods for deriving redundant quadratic constraints. A well-known linear model is shown to follow from the models proposed. Recommendations on how to develop its strengthened analogs are given. This study is partially sponsored from the grant UM2-2574-KV-03 (CRDF Cooperative Grants Program). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 63—75, January–February 2006.     

Stability of a vector integer quadratic programming problem with respect to vector criterion and constraints

The paper analyzes five types of stability against perturbations of initial data in criterion functions and constraints of vector integer quadratic optimization problems. Necessary and sufficient conditions are proved for all the types of stability. The relationship among stability with respect to changes of vector criterion coefficients, stability with respect to changes of initial data in constraints, and stability with respect to vector criterion and constraints is established. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 63–72, September–October 2006.     

Solving Optimal Control Problems on the Class of Step Functions

Linear optimal control problems with multipoint non-separated conditions with a quadratic performance criterion of control are analyzed. An approach with a violation of intermediate conditions is proposed. The original problem is reduced to the classical quadratic programming problem with the dimension determined by the number of intermediate points. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 153–162, July–August 2005.     

Stability and regularization of the lexicographic vector problem of quadratic discrete programming

The paper studies the bounds of variation of input parameters for a vector quadratic discrete optimization problem, which do not expand the set of lexicographic optima. A stability criterion is described and a regularization method is presented, which makes it possible to pass from a possibly unstable problem to a series of perturbed stable problems with a previous set of lexicographic optima. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 54–62, March–April, 2000.     

Solving systems of linear equations with Boolean variables

The paper presents a method to solve systems of linear equations with Boolean variables, which implements an enumeration strategy. Necessary and sufficient conditions for the existence of feasible plans are formalized. A formal procedure to analyze subsets of alternatives is described. The structure of an algorithm that possesses the property of completeness is presented. Special cases of systems of equations are examined. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 42–50, September–October 2006.     

An approach to determining Shor’s dual quadratic estimates

For a general quadratic problem, an analog is formulated as a homogeneous quadratic problem. The estimates ψ* constructed based on Shor’s dual quadratic estimates for these problems are proved to be equal. It is shown that, for the case of a homogeneous quadratic problem, finding ψ* is reduced to an unconstraint minimization problem for a convex function. The study was partially sponsored by the grant UKM2-2812-KV-06 (CRDF Cooperative Grants Program). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 89–99, March–April 2008.     

Necessary and sufficient optimality conditions of a design decision on the structure of a local computer network

A problem of nonlinear programming with Boolean variables is considered, for which the possibility of extension of the optimality conditions of solving a special problem of nonlinear programming (with continuous variables) is shown by statistical estimation of possible design decisions. This contributed to the solution of the initial problem by simpler methods. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 133–137, September–October, 1999.     

Analysis of stability of stochastic dynamic systems under Poisson perturbations. II. Stability of solutions in quadratic mean of systems of linear stochastic differential equations under Poisson perturbations

Necessary and sufficient conditions of asymptotic stability in quadratic mean are obtained for trivial solutions of systems of linear stochastic differential equations under Poisson perturbations. Model problems are analyzed. Part I of this article is published in No. 4 (2005). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 50–66, November–December 2005.     

基于二次型规划的平面冗余机械臂的自运动

提出一种基于二次型性能指标的方法,用于规划平面冗余机械臂的自运动轨迹．鉴于实际的机械臂都存在关节物理约束,该自运动规划方案考虑了关节极限和关节速度极限的躲避．提出了基于线性变分不等式的原对偶神经网络,并将其作为所对应的二次型规划方案的实时求解器．仿真结果证实了该基于神经网络的自运动规划方案的有效性．     

A new approach to the decomposition of Boolean functions by the method of <Emphasis Type="Italic">q</Emphasis>-partitions. III. Joint decomposition of a function system

The paper considers the set-theoretical approach to the joint decomposition of systems of Boolean functions of variables specified in different representation forms. The approach is based on the method of q-partitions of conjuncterms and concept of decomposition clones. Theorems on joint decomposition of a system of full and partial functions are formulated. The approach is illustrated by examples. Parts I and II of this article are published in No. 5 (2001) and No. 1 (2002). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 39–58, March–April 2007.     

A Rigorous Global Filtering Algorithm for Quadratic Constraints*

This article introduces a new filtering algorithm for handling systems of quadratic equations and inequations. Such constraints are widely used to model distance relations in numerous application areas ranging from robotics to chemistry. Classical filtering algorithms are based upon local consistencies and thus, are often unable to achieve a significant pruning of the domains of the variables occurring in quadratic constraint systems. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global filtering algorithm that works on a tight linear relaxation of the quadratic constraints. The Simplex algorithm is then used to narrow the domains. Since most implementations of the Simplex work with floating point numbers and thus, are unsafe, we provide a procedure to generate safe linearizations. We also exploit a procedure provided by Neumaier and Shcherbina to get a safe objective value when calling the Simplex algorithm. With these two procedures, we prevent the Simplex algorithm from removing any solution while filtering linear constraint systems. Experimental results on classical benchmarks show that this new algorithm yields a much more effective pruning of the domains than local consistency filtering algorithms.*This article is an extended version of [23].     

A New Optimal Force Distribution Scheme of Multiple Cooperating Robots Using Dual Method

A new optimal force distribution scheme of multiple cooperating robots is proposed, in which the duality theory of nonlinear programming (NLP) is combined with the quadratic programming (QP) approach. The optimal force distribution problem is formulated as a QP problem with both linear and quadratic constraints, and its solution is obtained by an efficient algorithm. The use of the quadratic constraints is important in that it considerably reduces the number of constraints, thus enabling the Dual method of NLP to be used in the solution algorithm. Moreover, it can treat norm constraints without approximation, such as bound of the norm of the force exerted by each robot. The proposed scheme is more efficient in terms of speed than any other method. Numerical examples of two PUMA robot task using the proposed method and a well-known fast method are compared, and the results indicate the capability of real time application of our method.     

Optimal control of the dynamic state of a thin compound plate

This paper addresses new optimal control problems for dynamic deflections of a thin compound plate with quadratic cost functionals. Theorems on the existence of optimal controls are proved for all the cases considered. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 151–175, July–August 2006.     

求解布尔与非线性数值约束相混合的约束问题

布尔与数值变量相混合的约束问题有着广泛的应用,但是当约束中的数值变量间存在非线性关系时该问题求解起来十分困难.目前的许多求解方法都是不完备的,即这些方法不能完全肯定某些包含非线性数值表达式的约束是否能够成立.针对这种问题,提出了将非线性数值约束转化为特殊形式的优化问题,采用全局优化算法对其进行求解的方法.已经实现了一个基于此方法的原型工具.实验结果表明,该方法能够有效地求解非线性混合约束问题,并且总能够得到该约束条件是否可满足的结果.     

A computational study on the quadratic knapsack problem with multiple constraints

The quadratic knapsack problem (QKP) has been the subject of considerable research in recent years. Despite notable advances in special purpose solution methodologies for QKP, this problem class remains very difficult to solve. With the exception of special cases, the state-of-the-art is limited to addressing problems of a few hundred variables and a single knapsack constraint.In this paper we provide a comparison of quadratic and linear representations of QKP based on test problems with multiple knapsack constraints and up to eight hundred variables. For the linear representations, three standard linearizations are investigated. Both the quadratic and linear models are solved by standard branch-and-cut optimizers available via CPLEX. Our results show that the linear models perform well on small problem instances but for larger problems the quadratic model outperforms the linear models tested both in terms of solution quality and solution time by a wide margin. Moreover, our results demonstrate that QKP instances larger than those previously addressed in the literature as well as instances with multiple constraints can be successfully and efficiently solved by branch and cut methodologies.     

On solutions of fuzzy random multiobjective quadratic programming with applications in portfolio problem

In this paper, a multiobjective quadratic programming problem fuzzy random coefficients matrix in the objectives and constraints and the decision vector are fuzzy variables is considered. First, we show that the efficient solutions fuzzy quadratic multiobjective programming problems series-optimal-solutions of relative scalar fuzzy quadratic programming. Some theorems are to find an optimal solution of the relative scalar quadratic multiobjective programming with fuzzy coefficients, having decision vectors as fuzzy variables. An application fuzzy portfolio optimization problem as a convex quadratic programming approach is discussed and an acceptable solution to such problem is given. At the end, numerical examples are illustrated in the support of the obtained results.     

Solution of boolean differential equations on systolic arrays

Conclusion The proposed method for solving Boolean differential equations relies on matrix interpretation of the representation and solution of Boolean differential equations. The algorithm is accordingly interpreted in the language of parallel computations, producing an efficient solution of the problem on parallel structures. This approach is consistent with the requirements and development trends in VLSI technology. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 36–53, January–February, 1996.     

Lagrangean decompositions for the unconstrained binary quadratic programming problem

The unconstrained binary quadratic programming problem (QP) is a classical non‐linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.     

面向冗余度机械臂QP问题求解的E47和94LVI数值算法

冗余度机械臂的二次规划(QP)问题同时受制于等式约束、不等式约束和双端约束,且面向冗余度机械臂实时控制的该类QP问题的求解对运算实时性有较高要求。考虑同时受制于上述三种约束的二次规划问题的求解,给出并研究两种数值算法(E47和94LVI算法)。这类带约束的二次规划问题被等价转换为分段线性投影方程。应用E47和94LVI算法求解上述分段线性投影方程,从而得到二次规划问题的最优数值解。同时,通过大量的数值实验,研究两种算法面向冗余度机械臂的QP问题求解性能,并给出E47、94LVI算法与经典有效集算法的对比实验结果。最终证实了E47和94LVI两种算法在求解二次规划问题上的高效性和优越性。