An Iterative Solver-Based Long-Step Infeasible Primal-Dual Path-Following Algorithm for Convex QP Based on a Class of Preconditioners

In this paper we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors’ previous paper \cite{ONE04}, we propose a new linear system, which we refer to as the \emph{hybrid augmented normal equation} (HANE), to … Read more

A General Robust-Optimization Formulation for Nonlinear Programming

Most research in robust optimization has so far been focused on inequality-only, convex conic programming with simple linear models for uncertain parameters. Many practical optimization problems, however, are nonlinear and non-convex. Even in linear programming, coefficients may still be nonlinear functions of uncertain parameters. In this paper, we propose robust formulations that extend the robust-optimization … Read more

Semidefinite-Based Branch-and-Bound for Nonconvex Quadratic Programming

This paper presents a branch-and-bound algorithm for nonconvex quadratic programming, which is based on solving semidefinite relaxations at each node of the enumeration tree. The method is motivated by a recent branch-and-cut approach for the box-constrained case that employs linear relaxations of the first-order KKT conditions. We discuss certain limitations of linear relaxations when handling … Read more

Constructing Generalized Mean Functions Using Convex Functions with Regularity Conditions

The generalized mean function has been widely used in convex analysis and mathematical programming. This paper studies a further generalization of such a function. A necessary and sufficient condition is obtained for the convexity of a generalized function. Additional sufficient conditions that can be easily checked are derived for the purpose of identifying some classes … Read more

Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials

Lov\’ asz and Schrijver [1991] have constructed semidefinite relaxations for the stable set polytope of a graph $G=(V,E)$ by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most $\alpha(G)$ steps, where $\alpha(G)$ is the stability number of $G$. Two other hierarchies of semidefinite bounds for the stability number have … Read more

A note 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, which corrects a result given in [9]. Article Download View A note on KKT points of homogeneous programs

Enlarging Neighborhoods of Interior-Point Algorithms for Linear Programming via Least Values of Proximity measure Functions

It is well known that a wide-neighborhood interior-point algorithm for linear programming performs much better in implementation than those small-neighborhood counterparts. In this paper, we provide a unified way to enlarge the neighborhoods of predictor-corrector interior-point algorithms for linear programming. We prove that our methods not only enlarge the neighborhoods but also retain the so-far … Read more

Computing Proximal Points on Nonconvex Functions

The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with … Read more

Jordan-algebraic approach to convexity theorem for quadratic mappings

We describe a Jordan-algebraic version of results related to convexity of images of quadratic mappings as well as related results on exactness of symmetric relaxations of certain classes of nonconvex optimization problems. The exactness of relaxations is proved based on rank estimates. Our approach provides a unifying viewpoint on a large number of classical results … Read more