Two properties of condition numbers for convex programs via implicitly defined barrier functions

We study two issues on condition numbers for convex programs: one has to do with the growth of the condition numbers of the linear equations arising in interior-point algorithms; the other deals with solving conic systems and estimating their distance to infeasibility.?These two issues share a common ground: the key tool for their development is a simple, novel perspective based on implicitly-defined barrier functions. This tool has potential use in optimization beyond the context of condition numbers. Received: October 2000 / Accepted: October 2001?Published online March 27, 2002     

Dual versus primal-dual interior-point methods for linear and conic programming

We observe a curious property of dual versus primal-dual path-following interior-point methods when applied to unbounded linear or conic programming problems in dual form. While primal-dual methods can be viewed as implicitly following a central path to detect primal infeasibility and dual unboundedness, dual methods can sometimes implicitly move away from the analytic center of the set of infeasibility/unboundedness detectors. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

On the behavior of the homogeneous self-dual model for conic convex optimization

There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model's behavior are precisely controlled independent of the problem instance: (i) the sizes of ɛ-optimal solutions, and (ii) the maximum distance of ɛ-optimal solutions to the boundary of the cone of the HSD variables. This norm is also useful in developing a stopping-rule theory for HSD-based interior-point solvers such as SeDuMi. Under mild assumptions, we show that a standard stopping rule implicitly involves the sum of the sizes of the ɛ-optimal primal and dual solutions, as well as the size of the initial primal and dual infeasibility residuals. This theory suggests possible criteria for developing starting points for the homogeneous self-dual model that might improve the resulting solution time in practice. This research has been partially supported through the MIT-Singapore Alliance.     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

Path-following interior point algorithms for the Cartesian <Emphasis Type="Italic">P</Emphasis><Subscript>*</Subscript>(κ)-LCP over symmetric cones

In this paper, we establish a theoretical framework of path-following interior point algorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P _*(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P _*(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms. This work was supported by National Natural Science Foundation of China (Grant Nos. 10671010, 70841008)     

Lifting for conic mixed-integer programming

Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify the computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative orthants, conic lifting reduces to the lifting for linear integer programming as one may expect.     

Characterizations of interiors of feasible and infeasible data instances and feasibility for conic linear programming

In this paper, we present simple proofs for the main results that appear in Nunez (Math Program 91:375–390, 2002) using a lemma in Freund and Vera (Math Program 86:225–260, 1999) for conic linear programming. Connections between interiors and boundaries of feasible and infeasible data instances and weak and strong feasibilities of a conic linear programming primal-dual pair are made.     

Inverse conic programming with applications

Linear programming duality yields efficient algorithms for solving inverse linear programs. We show that special classes of conic programs admit a similar duality and, as a consequence, establish that the corresponding inverse programs are efficiently solvable. We discuss applications of inverse conic programming in portfolio optimization and utility function identification.     

On implementing a primal-dual interior-point method for conic quadratic optimization

 Based on the work of the Nesterov and Todd on self-scaled cones an implementation of a primal-dual interior-point method for solving large-scale sparse conic quadratic optimization problems is presented. The main features of the implementation are it is based on a homogeneous and self-dual model, it handles rotated quadratic cones directly, it employs a Mehrotra type predictor-corrector extension and sparse linear algebra to improve the computational efficiency. Finally, the implementation exploits fixed variables which naturally occurs in many conic quadratic optimization problems. This is a novel feature for our implementation. Computational results are also presented to document that the implementation can solve very large problems robustly and efficiently. Received: November 18, 2000 / Accepted: January 18, 2001 Published online: September 27, 2002 Key Words. conic optimization – interior-point methods – large-scale implementation     

Return-mapping algorithms for associative isotropic hardening plasticity using conic optimization

We present a mathematical programming approach for elastoplastic constitutive initial value problems. Consideration of the associative plasticity and a linear isotropic hardening model allowed us to formulate the local discrete constitutive equations as conic programs. Specifically, we demonstrate that implicit return-mapping schemes for well-known yield criteria, such as the Rankine, von Mises, Tresca, Drucker-Prager, and Mohr–Coulomb criteria, can be expressed as second-order and semidefinite conic programs. Additionally, we propose a novel scheme for the numerical evaluation of the consistent elastoplastic tangent operator based on a first-order parameter derivative of the optimal solutions.     

Sampling subproblems of heterogeneous Max‐Cut problems and approximation algorithms

Recent work in the analysis of randomized approximation algorithms for NP‐hard optimization problems has involved approximating the solution to a problem by the solution of a related subproblem of constant size, where the subproblem is constructed by sampling elements of the original problem uniformly at random. In light of interest in problems with a heterogeneous structure, for which uniform sampling might be expected to yield suboptimal results, we investigate the use of nonuniform sampling probabilities. We develop and analyze an algorithm which uses a novel sampling method to obtain improved bounds for approximating the Max‐Cut of a graph. In particular, we show that by judicious choice of sampling probabilities one can obtain error bounds that are superior to the ones obtained by uniform sampling, both for unweighted and weighted versions of Max‐Cut. Of at least as much interest as the results we derive are the techniques we use. The first technique is a method to compute a compressed approximate decomposition of a matrix as the product of three smaller matrices, each of which has several appealing properties. The second technique is a method to approximate the feasibility or infeasibility of a large linear program by checking the feasibility or infeasibility of a nonuniformly randomly chosen subprogram of the original linear program. We expect that these and related techniques will prove fruitful for the future development of randomized approximation algorithms for problems whose input instances contain heterogeneities. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems

Convex quadratically constrained quadratic problems are considered. It is shown that such problems can be transformed to aconic form. The feasible set of the conic form is the intersection of a direct product of standard quadratic cones intersected with a hyperplane (the analogue of a simplex), and a linear subspace. For a problem of such form, the analogue of Karmarkar's projective transformation and logarithmic barrier function are built. This allows us to extend “word by word” the method of Karmarkar for LP to QCQP and allows us to obtain a similar polynomial worst-case bound for the number of iterations.     

Computer Codes for the Analysis of Infeasible Linear Programs

As linear programs have grown larger and more complex, infeasible models are appearing more frequently. Because of the scale and complexity of the models, automated assistance is very often needed in determining the cause of the infeasibility so that model repairs can be made. Fortunately, researchers have developed algorithms for analysing infeasible LPs in recent years, and these have lately found their way into commercial LP computer codes. This paper briefly reviews the underlying algorithms, surveys the computer codes, and compares their performance on a set of test problems.     

Quadratic double-ratio minimax optimization

The quadratic double-ratio minimax optimization (QRM) admits a generalized linear conic fractional reformulation. It leads to two algorithms to globally solve (QRM) from the primal and dual sides, respectively. The hidden convexity of (QRM) remains unknown except for the special case when both denominators are equal.     

Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems

ln) iterations, where ν is the parameter of a self-concordant barrier for the cone, ε is a relative accuracy and ρ_f is a feasibility measure. We also discuss the behavior of path-following methods as applied to infeasible problems. We prove that strict infeasibility (primal or dual) can be detected in O(ln) iterations, where ρ_· is a primal or dual infeasibility measure. Received April 25, 1996 / Revised version received March 4, 1998 Published online October 9, 1998     

Development of effective algorithms for detecting breakdowns in models of systems

For a linear dynamic system with undetermined parameters we discuss the construction of algorithms and programs to exhibit breakdown criteria for breakdowns using Kalman filtering and sequential statistical analysis. Translated fromAlgoritmy Upravleniya i Identifikatsii, pp. 118–128, 1997.     

Blocking Sets Of External Lines To A Conic In PG(2,q), q ODD

We determine all point-sets of minimum size in PG(2,q), q odd that meet every external line to a conic in PG(2,q). The proof uses a result on the linear system of polynomials vanishing at every internal point to the conic and a corollary to the classification theorem of all subgroups of PGL(2,q). * Research supported by the Italian Ministry MURST, Strutture geometriche, combinatoria e loro applicazioni and by the Hungarian-Italian Intergovernemental project “Algebraic and Geometric Structures”.     

On duality gap in linear conic problems

In their paper “Duality of linear conic problems” Shapiro and Nemirovski considered two possible properties (A) and (B) for dual linear conic problems (P) and (D). The property (A) is “If either (P) or (D) is feasible, then there is no duality gap between (P) and (D)”, while property (B) is “If both (P) and (D) are feasible, then there is no duality gap between (P) and (D) and the optimal values val(P) and val(D) are finite”. They showed that (A) holds if and only if the cone K is polyhedral, and gave some partial results related to (B). Later Shapiro conjectured that (B) holds if and only if all the nontrivial faces of the cone K are polyhedral. In this note we mainly prove that both the “if” and “only if” parts of this conjecture are not true by providing examples of closed convex cone in \mathbbR⁴{\mathbb{R}^{4}} for which the corresponding implications are not valid. Moreover, we give alternative proofs for the results related to (B) established by Shapiro and Nemirovski.     

A geometric analysis of Renegar’s condition number,and its interplay with conic curvature

For a conic linear system of the form Ax ∈K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Among these, Renegar’s condition number is arguably the most prominent for its relation to data perturbation, error bounds, problem geometry, and computational complexity of algorithms. Nonetheless, is a representation-dependent measure which is usually difficult to interpret and may lead to overly conservative bounds of computational complexity and/or geometric quantities associated with the set of feasible solutions. Herein we show that Renegar’s condition number is bounded from above and below by certain purely geometric quantities associated with A and K; furthermore our bounds highlight the role of the singular values of A and their relationship with the condition number. Moreover, by using the notion of conic curvature, we show how Renegar’s condition number can be used to provide both lower and upper bounds on the width of the set of feasible solutions. This complements the literature where only lower bounds have heretofore been developed.