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 encod...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.展开更多
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 propo...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 kind of direct methods is presented for the solution of optimal control problems with state constraints. These methods are sequential quadratic programming methods. At every iteration a quadratic programming which i...A kind of direct methods is presented for the solution of optimal control problems with state constraints. These methods are sequential quadratic programming methods. At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and linear approximations to constraints is solved to get a search direction for a merit function. The merit function is formulated by augmenting the Lagrangian function with a penalty term. A line search is carried out along the search direction to determine a step length such that the merit function is decreased. The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadratic programming methods.展开更多
In this paper we present a new method for solving the Stokes problem which is a constrained optimization method. The new method is simpler and requires less computation than the existing methods. In this method we tra...In this paper we present a new method for solving the Stokes problem which is a constrained optimization method. The new method is simpler and requires less computation than the existing methods. In this method we transform the Stokes problem into a quadratic programming problem and by solving it, the velocity and the pressure are obtained.展开更多
A mechanism for proving global convergence in filter-SQP （sequence of quadratic programming） method with the nonlinear complementarity problem （NCP） function is described for constrained nonlinear optimization pro...A mechanism for proving global convergence in filter-SQP （sequence of quadratic programming） method with the nonlinear complementarity problem （NCP） function is described for constrained nonlinear optimization problem.We introduce an NCP function into the filter and construct a new SQP-filter algorithm.Such methods are characterized by their use of the dominance concept of multi-objective optimization,instead of a penalty parameter whose adjustment can be problematic.We prove that the algorithm has global convergence and superlinear convergence rates under some mild conditions.展开更多
In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above...In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.展开更多
The present paper is devoted to a novel smoothing function method for convex quadratic programming problem with mixed constrains, which has important application in mechanics and engineering science. The problem is re...The present paper is devoted to a novel smoothing function method for convex quadratic programming problem with mixed constrains, which has important application in mechanics and engineering science. The problem is reformulated as a system of non-smooth equations, and then a smoothing function for the system of non-smooth equations is proposed. The condition of convergences of this iteration algorithm is given. Theory analysis and primary numerical results illustrate that this method is feasible and effective.展开更多
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...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.展开更多
The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex q...The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.展开更多
In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the worst-case performance ratio at le...In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the worst-case performance ratio at leastα=0.87856….In fact,the estimated worst-case performance ratio is dependent on the data of the problem withαbeing a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at leastα+δ_d if every weight is strictly positive,whereδ_d>0 is a constant depending on the problem dimension and data.展开更多
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. Str...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.展开更多
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 ...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.展开更多
Presents a regular splitting and potential reduction method for solving a quadratic programming problem with box constraints. Discussion on the regular splitting and potential reduction algorithm; Complexity analysis ...Presents a regular splitting and potential reduction method for solving a quadratic programming problem with box constraints. Discussion on the regular splitting and potential reduction algorithm; Complexity analysis of the algorithm; Analysis of the complexity bound on obtaining an approximate solution.展开更多
A matrix splitting method is presented for minimizing a quadratic programming (QP) problem, and a general algorithm is designed to solve the QP problem and generates a sequence of iterative points. We prove that the s...A matrix splitting method is presented for minimizing a quadratic programming (QP) problem, and a general algorithm is designed to solve the QP problem and generates a sequence of iterative points. We prove that the sequence generated by the algorithm converges to the optimal solution and has an R-linear rate of convergence if the QP problem is strictly convex and nondegenerate, and that every accumulation point of the sequence generated by the general algorithm is a KKT point of the original problem under the hypothesis that the value of the objective function is bounded below on the constrained region, and that the sequence converges to a KKT point if the problem is nondegenerate and the constrained region is bounded.展开更多
Inspired by the success of the projected Barzilai-Borwein (PBB) method for largescale box-constrained quadratic programming, we propose and analyze the monotone projected gradient methods in this paper. We show by exp...Inspired by the success of the projected Barzilai-Borwein (PBB) method for largescale box-constrained quadratic programming, we propose and analyze the monotone projected gradient methods in this paper. We show by experiments and analyses that for the new methods,it is generally a bad option to compute steplengths based on the negative gradients. Thus in our algorithms, some continuous or discontinuous projected gradients are used instead to compute the steplengths. Numerical experiments on a wide variety of test problems are presented, indicating that the new methods usually outperform the PBB method.展开更多
A new algorithm for solving the three-dimensional elastic contact problem with friction is presented. The algorithm is a non-interior smoothing algorithm based on an NCP-function. The parametric variational principle ...A new algorithm for solving the three-dimensional elastic contact problem with friction is presented. The algorithm is a non-interior smoothing algorithm based on an NCP-function. The parametric variational principle and parametric quadratic programming method were applied to the analysis of three-dimensional frictional contact problem. The solution of the contact problem was finally reduced to a linear complementarity problem, which was reformulated as a system of nonsmooth equations via an NCP-function. A smoothing approximation to the nonsmooth equations was given by the aggregate function. A Newton method was used to solve the resulting smoothing nonlinear equations. The algorithm presented is easy to understand and implement. The reliability and efficiency of this algorithm are demonstrated both by the numerical experiments of LCP in mathematical way and the examples of contact problems in mechanics.展开更多
A heuristic technique is developed for a nonlinear magnetohydrodynamics （MHD） Jeffery-Hamel problem with the help of the feed-forward artificial neural net- work （ANN） optimized with the genetic algorithm （GA） a...A heuristic technique is developed for a nonlinear magnetohydrodynamics （MHD） Jeffery-Hamel problem with the help of the feed-forward artificial neural net- work （ANN） optimized with the genetic algorithm （GA） and the sequential quadratic programming （SQP） method. The twodimensional （2D） MHD Jeffery-Hamel problem is transformed into a higher order boundary value problem （BVP） of ordinary differential equations （ODEs）. The mathematical model of the transformed BVP is formulated with the ANN in an unsupervised manner. The training of the weights of the ANN is carried out with the evolutionary calculation based on the GA hybridized with the SQP method for the rapid local convergence. The proposed scheme is evaluated on the variants of the Jeffery-Hamel flow by varying the Reynold number, the Hartmann number, and the an- gles of the walls. A large number of simulations are performed with an extensive analysis to validate the accuracy, convergence, and effectiveness of the scheme. The comparison of the standard numerical solution and the analytic solution establishes the correctness of the proposed designed methodologies.展开更多
The box-constrained weighted maximin dispersion problem is to find a point in an n-dimensional box such that the minimum of the weighted Euclidean distance from given m points is maximized. In this paper, we first ref...The box-constrained weighted maximin dispersion problem is to find a point in an n-dimensional box such that the minimum of the weighted Euclidean distance from given m points is maximized. In this paper, we first reformulate the maximin dispersion problem as a non-convex quadratically constrained quadratic programming (QCQP) problem. We adopt the successive convex approximation (SCA) algorithm to solve the problem. Numerical results show that the proposed algorithm is efficient.展开更多
In this paper a class of iterative methods for the minimax problem i; proposed.We present a sequence of the extented linear-quadratic programming (ELQP) problems as subproblems of the original minimal problem and solv...In this paper a class of iterative methods for the minimax problem i; proposed.We present a sequence of the extented linear-quadratic programming (ELQP) problems as subproblems of the original minimal problem and solve the ELQP problem iteratively.The locally linear and su-perlinear convergence results of the algorithm are established.展开更多
基金supported by the National Natural Science Foundation of China (60873099)
文摘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.
基金the National Natural Science Foundation of China(No.50178916,No.19732020 and No.19872016)the National Key Basic lteseareh Special Foundation(No.G1999032805)+1 种基金the Special Funds for Major State Basic Researeh Projectsthe Foundation for University Key Teachers by the Ministry of Education of China
文摘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 kind of direct methods is presented for the solution of optimal control problems with state constraints. These methods are sequential quadratic programming methods. At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and linear approximations to constraints is solved to get a search direction for a merit function. The merit function is formulated by augmenting the Lagrangian function with a penalty term. A line search is carried out along the search direction to determine a step length such that the merit function is decreased. The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadratic programming methods.
文摘In this paper we present a new method for solving the Stokes problem which is a constrained optimization method. The new method is simpler and requires less computation than the existing methods. In this method we transform the Stokes problem into a quadratic programming problem and by solving it, the velocity and the pressure are obtained.
基金Project supported by the National Natural Science Foundation of China (Grant Nos.10571137,10771162)
文摘A mechanism for proving global convergence in filter-SQP （sequence of quadratic programming） method with the nonlinear complementarity problem （NCP） function is described for constrained nonlinear optimization problem.We introduce an NCP function into the filter and construct a new SQP-filter algorithm.Such methods are characterized by their use of the dominance concept of multi-objective optimization,instead of a penalty parameter whose adjustment can be problematic.We prove that the algorithm has global convergence and superlinear convergence rates under some mild conditions.
文摘In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.
文摘The present paper is devoted to a novel smoothing function method for convex quadratic programming problem with mixed constrains, which has important application in mechanics and engineering science. The problem is reformulated as a system of non-smooth equations, and then a smoothing function for the system of non-smooth equations is proposed. The condition of convergences of this iteration algorithm is given. Theory analysis and primary numerical results illustrate that this method is feasible and effective.
基金Fundamental Research Funds for the Central Universities,China(No.2232019D3-38)Shanghai Sailing Program,China(No.22YF1400900)。
文摘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.
文摘The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.
基金This work was supported by the National Natural Science Foundation of China (Grant No.10401038)Startup Grant for Doctoral Research of Beijing University of Technology and Hong Kong RGC Earmarked Grant CUHK4242/04E
文摘In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the worst-case performance ratio at leastα=0.87856….In fact,the estimated worst-case performance ratio is dependent on the data of the problem withαbeing a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at leastα+δ_d if every weight is strictly positive,whereδ_d>0 is a constant depending on the problem dimension and data.
基金Supported by the fundamental research funds for the central universities under grant YWF-10-02-021 and by National Natural Science Foundation of China under grant 11001006 The author is very grateful to all the three anonymous referees for their constructive criticisms and useful suggestions that help to improve the paper.
文摘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.
基金supported by the Natural Science Foundation of Tianjin(No.18JCYBJC85800)the Innovative Talents Cultivation of Young Middle Aged Backbone Teachers of Tianjin(No.135205GC38)+1 种基金Tianjin Normal University Undergraduate Teaching Quality and Teaching Reform Research Project(No.B201006505)University Student Innovation Project(No.202110065004).
文摘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.
基金This research supported partially by The National Natural Science Foundation of China-19771079 and 19601035State Key Laboratory of Scientific and Engineering Computing.
文摘Presents a regular splitting and potential reduction method for solving a quadratic programming problem with box constraints. Discussion on the regular splitting and potential reduction algorithm; Complexity analysis of the algorithm; Analysis of the complexity bound on obtaining an approximate solution.
基金the National Natural Science Foundation of China (No.19771079)and State Key Laboratory of Scientific and Engineering Computing
文摘A matrix splitting method is presented for minimizing a quadratic programming (QP) problem, and a general algorithm is designed to solve the QP problem and generates a sequence of iterative points. We prove that the sequence generated by the algorithm converges to the optimal solution and has an R-linear rate of convergence if the QP problem is strictly convex and nondegenerate, and that every accumulation point of the sequence generated by the general algorithm is a KKT point of the original problem under the hypothesis that the value of the objective function is bounded below on the constrained region, and that the sequence converges to a KKT point if the problem is nondegenerate and the constrained region is bounded.
基金supported by the National Natural Science Foundation of China(Grant Nos.10171104,10571171&40233029).
文摘Inspired by the success of the projected Barzilai-Borwein (PBB) method for largescale box-constrained quadratic programming, we propose and analyze the monotone projected gradient methods in this paper. We show by experiments and analyses that for the new methods,it is generally a bad option to compute steplengths based on the negative gradients. Thus in our algorithms, some continuous or discontinuous projected gradients are used instead to compute the steplengths. Numerical experiments on a wide variety of test problems are presented, indicating that the new methods usually outperform the PBB method.
文摘A new algorithm for solving the three-dimensional elastic contact problem with friction is presented. The algorithm is a non-interior smoothing algorithm based on an NCP-function. The parametric variational principle and parametric quadratic programming method were applied to the analysis of three-dimensional frictional contact problem. The solution of the contact problem was finally reduced to a linear complementarity problem, which was reformulated as a system of nonsmooth equations via an NCP-function. A smoothing approximation to the nonsmooth equations was given by the aggregate function. A Newton method was used to solve the resulting smoothing nonlinear equations. The algorithm presented is easy to understand and implement. The reliability and efficiency of this algorithm are demonstrated both by the numerical experiments of LCP in mathematical way and the examples of contact problems in mechanics.
文摘A heuristic technique is developed for a nonlinear magnetohydrodynamics （MHD） Jeffery-Hamel problem with the help of the feed-forward artificial neural net- work （ANN） optimized with the genetic algorithm （GA） and the sequential quadratic programming （SQP） method. The twodimensional （2D） MHD Jeffery-Hamel problem is transformed into a higher order boundary value problem （BVP） of ordinary differential equations （ODEs）. The mathematical model of the transformed BVP is formulated with the ANN in an unsupervised manner. The training of the weights of the ANN is carried out with the evolutionary calculation based on the GA hybridized with the SQP method for the rapid local convergence. The proposed scheme is evaluated on the variants of the Jeffery-Hamel flow by varying the Reynold number, the Hartmann number, and the an- gles of the walls. A large number of simulations are performed with an extensive analysis to validate the accuracy, convergence, and effectiveness of the scheme. The comparison of the standard numerical solution and the analytic solution establishes the correctness of the proposed designed methodologies.
文摘The box-constrained weighted maximin dispersion problem is to find a point in an n-dimensional box such that the minimum of the weighted Euclidean distance from given m points is maximized. In this paper, we first reformulate the maximin dispersion problem as a non-convex quadratically constrained quadratic programming (QCQP) problem. We adopt the successive convex approximation (SCA) algorithm to solve the problem. Numerical results show that the proposed algorithm is efficient.
文摘In this paper a class of iterative methods for the minimax problem i; proposed.We present a sequence of the extented linear-quadratic programming (ELQP) problems as subproblems of the original minimal problem and solve the ELQP problem iteratively.The locally linear and su-perlinear convergence results of the algorithm are established.
