Global optimization of a quadratic functional with quadratic equality constraints

In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. While it is obvious that, for a nonempty constraint set, there exists a global minimum cost, a method to determine if a given local solution yields the global minimum cost has not been established. We develop a necessary and sufficient condition that will guarantee that solutions of the optimization problem yield the global minimum cost. This constrained optimization problem occurs naturally in the computation of the phase margin for multivariable control systems. Our results guarantee that numerical routines can be developed that will converge to the global solution for the phase margin.     

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.     

Analytical solutions to the optimization of a quadratic cost function subject to linear and quadratic equality constraints

In the area of broad-band antenna array signal processing, the global minimum of a quadratic equality constrained quadratic cost minimization problem is often required. The problem posed is usually characterized by a large optimization space (around 50–90 tuples), a large number of linear equality constraints, and a few quadratic equality constraints each having very low rank quadratic constraint matrices. Two main difficulties arise in this class of problem. Firstly, the feasibility region is nonconvex and multiple local minima abound. This makes conventional numerical search techniques unattractive as they are unable to locate the global optimum consistently (unless a finite search area is specified). Secondly, the large optimization space makes the use of decision-method algorithms for the theory of the reals unattractive. This is because these algorithms involve the solution of the roots of univariate polynomials of order to the square of the optimization space. In this paper we present a new algorithm which exploits the structure of the constraints to reduce the optimization space to a more manageable size. The new algorithm relies on linear-algebra concepts, basic optimization theory, and a multivariate polynomial root-solving tool often used by decision-method algorithms.This research was supported by the Australian Research Council and the Corporative Research Centre for Broadband Telecommunications and Networking.     

A Dual Algorithm for Minimizing a Quadratic Function with Two Quadratic Constraints

In this paper, we present a dual algorithm for minimizing a convex quadratic function with two quadratic constraints. Such a minimization problem is a subproblem that appears in some trust region algorithms for general nonlinear programming. Some theoretical properties of the dual problem are given. Global convergence of the algorithm is proved and a local superlinear convergence result is presented. Numerical examples are also provided.     

Quadratic optimization problems in robust beamforming

This paper presents a class of constrained optimization problems whereby a quadratic cost function is to be minimized with respect to a weight vector subject to an inequality quadratic constraint on the weight vector. This class of constrained optimization problems arises as a result of a motivation for designing robust antenna array processors in the field of adaptive array processing. The constrained optimization problem is first solved by using the primal-dual method. Numerical techniques are presented to reduce the computational complexity of determining the optimal Lagrange multiplier and hence the optimal weight vector. Subsequently, a set of linear constraints or at most linear plus norm constraints are developed for approximating the performance achievable with the quadratic constraint. The use of linear constraints is very attractive, since they reduce the computational burden required to determine the optimal weight vector.     

Ellipsoidal Approach to Box-Constrained Quadratic Problems

We present a new heuristic for the global solution of box constrained quadratic problems, based on the classical results which hold for the minimization of quadratic problems with ellipsoidal constraints. The approach is tested on several problems randomly generated and on graph instances from the DIMACS challenge, medium size instances of the Maximum Clique Problem. The numerical results seem to suggest some effectiveness of the proposed approach.     

On the Indefinite Quadratic Fractional Optimization with Two Quadratic Constraints

In this paper, we consider minimizing the ratio of two indefinite quadratic functions subject to two quadratic constraints. Using the extension of Charnes–Cooper transformation, we transform the problem to a homogenized quadratic problem. Then, we show that, under certain assumptions, it can be solved to global optimality using semidefinite optimization relaxation.     

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.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming

When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida.     

On the role of continuously differentiable exact penalty functions in constrained global optimization

The aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an attraction point for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem.     

Global and Local Quadratic Minimization

We present a method which when applied to certain non-convex QP will locatethe globalminimum, all isolated local minima and some of the non-isolated localminima. The method proceeds by formulating a (multi) parametric convex QP interms ofthe data of the given non-convex QP. Based on the solution of the parametricQP,an unconstrained minimization problem is formulated. This problem ispiece-wisequadratic. A key result is that the isolated local minimizers (including theglobalminimizer) of the original non-convex problem are in one-to-one correspondencewiththose of the derived unconstrained problem.The theory is illustrated with several numerical examples. A numericalprocedure isdeveloped for a special class of non-convex QP's. It is applied to a problemfrom theliterature and verifies a known global optimum and in addition, locates apreviously unknown local minimum.     

Approximating Global Quadratic Optimization with Convex Quadratic Constraints

We consider the problem of approximating the global maximum of a quadratic program (QP) subject to convex non-homogeneous quadratic constraints. We prove an approximation quality bound that is related to a condition number of the convex feasible set; and it is the currently best for approximating certain problems, such as quadratic optimization over the assignment polytope, according to the best of our knowledge.     

有限维逼近无限维总极值的积分型方法

本文用有限维逼近无限维的方法来讨论函数空间中的总体最优化问题．我们给出了新的最优性条件和用变测度方法求得的有限维解逼近总体最优解的算法．对于有约柬问题，我们用不连续罚函数法把有约束问题化为无约束问题来求解．最后，我们通过一个具有非凸状态约束的最优控制问可题的实例来说明算法的有效性．     

Global Quadratic Minimization over Bivalent Constraints: Necessary and Sufficient Global Optimality Condition

In this paper, we establish global optimality conditions for quadratic optimization problems with quadratic equality and bivalent constraints. We first present a necessary and sufficient condition for a global minimizer of quadratic optimization problems with quadratic equality and bivalent constraints. Then we examine situations where this optimality condition is equivalent to checking the positive semidefiniteness of a related matrix, and so, can be verified in polynomial time by using elementary eigenvalues decomposition techniques. As a consequence, we also present simple sufficient global optimality conditions, which can be verified by solving a linear matrix inequality problem, extending several known sufficient optimality conditions in the existing literature.     

A Lagrangian approach to intrinsic linearized elasticity

We consider the pure traction problem and the pure displacement problem of three-dimensional linearized elasticity. We show that, in each case, the intrinsic approach leads to a quadratic minimization problem constrained by Donati-like relations. Using the Babu?ka–Brezzi inf–sup condition, we then show that, in each case, the minimizer of the constrained minimization problem found in an intrinsic approach is the first argument of the saddle-point of an ad hoc Lagrangian, so that the second argument of this saddle-point is the Lagrange multiplier associated with the corresponding constraints.     

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.     

Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems

In this paper we first establish a Lagrange multiplier condition characterizing a regularized Lagrangian duality for quadratic minimization problems with finitely many linear equality and quadratic inequality constraints, where the linear constraints are not relaxed in the regularized Lagrangian dual. In particular, in the case of a quadratic optimization problem with a single quadratic inequality constraint such as the linearly constrained trust-region problems, we show that the Slater constraint qualification (SCQ) is necessary and sufficient for the regularized Lagrangian duality in the sense that the regularized duality holds for each quadratic objective function over the constraints if and only if (SCQ) holds. A new theorem of the alternative for systems involving both equality constraints and two quadratic inequality constraints plays a key role. We also provide classes of quadratic programs, including a class of CDT-subproblems with linear equality constraints, where (SCQ) ensures regularized Lagrangian duality.     

Quadratic programming problems and related linear complementarity problems

This paper investigates the general quadratic programming problem, i.e., the problem of finding the minimum of a quadratic function subject to linear constraints. In the case where, over the set of feasible points, the objective function is bounded from below, this problem can be solved by the minimization of a linear function, subject to the solution set of a linear complementarity problem, representing the Kuhn-Tucker conditions of the quadratic problem.To detect in the quadratic problem the unboundedness from below of the objective function, necessary and sufficient conditions are derived. It is shown that, when these conditions are applied, the general quadratic programming problem becomes equivalent to the investigation of an appropriately formulated linear complementarity problem.This research was supported by the Hungarian Research Foundation, Grant No. OTKA/1044.