Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations

In this work, we take advantage of the powerful quadratic programming theory to obtain optimal solutions of scheduling problems. We apply a methodology that starts, in contrast to more classical approaches, by formulating three unrelated parallel machine scheduling problems as 0–1 quadratic programs under linear constraints. By construction, these quadratic programs are non-convex. Therefore, before submitting them to a branch-and-bound procedure, we reformulate them in such a way that we can ensure convexity and a high-quality continuous lower bound. Experimental results show that this methodology is interesting by obtaining the best results in literature for two of the three studied scheduling problems.     

Construction of Bézier Surfaces from Prescribed Boundary

In this paper, we present a method for generating Bézier surfaces from the boundary information based on a general second order functional and a third order functional associated with the triharmonic equation. By solving simple linear equations, the internal control points of the resulting Bézier surface can be obtained as linear combinations of the given boundary control points. This is a generalization of previous works on Plateau-Bézier problem, harmonic, biharmonic and quasi-harmonic Bézier surfaces. Some representative examples show the effectiveness of the presented method.     

Some Randomized Algorithms for Convex Quadratic Programming

We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems, which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present. We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular, we do not assume boundedness of the feasible set as required in related methods. Accepted 7 May 1997     

Polynomials Annihilating the Witt Ring

Let F be a non-formally real field of characteristic not 2 and let W(F) be the Witt ring of F. In certain cases generators for the annihilator ideal are determined. Aim the primary decomposition of A(F) is given. For formally d fields F, as an analogue the primary decomposition of A_t(F) = {f(X) ∈ Z[X]| f(ω) = 0 for all ω ∈ W_t(F)}, where W_t(F) is the torsion part of the Witt group, is obtained.     

A class of methods for solving large,convex quadratic programs subject to box constraints

In this paper we analyze conjugate gradient-type algorithms for solving convex quadratic programs subject only to box constraints (i.e., lower and upper bounds on the variables). Programs of this type, which we denote by BQP, play an important role in many optimization models and algorithms. We propose a new class of finite algorithms based on a nonfinite heuristic for solving a large, sparse BQP. The numerical results suggest that these algorithms are competitive with Dembo and Tulowitzski's (1983) CRGP algorithm in general, and perform better than CRGP for problems that have a low percentage of free variables at optimality, and for problems with only nonnegativity constraints.     

The Full Study of Planar Quadratic Differential Systems Possessing a Line of Singularities at Infinity

In this article we make a full study of the class of non-degenerate real planar quadratic differential systems having all points at infinity (in the Poincaré compactification) as singularities. We prove that all such systems have invariant affine lines of total multiplicity 3, give all their configurations of invariant lines and show that all these systems are integrable via the method of Darboux having cubic polynomials as inverse integrating factors. After constructing the topologically distinct phase portraits in this class we give invariant necessary and sufficient conditions in terms of the 12 coefficients of the systems for the realization of each one of them and give representatives of the orbits under the action of the affine group and time rescaling. We construct the moduli space of this class for this action and give the corresponding bifurcation diagram. Dedicated to Professor Zhifen Zhang on the occasion of her 80th birthday     

Effect of quadratic pressure gradient term on a one-dimensional moving boundary problem based on modified Darcy’s law

A relatively high formation pressure gradient can exist in seepage flow in low-permeable porous media with a threshold pressure gradient, and a significant error may then be caused in the model computation by neglecting the quadratic pressure gradient term in the governing equations. Based on these concerns, in consideration of the quadratic pressure gradient term, a basic moving boundary model is constructed for a one-dimensional seepage flow problem with a threshold pressure gradient. Owing to a strong nonlinearity and the existing moving boundary in the mathematical model, a corresponding numerical solution method is presented. First, a spatial coordinate transformation method is adopted in order to transform the system of partial differential equations with moving boundary conditions into a closed system with fixed boundary conditions; then the solution can be stably numerically obtained by a fully implicit finite-difference method. The validity of the numerical method is verified by a published exact analytical solution. Furthermore, to compare with Darcy’s flow problem, the exact analytical solution for the case of Darcy’s flow considering the quadratic pressure gradient term is also derived by an inverse Laplace transform. A comparison of these model solutions leads to the conclusion that such moving boundary problems must incorporate the quadratic pressure gradient term in their governing equations; the sensitive effects of the quadratic pressure gradient term tend to diminish, with the dimensionless threshold pressure gradient increasing for the one-dimensional problem.     

复杂结构优化选型的计算方法

本文为复杂结构优化选型提供了一个比较实用的计算方法:根据原有结构型式和设计经验来建立优化选型计算模型;对目标函数和约束条件作数学上近似处理后,利用Kuhn-Tucker条件和Lagrange乘子,把选型问题转化为求解典型二次规划问题;引进加权因子和利用改进后的变尺度法使计算过程简化、可靠,而且精度较高.     

A congruence for the Fourier coefficients of a modular form and its application to quadratic forms

Let F(z)=∑ _n=1^∞ A(n)q ⁿ denote the unique weight 6 normalized cuspidal eigenform on Γ₀(4). We prove that A(p)≡0,2,−1(mod 11) when p≠11 is a prime. We then use this congruence to give an application to the number of representations of an integer by quadratic form of level 4.