Highly Accurate Golden Section Search Algorithms and Fictitious Time Integration Method for Solving Nonlinear Eigenvalue Problems

This study sets up two new merit functions,which are minimized for the detection of real eigenvalue and complex eigenvalue to address nonlinear eigenvalue problems.For each eigen-parameter the vector variable is solved from a nonhomogeneous linear system obtained by reducing the number of eigen-equation one less,where one of the nonzero components of the eigenvector is normalized to the unit and moves the column containing that component to the right-hand side as a nonzero input vector.1D and 2D golden section search algorithms are employed to minimize the merit functions to locate real and complex eigenvalues.Simultaneously,the real and complex eigenvectors can be computed very accurately.A simpler approach to the nonlinear eigenvalue problems is proposed,which implements a normalization condition for the uniqueness of the eigenvector into the eigenequation directly.The real eigenvalues can be computed by the fictitious time integration method(FTIM),which saves computational costs compared to the one-dimensional golden section search algorithm(1D GSSA).The simpler method is also combined with the Newton iterationmethod,which is convergent very fast.All the proposed methods are easily programmed to compute the eigenvalue and eigenvector with high accuracy and efficiency.

Orthogonal genetic algorithm for solving quadratic bilevel programming problems

A quadratic bilevel programming problem is transformed into a single level complementarity slackness problem by applying Karush-Kuhn-Tucker（KKT） conditions.To cope with the complementarity constraints,a binary encoding scheme is adopted for KKT multipliers,and then the complementarity slackness problem is simplified to successive quadratic programming problems,which can be solved by many algorithms available.Based on 0-1 binary encoding,an orthogonal genetic algorithm,in which the orthogonal experimental design with both two-level orthogonal array and factor analysis is used as crossover operator,is proposed.Numerical experiments on 10 benchmark examples show that the orthogonal genetic algorithm can find global optimal solutions of quadratic bilevel programming problems with high accuracy in a small number of iterations.

Reconsideration on Homogeneous Quadratic Riemann Boundary Value Problem

The homogeneous quadratic riemann boundary value problem (1) with H?lder continuous coefficients for the normal case was considered by the author in 1997. But the solutions obtained there are incomplete. Here its general method of solution is obtained. Key words homogeneous quadratic Riemann boundary value problem - ordinary and special nodes - index - sectionally holomorphic function CLC number O 175.5 Foundation item: Supported by the National Natural Science Foundation of China (19871064)Biography: Lu Jian-ke (1922-), male, Professor, research direction: complex analysis and its applications.

MIXED ENERGY METHOD FOR SOLUTION OF QUADRATIC PROGRAMMING PROBLEMS AND ELASTIC-PLASTIC ANALYSIS OF TRUSS STRUCTURES

A new algorithm for the solution of quadratic programming problemsis put forward in terms of the mixed energy theory and is furtherused for the incremental solution of elastic-plastic trussstructures. The method proposed is different from the traditionalone, for which the unknown variables are selected just in one classsuch as displacements or stresses. The present method selects thevariables in the mixed form with both displacement and stress. As themethod is established in the hybrid space, the information found inthe previous incremental step can be used for the solution of thepresent step, making the algorithm highly effi- cient in thenumerical solution process of quadratic programming problems. Theresults obtained in the exm- ples of the elastic-plastic solution ofthe truss structures verify what has been predicted in thetheoretical anal- ysis.

A branch-and-bound algorithm for multi-dimensional quadratic 0-1 knapsack problems

In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.

Solution to the quadratic assignment problem usingsemi-Lagrangian relaxation

The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.

Modified Exact Jacobian Semidefinite Programming Relaxation for Celis-Dennis-Tapia Problem

A modified exact Jacobian semidefinite programming(SDP)relaxation method is proposed in this paper to solve the Celis-Dennis-Tapia(CDT)problem using the Jacobian matrix of objective and constraining polynomials.In the modified relaxation problem,the number of introduced constraints and the lowest relaxation order decreases significantly.At the same time,the finite convergence property is guaranteed.In addition,the proposed method can be applied to the quadratically constrained problem with two quadratic constraints.Moreover,the efficiency of the proposed method is verified by numerical experiments.

A NEW MATRIX PERTURBATION METHOD FOR ANALYTICAL SOLUTION OF THE COMPLEX MODAL EIGENVALUE PROBLEM OF VISCOUSLY DAMPED LINEAR VIBRATION SYSTEMS

A new matrix perturbation analysis method is presented for efficient approximate solution of the complex modal quadratic generalized eigenvalue problem of viscously damped linear vibration systems. First, the damping matrix is decomposed into the sum of a proportional-and a nonproportional-damping parts, and the solutions of the real modal eigenproblem with the proportional dampings are determined, which are a set of initial approximate solutions of the complex modal eigenproblem. Second, by taking the nonproportional-damping part as a small modification to the proportional one and using the matrix perturbation analysis method, a set of approximate solutions of the complex modal eigenvalue problem can be obtained analytically. The result is quite simple. The new method is applicable to the systems with viscous dampings-which do not deviate far away from the proportional-damping case. It is particularly important that the solution technique be also effective to the systems with heavy, but not over, dampings. The solution formulas of complex modal eigenvlaues and eigenvectors are derived up to second-order perturbation terms. The effectiveness of the perturbation algorithm is illustrated by an exemplar numerical problem with heavy dampings. In addition, the practicability of approximately estimating the complex modal eigenvalues, under the proportional-damping hypothesis, of damped vibration systems is discussed by several numerical examples.

Error Analysis of the Feedback Controls Arising in the Stochastic Linear Quadratic Control Problems

In this work,the author proposes a discretization for stochastic linear quadratic control problems(SLQ problems)subject to stochastic differential equations.The author firstly makes temporal discretization and obtains SLQ problems governed by stochastic difference equations.Then the author derives the convergence rates for this discretization relying on stochastic differential/difference Riccati equations.Finally an algorithm is presented.Compared with the existing results relying on stochastic Pontryagin-type maximum principle,the proposed scheme avoids solving backward stochastic differential equations and/or conditional expectations.

Stability analysis of proportional delayed projection neural network for quadratic programming problem

At present,projection neural network(PNN)with bounded time delay has been widely used for solving convex quadratic programming problem(QPP).However,there is little research concerning PNN with unbounded time delay.In this paper,we propose the proportional delayed PNN to solve QPP with equality constraints.By utilizing homeo morphism mapping principle,we prove the proportional delayed PNN exists with unique equilibrium point which is the optimal solution of QPP.Simultaneously,delay-dependent criteria about global exponential stability(GES)and global polynomial stability(GPS)are also acquired by applying the method of variation of constants and inequality techniques.On the other hand,when proportional delay factor q is equal to 1,the proportional delayed PNN becomes the one without time delay which still can be utilized for solving QPP.But in most situations,q is not equal to 1,and time delay is unpredictable and may be unbounded in the actual neural network,which causes instability of system.Therefore,it is necessary to consider proportional delayed PNN.A numerical example demonstrates that,compared with the proportional delayed Lagrange neural network,the proportional delayed PNN is faster in terms of convergence rate.The possible reason is that appropriate parameters make the model converge to the equilibrium point along the direction of gradient descent.

Robust ACO-Based Landmark Matching and Maxillofacial Anomalies Classification

Imagery assessment is an efficient method for detecting craniofacial anomalies.A cephalometric landmark matching approach may help in orthodontic diagnosis,craniofacial growth assessment and treatment planning.Automatic landmark matching and anomalies detection helps face the manual labelling lim-itations and optimize preoperative planning of maxillofacial surgery.The aim of this study was to develop an accurate Cephalometric Landmark Matching method as well as an automatic system for anatomical anomalies classification.First,the Active Appearance Model(AAM)was used for the matching process.This pro-cess was achieved by the Ant Colony Optimization(ACO)algorithm enriched with proximity information.Then,the maxillofacial anomalies were classified using the Support Vector Machine(SVM).The experiments were conducted on X-ray cephalograms of 400 patients where the ground truth was produced by two experts.The frameworks achieved a landmark matching error(LE)of 0.50±1.04 and a successful landmark matching of 89.47%in the 2 mm and 3 mm range and of 100%in the 4 mm range.The classification of anomalies achieved an accuracy of 98.75%.Compared to previous work,the proposed approach is simpler and has a comparable range of acceptable matching cost and anomaly classification.Results have also shown that it outperformed the K-nearest neigh-bors(KNN)classifier.

Characterization of optimal feedback for stochastic linear quadratic control problems

One of the fundamental issues in Control Theory is to design feedback controls.It is well-known that,the purpose of introducing Riccati equations in the study of deterministic linear quadratic control problems is exactly to construct the desired feedbacks.To date,the same problem in the stochastic setting is only partially well-understood.In this paper,we establish the equivalence between the existence of optimal feedback controls for the stochastic linear quadratic control problems with random coefficients and the solvability of the corresponding backward stochastic Riccati equations in a suitable sense.We also give a counterexample showing the nonexistence of feedback controls to a solvable stochastic linear quadratic control problem.This is a new phenomenon in the stochastic setting,significantly different from its deterministic counterpart.

New approach to training support vector machine

Support vector machine has become an increasingly popular tool for machine learning tasks involving classification, regression or novelty detection. Training a support vector machine requires the solution of a very large quadratic programming problem. Traditional optimization methods cannot be directly applied due to memory restrictions. Up to now, several approaches exist for circumventing the above shortcomings and work well. Another learning algorithm, particle swarm optimization, for training SVM is introduted. The method is tested on UCI datasets.

Virtual Machine Scheduling for Improving Energy Efficiency in laaS Cloud

In IaaS Cloud,different mapping relationships between virtual machines(VMs) and physical machines(PMs) cause different resource utilization,so how to place VMs on PMs to reduce energy consumption is becoming one of the major concerns for cloud providers.The existing VM scheduling schemes propose optimize PMs or network resources utilization,but few of them attempt to improve the energy efficiency of these two kinds of resources simultaneously.This paper proposes a VM scheduling scheme meeting multiple resource constraints,such as the physical server size(CPU,memory,storage,bandwidth,etc.) and network link capacity to reduce both the numbers of active PMs and network elements so as to finally reduce energy consumption.Since VM scheduling problem is abstracted as a combination of bin packing problem and quadratic assignment problem,which is also known as a classic combinatorial optimization and NP-hard problem.Accordingly,we design a twostage heuristic algorithm to solve the issue,and the simulations show that our solution outperforms the existing PM- or network-only optimization solutions.

Sensitivity Analysis of Semi-simple Eigenvalues of Regular Quadratic Eigenvalue Problems

This paper discusses the sensitivity analysis of semisimple eigenvalues and associated eigen-matrix triples of regular quadratic eigenvalue problems analytically dependent on several parameters. The directional derivatives of semisimple eigenvalues are obtained. The average of semisimple eigenvalues and corresponding eigen-matrix triple are proved to be analytic, and their partial derivatives are given. On these grounds, the sensitivities of the semisimple eigenvalues and corresponding eigenvector matrices are defined.

TWO PROBLEMS OF PLANAR QUADRATIC SYSTEMS

The main results of this paper are as follows: （ⅰ） The important formulas, given by Bautin, of three focal quantities for the specific form of quadratle system （E2） have been generalized to the general form of （E2）. （ⅱ） By using the method in [13], a kind of （E2） possessing at least four limit cycles is given. Theorem 2 herein contains the results in [11--13] on （1,3）-distribution of limit cycles of （E2）.

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.

Backbone analysis and algorithm design for the quadratic assignment problem

As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.

Static response analysis of structures with interval parameters using the second-order Taylor series expansion and the DCA for QB

In this paper, based on the second-order Taylor series expansion and the difference of convex functions algo- rithm for quadratic problems with box constraints （the DCA for QB）, a new method is proposed to solve the static response problem of structures with fairly large uncertainties in interval parameters. Although current methods are effective for solving the static response problem of structures with interval parameters with small uncertainties, these methods may fail to estimate the region of the static response of uncertain structures if the uncertainties in the parameters are fairly large. To resolve this problem, first, the general expression of the static response of structures in terms of structural parameters is derived based on the second-order Taylor series expansion. Then the problem of determining the bounds of the static response of uncertain structures is transformed into a series of quadratic problems with box constraints. These quadratic problems with box constraints can be solved using the DCA approach effectively. The numerical examples are given to illustrate the accuracy and the efficiency of the proposed method when comparing with other existing methods.

A Posteriori Error Estimates of Mixed Methods for Quadratic Optimal Control Problems Governed by Parabolic Equations

In this paper,we discuss the a posteriori error estimates of the mixed finite element method for quadratic optimal control problems governed by linear parabolic equations.The state and the co-state are discretized by the high order Raviart-Thomas mixed finite element spaces and the control is approximated by piecewise constant functions.We derive a posteriori error estimates for both the state and the control approximation.Such estimates,which are apparently not available in the literature,are an important step towards developing reliable adaptive mixed finite element approximation schemes for the control problem.