Search

This paper is concerned with the distributed optimisation problem over a multi-agent network, where the objective function is described by a sum of all the local objectives of agents. The target of agents is to collectively reach an optimal solution while minimising the global objective function. Under the assumption that the information exchange among agents is depicted by a sequence of time-varying undirected graphs, a distributed optimisation algorithm with uncoordinated time-varying step-sizes is presented, which signifies that the step-sizes of agents are not always uniform per iteration. In light of some reasonable assumptions, this paper fully conducts an explicit analysis for the convergence rate of the optimisation method. A striking feature is that the algorithm has a geometric convergence rate even if the step-sizes are time-varying and uncoordinated. Simulation results on two numerical experiments in power systems show effectiveness and performance of the proposed algorithm.

We introduce an interior-point method for symmetric optimization based on a new method for determining search directions. In order to accomplish this, we use a new equivalent algebraic transformati...

consider primal-dual mixed finite element methods for the solution of the elliptic Cauchy problem, or other related data assimilation problems. The method has a local conservation property. We deri ...

In this paper, we propose a large-update primal-dual interior point algorithm for P*(κ)-linear complementarity problem. The method is based on a new class of kernel functions which is neither classical logarithmic function nor self-regular functions. It is determines both search directions and the proximity measure between the iterate and the center path. We show that if a strictly feasible starting point is available, then the new algorithm has $$o\left( {(1 + 2k)p\sqrt n {{\left( {\frac{1}{p}\log n + 1} \right)}^2}\log \frac{n}{\varepsilon }} \right)$$ iteration complexity which becomes $$o\left( {(1 + 2k)\sqrt n log{\kern 1pt} {\kern 1pt} n\log \frac{n}{\varepsilon }} \right)$$ with special choice of the parameter p. It is matches the currently best known iteration bound for P*(κ)-linear complementarity problem. Some computational results have been provided.

In this paper, we consider the problem of image denoising by total variation regularization. We combine the conditional gradient method with the total variation regularization in the dual formulation to derive a new method for denoising images. The convergence of this method is proved. Some numerical examples are given to illustrate the effectiveness of the proposed method.

We have adapted, implemented and trained the Learned Primal Dual algorithm suggested by Adler and Öktem and evaluated its performance in reconstructing projection data from our PET scanner. Learned Primal Dual reconstructions are compared to Maximum Likelihood Expectation Maximisation (MLEM) reconstructions. Different strategies for training are also compared. Whenever the noise level of the data to reconstruct is sufficiently represented in the training set, the Learned Primal Dual algorithm performs well on the recovery of the activity concentrations and on noise reduction as compared to MLEM. The algorithm is also shown to be robust against the appearance of artefacts, even when the images that are to be reconstructed present features were not present in the training set. Once trained, the algorithm reconstructs images in few seconds or less.

In this paper, we present an interior point method for nonlinear programming that avoids the use of penalty function or filter. We use an adaptively perturbed primal dual interior point fra...

This paper proposes a method for primal-dual convex optimization in variational large deformation diffeomorphic metric mapping problems formulated with robust regularizers and robust image similarity metrics. The method is based on Chambolle and Pock primal-dual algorithm for solving general convex optimization problems. Diagonal preconditioning is used to ensure the convergence of the algorithm to the global minimum. We consider three robust regularizers liable to provide acceptable results in diffeomorphic registration: Huber, V-Huber and total generalized variation. The Huber norm is used in the image similarity term. The primal-dual equations are derived for the stationary and the non-stationary parameterizations of diffeomorphisms. The resulting algorithms have been implemented for running in the GPU using Cuda. For the most memory consuming methods, we have developed a multi-GPU implementation. The GPU implementations allowed us to perform an exhaustive evaluation study in NIREP and LPBA40 databases. The experiments showed that, for all the considered regularizers, the proposed method converges to diffeomorphic solutions while better preserving discontinuities at the boundaries of the objects compared to baseline diffeomorphic registration methods. In most cases, the evaluation showed a competitive performance for the robust regularizers, close to the performance of the baseline diffeomorphic registration methods.

We present a primal-dual predictor-corrector interior-point method for symmetric cone optimization. The proposed algorithm is based on the Nesterov-Todd search directions and a wide neighborhood, which is an even wider neighborhood than a given negative infinity neighborhood. At each iteration, the method computes two corrector directions in addition to the Ai and Zhang directions (SIAM J. Optim. 16, 400–417, 2005), in order to improve performance. Moreover, we derive the complexity bound of the wide neighborhood predictor-corrector interior-point method for symmetric cone optimization that coincides with the currently best known theoretical complexity bounds for the short step algorithm. Finally, some numerical experiments are provided to reveal 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 work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based $$(3+\epsilon )$$ -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a $$ (4+ 1/ (e-1) +\epsilon )$$ -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately.

We consider the problem of recovering a smooth graph signal from noisy samples taken on a subset of graph nodes. The smoothness of the graph signal is quantified in terms of total variation. We formulate the signal recovery task as a convex optimization problem that minimizes the total variation of the graph signal while controlling its global or node-wise empirical error. We propose a first-order primal-dual algorithm to solve these total variation minimization problems. A distributed implementation of the algorithm is devised to handle large-dimensional applications efficiently. We use synthetic and real-world data to extensively compare the performance of our approach with state-of-the-art methods.

In this paper, we show that there is a \(\frac{5}{2}\ell \cdot \ln (1+k)\)-competitive randomized algorithm for the k-sever problem on weighted Hierarchically Separated Trees (HSTs) with depth \(\ell \) when \(n=k+1\) where n is the number of points in the metric space, which improved previous best competitive ratio \(12 \ell \ln (1+4\ell (1+k))\) by Bansal et al. (FOCS, pp 267–276, 2011).

In this paper, we consider the generalized prize-collecting Steiner forest problem, extending the prize-collecting Steiner forest problem. In this problem, we are given a connected graph $$G = (V, E)$$ and a set of vertex sets $${\mathcal {V}} = \{V_1, V_2,\cdots , V_{l}\}$$ . Every edge in E has a nonnegative cost, and every vertex set in $${\mathcal {V}}$$ has a nonnegative penalty cost. For a given edge set $$F\subseteq E$$ , vertex set $$V_i\in {\mathcal {V}}$$ is said to be connected by edge set F if $$V_i$$ is in a connected component of the F-spanned subgraph. The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized. Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.

In this paper, we consider an optimization problem of the grasping manipulation of multi-fingered hand-arm robots. We first formulate an optimization model for the problem, based on the dynamic equations of the object and the friction constraints. Then, we reformulate the model as a convex quadratic programming over circular cones. Moreover, we propose a primal-dual interior-point algorithm based on the kernel function to solve this convex quadratic programming over circular cones. We derive both the convergence of the algorithm and the iteration bounds for large- and small-update methods, respectively. Finally, we carry out the numerical tests of $$180^{\circ }$$ and $$90^{\circ }$$ manipulations of the hand-arm robot to demonstrate the effectiveness of the proposed algorithm.

Mehta and Panigrahi (FOCS 2012) introduce the problem of online matching with stochastic rewards, where edges are associated with success probabilities and a match succeeds with the probability of the corresponding edge. It is one of the few online matching problems that have defied the randomized online primal dual framework by Devanur, Jain, and Kleinberg (SODA 2013) thus far. This paper unlocks the power of randomized online primal dual in online matching with stochastic rewards by employing the configuration linear program rather than the standard matching linear program used in previous works. Our main result is a 0.572 competitive algorithm for the case of vanishing and unequal probabilities, improving the best previous bound of 0.534 by Mehta, Waggoner, and Zadimoghaddam (SODA 2015) and, in fact, is even better than the best previous bound of 0.567 by Mehta and Panigrahi (FOCS 2012) for the more restricted case of vanishing and equal probabilities. For vanishing and equal probabilities, we get a better competitive ratio of 0.576. Our results further generalize to the vertex-weighted case due to the intrinsic robustness of the randomized online primal dual analysis.

With the advent of big data scenarios, centralized processing is no more feasible and is on the verge of getting obsolete. With this shift in paradigm, distributed processing is becoming more relevant, i.e., instead of burdening the central processor, sharing the load between the multiple processing units. The decentralization capability of the ADMM algorithm made it popular since the recent past. Another recent algorithm PDMM paved its way for distributed processing, which is still in its development state. Both the algorithms work well with the medium-scale problems, but dealing with large scale problems is still a challenging task. This work is an effort towards handling large scale data with reduced computation load. To this end, the proposed framework tries to combine the advantages of the SVRG and PDMM algorithms. The algorithm is proved to converge with rate $\mathcal{O}(1/K$ for strongly convex loss functions, which is faster than the existing algorithms. Experimental evaluations on the real data prove the efficacy of the proposed algorithm over the state of the art methodologies.

We consider the k-prize-collecting Steiner tree problem. An instance is composed of an integer k and a graph G with costs on edges and penalties on vertices. The objective is to find a tree spanning at least k vertices which minimizes the cost of the edges in the tree plus the penalties of vertices not in the tree. This is one of the most fundamental network design problems and is a common generalization of the prize-collecting Steiner tree and the k-minimum spanning tree problems. Our main result is a 2-approximation algorithm, which improves on the currently best known approximation factor of 3.96 and has a faster running time. The algorithm builds on a modification of the primal-dual framework of Goemans and Williamson, and reveals interesting properties that can be applied to other similar problems.

Single crystal plasticity plays a major role in the analysis of material anisotropy and texture evolution, treats each crystalline grain individually. The polycrystalline material response is obtained upon considering a structure consisting of various individual grains, often also considering interface effects at the grain boundaries. On the individual grain level, single crystal plasticity can be treated in the mathematical framework of multi-surface plasticity, leading to a constrained optimization problem wherein multiple constraints are defined as yield criteria on the different slip systems. In this work, we present a new algorithm for the solution of the constrained optimization problem based on the Infeasible Primal Dual Interior Point method (IPDIPM). The main motivation herein is the handling of the ill-posed problem without the use of simple perturbation technique, see e.g. Miehe and Schroder [2001]. The proposed algorithm, involving slack variables, is developed for the framework of small strain single crystal plasticity. The use of slack variables therein stabilizes the conventional method and allows for a temporary violation of the constraint condition during the optimization. Moreover, all slip systems are considered simultaneously, omitting an iterative active set search. Several numerical examples are simulated to show the performance of the developed algorithm.

Given a ground set \(\mathcal {U}\) of n elements and a family of m subsets \(\mathcal {S} = \{S_i : S_i\subseteq \mathcal {U}\}\). Each subset \(S\in \mathcal {S}\) has a positive cost c(S) and every element \(e\in \mathcal {U}\) is associated with an integer coverage requirement \(r_e>0\), which means that e has to be covered at least \(r_e\) times. The weighted set multi-cover problem asks for the minimum cost subcollection which covers all of the elements such that each element e is covered at least \(r_e\) times.

In the classical k-means problem, we are given a data set \(\mathcal {D}\subseteq \mathbb {R}^{\ell }\) and an integer k. The object is to select a set \(S\subseteq \mathcal {R}^{\ell }\) of size at most k such that each point in \(\mathcal {D}\) is connected to the closet cluster in S with minimum total squared distances. However, in some real-life applications, it is more desirable and beneficial to pay a small penalty for not connecting some outliers in \(\mathcal {D}\) that are too far away from most points. As a result, we are motivated to study the k-means problem with penalties, for which we propose a \((6.357 + \varepsilon )\)-approximation algorithm via the primal-dual technique, improving the previous best approximation ratio of \(19.849 + \epsilon \) in [7] also by using the primal-dual technique.

Conventional online multi-task learning algorithms suffer from two critical limitations: 1) Heavy communication caused by delivering high velocity of sequential data to a central machine; 2) Expensive runtime complexity for building task relatedness. To address these issues, in this paper we consider a setting where multiple tasks are geographically located in different places, where one task can synchronize data with others to leverage knowledge of related tasks. Specifically, we propose an adaptive primal-dual algorithm, which not only captures task-specific noise in adversarial learning but also carries out a projection-free update with runtime efficiency. Moreover, our model is well-suited to decentralized periodic-connected tasks as it allows the energy-starved or bandwidth-constraint tasks to postpone the update. Theoretical results demonstrate the convergence guarantee of our distributed algorithm with an optimal regret. Empirical results confirm that the proposed model is highly effective on various real-world datasets.

Dual averaging-type methods are widely used in industrial machine learning applications due to their ability to promoting solution structure (e.g., sparsity) efficiently. In this paper, we propose a novel accelerated dual-averaging primal-dual algorithm for minimizing a composite convex function. We also derive a stochastic version of the proposed method which solves empirical risk minimization, and its advantages on handling sparse data are demonstrated both theoretically and empirically.

This paper considers the decentralized dynamic optimization problem defined over a multi-agent network. Each agent possesses a time-varying local objective function, and all agents aim to collaboratively track the drifting global optimal solution that minimizes the summation of all local objective functions. The decentralized dynamic consensus optimization problem can be solved by primal or primal-dual methods, and when the problem degenerates to be static, it has been proved in literature that primal-dual strategies are superior to primal ones. This motivates us to ask: are primal-dual strategies necessarily better than primal ones in decentralized dynamic optimization?To answer this question, this paper studies and compares the convergence properties of the primal approach, decentralized gradient descent (DGD), and the primal-dual approach, decentralized gradient tracking (DGT). Theoretical analysis reveals that primal methods can outperform primal-dual methods in some dynamic settings. We find that DGT is highly influenced by the variation of optimal gradients while DGD is greatly affected by the upper bound of optimal gradients. Moreover, we show that DGT is more sensitive to the network topology and a sparsely-connected network can significantly deteriorate its convergence performance. These conclusions provide guidelines on how to choose proper dynamic algorithms in various application scenarios. Numerical experiments are constructed to validate the theoretical analysis.

In this paper, we study the $k$-forest problem in the model of resource augmentation. In the $k$-forest problem, given an edge-weighted graph $G(V,E)$, a parameter $k$, and a set of $m$ demand pairs $\subseteq V \times V$, the objective is to construct a minimum-cost subgraph that connects at least $k$ demands. The problem is hard to approximate---the best-known approximation ratio is $O(\min\{\sqrt{n}, \sqrt{k}\})$. Furthermore, $k$-forest is as hard to approximate as the notoriously-hard densest $k$-subgraph problem. While the $k$-forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are {\em not} connected. In particular, the objective of the $k$-forest problem can be viewed as to remove at most $m-k$ demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the $k$-forest problem that, for every $\epsilon>0$, removes at most $m-k$ demands and has cost no more than $O(1/\epsilon^{2})$ times the cost of an optimal algorithm that removes at most $(1-\epsilon)(m-k)$ demands.

We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we provide a framework of analysis that is derived by duality properties, does not rely on potential functions and is applicable to a variety of scheduling problems. A key ingredient in our approach is bypassing the need for "black-box" rounding of fractional solutions, which yields improved competitive ratios. We begin with an interpretation of Highest-Density-First (HDF) as a primal-dual algorithm, and a corresponding proof that HDF is optimal for total fractional weighted flow time (and thus scalable for the integral objective). Building upon the salient ideas of the proof, we show how to apply and extend this analysis to the more general problem of minimizing $\sum_j w_j g(F_j)$, where $w_j$ is the job weight, $F_j$ is the flow time and $g$ is a non-decreasing cost function. Among other results, we present improved competitive ratios for the setting in which $g$ is a concave function, and the setting of same-density jobs but general cost functions. We further apply our framework of analysis to online weighted completion time with general cost functions as well as scheduling under polyhedral constraints., Comment: 30 pages

In this paper, an efficient and robust approach is proposed to reconstruct magnetic resonance (MR) images from undersampled k-space data. The proposed method adopts the first-order primal-dual framework to solve the $L_{2}-L_{1}$ compressed sensing parallel imaging reconstruction problem with the objective to remove undersampling artifacts while keeping the features with a wide range of parameter tuning. Feasibility of the proposed approach has been validated on four different in vivo brain data sets from different scanners. The experimental results show that the proposed method is able to remove undersampling artifact, preserve details and is insensitive to the parameters chosen.

In this work, we propose a novel clustering framework by gradually shrinking the graph of samples called adaptive graph shrinking (AGS). It is motivated by the smoothness of graph signal which will reach a lower bound when samples from the same cluster merge into one component of a graph. We mimic the merging process by using some dynamic clients to represent original samples. The dynamic nature of representatives also reduces to a dynamic graph which endows the final stable graph a lower smoothness, whereas the previous work robust continuous clustering (RCC) uses a fixed graph. This dynamic process is realized by alternatively optimizing the representatives and weights of the graph. We perform experiments on two public database COIL20 and MNIST to demonstrate that the dynamically shrinking of the graph is able to promote the clustering performance.

In this work, we present a new model-free and off-policy reinforcement learning (RL) algorithm, that is capable of finding a near-optimal policy with state-action observations from arbitrary behavior policies. Our algorithm, called the stochastic primal-dual Q-learning (SPD Q-learning), hinges upon a new linear programming formulation and a dual perspective of the standard Q-learning. In contrast to previous primal-dual RL algorithms, SPD-Q learning includes a Q-function estimation step, thus allowing to recover an approximate policy from the primal solution as well as the dual solution. We prove a first-of-its-kind result that the SPD Q-learning guarantees a certain convergence rate, even when the state-action distribution under a given behavior policy is time-varying but sub-linearly converges to a stationary distribution.

Dual energy computed tomography (DECT) usually uses 80kVp and 140kVp for patient scans. Due to high attenuation, the 80kVp image may become too noisy for reduced photon flux scenarios such as low-dose protocols or large-sized patients, further leading to unacceptable decomposed image quality. In this paper, we proposed a deep-neural-network-based reconstruction approach to compensate for the increased noise in low-dose DECT scan. The learned primal-dual network structure was used in this study, where the input and output of the network consisted of both low- and high-energy data. The network was trained on 30 patients who went through normal-dose chest DECT scans with simulated noises inserted into the raw data. It was further evaluated on another 10 patients undergoing half-dose chest DECT scans. Improved image quality close to the normal-dose scan was achieved and no significant bias was found on Hounsfield units (HU) values or iodine concentration.

Purpose To achieve faster reconstruction and better imaging quality of positive-contrast MRI based on the susceptibility mapping by incorporating a primal-dual (PD) formulation. Methods The susceptibility-based positive contrast MR technique was applied to estimate arbitrary magnetic susceptibility distributions of the metallic devices using a kernel deconvolution algorithm with a regularized l 1 minimization. The regularized positive-contrast inversion problem and its PD formulation were derived. The visualization of the positive contrast and convergence behavior of the PD algorithm were compared with those of the nonlinear conjugate gradient algorithm, fast iterative soft-thresholding algorithm, and alternating direction method of multipliers. These methods were tested and validated on computer simulations and phantom experiments. Results The PD approach could provide a faster reconstruction time compared with other methods. Experimental results showed that the PD algorithm could achieve comparable or even better visualization and accuracy of the metallic interventional devices in positive-contrast imaging with different SNRs and orientations to the B0 field. Conclusion A susceptibility-based positive-contrast imaging technique by PD algorithm was proposed. The PD approach has more superior performance than other algorithms in terms of reconstruction time and accuracy for imaging the metallic interventional devices.

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 present a Newton-type hybrid proximal extragradient primal–dual interior point method for solving smooth monotone mixed complementarity problems. Dual variables for the nonnegativity constraints are introduced. The ergodic complexity of the method is $$\mathcal {O}(1/k^{3/2})$$ . The method performs two types of iterations: underelaxed hybrid proximal extragradient iterations and short-steps primal–dual interior point iterations.

We propose a family of search directions based on primal-dual entropy in the context of interior-point methods for linear optimization. We show that by using entropy-based search directions in the predictor step of a predictor-corrector algorithm together with a homogeneous self-dual embedding, we can achieve the current best iteration complexity bound for linear optimization. Then, we focus on some wide neighborhood algorithms and show that in our family of entropy-based search directions, we can find the best search direction and step size combination by performing a plane search at each iteration. For this purpose, we propose a heuristic plane search algorithm as well as an exact one. Finally, we perform computational experiments to study the performance of entropy-based search directions in wide neighborhoods of the central path, with and without utilizing the plane search algorithms.

In this paper,we propose a new predictor–corrector interior-point method for symmetric cone programming. This algorithm is based on a wide neighbourhood and the Nesterov–Todd direction. We prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of 1−(1/O(r)), where r is the rank of the associated Euclidean Jordan algebras. In particular, the complexity bound is O(rlog⁡e−1), where e>0 is a given tolerance. To our knowledge, this is the best complexity result obtained so far for interior-point methods with a wide neighbourhood over symmetric cones. The numerical results show that the proposed algorithm is effective.

分布式电源出力的随机性与波动性使得配电网系统的潮流分布和电能质量等方面受到了重大影响。考虑到配电网电压波动等问题，在复杂的非线性规划问题的基础上，提出一种解决含分布式电源配电网无功优化问题的二阶锥规划方法，以达到调节电压水平、提高电能质量和降低系统损耗的目的。该方法首先将电力系统各节点电压偏差、电源有功和无功出力的上下界作为约束条件，以分布式电源的接入位置和接入容量作为决策变量，建立以电力系统损耗期望值最小为目标的SOCP模型，并采用现代原对偶内点算法加以求解。通过IEEE14节点系统的计算结果，验证了所提模型与方法的有效性和可行性。 The uncertainty of the distributed power supply’s output has a major impact on the voltage fluc-tuation of power system, the power flow distribution and the power quality. Considering the problems such as the voltage fluctuation of distribution network and the over limit, for the pur-pose of regulating the voltage, improving the power quality and decreasing the system loss, a new method named second-order cone programming method proposed in this article can solve the reactive power optimization problem based on complex nonlinear programming problem in distribution network which includes the distributed power supply. Firstly, the new method which takes the voltage deviation of each node in power system and the distributed power supply’s output limit as constraints and takes the access location and the access capacity as decision variable establishes power system SOCP model aimed at minimizing the loss of power system. Then the article solves the problem using Modern primal dual interior point algorithm. The validity and feasibility of the proposed model and method are verified by the calculation results of IEEE14 system. It also shows that the method has high computational efficiency and feasibility.

We consider the following single-machine scheduling problem, which is often denoted $1||\sum f_{j}$: we are given $n$ jobs to be scheduled on a single machine, where each job $j$ has an integral processing time $p_j$, and there is a nondecreasing, nonnegative cost function $f_j(C_{j})$ that specifies the cost of finishing $j$ at time $C_{j}$; the objective is to minimize $\sum_{j=1}^n f_j(C_j)$. Bansal \& Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the LP is less than 4. Finally, we show how the technique can be adapted to yield, for any $\epsilon >0$, a $(4+\epsilon )$-approximation algorithm for this problem., Comment: 26 pages. A preliminary version appeared in APPROX 2011. arXiv admin note: text overlap with arXiv:1403.0298

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.

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithms for solving symmetric optimization problems. In this paper we present a new kernel function for which interior point method yields iteration bounds $${\mathcal {O}}(\sqrt{r}\log r\log \frac{r}{\epsilon })$$ and $${\mathcal {O}}(\sqrt{r}\log \frac{r}{\epsilon })$$ for large-and small-update methods, respectively, which matches currently the best known bounds for such methods.

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 total variation-based Rudin–Osher–Fatemi model is an effective and popular prior model in the image processing problem. Different to frequently using the splitting scheme to directly solve this model, we propose the primal dual method to solve the smoothing total variation-based Rudin–Osher–Fatemi model and give some convergence analysis of proposed method. Numerical implements show that our proposed model and method can efficiently improve the numerical results compared with the Rudin–Osher–Fatemi model.

Summary We present a novel distributed primal-dual active-set method for model predictive control. The primal-dual active-set method is used for solving model predictive control problems for large-scale systems with quadratic cost, linear dynamics, additive disturbance, and box constraints. The proposed algorithm is compared with dual decomposition and an alternating direction method of multipliers. Theoretical and experimental results show the effectiveness of the proposed approach for large-scale systems with communication delays. The application to building control systems is thoroughly investigated. Copyright © 2016 John Wiley & Sons, Ltd.

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.