Geometry of optimality conditions and constraint qualifications: The convex case

The cones of directions of constancy are used to derive: new as well as known optimality conditions; weakest constraint qualifications; and regularization techniques, for the convex programming problem. In addition, the badly behaved set of constraints, i.e. the set of constraints which causes problems in the Kuhn—Tucker theory, is isolated and a computational procedure for checking whether a feasible point is regular or not is presented.This research was supported by the National Research Council of Canada and le Gouvernement du Quebec and is part of the author's Ph.D. Dissertation done at McGill University, Montreal, Que., under the guidance of Professor S. Zlobec.     

Generalizations of Slater's constraint qualification for infinite convex programs

In this paper we study constraint qualifications and duality results for infinite convex programs (P) = inf{f(x): g(x) – S, x C}, whereg = (g ₁,g ₂) andS = S ₁ ×S ₂,S _i are convex cones,i = 1, 2,C is a convex subset of a vector spaceX, andf andg _i are, respectively, convex andS _i -convex,i = 1, 2. In particular, we consider the special case whenS ₂ is in afinite dimensional space,g ₂ is affine andS ₂ is polyhedral. We show that a recently introduced simple constraint qualification, and the so-called quasi relative interior constraint qualification both extend to (P), from the special case thatg = g ₂ is affine andS = S ₂ is polyhedral in a finite dimensional space (the so-called partially finite program). This provides generalized Slater type conditions for (P) which are much weaker than the standard Slater condition. We exhibit the relationship between these two constraint qualifications and show how to replace the affine assumption ong ₂ and the finite dimensionality assumption onS ₂, by a local compactness assumption. We then introduce the notion of strong quasi relative interior to get parallel results for more general infinite dimensional programs without the local compactness assumption. Our basic tool reduces to guaranteeing the closure of the sum of two closed convex cones.     

Bounds for eigenvalues using traces

Several new inequalities are obtained for the modulus, the real part, and the imaginary part of a linear combination of the ordered eigenvalues of a square complex matrix. Included are bounds for the condition number, the spread, and the spectral radius. These inequalities involve the trace of a matrix and the trace of its square. Necessary and sufficient conditions for equality are given for each inequality.     

Method of reduction in convex programming

We present an algorithm which solves a convex program with faithfully convex (not necessarily differentiable) constraints. While finding a feasible starting point, the algorithm reduces the program to an equivalent program for which Slater's condition is satisfied. Included are algorithms for calculating various objects which have recently appeared in the literature. Stability of the algorithm is discussed.     

Low-rank matrix completion using nuclear norm minimization and facial reduction

We consider a global optimization problem for Lipschitz-continuous functions with an unknown Lipschitz constant. Our approach is based on the well-known DIRECT (DIviding RECTangles) algorithm and motivated by the diagonal partitioning strategy. One of the main advantages of the diagonal partitioning scheme is that the objective function is evaluated at two points at each hyper-rectangle and, therefore, more comprehensive information about the objective function is considered than using the central sampling strategy used in most DIRECT-type algorithms. In this paper, we introduce a new DIRECT-type algorithm, which we call BIRECT (BIsecting RECTangles). In this algorithm, a bisection is used instead of a trisection which is typical for diagonal-based and DIRECT-type algorithms. The bisection is preferable to the trisection because of the shapes of hyper-rectangles, but usual evaluation of the objective function at the center or at the endpoints of the diagonal are not favorable for bisection. In the proposed algorithm the objective function is evaluated at two points on the diagonal equidistant between themselves and the endpoints of a diagonal. This sampling strategy enables reuse of the sampling points in descendant hyper-rectangles. The developed algorithm gives very competitive numerical results compared to the DIRECT algorithm and its well know modifications.     

Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem

We investigate new bounding strategies based on different relaxations of the quadratic assignment problem. In particular, we improve the lower bound found by using an eigenvalue decomposition of the quadratic part and by solving a linear program for the linear part. The improvement is accomplished by applying a steepest ascent algorithm to the sum of the two bounds.Both authors would like to thank the Natural Sciences and Engineering Research Council Canada and the Austrian Government for their support.This author would like to acknowledge partial support from the Department of Combinatorics and Optimization at the University of Waterloo.Research partially supported by Natural Sciences and Engineering Research Council Canada.     

Generating and measuring instances of hard semidefinite programs

Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal–dual strictly complementary optimal solution pair. On the other hand, there exist Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if a constraint qualification, e.g., Slater’s condition (strict feasibility) holds. Measures of strict feasibility, also called distance to infeasibility, have been used in complexity analysis, and, it is known that (near) loss of strict feasibility results in numerical difficulties. In addition, there exist SDP problems which have a zero duality gap but no strict complementary primal–dual optimal solution. We refer to these problems as hard instances of SDP. The assumption of strict complementarity is essential for asymptotic superlinear and quadratic rate convergence proofs. In this paper, we introduce a procedure for generating hard instances of SDP with a specified complementarity nullity (the dimension of the common nullspace of primal–dual optimal pairs). We then show, empirically, that the complementarity nullity correlates well with the observed local convergence rate and the number of iterations required to obtain optimal solutions to a specified accuracy, i.e., we show, even when Slater’s condition holds, that the loss of strict complementarity results in numerical difficulties. We include two new measures of hardness that correlate well with the complementarity nullity.     

ADMM for the SDP relaxation of the QAP

Semidefinite programming, SDP, relaxations have proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem, QAP, arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal–dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers ADMM in combination with facial reduction, FR, to solve the SDP relaxation. This first order approach allows for: inexpensive iterations, a method of cheaply obtaining low rank solutions; and a trivial way of exploiting the FR for adding cutting plane inequalities. In fact, we solve the doubly nonnegative, DNN, relaxation that includes both the SDP and all the nonnegativity constraints. When compared to current approaches and current best available bounds we obtain robustness, efficiency and improved bounds.     

Regularization using a parameterized trust region subproblem

We present a new method for regularization of ill-conditioned problems, such as those that arise in image restoration or mathematical processing of medical data. The method extends the traditional trust-region subproblem, TRS, approach that makes use of the L-curve maximum curvature criterion, a strategy recently proposed to find a good regularization parameter. We apply a parameterized trust region approach to estimate the region of maximum curvature of the L-curve and find the regularized solution. This exploits the close connections between various parameters used to solve TRS. A MATLAB code for the algorithm is tested and a comparison to the conjugate gradient least squares, CGLS, approach is given and analysed.