Nonnegative definite matrices and their applications to matrix quadratic programming problems

In this paper, the concept that a matrix is nonnegative definite over a subspace and the tool of generalized inverse are used to express a general form of matrix quadratic programming. Several fundamental conclusions are obtained. An application to the common penalty method for handling constrained minimization problem is given.     

Nonnegative definite and positive definite solutions to the matrix equation AXA* = B

The general nonegative definite solution to the matrix equation AXA^* = B is established in a form which can be viewed as advantageous over that derived by Khatri and Mitra (1976). The problem of determining an existence criterion and a representation of a positive definite to this equation is considered.     

Nonnegative definite and positive definite solutions to the matrix equation AXA * = B

The general nonegative definite solution to the matrix equation AXA^* = B is established in a form which can be viewed as advantageous over that derived by Khatri and Mitra (1976). The problem of determining an existence criterion and a representation of a positive definite to this equation is considered.     

Generalized Hadamard matrices and related matrices and their applications to the construction of the positive definite integral hermitian forms

A method of construction for the positive definite integral hermitian forms of determinant unity is established by using the generalized Hadamard matrices or the generalized conference matrices.     

正定二次规划的一个对偶算法

给出了一个正定二次规划的对偶算法．算法把原问题分解为一系列子问题,在保持原问题的Wolfe对偶可行的前提下,通过迭代计算,由这一系列子问题的最优解向原问题的最优解逼近．同时给出了算法的有限收敛性．     

Interactive fuzzy programming approach to Bi-level quadratic fractional programming problems

In this paper we propose an interactive fuzzy programming method for obtaining a satisfactory solution to a “bi-level quadratic fractional programming problem” with two decision makers (DMs) interacting with their optimal solutions. After determining the fuzzy goals of the DMs at both levels, a satisfactory solution is efficiently derived by updating the satisfactory level of the DM at the upper level with consideration of overall satisfactory balance between both levels. Optimal solutions to the formulated programming problems are obtained by combined use of some of the proper methods. Theoretical results are illustrated with the help of a numerical example.     

Necessary conditions in stochastic linear quadratic problems and their applications

Stochastic linear quadratic optimal control problems are considered. A unified approach is proposed to treat the necessary optimality conditions of closed-loop optimal strategies and open-loop optimal controls. Notice that the former notion does not rely on initial wealth, while the later one does. Our conclusions of closed-loop optimal strategies are directly derived by suitable variational methods, the approach to which is different from [12], [11]. Moreover, the necessary conditions for closed-loop optimal strategies happen to be sufficient which takes us by surprise. Finally, two applications are given as illustration.     

Generalized Hankel matrices of Markov parameters and their applications to control problems

The concept of Hankel matrices of Markov parameters associated with two polynomials is generalized for matrices. The generalized Hankel matrices of Markov parameters are then used to develop methods for testing the relative primeness of two matrices A and B, for determining stability and inertia of a matrix, and for constructing a class of matrices C such that A + C has a desired spectrum. Neither the method of construction of the generalized Hankel matrices nor the methods developed using these matrices require explicit computation of the characteristic polynomial of A (or of B).     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

Fuzzy costs in quadratic programming problems

Although quadratic programming problems are a special class of nonlinear programming, they can also be seen as general linear programming problems. These quadratic problems are of the utmost importance in an increasing variety of practical fields. As, in addition, ambiguity and vagueness are natural and ever-present in real-life situations requiring operative solutions, it makes perfect sense to address them using fuzzy concepts formulated as quadratic programming problems with uncertainty, i.e., as Fuzzy Quadratic Programming problems. This work proposes two novel fuzzy-sets-based methods to solve a particular class of Fuzzy Quadratic Programming problems which have vagueness coefficients in the objective function. Moreover, two other linear approaches are extended to solve the quadratic case. Finally, it is shown that the solutions reached from the extended approaches may be obtained from two proposed parametric multiobjective approaches.     

Ranking in quadratic integer programming problems

The present paper develops an algorithm for ranking the integer feasible solutions of a quadratic integer programming (QIP) problem. A linear integer programming (LIP) problem is constructed which provides bounds on the values of the objective function of the quadratic problem. The integer feasible solutions of this related integer linear programming problem are systematically scanned to rank the integer feasible solutions of the quadratic problem in non-decreasing order of the objective function values. The ranking in the QIP problem is useful in solving a nonlinear integer programming problem in which some other complicated nonlinear restrictions are imposed which cannot be included in the simple linear constraints of QIP, the objective function being still quadratic.     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm

In this paper, we present an original method to solve convex bilevel programming problems in an optimistic approach. Both upper and lower level objective functions are convex and the feasible region is a polyhedron. The enumeration sequential linear programming algorithm uses primal and dual monotonicity properties of the primal and dual lower level objective functions and constraints within an enumeration frame work. New optimality conditions are given, expressed in terms of tightness of the constraints of lower level problem. These optimality conditions are used at each step of our algorithm to compute an improving rational solution within some indexes of lower level primal-dual variables and monotonicity networks as well. Some preliminary computational results are reported.     

Concavity of certain maps on positive definite matrices and applications to Hadamard products

If f is a positive function on (0, ∞) which is monotone of order n for every n in the sense of Löwner and if Φ₁ and Φ₂ are concave maps among positive definite matrices, then the following map involving tensor products:

$\text{(A,B)?f[Φ}{}_1\text{(A)}{}^{\mathrm{?1}}\text{?Φ}{}_2\text{(B)]·(Φ}{}_1\text{(A)?I)}$

is proved to be concave. If Φ₁ is affine, it is proved without use of positivity that the map

$\text{(A,B)?f[Φ}{}_1\text{(A)?Φ}{}_2\text{(B)}{}^{\mathrm{?1}}\text{]·(Φ}{}_1\text{(A)?I)}$

is convex. These yield the concavity of the map

$\text{(A,B)?A}{}^{\mathrm{1?p}}\text{?B}{}^{\mathrm{p}}$

(0<p?1) (Lieb's theorem) and the convexity of the map

$\text{(A,B)?A}{}^{\mathrm{1+p}}\text{?B}{}^{\mathrm{?p}}$

(0<p?1), as well as the convexity of the map

$\text{(A,B)?(A·log[A])?I?A?log[B]}$

.These concavity and convexity theorems are then applied to obtain unusual estimates, from above and below, for Hadamard products of positive definite matrices.     

Some NP-complete problems in quadratic and nonlinear programming

In continuous variable, smooth, nonconvex nonlinear programming, we analyze the complexity of checking whether

1. a given feasible solution is not a local minimum, and
2. the objective function is not bounded below on the set of feasible solutions.

We construct a special class of indefinite quadratic programs, with simple constraints and integer data, and show that checking (a) or (b) on this class is NP-complete. As a corollary, we show that checking whether a given integer square matrix is not copositive, is NP-complete.     

Globally solving nonconvex quadratic programming problems via completely positive programming

Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.     

Extremal problems on the set of nonnegative definite matrices

An optimization problem of minimizing a real-valued function of certain elements of a symmetric matrix subject to this matrix being nonnegative definite is considered. Optimality conditions are proposed. The duality result of Olkin and Pukelsheim (1982) is extended to a wide class of such problems. Applications are discussed.     

Algorithms for bound constrained quadratic programming problems

Summary We present an algorithm which combines standard active set strategies with the gradient projection method for the solution of quadratic programming problems subject to bounds. We show, in particular, that if the quadratic is bounded below on the feasible set then termination occurs at a stationary point in a finite number of iterations. Moreover, if all stationary points are nondegenerate, termination occurs at a local minimizer. A numerical comparison of the algorithm based on the gradient projection algorithm with a standard active set strategy shows that on mildly degenerate problems the gradient projection algorithm requires considerable less iterations and time than the active set strategy. On nondegenerate problems the number of iterations typically decreases by at least a factor of 10. For strongly degenerate problems, the performance of the gradient projection algorithm deteriorates, but it still performs better than the active set method.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38