Exploiting special structure in a primal—dual path-following algorithm

A primal-dual path-following algorithm that applies directly to a linear program of the form, min{c ^t xAx = b, Hx u, x 0,x ⁿ }, is presented. This algorithm explicitly handles upper bounds, generalized upper bounds, variable upper bounds, and block diagonal structure. We also show how the structure of time-staged problems and network flow problems can be exploited, especially on a parallel computer. Finally, using our algorithm, we obtain a complexity bound of O( ds ² log(nk)) fortransportation problems withs origins,d destinations (s <d), andn arcs, wherek is the maximum absolute value of the input data.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402 and by ONR Contract N00014-87-K-0214.     

A new class of polynomial primal–dual methods for linear and semidefinite optimization

We propose a new class of primal–dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large-update method for LO based on the new search direction has a polynomial complexity of O(n^4/(4+ρ)log(n/ε)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. If ρ=0, our results reproduce the well-known complexity of the standard primal–dual Newton method for LO. At each iteration, our algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented.     

Accelerated primal–dual proximal block coordinate updating methods for constrained convex optimization

Block coordinate update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primal–dual BCU method for solving linearly constrained convex program with multi-block variables. The method is an accelerated version of a primal–dual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes an O(1 / t) convergence rate under convexity assumption. We show that the rate can be accelerated to \(O(1/t^2)\) if the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can be modified to achieve a linear rate of convergence. The numerical experiments show that the accelerated method performs stably with a single set of parameters while the original method needs to tune the parameters for different datasets in order to achieve a comparable level of performance.     

A primal–dual algorithm for risk minimization

Mathematical Programming - In this paper, we develop an algorithm to efficiently solve risk-averse optimization problems posed in reflexive Banach space. Such problems often arise in many practical...     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.     

Proximal primal–dual best approximation algorithm with memory

We propose a new modified primal–dual proximal best approximation method for solving convex not necessarily differentiable optimization problems. The novelty of the method relies on introducing memory by taking into account iterates computed in previous steps in the formulas defining current iterate. To this end we consider projections onto intersections of halfspaces generated on the basis of the current as well as the previous iterates. To calculate these projections we are using recently obtained closed-form expressions for projectors onto polyhedral sets. The resulting algorithm with memory inherits strong convergence properties of the original best approximation proximal primal–dual algorithm. Additionally, we compare our algorithm with the original (non-inertial) one with the help of the so called attraction property defined below. Extensive numerical experimental results on image reconstruction problems illustrate the advantages of including memory into the original algorithm.     

Near boundary behavior of primal—dual potential reduction algorithms for linear programming

This paper is concerned with selection of the-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + , ), the level of determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant, must be set close ton + . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate that can be sometimes chosen in a wide range [n + , ) while still guaranteeing the currently best convergence rate of O( L) iterations. This finding is encouraging since in practice large values of have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.Research supported in part by NSF Grant DDM-8922636.     

Combined partial regularization and descent method for a generalized primal–dual system

A variational inequality system, which is a generalization of the saddle point problem, is considered. The system does not possess monotonicity properties and the feasible set is unbounded in general. To solve the problem we propose a completely implementable iterative scheme, whose convergence is proved under certain coercivity type conditions.     

New developments in the primal–dual column generation technique

The optimal solutions of the restricted master problems typically leads to an unstable behavior of the standard column generation technique and, consequently, originates an unnecessarily large number of iterations of the method. To overcome this drawback, variations of the standard approach use interior points of the dual feasible set instead of optimal solutions. In this paper, we focus on a variation known as the primal–dual column generation technique which uses a primal–dual interior point method to obtain well-centered non-optimal solutions of the restricted master problems. We show that the method converges to an optimal solution of the master problem even though non-optimal solutions are used in the course of the procedure. Also, computational experiments are presented using linear-relaxed reformulations of three classical integer programming problems: the cutting stock problem, the vehicle routing problem with time windows, and the capacitated lot sizing problem with setup times. The numerical results indicate that the appropriate use of a primal–dual interior point method within the column generation technique contributes to a reduction of the number of iterations as well as the running times, on average. Furthermore, the results show that the larger the instance, the better the relative performance of the primal–dual column generation technique.     

A primal–dual interior point method for nonlinear semidefinite programming

This paper is concerned with a primal–dual interior point method for solving nonlinear semidefinite programming problems. The method consists of the outer iteration (SDPIP) that finds a KKT point and the inner iteration (SDPLS) that calculates an approximate barrier KKT point. Algorithm SDPLS uses a commutative class of Newton-like directions for the generation of line search directions. By combining the primal barrier penalty function and the primal–dual barrier function, a new primal–dual merit function is proposed. We prove the global convergence property of our method. Finally some numerical experiments are given.     

A primal–dual regularized interior-point method for convex quadratic programs

Interior-point methods in augmented form for linear and convex quadratic programming require the solution of a sequence of symmetric indefinite linear systems which are used to derive search directions. Safeguards are typically required in order to handle free variables or rank-deficient Jacobians. We propose a consistent framework and accompanying theoretical justification for regularizing these linear systems. Our approach can be interpreted as a simultaneous proximal-point regularization of the primal and dual problems. The regularization is termedexact to emphasize that, although the problems are regularized, the algorithm recovers a solution of the original problem, for appropriate values of the regularization parameters.     

A primal–dual augmented Lagrangian penalty-interior-point filter line search algorithm

Interior-point methods have been shown to be very efficient for large-scale nonlinear programming. The combination with penalty methods increases their robustness due to the regularization of the constraints caused by the penalty term. In this paper a primal–dual penalty-interior-point algorithm is proposed, that is based on an augmented Lagrangian approach with an \(\ell 2\)-exact penalty function. Global convergence is maintained by a combination of a merit function and a filter approach. Unlike the majority of filter methods, no separate feasibility restoration phase is required. The algorithm has been implemented within the solver WORHP to study different penalty and line search options and to compare its numerical performance to two other state-of-the-art nonlinear programming algorithms, the interior-point method IPOPT and the sequential quadratic programming method of WORHP.     

A stable primal–dual approach for linear programming under nondegeneracy assumptions

This paper studies a primal–dual interior/exterior-point path-following approach for linear programming that is motivated on using an iterative solver rather than a direct solver for the search direction. We begin with the usual perturbed primal–dual optimality equations. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. Assuming that a basis matrix (easily factorizable and well-conditioned) can be found, we apply a simple preprocessing step to eliminate both the primal and dual feasibility equations. This results in a single bilinear equation that maintains the well-posedness property. Sparsity is maintained. We then apply either a direct solution method or an iterative solver (within an inexact Newton framework) to solve this equation. Since the linearization is well posed, we use affine scaling and do not maintain nonnegativity once we are close enough to the optimum, i.e. we apply a change to a pure Newton step technique. In addition, we correctly identify some of the primal and dual variables that converge to 0 and delete them (purify step). We test our method with random nondegenerate problems and problems from the Netlib set, and we compare it with the standard Normal Equations NEQ approach. We use a heuristic to find the basis matrix. We show that our method is efficient for large, well-conditioned problems. It is slower than NEQ on ill-conditioned problems, but it yields higher accuracy solutions.