Sufficient Global Optimality Conditions for Bivalent Quadratic Optimization

We prove a sufficient global optimality condition for the problem of minimizing a quadratic function subject to quadratic equality constraints where the variables are allowed to take values –1 and 1. We extend the condition to quadratic problems with matrix variables and orthonormality constraints, and in particular to the quadratic assignment problem.     

混合整数二次规划问题的全局最优性条件

本文给出了混合整数二次规划问题的全局最优性条件,包括全局最优充分性条件和全局最优必要性条件.我们还给出了一个数值实例用以说明如何利用本文所给出的全局最优性条件来判定一个给定点是否是全局最优解.     

Optimality Conditions for D.C. Vector Optimization Problems Under Reverse Convex Constraints

In this paper, we establish global necessary and sufficient optimality conditions for D.C. vector optimization problems under reverse convex constraints. An application to vector fractional mathematical programming is also given. Mathematics Subject Classifications (1991). Primary 90C29, Secondary 49K30.     

Global Optimization of a Quadratic Functional with Quadratic Equality Constraints, Part 2

In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. It is assumed that the cost functional is positive definite and that the constraints are both feasible and regular (but otherwise they are unrestricted quadratic functions). Thus, the existence of a global constrained minimum is assured. We develop a necessary and sufficient condition that completely characterizes the global minimum cost. Such a condition is of essential importance in iterative numerical methods for solving the constrained minimization problem, because it readily distinguishes between local minima and global minima and thus provides a stopping criterion for the computation. The result is similar to one obtained previously by the authors. In the previous result, we gave a characterization of the global minimum of a constrained quadratic minimization problem in which the cost functional was an arbitrary quadratic functional (as opposed to positive-definite here) and the constraints were at least positive-semidefinite quadratic functions (as opposed to essentially unrestricted here).     

Sufficient Conditions for Global Optimality of Bivalent Nonconvex Quadratic Programs with Inequality Constraints

We present sufficient conditions for the global optimality of bivalent nonconvex quadratic programs involving quadratic inequality constraints as well as equality constraints. By employing the Lagrangian function, we extend the global subdifferential approach, developed recently in Jeyakumar et al. (J. Glob. Optim., 2007, to appear; Math. Program. Ser. A, 2007, to appear) for studying bivalent quadratic programs without quadratic constraints, and derive global optimality conditions. The authors are grateful to the referees for constructive comments and suggestions which have contributed to the final preparation of the paper. Z.Y. Wu’s current address: School of Information Technology and Mathematical Sciences, University of Ballarat, Ballarat, Victoria, Australia. The work of this author was completed while at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

First and Second-Order Optimality Conditions for Convex Composite Multiobjective Optimization

Multiobjective optimization is a useful mathematical model in order to investigate real-world problems with conflicting objectives, arising from economics, engineering, and human decision making. In this paper, a convex composite multiobjective optimization problem, subject to a closed convex constraint set, is studied. New first-order optimality conditions for a weakly efficient solution of the convex composite multiobjective optimization problem are established via scalarization. These conditions are then extended to derive second-order optimality conditions.     

A Non-Interior Path Following Method for Convex Quadratic Programming Problems with Bound Constraints

We propose a non-interior path following algorithm for convex quadratic programming problems with bound constraints based on Chen-Harker-Kanzow-Smale smoothing technique. Conditions are given under which the algorithm is globally convergent or globally linearly convergent. Preliminary numerical experiments indicate that the method is promising.     

Optimality Conditions for the Difference of Convex Set-Valued Mappings

Using the concept of subdifferential of cone-convex set valued mappings recently introduced by Baier and Jahn J. Optimiz. Theory Appl. 100 (1999), 233–240, we give necessary optimality conditions for nonconvex multiobjective optimization problems. An example illustrating the usefulness of our results is also given. Mathematics Subject classification: Primary 90C29, 90C26; Secondary 49K99.     

On a Quadratic Optimization Problem with Equality Constraints

The constrained optimization problem with a quadratic cost functional and two quadratic equality constraints has been studied by Bar-on and Grasse, with positive-definite matrix in the objective. In this note, we shall relax the matrix in the objective to be positive semidefinite. A necessary and sufficient condition to characterize a local optimal solution to be global is established. Also, a perturbation scheme is proposed to solve this generalized problem.     

Convex Quadratic Approximation

For some applications it is desired to approximate a set of m data points in ⁿ with a convex quadratic function. Furthermore, it is required that the convex quadratic approximation underestimate all m of the data points. It is shown here how to formulate and solve this problem using a convex quadratic function with s = (n + 1)(n + 2)/2 parameters, s m, so as to minimize the approximation error in the L ¹ norm. The approximating function is q(p,x), where p ^s is the vector of parameters, and x n. The Hessian of q(p,x) with respect to x (for fixed p) is positive semi-definite, and its Hessian with respect to p (for fixed x) is shown to be positive semi-definite and of rank n. An algorithm is described for computing an optimal p* for any specified set of m data points, and computational results (for n = 4,6,10,15) are presented showing that the optimal q(p*,x) can be obtained efficiently. It is shown that the approximation will usually interpolate s of the m data points.     

Conditions for Global Optimality 2

In this paper bearing the same title as our earlier survey-paper [11] we pursue the goal of characterizing the global solutions of an optimization problem, i.e. getting at necessary and sufficient conditions for a feasible point to be a global minimizer (or maximizer) of the objective function. We emphasize nonconvex optimization problems presenting some specific structures like convex-anticonvex ones or quadratic ones.     

求总极值问题的最优性条件

郑权提出了求总极值问题的积分－水平集的概念性算法,同时给出了最优性条件。本文提出了修正的积分－水平集算法,并且给出了类似的总极值存在的最优性条件。     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

积分型总极值方法的最优性条件

郑权提出了求总极值问题的积分—水平集的概念性算法,同时给出了最优性条件.本文构造函数F(x),讨论了该函数的性质,证明求解原问题等价于求解方程F(c)=0的根.在文中给出了相应的总极值存在的最优性条件.     

Asymptotic Dual Conditions Characterizing Optimality for Infinite Convex Programs

Characterizations of optimality are presented for infinite-dimensional convex programming problems, where the number of constraints is not restricted to be finite and where no constraint qualification is assumed. The optimality conditions are given in asymptotic forms using subdifferentials and €-subdifferentials. They are obtained by employing a version of the Farkas lemma for systems involving convex functions. An extension of the results to problems with a semiconvex objective function is also given.     

一种新广义凸多目标分式规划的最优性充分条件

提出了（F,α,ρ,θ）-b-凸函数的概念,它是一类新的广义凸函数,并给出了这类广义凸函数的性质.在此基础上,讨论了目标函数和约束函数均为（F,α,ρ,θ）-b-凸函数的多目标分式规划,利用广义K-T条件,得到了这类多目标规划有效解和弱有效解的几个充分条件,推广了已有文献的相关结果.     

一个求解箱约束二次规划的非内点预估校正算法

利用Chen-Harker-Kanzow-Smale光滑技术,给出了一个求解箱约束二次规划的预估校正的算法,它是Xu‘s方程的进一步研究,它的思想是将问题的K-T条件转化成一组光滑的等式,再用预估校正方法求解.同现存的算法相比,该算法具有较快的收敛速度,且所需的条件相对较弱.本文改进了该领域内的一些最新结果.     

Iterative Convex Quadratic Approximation for Global Optimization in Protein Docking

An algorithm for finding an approximate global minimum of a funnel shaped function with many local minima is described. It is applied to compute the minimum energy docking position of a ligand with respect to a protein molecule. The method is based on the iterative use of a convex, general quadratic approximation that underestimates a set of local minima, where the error in the approximation is minimized in the L¹ norm. The quadratic approximation is used to generate a reduced domain, which is assumed to contain the global minimum of the funnel shaped function. Additional local minima are computed in this reduced domain, and an improved approximation is computed. This process is iterated until a convergence tolerance is satisfied. The algorithm has been applied to find the global minimum of the energy function generated by the Docking Mesh Evaluator program. Results for three different protein docking examples are presented. Each of these energy functions has thousands of local minima. Convergence of the algorithm to an approximate global minimum is shown for all three examples.     

On First Order Optimality Conditions for Vector Optimization

We develop first order optimality conditions for constrained vector optimization. The partial orders for the objective and the constraints are induced by closed and convex cones with nonempty interior. After presenting some well known existence results for these problems, based on a scalarization approach, we establish necessity of the optimality conditions under a Slater-like constraint qualification, and then sufficiency for the K-convex case. We present two alternative sets of optimality conditions, with the same properties in connection with necessity and sufficiency, but which are different with respect to the dimension of the spaces to which the dual multipliers belong. We introduce a duality scheme, with a point-to-set dual objective, for which strong duality holds. Some examples and open problems for future research are also presented,