On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems

Iterative solvers appear to be very promising in the development of efficient software, based on Interior Point methods, for large-scale nonlinear optimization problems. In this paper we focus on the use of preconditioned iterative techniques to solve the KKT system arising at each iteration of a Potential Reduction method for convex Quadratic Programming. We consider the augmented system approach and analyze the behaviour of the Constraint Preconditioner with the Conjugate Gradient algorithm. Comparisons with a direct solution of the augmented system and with MOSEK show the effectiveness of the iterative approach on large-scale sparse problems. Work partially supported by the Italian MIUR FIRB Project Large Scale Nonlinear Optimization, grant no. RBNE01WBBB.     

Lot-sizing with non-stationary cumulative capacities

We study a new class of capacitated economic lot-sizing problems. We show that the problem is NP-hard in general and derive a fully polynomial-time approximation algorithm under mild conditions on the cost functions. Furthermore, we develop a polynomial-time algorithm for the case where all cost functions are concave.     

The complexity of approximating a nonlinear program

We consider the problem of finding the maximum of a multivariate polynomial inside a convex polytope. We show that there is no polynomial time approximation algorithm for this problem, even one with a very poor guarantee, unless P = NP. We show that even when the polynomial is quadratic (i.e. quadratic programming) there is no polynomial time approximation unless NP is contained in quasi-polynomial time.Our results rely on recent advances in the theory of interactive proof systems. They exemplify an interesting interplay of discrete and continuous mathematics—using a combinatorial argument to get a hardness result for a continuous optimization problem.     

Sufficient conditions for the stability of the karush- kuhn - tucker point set in quadratic programming

We obtain some conditions under which a small perturbation in the data of a quadratic programming problem can yield only a small change in its Karush-Kuhn-Tucker point set. Convexity of the objective function and boundedness of the constraint set are not assumed. The obtained results are illustrated by several examples     

On KKT Points of Homogeneous Programs

Homogeneous programming is an important class of optimization problems. The purpose of this note is to give a truly equivalent characterization of KKT points of homogeneous programming problems, correcting a result given by Lasserre and Hiriart-Urruty in Ref. 1.Communicated by P. TsengThis work was partially supported by the National Natural Science Foundation of China, Grants 10201032 and 70221001, and by the Research Grants Council, Hong Kong, Grant CUHK4180/03E.The authors thank two anonymous referees for valuable remarks and insights that have helped improving the paper.     

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     

BFGS‐like updates of constraint preconditioners for sequences of KKT linear systems in quadratic programming

We focus on efficient preconditioning techniques for sequences of Karush‐Kuhn‐Tucker (KKT) linear systems arising from the interior point (IP) solution of large convex quadratic programming problems. Constraint preconditioners (CPs), although very effective in accelerating Krylov methods in the solution of KKT systems, have a very high computational cost in some instances, because their factorization may be the most time‐consuming task at each IP iteration. We overcome this problem by computing the CP from scratch only at selected IP iterations and by updating the last computed CP at the remaining iterations, via suitable low‐rank modifications based on a BFGS‐like formula. This work extends the limited‐memory preconditioners (LMPs) for symmetric positive definite matrices proposed by Gratton, Sartenaer and Tshimanga in 2011, by exploiting specific features of KKT systems and CPs. We prove that the updated preconditioners still belong to the class of exact CPs, thus allowing the use of the conjugate gradient method. Furthermore, they have the property of increasing the number of unit eigenvalues of the preconditioned matrix as compared with the generally used CPs. Numerical experiments are reported, which show the effectiveness of our updating technique when the cost for the factorization of the CP is high.     

On the convergence properties of Hildreth's quadratic programming algorithm

We prove the linear convergence rate of Hildreth's method for quadratic programming, in both its sequential and simulateneous versions. We give bounds on the asymptotic error constant and compare these bounds to those given by Mandel for the cyclic relaxation method for solving linear inequalities.Research of this author was partially supported by CNPq grant No. 301280/86.On leave from the Universidade Federal do Rio de Janeiro, Instituto de Matemática, Rio de Janeiro, R.J. 21.910, Brazil. Research of this author was partially supported by NIH grant HL28438.     

On approximating complex quadratic optimization problems via semidefinite programming relaxations

In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite. This research was supported in part by NSF grant DMS-0306611.     

Some properties of generalized proximal point methods for quadratic and linear programming

The proximal point method for convex optimization has been extended recently through the use of generalized distances (e.g., Bregman distances) instead of the Euclidean one. One advantage of these extensions is the possibility of eliminating certain constraints (mainly positivity) from the subproblems, transforming an inequality constrained problem into a sequence of unconstrained or equality constrained problems. We consider here methods obtained using a certain class of Bregman functions applied to convex quadratic (including linear) programming, which are of the interior-point type. We prove that the limit of the sequence generated by the method lies in the relative interior of the solution set, and furthermore is the closest optimal solution to the initial point, in the sense of the Bregman distance. These results do not hold for the standard proximal point method, i.e., when the square of the Euclidean norm is used as the Bregman distance.The research leading to this paper was partially supported by CNPq Grant 301280/86.We thank two anonymous referees whose comments and suggestions allowed us to improve our results in a significant way.     

A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions

This paper presents a theoretical result on convergence of a primal affine-scaling method for convex quadratic programs. It is shown that, as long as the stepsize is less than a threshold value which depends on the input data only, Ye and Tse's interior ellipsoid algorithm for convex quadratic programming is globally convergent without nondegeneracy assumptions. In addition, its local convergence rate is at least linear and the dual iterates have an ergodically convergent property.Research supported in part by the NSF under grant DDM-8721709.     

An optimal algorithm for a class of equality constrained quadratic programming problems with bounded spectrum

The implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for the solution of large convex equality constrained quadratic programming problems is considered. It is proved that if the auxiliary problems are approximately solved by the conjugate gradient method, then the algorithm finds an approximate solution of the class of problems with uniformly bounded spectrum of the Hessian matrix at O(1) matrix–vector multiplications. If applied to the class of problems with the Hessian matrices that are in addition either sufficiently sparse or can be expressed as a product of such sparse matrices, then the cost of the solution is proportional to the dimension of the problems. Theoretical results are illustrated by numerical experiments. This research is supported by grants of the Ministry of Education No. S3086102, ET400300415 and MSM 6198910027.     

Finding discrete global minima with a filled function for integer programming

The filled function method is an approach to find the global minimum of multidimensional functions. This paper proposes a new definition of the filled function for integer programming problem. A filled function which satisfies this definition is presented. Furthermore, we discuss the properties of the filled function and design a new filled function algorithm. Numerical experiments on several test problems with up to 50 integer variables have demonstrated the applicability and efficiency of the proposed method.     

Computational study of a family of mixed-integer quadratic programming problems

We present computational experience with a branch-and-cut algorithm to solve quadratic programming problems where there is an upper bound on the number of positive variables. Such problems arise in financial applications. The algorithm solves the largest real-life problems in a few minutes of run-time.     

Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization

This paper proves local convergence rates of primal-dual interior point methods for general nonlinearly constrained optimization problems. Conditions to be satisfied at a solution are those given by the usual Jacobian uniqueness conditions. Proofs about convergence rates are given for three kinds of step size rules. They are: (i) the step size rule adopted by Zhang et al. in their convergence analysis of a primal-dual interior point method for linear programs, in which they used single step size for primal and dual variables; (ii) the step size rule used in the software package OB1, which uses different step sizes for primal and dual variables; and (iii) the step size rule used by Yamashita for his globally convergent primal-dual interior point method for general constrained optimization problems, which also uses different step sizes for primal and dual variables. Conditions to the barrier parameter and parameters in step size rules are given for each case. For these step size rules, local and quadratic convergence of the Newton method and local and superlinear convergence of the quasi-Newton method are proved. A preliminary version of this paper was presented at the conference “Optimization-Models and Algorithms” held at the Institute of Statistical Mathematics, Tokyo, March 1993.     

A numerically efficient procedure for the Theil-Van de Panne quadratic programming method

A procedure is given for implementing the Theil-Van de Panne algorithm, which utilizes the Cholesky decomposition to reduce the computations involved in matrix inversions.