Search

We characterize the optimal solution to the linear programming relaxation of the standard formulation for the minimum satisfiability problem. We give a O ( n m 2 ) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n ( m ) is the number of variables (clauses). As a by-product, we obtain a 2 ( 1 − 1 ∕ 2 k ) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause.

An antiwindup control framework is developed for primal-dual dynamics in convex optimization. The proposed architecture provides for straightforward implementation of the ensuing primal-dual dynamics and for establishing global asymptotic stability using the notion of shifted-passivity with Lyapunov function commonly encountered in antiwindup literature.

The standard data envelopment analysis (DEA) procedure involves solving a pair of two types of models, multiplier model and envelopment model, and one of the most interesting features of DEA is that these two types of models are equivalent due to duality in linear programming. However, while several prominent network DEA models have been proposed in the literature in multiplier and/or envelopment forms, it is still doubtful or unclear whether and how the same primal-dual correspondence can be retained between the two types of network DEA models as in the standard DEA. To address this issue, we develop an axiomatic derivation of some two-stage network DEA models in this paper focusing on the basic two-stage serial process structure. We define the production possibility set for the basic two-stage serial process based upon some reasonable axiomatic properties. Subsequently we develop envelopment network DEA models using different distance measures, which are then shown to result in well-known existing two-stage network DEA models in the multiplier form.

We propose an image restoration model based on the minimized surface regularization. The proposed model closely relates to the classical smoothing ROF model (Rudin et al., 1992). We deduce two different conjugation forms via coupling the gradient operator with the smoothing parameter α or not, and then provide the existence of the minimizer in the continuous setting. In order to efficiently solving the proposed model, we employ the primal dual method by reformulating the proposed model as a min–max problem. Relying on the convex conjugation, the convergence of the algorithm is provided as well. Numerical implementations mainly emphasize the effectiveness of the proposed method by comparing it to other two well-known methods in terms of the CPU time and restoration quality.

We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O ( f 2 ) -approximately optimal solution in O ( f ⋅ log ⁡ ( m + n ) ) amortized update time, where f is the maximum “frequency” of an element, n is the number of sets, and m is the maximum number of elements in the universe at any point in time. (2) For the dynamic b-matching problem, we maintain an O ( 1 ) -approximately optimal solution in O ( log 3 ⁡ n ) amortized update time, where n is the number of nodes in the graph.

The inverse medium problem with discontinuous refractive index is a kind of challenging inverse problem. We employ the primal dual theory and fast solution of integral equations, and propose a new iterative imaging method. The selection criteria of regularization parameter is given by the method of generalized cross-validation. Based on multi-frequency measurements of the scattered field, a recursive linearization algorithm has been presented with respect to the frequency from low to high. We also discuss the initial guess selection strategy by semi-analytical approaches. Numerical experiments are presented to show the effectiveness of the proposed method.

The aim of super-resolution (SR) algorithms is to recover high-resolution (HR) images and videos from low-resolution (LR) ones. Since the SR is considered as an ill-posed minimization problem, regularization techniques are then considered. The choice of the regularization term plays a major role in the quality of the obtained HR image. Even if many terms have been proposed in the literature, they still suffer from different undesirable artifacts. To address these weaknesses, we propose a variational SR model based on Huber-Norm using Bregman distances. This offers the new model to be more consistent against contrast loss and smoothing gray values, in contrast, strong edges and contours are well preserved in the reconstruct HR image. Moreover, the use of first-order primaldual algorithm with an adaptive regularization parameter choice assure the convergence to the desired HR image, in a fast way, preserving important image features. As a result, the proposed algorithm shows promising results for various real and synthetic datasets compared with other methods. We treat the multi-frame super-resolution task based on Bregman distance.We propose a variational SR model based on Huber-Norm and bilateral total variation.The improved regularization is efficient in degraded image super-resolution task using primaldual algorithm.The proposed method gives better performance comparing with other approaches.

In this paper, we define a new, special second order cone as a type-$k$ second order cone. We focus on the case of $k=2$, which can be viewed as SOCO with an additional {\em complicating variable}. For this new problem, we develop the necessary prerequisites, based on previous work for traditional SOCO. We then develop a primal-dual interior point algorithm for solving a type-2 second order conic optimization (SOCO) problem, based on a family of kernel functions suitable for this type-2 SOCO. We finally derive the following iteration bound for our framework: \[\frac{L^\gamma}{\theta \kappa \gamma} \left[2N \psi\left( \frac{\varrho \left(\tau /4N\right)}{\sqrt{1-\theta}}\right)\right]^\gamma\log \frac{3N}{\epsilon}.\]

In this paper, we investigate the continuous time partial primal–dual gradient dynamics (P-PDGD) for solving convex optimization problems with the form min x ∈ X , y ∈ Ω f ( x ) + h ( y ) , s . t . A x + B y = C , where f ( x ) is strongly convex and smooth, but h ( y ) is strongly convex and non-smooth. Affine equality and general convex set constraints are included. We prove the existence of the solution to P-PDGD and its exponential stability . Then, bounds on decaying rates are provided. Moreover, it is also shown that the decaying rates can be regulated by setting the stepsize.

We develop a parallel primal-dual splitting method to solve large-scale image restoration problems, which involve the sum of several linear-operator-coupled nonsmooth but proximable terms. With the proposed method, the objective function is decomposed into pieces that can be processed individually. No inverse operator is involved in our method and the highly parallel structure makes it preferable in distributed computation. The convergence is proven and the convergence rate is analyzed. Besides, its equivalence to the relaxed parallel linearized alternating direction method of multipliers (PLADMM) is addressed. Applications to image restoration problems with compound l1-regularizer and comparisons with state-of-the-art methods are detailed to show the superiority of the proposed method.

The notion of penalty has been introduced into many combinatorial optimization models. In this paper, we consider the submodular vertex cover problems with linear and submodular penalties, which are two variants of the submodular vertex cover problem where not all the edges are required to be covered by a vertex cover, and the uncovered edges are penalized. The problem is to determine a vertex subset to cover some edges and penalize the uncovered edges such that the total cost including covering and penalty is minimized. To overcome the difficulty of implementing the primal-dual framework directly, we relax the two dual programs to slightly weaker versions. We then present two primal-dual approximation algorithms with approximation ratios of 2 and 4, respectively.

A primal-dual interior-point method (IPM) based on a new class of proximity functions is proposed for solving Semidefinite Optimization (SDO) problems. The proposed functions are induced from the kernel functions with trigonometric barrier terms. We derive iteration complexity of large-update IPMs for SDO as O ( n log n log n ź ) . This improves the result obtained in Li and Zhang (2015) for linear optimization and matches to the bound for the so-called self-regular kernel functions.

Compressed sensing (CS) can recover a signal from a small number of observed transforms of that signal. It mainly consists of two complimentary elements including compressed sampling and computational image reconstruction. In this work, we have developed a ghost imaging system and proposed a primal dual interior point compressed sensing algorithm. We also demonstrated the performance of our imaging system and CS algorithm with simulations and experiment compared to conventional approaches. The discrete samples signal can be reconstructed by our CS algorithm. Experimental results show that the proposed compressed imaging method outperforms the conventional CS approaches in both computational time and reconstruction accuracy.

The total variation (TV) based iterative regularization method has been utilized to recover images degraded by blur and impulse noise. It is well-known that the TV regularization model preserves the edges well in the restored images while suffers from staircase effect. In this paper, we consider a high-order total variation minimization model which removes undesired artifacts for restoring blurry and noisy images. Then a primal-dual splitting algorithm is developed to solve the high-order minimization problem. The convergence of the proposed method is guaranteed. Numerical results illustrate that the proposed method is competitive with the state-of-the-art methods in terms of the peak signal-to-noise (PSNR) and the structural similarity index measurement (SSIM).

A day-ahead voltage stability constrained dynamic optimal reactive power flow (VSC-DORPF) model is proposed in this paper. The amount of dynamic reactive power reserves (DRPR) is used as a measure of voltage stability of power system. The effective dynamic reactive power reserves (EDRPR) of reactive power sources are calculated to obtain DRPR of each area and the maximum variations in reactive power generation under contingency are taken as the required minimal DRPR for each area. Then the DRPR are introduced into the VSC-DORPF model as one of multiple objective functions and constraints in order to enhance the voltage stability of power system. A hybrid method, integrated by branch-bound method and primal–dual interior point (PDIP) method, is proposed to solve this VSC-DORPF problem. The discrete control variables and the time coupled constraints are handled by the proposed branching and pruning principles. As a result, the VSC-DORPF problem is decomposed into a series of optimal reactive power flow (ORPF) problems with continuous control variables only. Numerical tests with IEEE 30-bus system and IEEE 118-bus system show that the proposed model and method are effective.

We develop a primal dual active set with continuation algorithm for solving the l 0 -regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the primal dual active set method with a continuation strategy on the regularization parameter. At each inner iteration, it first identifies the active set from both primal and dual variables, and then updates the primal variable by solving a (typically small) least-squares problem defined on the active set, from which the dual variable can be updated explicitly. Under certain conditions on the sensing matrix, i.e., mutual incoherence property or restricted isometry property, and the noise level, a finite step global convergence of the overall algorithm is established. Extensive numerical examples are presented to illustrate the efficiency and accuracy of the algorithm and its convergence behavior.

Total variation method has been widely used in image processing, however, it produces undesirable staircase effect. Recently, the two-step method has been used to alleviate the staircase effect successfully. Combined with a new vector field and an edge indicator function, a novel variational model is proposed in this paper. Unlike the two-step method, the proposed model contains only one energy functional, that is to say, the new vector field and the reconstructed image are interwoven. Due to using the information of the restored image fully, the new vector field is more accurate than the normal vector field, and the reconstructed image is also better than that in the two-step method. To solve the new model, we design a primal-dual method to simulate the minimization problem. The numerical experiments show that the new model can obtain significant improvement not only in noise removal but also in avoiding staircase effect.

Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using the primal-dual interior point algorithm. We discuss in detail how to deal with the challenges of using the interior point algorithm with the core components of the branch-price-and-cut method. The effort to overcome the difficulties pays off in a number of advantageous features offered by the new approach. We present the computational results of solving well-known instances of the vehicle routing problem with time windows, a challenging integer programming problem. The results indicate that the proposed approach delivers the best overall performance when compared with a similar branch-price-and-cut method which is based on the simplex algorithm.

We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on “the simplest (linear program) relaxation” (Queyranne and Schulz, 1994 [17] ). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16] ), using dual fitting. In the offline setting, we develop a primal–dual algorithm with approximation guarantee 1 + 2 . The latter implies that the cost of the optimal schedule is within a factor of 1 + 2 of the cost of the optimal LP solution.

This paper studies the stability of the primal–dual algorithm for Internet congestion control with round-trip communication delays. The model is formulated as a time-delayed multivariable control system for a general network, and then is studied by using time-delayed control theory. A necessary and sufficient condition is established for a network with a general topology, and then is further discussed for the representative dumbbell network. The stability condition is applied to the design of FAST TCP and adaptive virtual queue (AVQ) scheme as guideline, which is validated by simulation results.

This paper gives a primal-dual derivation of the Least Squares Support Vector Machine (LS-SVM) using Instrumental Variables (IVs), denoted simply as the Primal-dual Instrumental Variable Estimator. Then we propose a convex optimization approach for learning the optimal instruments. Besides the traditional argumentation for the use of IVs, the primal-dual derivation gives an interesting other advantage, namely that the complexity of the system to be solved is expressed in the number of instruments, rather than in the number of samples as typically the case for SVM and LS-SVM formulations. This note explores some exciting issues in the design and analysis of such estimator.

In this paper, we address the primal-dual column generation technique, which relies on well-centred suboptimal solutions of the restricted master problems. We summarize new theoretical developments and present computational results for two classical combinatorial optimization problems, in which this technique has not been tested before. The results show that the primal-dual column generation technique usually leads to substantial reductions in the number of iterations and CPU time when compared to two other well-established approaches: the classical column generation technique and the analytic centre cutting plane method.

We introduce a new kind of kernel function, which yields efficient large-update primal-dual interior-point methods. We conclude that in some situations its iteration bounds are O(m^3^m^+^1^2^mn^m^+^1^2^mlogn@e), which are at least as good as the best known bounds so far, O(nlognlogn@e), for large-update primal-dual interior-point methods. The result decreases the gap between the practical behavior of the large-update algorithms and their theoretical performance results, which is an open problem. Numerical results show that the algorithms are feasible.

In this paper, a new feasible primal–dual interior point algorithm for solving inequality constrained optimization problems is presented. At each iteration, the algorithm solves only two or three reduced systems of linear equations with the same coefficient matrix. The searching direction is feasible and the object function is monotone decreasing. The proposed algorithm is proved to possess global and superlinear convergence under mild conditions. Finally, some numerical experiments with the algorithm are reported.

A common feature shared by most practical algorithms in interior point methods is the use of Mehrotra’s predictor–corrector algorithm in [S. Mehrotra, On the implementation of a (primal-dual) interior point method, SIAM Journal on Optimization 2 (1992) 575–601.] where the predictor step is never performed but it is used only to calculate an adaptive update, and thus instead of a predictor and a corrector centering step, a single Newton step is made toward the adaptively chosen target. In this paper we propose a new adaptive single-step large-update primal-dual interior point algorithm with wide neighborhood for linear optimization(LO) problems based on the simple kernel function which is first defined in [Y.Q. Bai, C. Roos, A primal-dual interior-point method based on a new kernel function with linear growth rate, in: Proceedings of Industrial Optimization Symposium and Optimization Day, Nov., 2002]. We show that the algorithm has O ( q n τ log ( n / e ) ) complexity which is similar to the one in the above-mentioned reference.

In this paper we propose a primal-dual path-following interior-point algorithm for second-order cone optimization. The algorithm is based on a new technique for finding the search directions and the strategy of the central path. At each iteration, we use only full Nesterov-Todd step. Moreover, we derive the currently best known iteration bound for the algorithm with small-update method, namely, [email protected], where N denotes the number of second-order cones in the problem formulation and @e the desired accuracy.

In this paper we present a new primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full Nesterov–Todd step. Moreover, we obtain the currently best known iteration bound for the algorithm with small-update method, namely, O ( n log n ϵ ) , which is as good as the linear analogue.

In this paper we develop new primal–dual interior-point methods for linear programming problems, which are based on the concept of parabolic target space. We show that such schemes work in the infinity-neighborhood of the primal–dual central path. Nevertheless, these methods possess the best known complexity estimate. We demonstrate that the adaptive-step path-following strategies can be naturally incorporated in such schemes.

We present a primal-dual application of the proximal point algorithm to solve convex constrained minimization problems. Motivated by the work of Eckstein [Math. Oper. Res. 18 (1993) 203] about the generalized proximal point method, we propose here a mixed proximal multipliers method where we improve the result of Eckstein [Math. Oper. Res. 18 (1993) 203] Theorem 1.

We present local ratio interpretations of known algorithms for minimums-tcut and the assignment problem. Our interpretations are the first application of local ratio with negative weights. These interpretations lead to primal-dual analyses that are based on new IP formulations.

We extend in two directions the Analytic Center, Cutting Plane Method for Variational Inequalities with quadratic cuts, ACCPM-VI(quadratic cuts), introduced by Denault and Goffin in 1998. First, we define a primal-dual method to find the analytic center at each iteration. Second, the Broyden-Fletcher-Goldfarb-Shanno Jacobian approximation, of quasi-Newton fame, is used in the definition of the cuts, making the algorithm applicable to problems without tractable Jacobians. The algorithm is tested on a variety of variational inequality problems, including one challenging problem of pricing the pollution permits put forward in the Kyoto Protocol.

We extend the duality approach of Haugh-Kogan and Rogers to two-player stochastic zero-sum stopping games where players have asymmetric information of the state space at each action time, and modify the Andersen-Broadie primal dual method to present a Monte-Carlo framework for estimating their optimal values. In addition, we provide a practical sub-simulation solution for evaluating general stochastic zero-sum games with symmetric information. The methods generate both lower and upper bounds for the optimal value, and hence give a valid confidence interval.

This paper presents a method of sensitivity analysis on the cost coefficients and the right-hand sides for most variants of the primal–dual interior point method. We first define an e -optimal solution to describe the characteristics of the final solution obtained by the primal–dual interior point method. Then an e -sensitivity analysis is defined to determine the characteristic region where the final solution remains the e -optimal solution as a cost coefficient or a right-hand side changes. To develop the method of e -sensitivity analysis, we first derive the expressions for the final solution from data which are commonly maintained in most variants of the primal–dual interior point method. Then we extract the characteristic regions on the cost coefficients and the right-hand sides by manipulating the mathematical expressions for the final solution. Finally, we show that in the nondegenerate case, the characteristic regions obtained by e -sensitivity analysis are convergent to those obtained by sensitivity analysis in the simplex algorithm.

Iterative Feedback Tuning (IFT) is a method to tune controllers using closed loop experimental data and estimation of gradients. In this paper is shown how IFT can be extended to the case when there are constraints on some of the performance measures. This is accomplished by solving the Karush-Kuhn-Tucker conditions for the optimization problem using a primal-dual interior-point method. It is shown that only a few extra experiments have to be performed as compared to traditional IFT.

Primal-dual affine-scaling methods have recently been extended from linear programming to semidefinite programming. We show how to analyze these methods in the framework of potential reduction algorithms. The analysis suggests implementable variants of the methods as ‘long step predictor-corrector’ algorithms, where the step length is determined by the potential function. A numerical comparison with the potential reduction method of Nesterov and Todd is presented.

We analyse the primal-dual upper bound method for Bermudan options and prove that its bias is inversely proportional to the number of paths in sub-simulations for a large class of cases. We develop a methodology for estimating and reducing the bias. We present numerical results showing that the new technique is indeed effective.

HOPDM is an implementation of the primal-dual interior point method for solving large scale linear programming (LP) problems. HOPDM stands for Higher Order Primal Dual Method. Its newest version 2.12 (of May 1995) is a robust and efficient code that compares favourably with today's commercial LP solvers.

This paper presents an interior Multiobjective Linear Programming (MOLP) algorithm that is based on a variant of Karmarkar's interior-point algorithm known as the path-following primal-dual algorithm. The modification is accomplished by combining the single step direction vectors generated by the single-objective algorithm into a combined vector along which we step from the current iterate to the next iterate. Combining step direction vectors into a single step can be done by either approximating the gradient of an implicit utility function at the current iterate, or by creating convex combinations of single directions. We discuss both approaches and use the latter to develop an interior algorithm directed at handling MOLP problems. We refer to the resulting class of MOLP algorithms resulting from this variant as Primal-Dual Interior Multiobjective Linear Programming (PDIMOLP) algorithm.

We introduce the framework for a primal dual integer programming algorithm. We prove convergence, and discuss some special cases.

The Lagrangean relaxation of the single level capacitated dynamic lot-sizing problem can be solved using the primal-dual method. The algorithm has monotone and finite convergence properties. It works as a steepest ascent method. A variant of this approach is also studied. A heuristic routine used to obtain a feasible solution in each iteration is presented. Computational experiences show that this method usually yields better solutions than the subgradient method although it requires greater CPU times.

In this short note, we prove that the global convergence rate of the duality gap in a symmetric primal-dual potential algorithm for linear programming, without line search, is no better than linear. More specifically, the convergence rate is no better than (1 - @t/@/n), where @t is a number between zero and one.

The problem of minimizing a functional, subject to differential constraints, nondifferential constraints, initial constraints, and final constraints, is considered in connection with sequential gradient-restoration algorithms (SGRA) for optimal control problems. Both the primal formulation and the dual formulation are presented. Depending on whether the primal formulation is used or the dual formulation is used, one obtains a primal sequential gradient-restoration algorithm (PSGRA) or a dual sequential gradient-restoration algorithm (DSGRA). For the problem under consideration, it is found convenient to split the control vector into an independent control vector and a dependent control vector, the latter having the same dimension as the nondifferential constraint vector. This modification enhances the computational efficiency of both the primal formulation and the dual formulation. The system of Lagrange multipliers associated with (i) the gradient phase of SGRA and (ii) the restoration phase of SGRA is examined. For each phase, it is shown that the Lagrange multipliers are endowed with a duality property: they minimize a special functional, quadratic in the multipliers, subject to the multiplier differential equations and boundary conditions, for given state, control, and parameter. These duality properties have considerable computational implications: they allow one to reduce the auxiliary optimal control problems associated with (i) and (ii) to mathematical programming problems involving a finite number of parameters as unknowns.

An algorithm is described for finding a feasible point for a system of linear inequalities. If the solution set has nonempty interior, termination occurs after a finite number of iterations. The algorithm is a projection-type method, similar to the relaxation methods of Agmon, Motzkin, and Schoenberg. It differs from the previous methods in that it solves for a certain “dual” solution in addition to a primal solution.

This paper focuses on the computer implementation of Ford and Fulkerson's primaldual method for solving the transportation problem. It explores the practical implications of improving the efficiency with which transportation problems can be solved. By using appropriate techniques for storing data elements and manipulating their structural relationships, a computer procedure, which is quite efficient in terms of central processor execution time and core storage requirements, is developed. Computational results using a FORTRAN program on test problems ranging in size from 15 sources and 25 destinations to 30 sources and 400 destinations are presented and discussed. These results indicate that the method of implementation is instrumental in reducing the effect of problem size on computational requirements. The paper emphasizes the general principles of the implementation rather than those aspects which are specifically related to the language and computer used for experimentation. Also, the applicability of the research is extended by an investigation of the potential for using the implementation concepts with other algorithms.

A saddle-point formulation of linear programming problems with random objective function and RHS coefficients is proposed. Under a certainty equivalent criterion, a pair of primal-dual deterministic equivalents is derived. These problems are symmetric dual quadratic programs, and can be interpreted as generalizations of the classical mean-variance model.

The problem of finding the minimum weight configuration for a statically determinate structure of fixed layout under two alternative load systems, as analysed by Chern and Prager, is re-examined by a special primal-dual formulation known as geometric programming. It is found that geometric programming in its unmodified form is less general than the Chern-Prager primal-dual method but does offer certain advantages with respect to information content at the optimum.

The use of integer programming as a modeling technique is widespread in practice, but current algorithms for solving these models are less than satisfactory even for problems of modest size. Thus the search continues for more efficient and reliable algorithms. In this paper we present a technique for solving all-integer programming problems. The algorithm, which we call the accelerated primal-dual algorithm (APDA), uses all-integer cutting planes and an advanced feasible start to speed convergence to optimality. We discuss computational results on a standard set of test problems.