ON SOME PROPERTIES OF SOLUTIONS TO SEMIDEFINITE PROGRAMMING

It is well known that for symmetric linear programming there exists a strictly complementary solution if the primal and the dual problems are both feasible. However, this is not necessary true for symmetric or general semide finite programming even if both the primal problem and its dual problem are strictly feasible. Some other properties are also concerned.     

Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.     

Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming

In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Most interior-point methods, on the other hand, do not provide such clear-cut information. If the primal and dual problems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primaldual iterates that approach feasibility and optimality. But if the primal or dual instance is infeasible, most methods give less precise diagnostics. There are methods with finite convergence to an exact solution even with real data. Unfortunately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and often quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general tools (extensions of the Farkas lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a homogeneous self-dual algorithm and for a generic infeasible-interior-point method for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain certificates that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Some new results in linear programs with trapezoidal fuzzy numbers: Finite convergence of the Ganesan and Veeramani’s method and a fuzzy revised simplex method

In a recent paper, Ganesan and Veermani [K. Ganesan, P. Veeramani, Fuzzy linear programs with trapezoidal fuzzy numbers, Ann. Oper. Res. 143 (2006) 305–315] considered a kind of linear programming involving symmetric trapezoidal fuzzy numbers without converting them to the crisp linear programming problems and then proved fuzzy analogues of some important theorems of linear programming that lead to a new method for solving fuzzy linear programming (FLP) problems. In this paper, we obtain some another new results for FLP problems. In fact, we show that if an FLP problem has a fuzzy feasible solution, it also has a fuzzy basic feasible solution and if an FLP problem has an optimal fuzzy solution, it has an optimal fuzzy basic solution too. We also prove that in the absence of degeneracy, the method proposed by Ganesan and Veermani stops in a finite number of iterations. Then, we propose a revised kind of their method that is more efficient and robust in practice. Finally, we give a new method to obtain an initial fuzzy basic feasible solution for solving FLP problems.     

The transportation problem revisited—preprocessing before using the primal–dual algorithm

We give a necessary condition for the existence of a feasible solution for the transportation problem through a set of admissible cells, and an algorithm to find a set of admissible cells that satisfies the necessary condition. Either there exists a feasible solution through the admissible cells (which is therefore optimal since the complementary slackness conditions hold) or we could begin using the primal–dual algorithm (PDA) at this point. Our approach has two important advantages: Our O(mn) procedure for updating dual variables takes much less computing time than any procedure for solving a maximum flow problem in the primal phase of the PDA. We are never concerned by the degeneracy problem as we are not seeking basic solutions, but admissible cells. An example is presented for illustrating our approach. We finally provide computational results for a set of 30 randomly generated instances. Comparison of our method with the PDA reveals a real speed up.     

Dynamic Lagrangian dual and reduced RLT constructs for solving 0–1 mixed-integer programs

In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0–1 linear programming problems. Similarly to delayed relax-and-cut approaches, the procedure dynamically appends valid inequalities to the linear programming relaxation as induced by the Reformulation-Linearization Technique (RLT). A Lagrangian dual algorithm that is augmented with a primal solution recovery scheme is applied implicitly to a full or partial first-level RLT relaxation, where RLT constraints that are currently being violated by the primal estimate are dynamically generated within the Lagrangian dual problem, thus controlling the size of the dual space while effectively capturing the strength of the RLT-enhanced relaxation. We present a preliminary computational study to demonstrate the efficacy of this approach.     

On geometric programming and complementary slackness

When the terms in a convex primal geometric programming (GP) problem are multiplied by slack variables whose values must be at least unity, the invariance conditions may be solved as constraints in a linear programming (LP) problem in logarithmically transformed variables. The number of transformed slack variables included in the optimal LP basis equals the degree of difficulty of the GP problem, and complementary slackness conditions indicate required changes in associated GP dual variables. A simple, efficient search procedure is used to generate a sequence of improving primal feasible solutions without requiring the use of the GP dual objective function. The solution procedure appears particularly advantageous when solving very large geometric programming problems, because only the right-hand constants in a system of linear equations change at each iteration.The influence of J. G. Ecker, the writer's teacher, is present throughout this paper. Two anonymous referees and the Associate Editor made very helpful suggestions. Dean Richard W. Barsness provided generous support for this work.     

Dual gradient method for linearly constrained,strongly convex,separable mathematical programming problems

A new dual gradient method is given to solve linearly constrained, strongly convex, separable mathematical programming problems. The dual problem can be decomposed into one-dimensional problems whose solutions can be computed extremely easily. The dual objective function is shown to have a Lipschitz continuous gradient, and therefore a gradient-type algorithm can be used for solving the dual problem. The primal optimal solution can be obtained from the dual optimal solution in a straightforward way. Convergence proofs and computational results are given.     

Robust least square semidefinite programming with applications

In this paper, we consider a least square semidefinite programming problem under ellipsoidal data uncertainty. We show that the robustification of this uncertain problem can be reformulated as a semidefinite linear programming problem with an additional second-order cone constraint. We then provide an explicit quantitative sensitivity analysis on how the solution under the robustification depends on the size/shape of the ellipsoidal data uncertainty set. Next, we prove that, under suitable constraint qualifications, the reformulation has zero duality gap with its dual problem, even when the primal problem itself is infeasible. The dual problem is equivalent to minimizing a smooth objective function over the Cartesian product of second-order cones and the Euclidean space, which is easy to project onto. Thus, we propose a simple variant of the spectral projected gradient method (Birgin et al. in SIAM J. Optim. 10:1196–1211, 2000) to solve the dual problem. While it is well-known that any accumulation point of the sequence generated from the algorithm is a dual optimal solution, we show in addition that the dual objective value along the sequence generated converges to a finite value if and only if the primal problem is feasible, again under suitable constraint qualifications. This latter fact leads to a simple certificate for primal infeasibility in situations when the primal feasible set lies in a known compact set. As an application, we consider robust correlation stress testing where data uncertainty arises due to untimely recording of portfolio holdings. In our computational experiments on this particular application, our algorithm performs reasonably well on medium-sized problems for real data when finding the optimal solution (if exists) or identifying primal infeasibility, and usually outperforms the standard interior-point solver SDPT3 in terms of CPU time.     

Optimal value range in interval linear programming

We deal with the linear programming problem in which input data can vary in some given real compact intervals. The aim is to compute the exact range of the optimal value function. We present a general approach to the situation the feasible set is described by an arbitrary linear interval system. Moreover, certain dependencies between the constraint matrix coefficients can be involved. As long as we are able to characterize the primal and dual solution set (the set of all possible primal and dual feasible solutions, respectively), the bounds of the objective function result from two nonlinear programming problems. We demonstrate our approach on various cases of the interval linear programming problem (with and without dependencies).     

An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints

This paper presents an efficient algorithm for solving the Lagrangean dual of nonlinear knapsack problems with additional nested constraints. The dual solution provides a feasible primal solution (if it exists) and associated lower and upper bounds on the optimal objective function value of the primal problem. Computational experience is cited indicating computation time, number of dual iterations, and “tightness” of the bounds.     

Perturbing the Dual Feasible Region for Solving Convex Quadratic Programs

A dual l _p-norm perturbation approach is introduced for solving convex quadratic programming problems. The feasible region of the Lagrangian dual program is approximated by a proper subset that is defined by a single smooth convex constraint involving the l _p-norm of a vector measure of constraint violation. It is shown that the perturbed dual program becomes the dual program as p and, under some standard conditions, the optimal solution of the perturbed dual program converges to a dual optimal solution. A closed-form formula that converts an optimal solution of the perturbed dual program into a feasible solution of the primal convex quadratic program is also provided. Such primal feasible solutions converge to an optimal primal solution as p. The proposed approach generalizes the previously proposed primal perturbation approach with an entropic barrier function. Its theory specializes easily for linear programming.     

A dual perturbation view of linear programming

Solving standard-form linear prograrns via perturbation of the primal objective function has received much attention recently. In this paper, we investigate a new perturbation scheme which obtains a dual optimal solution by perturbing the dual feasible domain under different norms. A dual-to-primal conversion formula is also provided. We show that this new perturbation scheme actually generalizes the primal entropic perturbation approach to linear programming.Partially sponsored by the North Carolina Supercomputing Center 1994 Cray Research Grant and the National Textile Center Research Grant.     

An Exact Solution to Linear Programming Using an Interior Point Method

This paper presents sufficient conditions for optimality of the Linear programming (LP) problem in the neighborhood of an optimal solution, and applies them to an interior point method for solving the LP problem. We show that after a finite number of iterations, an exact solution to the LP problem is obtained by solving a linear system of equations under the assumptions that the primal and dual problems are both nondegenerate, and that the minimum value is bounded. If necessary, the dual solution can also be found.     

Mathematical programming via the least-squares method

The least-squares method is used to obtain a stable algorithm for a system of linear inequalities as well as linear and nonlinear programming. For these problems the solution with minimal norm for a system of linear inequalities is found by solving the non-negative least-squares (NNLS) problem. Approximate and exact solutions of these problems are discussed. Attention is mainly paid to finding the initial solution to an LP problem. For this purpose an NNLS problem is formulated, enabling finding the initial solution to the primal or dual problem, which may turn out to be optimal. The presented methods are primarily suitable for ill-conditioned and degenerate problems, as well as for LP problems for which the initial solution is not known. The algorithms are illustrated using some test problems.     

A Trust Region Target Value Method for Optimizing Nondifferentiable Lagrangian Duals of Linear Programs

In this paper, we design a new variable target value procedure, the trust region target value (TRTV) method, for optimizing nondifferentiable Lagrangian dual formulations of large-scale, ill-conditioned linear programming problems. Such problems typically arise in the context of Lagrangian relaxation approaches and branch-and-bound/cut algorithms for solving linear mixed-integer programs. Subgradient optimization strategies are well-suited for this purpose and are popularly used, particularly in Lagrangian relaxation contexts, because of their simplicity in computation and mild memory requirements. However, they lack robustness and can often stall while yet remote from optimality. With this motivation, we design our proposed TRTV method to retain simplicity in computations, be theoretically convergent, as well as yield an effective and robust performance in practice. Furthermore, we augment this approach with dual refinement and primal recovery procedures based on outer-linearization and trust region strategies to further improve the accuracy of the resulting solutions and to derive primal solutions as well. Our computational study reveals a highly competitive performance of the proposed TRTV algorithm among several implemented nondifferentiable optimization procedures. Moreover, the dual refinement and primal recovery procedures help further reduce the optimality gap and promote attaining a relatively greater degree of primal feasibility as compared with several alternative ergodic primal recovery schemes. Also, the proposed method displays significantly lesser computational requirement than that of a commercial linear programming solver CPLEX.This research has been supported by the National Science Foundation under Grant Number DMI-0094462.     

An inexact interior point method for L 1-regularized sparse covariance selection

Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.     

Finding the projection of a given point on the set of solutions of a linear programming problem

The problem of finding the projections of points on the sets of solutions of primal and dual problems of linear programming is considered. This problem is reduced to a single solution of the problem of minimizing a new auxiliary function, starting from some threshold value of the penalty coefficient. Estimates of the threshold value are obtained. A software implementation of the proposed method is compared with some known commercial and research software packages for solving linear programming problems.     

A primal-dual homotopy algorithm for $$\ell _{1}$$-minimization with $$\ell _{\infty }$$ℓ∞-constraints

In this paper we propose a primal-dual homotopy method for \(\ell _1\)-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem and a respective piecewise constant path for the dual problem. We show that by solving a small linear program, one can jump to the next primal break point and then, solving another small linear program, a new optimal dual solution is calculated which enables the next such jump in the subsequent iteration. Using a theorem of the alternative, we show that the method never gets stuck and indeed calculates the whole path in a finite number of steps. Numerical experiments demonstrate the effectiveness of our algorithm. In many cases, our method significantly outperforms commercial LP solvers; this is possible since our approach employs a sequence of considerably simpler auxiliary linear programs that can be solved efficiently with specialized active-set strategies.     

Determination of optimal vertices from feasible solutions in unimodular linear programming

In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.This author's research is partially supported by NSF grant DDM-8921835 and Airforce Grant AFSOR-88-0088.