Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming

In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method (Nesterov in Doklady AN SSSR 269:543–547, 1983; Math Program 103:127–152, 2005), Nesterov’s smooth approximation scheme (Nesterov in Math Program 103:127–152, 2005), and Nemirovski’s prox-method (Nemirovski in SIAM J Opt 15:229–251, 2005), and propose a variant of Nesterov’s optimal method which has outperformed the latter one in our computational experiments. We also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of the cone programming problem. The performance of these methods is then compared using a set of randomly generated linear programming and semidefinite programming instances. We also compare the approach based on the variant of Nesterov’s optimal method with the low-rank method proposed by Burer and Monteiro (Math Program Ser B 95:329–357, 2003; Math Program 103:427–444, 2005) for solving a set of randomly generated SDP instances.     

New stopping criteria for detecting infeasibility in conic optimization

Detecting infeasibility in conic optimization and providing certificates for infeasibility pose a bigger challenge than in the linear case due to the lack of strong duality. In this paper we generalize the approximate Farkas lemma of Todd and Ye (Math Program 81:1–22, 1998) from the linear to the general conic setting, and use it to propose stopping criteria for interior point algorithms using self-dual embedding. The new criteria can identify if the solutions have large norm, thus they give an indication of infeasibility. The modified algorithms enjoy the same complexity bounds as the original ones, without assuming that the problem is feasible. Issues about the practical application of the criteria are also discussed. The authors were supported by the Canada Research Chairs program, NSERC Discovery Grant #5-48923 and MITACS.     

Cascading: an adjusted exchange method for robust conic programming

It is well known that the robust counterpart introduced by Ben-Tal and Nemirovski (Math Oper Res 23:769–805, 1998) increases the numerical complexity of the solution compared to the original problem. Kočvara, Nemirovski and Zowe therefore introduced in Kočvara et al. (Comput Struct 76:431–442, 2000) an approximation algorithm for the special case of robust material optimization, called cascading. As the title already indicates, we will show that their method can be seen as an adjustment of standard exchange methods to semi-infinite conic programming. We will see that the adjustment can be motivated by a suitable reformulation of the robust conic problem.      

Support vector machine via nonlinear rescaling method

In this paper we construct the linear support vector machine (SVM) based on the nonlinear rescaling (NR) methodology (see [Polyak in Math Program 54:177–222, 1992; Polyak in Math Program Ser A 92:197–235, 2002; Polyak and Teboulle in Math Program 76:265–284, 1997] and references therein). The formulation of the linear SVM based on the NR method leads to an algorithm which reduces the number of support vectors without compromising the classification performance compared to the linear soft-margin SVM formulation. The NR algorithm computes both the primal and the dual approximation at each step. The dual variables associated with the given data-set provide important information about each data point and play the key role in selecting the set of support vectors. Experimental results on ten benchmark classification problems show that the NR formulation is feasible. The quality of discrimination, in most instances, is comparable to the linear soft-margin SVM while the number of support vectors in several instances were substantially reduced.     

Mingling: mixed-integer rounding with bounds

Mixed-integer rounding (MIR) is a simple, yet powerful procedure for generating valid inequalities for mixed-integer programs. When used as cutting planes, MIR inequalities are very effective for mixed-integer programming problems with unbounded integer variables. For problems with bounded integer variables, however, cutting planes based on lifting techniques appear to be more effective. This is not surprising as lifting techniques make explicit use of the bounds on variables, whereas the MIR procedure does not. In this paper we describe a simple procedure, which we call mingling, for incorporating variable bound information into MIR. By explicitly using the variable bounds, the mingling procedure leads to strong inequalities for mixed-integer sets with bounded variables. We show that facets of mixed-integer knapsack sets derived earlier by superadditive lifting techniques can be obtained by the mingling procedure. In particular, the mingling inequalities developed in this paper subsume the continuous cover and reverse continuous cover inequalities of Marchand and Wolsey (Math Program 85:15–33, 1999) as well as the continuous integer knapsack cover and pack inequalities of Atamtürk (Math Program 98:145–175, 2003; Ann Oper Res 139:21–38, 2005). In addition, mingling inequalities give a generalization of the two-step MIR inequalities of Dash and Günlük (Math Program 105:29–53, 2006) under some conditions.     

On the extreme inequalities of infinite group problems

Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23–85, 1972) to generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res Lett 30(2):74–82, 2002), Dash and Günlük (Proceedings 10th conference on integer programming and combinatorial optimization. Springer, Heidelberg, pp 33–45 (2004), Math Program 106:29–53, 2006) and Richard et al. (Math Program 2008, to appear). We also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining extreme inequalities for infinite group relaxations of mixed integer programs are continuous. S.S. Dey and J.-P.P. Richard was supported by NSF Grant DMI-03-48611.     

Constant-Rank Condition and Second-Order Constraint Qualification

The constant-rank condition for feasible points of nonlinear programming problems was defined by Janin (Math. Program. Study 21:127–138, 1984). In that paper, the author proved that the constant-rank condition is a first-order constraint qualification. In this work, we prove that the constant-rank condition is also a second-order constraint qualification. We define other second-order constraint qualifications.     

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.     

Strong calmness of perturbed KKT system for a class of conic programming with degenerate solutions

ABSTRACT

This paper is concerned with the strong calmness of the KKT solution mapping for a class of canonically perturbed conic programming, which plays a central role in achieving fast convergence under situations when the Lagrange multiplier associated to a solution of these conic optimization problems is not unique. We show that the strong calmness of the KKT solution mapping is equivalent to a local error bound for the solutions to the perturbed KKT system, and is also equivalent to the pseudo-isolated calmness of the stationary point mapping along with the calmness of the multiplier set mapping at the corresponding reference point. Sufficient conditions are also provided for the strong calmness by establishing the pseudo-isolated calmness of the stationary point mapping in terms of the noncriticality of the associated multiplier, and the calmness of the multiplier set mapping in terms of a relative interior condition for the multiplier set. These results cover and extend the existing ones in Hager and Gowda [Stability in the presence of degeneracy and error estimation. Math Program. 1999;85:181–192]; Izmailov and Solodov [Stabilized SQP revisited. Math Program. 2012;133:93–120] for nonlinear programming and in Cui et al. [On the asymptotic superlinear convergence of the augmented Lagrangian method for semidefinite programming with multiple solutions. 2016, arXiv: 1610.00875v1]; Zhang and Zhang [Critical multipliers in semidefinite programming. 2018, arXiv: 1801.02218v1] for semidefinite programming.     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

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     

On matrices with the Edmonds–Johnson property

We survey the main results of the PhD Thesis presented by the author in January 2009 at the University of Padova. This work was supervised by Giacomo Zambelli. The thesis is written in English and is available from the author upon request. In this work we consider the Edmonds–Johnson property and we survey some related results. Next we present our contributions, that consist into two classes of matrices with the Edmonds–Johnson property. Our work generalizes previous results by Edmonds and Johnson (Math Program 5:88–124, 1973), and by Conforti et al. (in Integer programming and combinatorial optimization, proceedings of IPCO 2007). Both our results are special cases of a conjecture introduced by Gerards and Schrijver.     

Processing second-order stochastic dominance models using cutting-plane representations

Second-order stochastic dominance (SSD) is widely recognised as an important decision criterion in portfolio selection. Unfortunately, stochastic dominance models are known to be very demanding from a computational point of view. In this paper we consider two classes of models which use SSD as a choice criterion. The first, proposed by Dentcheva and Ruszczyński (J Bank Finance 30:433–451, 2006), uses a SSD constraint, which can be expressed as integrated chance constraints (ICCs). The second, proposed by Roman et al. (Math Program, Ser B 108:541–569, 2006) uses SSD through a multi-objective formulation with CVaR objectives. Cutting plane representations and algorithms were proposed by Klein Haneveld and Van der Vlerk (Comput Manage Sci 3:245–269, 2006) for ICCs, and by Künzi-Bay and Mayer (Comput Manage Sci 3:3–27, 2006) for CVaR minimization. These concepts are taken into consideration to propose representations and solution methods for the above class of SSD based models. We describe a cutting plane based solution algorithm and outline implementation details. A computational study is presented, which demonstrates the effectiveness and the scale-up properties of the solution algorithm, as applied to the SSD model of Roman et al. (Math Program, Ser B 108:541–569, 2006).     

A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case

 We study a special case of a structured mixed integer programming model that arises in production planning. For the most general case of the model, called PI, we have earlier identified families of facet–defining valid inequalities: (l, S) inequalities (introduced for the uncapacitated lot–sizing problem by Barany, Van Roy, and Wolsey), cover inequalities, and reverse cover inequalities. PI is 𝒩𝒫–hard; in this paper we focus on a special case, called PIC. We describe a polynomial algorithm for PIC, and we use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from this extended formulation onto the original space of variables, we show that (l, S) inequalities, cover inequalities, and reverse cover inequalities suffice to solve the special case PIC by linear programming. We also describe fast combinatorial separation algorithms for cover and reverse cover inequalities for PIC. Finally, we discuss the relationship between our results for PIC and a model studied previously by Goemans. Received: December 13, 2000 / Accepted: December 13, 2001 Published online: October 9, 2002 RID="★" ID="★" Some of the results in this paper have appeared in condensed form in Miller et al. (2001). Key words. mixed integer programming – polyhedral combinatorics – production planning – capacitated lot–sizing – fixed charge network flow – setup times This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America.     

A simple derivation of the MacWilliams identity for linear ordered codes and orthogonal arrays

In (Can J Math 51(2):326–346, 1999), Martin and Stinson provide a generalized MacWilliams identity for linear ordered orthogonal arrays and linear ordered codes (introduced by Rosenbloom and Tsfasman (Prob Inform Transm 33(1):45–52, 1997) as “codes for the m-metric”) using association schemes. We give an elementary proof of this generalized MacWilliams identity using group characters and use it to derive an explicit formula for the dual type distribution of a linear ordered code or orthogonal array.      

Pseudomonotone operators and the Bregman Proximal Point Algorithm

To permit the stable solution of ill-posed problems, the Proximal Point Algorithm (PPA) was introduced by Martinet (RIRO 4:154–159, 1970) and further developed by Rockafellar (SIAM J Control Optim 14:877–898, 1976). Later on, the usual proximal distance function was replaced by the more general class of Bregman(-like) functions and related distances; see e.g. Chen and Teboulle (SIAM J Optim 3:538–543, 1993), Eckstein (Math Program 83:113–123, 1998), Kaplan and Tichatschke (Optimization 56(1–2):253–265, 2007), and Solodov and Svaiter (Math Oper Res 25:214–230, 2000). An adequate use of such generalized non-quadratic distance kernels admits to obtain an interior-point-effect, that is, the auxiliary problems may be treated as unconstrained ones. In the above mentioned works and nearly all other works related with this topic it was assumed that the operator of the considered variational inequality is a maximal monotone and paramonotone operator. The approaches of El-Farouq (JOTA 109:311–326, 2001), and Schaible et al. (Taiwan J Math 10(2):497–513, 2006) only need pseudomonotonicity (in the sense of Karamardian in JOTA 18:445–454, 1976); however, they make use of other restrictive assumptions which on the one hand contradict the desired interior-point-effect and on the other hand imply uniqueness of the solution of the problem. The present work points to the discussion of the Bregman algorithm under significantly weaker assumptions, namely pseudomonotonicity [and an additional assumption much less restrictive than the ones used by El-Farouq and Schaible et al. We will be able to show that convergence results known from the monotone case still hold true; some of them will be sharpened or are even new. An interior-point-effect is obtained, and for the generated subproblems we allow inexact solutions by means of a unified use of a summable-error-criterion and an error criterion of fixed-relative-error-type (this combination is also new in the literature).     

Equivalence of Equilibrium Problems and Least Element Problems

In this paper, we introduce the concept of feasible set for an equilibrium problem with a convex cone and generalize the notion of a Z-function for bifunctions. Under suitable assumptions, we derive some equivalence results of equilibrium problems, least element problems, and nonlinear programming problems. The results presented extend some results of [Riddell, R.C.: Equivalence of nonlinear complementarity problems and least element problems in Banach lattices. Math. Oper. Res. 6, 462–474 (1981)] to equilibrium problems. This work was supported by the National Natural Science Foundation of China (10671135) and Specialized Research Fund for the Doctoral Program of Higher Education (20060610005) and the Educational Science Foundation of Chongqing (KJ051307).     

A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes

We consider the problem of developing an efficient algorithm for enumerating the extreme points of a convex polytope specified by linear constraints. Murty and Chung (Math Program 70:27–45, 1995) introduced the concept of a segment of a polytope, and used it to develop some steps for carrying out the enumeration efficiently until the convex hull of the set of known extreme points becomes a segment. That effort stops with a segment, other steps outlined in Murty and Chung (Math Program 70:27–45, 1995) for carrying out the enumeration after reaching a segment, or for checking whether the segment is equal to the original polytope, do not constitute an efficient algorithm. Here we describe the central problem in carrying out the enumeration efficiently after reaching a segment. We then discuss two procedures for enumerating extreme points, the mukkadvayam checking procedure, and the nearest point procedure. We divide polytopes into two classes: Class 1 polytopes have at least one extreme point satisfying the property that there is a hyperplane H through that extreme point such that every facet of the polytope incident at that extreme point has relative interior point intersections with both sides of H; Class 2 polytopes have the property that every hyperplane through any extreme point has at least one facet incident at that extreme point completely contained on one of its sides. We then prove that the procedures developed solve the problem efficiently when the polytope belongs to Class 2.     

Smoothed analysis of termination of linear programming algorithms

 We perform a smoothed analysis of a termination phase for linear programming algorithms. By combining this analysis with the smoothed analysis of Renegar's condition number by Dunagan, Spielman and Teng (http://arxiv.org/abs/cs.DS/0302011) we show that the smoothed complexity of interior-point algorithms for linear programming is O(m ³ log(m/Σ)). In contrast, the best known bound on the worst-case complexity of linear programming is O(m ³ L), where L could be as large as m. We include an introduction to smoothed analysis and a tutorial on proof techniques that have been useful in smoothed analyses. Received: December 10, 2002 / Accepted: April 28, 2003 Published online: June 5, 2003 Key words. smoothed analysis – linear programming – interior-point algorithms – condition numbers Mathematics Subject Classification (1991): 90C05, 90C51, 68Q25     

First- and second-order methods for semidefinite programming

 In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity. Received: December 16, 2002 / Accepted: May 5, 2003 Published online: May 28, 2003 Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods – nonlinear programming – Newton method – first-order methods – bundle method – matrix completion The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401. Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51