A canonical dual approach for solving linearly constrained quadratic programs

This paper provides a canonical dual approach for minimizing a general quadratic function over a set of linear constraints. We first perturb the feasible domain by a quadratic constraint, and then solve a “restricted” canonical dual program of the perturbed problem at each iteration to generate a sequence of feasible solutions of the original problem. The generated sequence is proven to be convergent to a Karush-Kuhn-Tucker point with a strictly decreasing objective value. Some numerical results are provided to illustrate the proposed approach.     

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

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

A New Self-Dual Embedding Method for Convex Programming

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.     

Optimization of dual response systems: A comprehensive procedure for degenerate and nondegenerate problems

Most dual response systems (DRSs) arising in response surface modeling can be approximated using a nonlinear (and typically nonconvex) mathematical program involving two quadratic functions. One of the quadratic functions is used as the objective function, the other for imposing a target constraint. This paper describes an effective heuristic for computing global (or near-global) optimal solutions for this type of problem. The first part of the paper addresses the special case of degeneracy, a condition that makes the system more difficult to solve. Included are means for detecting degeneracy as well as issues relating to its likelihood in practice. The subsequent part of the paper describes our new procedure, AXIS, which rotates a degenerate problem and then decomposes it into a finite sequence of nondegenerate subproblems of lower dimension. The nondegenerate subproblems are solved using the algorithm DRSALG developed earlier. In the final parts of the paper, the AXIS and DRSALG algorithms are integrated into a single dual response solver termed DR2. DR2 is tested against two nonlinear optimization procedures that have been used frequently in dual response applications. The new solver proves to be extremely effective at locating best-practice operating conditions.     

On the convergence of a class of outer approximation algorithms for convex programs

This paper presents a new class of outer approximation methods for solving general convex programs. The methods solve at each iteration a subproblem whose constraints contain the feasible set of the original problem. Moreover, the methods employ quadratic objective functions in the subproblems by adding a simple quadratic term to the objective function of the original problem, while other outer approximation methods usually use the original objective function itself throughout the iterations. By this modification, convergence of the methods can be proved under mild conditions. Furthermore, it is shown that generalized versions of the cut construction schemes in Kelley-Cheney-Goldstein's cutting plane method and Veinott's supporting hyperplane method can be incorporated with the present methods and a cut generated at each iteration need not be retained in the succeeding iterations.     

Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a suitable approach for solving such programs. However, the program does not become more tractable if this method is used, since Benders' cuts are quadratic in the integer variables. A new equivalent formulation that renders the program tractable is developed, under which the dual objective function is linear in the integer variables and the dual constraint set is independent of these variables. Benders' cuts that are derived from the new formulation are linear in the integer variables, and the original problem is decomposed into a series of integer linear master problems and standard quadratic subproblems. The new formulation does not introduce new primary variables or new constraints into the computational steps of the decomposition algorithm.The author wishes to thank two anonymous referees for their helpful comments and suggestions for revising the paper.     

Bounding a class of nonconvex linearly-constrained resource allocation problems via the surrogate dual

We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An important class of algorithms for the linearly constrained minimization of nonconvex cost functions utilize the branch and bound approach, using convex underestimating cost functions to compute the lower bounds.We suggest instead the use of the surrogate dual problem to bound subproblems. We show that the success of the surrogate dual in fathoming subproblems in a branch and bound algorithm may be determined without directly solving the surrogate dual itself, but that a simple test of the feasibility of a certain linear system of inequalities will suffice. This test is interpreted geometrically and used to characterize the extreme points and extreme rays of the optimal value function's level sets.Research partially supported by NSF under grant # ENG77-06555.     

A primal-dual augmented Lagrangian

Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we consider the formulation of subproblems in which the objective function is a generalization of the Hestenes-Powell augmented Lagrangian function. The main feature of the generalized function is that it is minimized with respect to both the primal and the dual variables simultaneously. The benefits of this approach include: (i) the ability to control the quality of the dual variables during the solution of the subproblem; (ii) the availability of improved dual estimates on early termination of the subproblem; and (iii) the ability to regularize the subproblem by imposing explicit bounds on the dual variables. We propose two primal-dual variants of conventional primal methods: a primal-dual bound constrained Lagrangian (pdBCL) method and a primal-dual ℓ ₁ linearly constrained Lagrangian (pdℓ ₁LCL) method. Finally, a new sequential quadratic programming (pdSQP) method is proposed that uses the primal-dual augmented Lagrangian as a merit function.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

On piecewise quadratic Newton and trust region problems

Some recent algorithms for nonsmooth optimization require solutions to certain piecewise quadratic programming subproblems. Two types of subproblems are considered in this paper. The first type seeks the minimization of a continuously differentiable and strictly convex piecewise quadratic function subject to linear equality constraints. We prove that a nonsmooth version of Newton’s method is globally and finitely convergent in this case. The second type involves the minimization of a possibly nonconvex and nondifferentiable piecewise quadratic function over a Euclidean ball. Characterizations of the global minimizer are studied under various conditions. The results extend a classical result on the trust region problem. Partially supported by National University of Singapore under grant 930033.     

Primal-relaxed dual global optimization approach

A deterministic global optimization approach is proposed for nonconvex constrained nonlinear programming problems. Partitioning of the variables, along with the introduction of transformation variables, if necessary, converts the original problem into primal and relaxed dual subproblems that provide valid upper and lower bounds respectively on the global optimum. Theoretical properties are presented which allow for a rigorous solution of the relaxed dual problem. Proofs of -finite convergence and -global optimality are provided. The approach is shown to be particularly suited to (a) quadratic programming problems, (b) quadratically constrained problems, and (c) unconstrained and constrained optimization of polynomial and rational polynomial functions. The theoretical approach is illustrated through a few example problems. Finally, some further developments in the approach are briefly discussed.The authors gratefully acknowledge financial support from National Science Foundation Presidential Young Investigator Award CBT-88-57013. The authors are also grateful to Drs. F. A. Al-Khayyal, B. Jaumard, P. M. Pardalos, and H. D. Sherali for helpful comments on an earlier draft of this paper.     

A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming

The constraint selection approach to linear programming begins by solving a relaxed version of the problem using only a few of the original constraints. If the solution obtained to this relaxation satisfies the remaining constraints it is optimal for the original LP. Otherwise, additional constraints must be incorporated in a larger relaxation. The procedure successively generates larger subproblems until an optimal solution is obtained which satisfies all of the original constraints. Computational results for a dual simplex implementation of this technique indicate that solving several small subproblems in this manner is more computationally efficient than solving the original LP using the revised simplex method.     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality

This paper presents a canonical duality theory for solving a general nonconvex quadratic minimization problem with nonconvex constraints. By using the canonical dual transformation developed by the first author, the nonconvex primal problem can be converted into a canonical dual problem with zero duality gap. A general analytical solution form is obtained. Both global and local extrema of the nonconvex problem can be identified by the triality theory associated with the canonical duality theory. Illustrative applications to quadratic minimization with multiple quadratic constraints, box/integer constraints, and general nonconvex polynomial constraints are discussed, along with insightful connections to classical Lagrangian duality. Criteria for the existence and uniqueness of optimal solutions are presented. Several numerical examples are provided.     

Fuzzy Bayesian estimation on lifetime data

Summary  The Bayesian estimation on lifetime data under fuzzy environments is proposed in this paper. In order to apply the Bayesian approach, the fuzzy parameters are assumed as fuzzy random variables with fuzzy prior distributions. The (conventional) Bayesian estimation method will be used to create the fuzzy Bayes point estimator by invoking the well-known theorem called “Resolution Identity” in fuzzy set theory. On the other hand, we also provide computational procedures to evaluate the membership degree of any given Bayes point estimate. In order to achieve this purpose, we transform the original problem into a nonlinear programming problem. This nonlinear programming problem is then divided into four subproblems for the purpose of simplifying computation. Finally, the subproblems can be solved by using any commercial optimizers, e.g., GAMS or LINDO.     

Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming

This paper presents a perfect duality theory and a complete set of solutions to nonconvex quadratic programming problems subjected to inequality constraints. By use of the canonical dual transformation developed recently, a canonical dual problem is formulated, which is perfectly dual to the primal problem in the sense that they have the same set of KKT points. It is proved that the KKT points depend on the index of the Hessian matrix of the total cost function. The global and local extrema of the nonconvex quadratic function can be identified by the triality theory [11]. Results show that if the global extrema of the nonconvex quadratic function are located on the boundary of the primal feasible space, the dual solutions should be interior points of the dual feasible set, which can be solved by deterministic methods. Certain nonconvex quadratic programming problems in {\open {R}}^{n} can be converted into a dual problem with only one variable. It turns out that a complete set of solutions for quadratic programming over a sphere is obtained as a by-product. Several examples are illustrated.     

Prices stabilization for inexact unit-commitment problems

A widespread and successful approach to tackle unit-commitment problems is constraint decomposition: by dualizing the linking constraints, the large-scale nonconvex problem decomposes into smaller independent subproblems. The dual problem consists then in finding the best Lagrangian multiplier (the optimal “price”); it is solved by a convex nonsmooth optimization method. Realistic modeling of technical production constraints makes the subproblems themselves difficult to solve exactly. Nonsmooth optimization algorithms can cope with inexact solutions of the subproblems. In this case however, we observe that the computed dual solutions show a noisy and unstable behaviour, that could prevent their use as price indicators. In this paper, we present a simple and easy-to-implement way to stabilize dual optimal solutions, by penalizing the noisy behaviour of the prices in the dual objective. After studying the impact of a general stabilization term on the model and the resolution scheme, we focus on the penalization by discrete total variation, showing the consistency of the approach. We illustrate our stabilization on a synthetic example, and real-life problems from EDF (the French Electricity Board).     

A hybrid algorithm for the minimum bounding sphere problem

Two primal approaches, the shrinking approach and the dual approach, have been studied for the exact Minimum Bounding Sphere (MBS) problem. In this paper, we present a dual algorithm that uses the shrinking approach to solve subproblems. The experiments show our hybrid algorithm is faster than the dedicated shrinking algorithm and dual algorithm for solving the exact MBS problem in large point sets.