求解Nash均衡子问题的一个算法

n人有限博弈的混合策略组合（p1^*,…,pn^*)为Nash均衡,如果其中每一策略pi^*都是参与人i(i=1,2,…,n),对其它n-1个参与人策略组合（p1^*,…,pi 1^*,pi-1^*,…,pn^*)的最优反应,即存在n个概率向量p1^*,…,pn^*使得对i=1,2,…,n及任意k1维概率向量pi恒有vi(p1^*,…,pn^*…)小于vi(pi^*,…,pi-1^*,pi 1^*,…pn^*),其中vi为参与人i的支付函数,pi=(pil,…,piki)）为ki维概率向量,即满足条件,pij大于等于0,∑kij=1pij=1,ki是参与人i的策略空间中策略个数,i=1,2,…,n,由此,Nash均衡的求解可化为下列优化问题：求n个概率向量pi^*,…,pn^8,使得对i=1,2,…,n及任意ki维的概率向量pi满足maxxvi(P1^*,…,pi-1^*,pi,Pi 1^*,…,pn^*)=vi(P1^*,,…,Pn^*)。     

Optimal design of efficient acoustic antenna arrays

Minimax optimal design of sonar transducer arrays can be formulated as a nonlinear program with many convex quadratic constraints and a nonconvex quadratic efficiency constraint. The variables of this problem are a scaling and phase shift applied to the output of each sensor. This problem is solved by applying Lagrangian relaxation to the convex quadratic constraints. Extensive computational experience shows that this approach can efficiently find near-optimal solutions of problems with up to 391 variables and 579 constraints. This work was supported by ONR Contracts N00014-83-C-0437 and N00014-82-C-824.     

Quadratic geometric programming with application to machining economics

Geometric Programming is extended to include convex quadratic functions. Generalized Geometric Programming is applied to this class of programs to obtain a convex dual program. Machining economics problems fall into this class. Such problems are studied by applying this duality to a nested set of three problems. One problem is zero degree of difficulty and the solution is obtained by solving a simple system of equations. The inclusion of a constraint restricting the force on the tool to be less than or equal to the breaking force provides a more realistic solution. This model is solved as a program with one degree of difficulty. Finally the behavior of the machining cost per part is studied parametrically as a function of axial depth. This research was supported by the Air Force Office of Scientific Research Grant AFOSR-83-0234     

A conjugate gradient method for the unconstrained minimization of strictly convex quadratic splines

In this paper, we show that an analogue of the classical conjugate gradient method converges linearly when applied to solving the problem of unconstrained minimization of a strictly convex quadratic spline. Since a strictly convex quadratic program with simple bound constraints can be reformulated as unconstrained minimization of a strictly convex quadratic spline, the conjugate gradient method is used to solve the unconstrained reformulation and find the solution of the original quadratic program. In particular, if the solution of the original quadratic program is nondegenerate, then the conjugate gradient method finds the solution in a finite number of iterations. This author's research is partially supported by the NASA/Langley Research Center under grant NCC-1-68 Supplement-15.     

Extending the QCR method to general mixed-integer programs

Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) into an equivalent program, with a convex objective function. Such a reformulation can be solved by a standard solver that uses a branch and bound algorithm. We prove that our reformulation is the best one within a convex reformulation scheme, from the continuous relaxation point of view. This reformulation, that we call MIQCR (Mixed Integer Quadratic Convex Reformulation), is based on the solution of an SDP relaxation of (MQP). Computational experiences are carried out with instances of (MQP) including one equality constraint or one inequality constraint. The results show that most of the considered instances with up to 40 variables can be solved in 1?h of CPU time by a standard solver.     

Piecewise convex programs

A piecewise convex program is a convex program such that the constraint set can be decomposed in a finite number of closed convex sets, called the cells of the decomposition, and such that on each of these cells the objective function can be described by a continuously differentiable convex function.In a first part, a cutting hyperplane method is proposed, which successively considers the various cells of the decomposition, checks whether the cell contains an optimal solution to the problem, and, if not, imposes a convexity cut which rejects the whole cell from the feasibility region. This elimination, which is basically a dual decomposition method but with an efficient use of the specific structure of the problem is shown to be finitely convergent.The second part of this paper is devoted to the study of some special cases of piecewise convex program and in particular the piecewise quadratic program having a polyhedral constraint set. Such a program arises naturally in stochastic quadratic programming with recourse, which is the subject of the last section.This paper is based on the author's Ph.D. Dissertation presented at the Faculté des Sciences Appliquées of the Université Catholique de Louvain. It describes research supported partly by the Programme National d'Impulsion à la Recherche en Informatique of the Belgian Government under contract No. I (14 bis) 6 and partly by a two-year fellowship of the Centre Interuniversitaire d'Etudes Doctorales dans les Sciences du Management.     

A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems

We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game.     

Error bounds and strong upper semicontinuity for monotone affine variational inequalities

Global error bounds for possibly degenerate or nondegenerate monotone affine variational inequality problems are given. The error bounds are on an arbitrary point and are in terms of the distance between the given point and a solution to a convex quadratic program. For the monotone linear complementarity problem the convex program is that of minimizing a quadratic function on the nonnegative orthant. These bounds may form the basis of an iterative quadratic programming procedure for solving affine variational inequality problems. A strong upper semicontinuity result is also obtained which may be useful for finitely terminating any convergent algorithm by periodically solving a linear program.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grants CCR-9101801 and CCR-9157632.     

On Extensions of the Frank-Wolfe Theorems

In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.     

New Sequential Quadratically-Constrained Quadratic Programming Method of Feasible Directions and Its Convergence Rate

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration. the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without thestrict complementarity assumption and the linear independence constraint qualification (LICQ). Research supported by the National Natural Science Foundation of China Project 10261001 and Guangxi Science Foundation Projects 0236001 and 0249003. The author thanks two anonymous referees for valuable comments and suggestions on the original version of this paper.     

On convex quadratic programs with linear complementarity constraints

The paper shows that the global resolution of a general convex quadratic program with complementarity constraints (QPCC), possibly infeasible or unbounded, can be accomplished in finite time. The method constructs a minmax mixed integer formulation by introducing finitely many binary variables, one for each complementarity constraint. Based on the primal-dual relationship of a pair of convex quadratic programs and on a logical Benders scheme, an extreme ray/point generation procedure is developed, which relies on valid satisfiability constraints for the integer program. To improve this scheme, we propose a two-stage approach wherein the first stage solves the mixed integer quadratic program with pre-set upper bounds on the complementarity variables, and the second stage solves the program outside this bounded region by the Benders scheme. We report computational results with our method. We also investigate the addition of a penalty term y ^T Dw to the objective function, where y and w are the complementary variables and D is a nonnegative diagonal matrix. The matrix D can be chosen effectively by solving a semidefinite program, ensuring that the objective function remains convex. The addition of the penalty term can often reduce the overall runtime by at least 50 %. We report preliminary computational testing on a QP relaxation method which can be used to obtain better lower bounds from infeasible points; this method could be incorporated into a branching scheme. By combining the penalty method and the QP relaxation method, more than 90 % of the gap can be closed for some QPCC problems.     

An SQP-type algorithm for nonlinear second-order cone programs

We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration, the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness of the algorithm. This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

Solution existence and stability of quadratically constrained convex quadratic programs

We propose verifiable necessary and sufficient conditions for the solution existence of a convex quadratic program whose constraint set is defined by finitely many convex linear-quadratic inequalities. A related stability analysis of the problem is also considered.     

An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs

We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, strengthening Burer’s well-known result on the exactness of the copositive relaxation in the case of nonconvex quadratic programs. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded relaxation for a rather large family of convex relaxations including the doubly nonnegative relaxation.

     

A new global optimization method for univariate constrained twice-differentiable NLP problems

In this paper, a new global optimization method is proposed for an optimization problem with twice-differentiable objective and constraint functions of a single variable. The method employs a difference of convex underestimator and a convex cut function, where the former is a continuous piecewise concave quadratic function, and the latter is a convex quadratic function. The main objectives of this research are to determine a quadratic concave underestimator that does not need an iterative local optimizer to determine the lower bounding value of the objective function and to determine a convex cut function that effectively detects infeasible regions for nonconvex constraints. The proposed method is proven to have a finite ε-convergence to locate the global optimum point. The numerical experiments indicate that the proposed method competes with another covering method, the index branch-and-bound algorithm, which uses the Lipschitz constant.     

Successive Linearization Methods for Nonlinear Semidefinite Programs

We present a successive linearization method with a trust region-type globalization for the solution of nonlinear semidefinite programs. At each iteration, the method solves a quadratic semidefinite program, which can be converted to a linear semidefinite program with a second order cone constraint. A subproblem of this kind can be solved quite efficiently by using some recent software for semidefinite and second-order cone programs. The method is shown to be globally convergent under certain assumptions. Numerical results on some nonlinear semidefinite programs including optimization problems with bilinear matrix inequalities are reported to illustrate the behaviour of the proposed method.The research of the fourth author was supported in part by a Grant-in-Aid for Scientific Research from Japan Society for the Promotion of Science. The research of the second author was supported by the DFG (Deutsche Forschungsgemeinschaft).     

Minimum principle sufficiency

We characterize the property of obtaining a solution to a convex program by minimizing over the feasible region a linearization of the objective function at any of its solution points (Minimum Principle Sufficiency). For the case of a monotone linear complementarity problem this MPS property is completely equivalent to the existence of a nondegenerate solution to the problem. For the case of a convex quadratic program, the MPS property is equivalent to the span of the Hessian of the objective function being contained in the normal cone to the feasible region at any solution point, plus the cone generated by the gradient of the objective function at any solution point. This in turn is equivalent to the quadratic program having a weak sharp minimum. An important application of the MPS property is that minimizing on the feasible region a linearization of the objective function at a point in a neighborhood of a solution point gives an exact solution of the convex program. This leads to finite termination of convergent algorithms that periodically minimize such a linearization.This material is based on research supported by National Science Foundation Grants DCR-8521228 and CCR-8723091, and Air Force Office of Scientific Research Grants AFOSR 86-0172 and AFOSR and AFOSR 89-0410.     

On a subproblem of trust region algorithms for constrained optimization

We study a subproblem that arises in some trust region algorithms for equality constrained optimization. It is the minimization of a general quadratic function with two special quadratic constraints. Properties of such subproblems are given. It is proved that the Hessian of the Lagrangian has at most one negative eigenvalue, and an example is presented to show that the Hessian may have a negative eigenvalue when one constraint is inactive at the solution.Research supported by a Research Fellowship of Fitzwilliam College, Cambridge, and by a research grant from the Chinese Academy of Sciences.     

Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint

This paper extends and completes the discussion by Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted) about the quadratic programming over one quadratic constraint (QP1QC). In particular, we relax the assumption to cover more general cases when the two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence. Under such an assumption, the nonconvex (QP1QC) problem can be solved through a dual approach with no duality gap. This is unusual for general nonconvex programming but we can explain by showing that (QP1QC) is indeed equivalent to a linearly constrained convex problem, which happens to be dual of the dual of itself. Another type of hidden convexity can be also found in the boundarification technique developed in Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted).