Search

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.

This paper investigates the use of a particular splitting-based optimization technique for constrained l∞-norm based peak-to-average power ratio (PAPR) reduction problem in multiuser orthogonal frequency-division multiplexing (OFDM) based multiple-input multi-output (MIMO) systems. PAPR reduction and multi-user interference (MUI) cancelation are considered in a saddle-point formulation on the downlink of a multi-user MIMO-OFDM system and an efficient primal-dual hybrid gradient (PDHG) inspired algorithm with easy-to-evaluate proximal operators is developed. The proposed algorithm converges significantly faster to satisfactory solutions with much improved asymptotical convergence rate than existing methods. Numerical results illustrate the superior performance of the proposed algorithm over existing methods in terms of PAPR reduction for different MIMO configurations.

We consider one of the problems of transport modelling - searching the equilibrium distribution of traffic flows in the network. We use the classic Beckmans model to describe time costs and flow distribution in the network represented by directed graph. Meanwhile agents behavior is not completely rational, what is described by the introduction of Markov logit dynamics: any driver selects a route randomly according to the Gibbs distribution taking into account current time costs on the edges of the graph. Thus, the problem is reduced to searching of the stationary distribution for this dynamics which is a stochastic Nash - Wardrope equilibrium in the corresponding population congestion game in the transport network. Since the game is potential, this problem is equivalent to the problem of minimization of some functional over flows distribution. The stochasticity is reflected in the appearance of the entropy regularization, in contrast to non-stochastic case. The dual problem is constructed to obtain a solution of the optimization problem. The universal primal-dual gradient method is applied. A major specificity of this method lies in an adaptive adjustment to the local smoothness of the problem, what is most important in case of the complex structure of the objective function and an inability to obtain a prior smoothness bound with acceptable accuracy. Such a situation occurs in the considered problem since the properties of the function strongly depend on the transport graph, on which we do not impose strong restrictions. The article describes the algorithm including the numerical differentiation for calculation of the objective function value and gradient. In addition, the paper represents a theoretical estimate of time complexity of the algorithm and the results of numerical experiments conducted on a small American town.

We consider a NP-hard resource allocation problem of allocating a set of resources to meet demands over a time period at the minimum cost. Each resource has a start time, finish time, availability and cost. The objective of the problem is to assign resources to meet the demands so that the overall cost is minimum. It is necessary that only one resource contributes to the demand of a slot. This constraint will be referred to as single resource assignment (SRA) constraint. We would refer to the problem as the S_RA problem. So far, only 16-approximation to this problem is known. In this paper, we propose an algorithm with approximation ratio of 12. FullText for HTML: https://doi.org/10.1051/ro/2017035

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 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.

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.

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 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.

We consider the squared metric soft capacitated facility location problem (SMSCFLP), which includes both the squared metric facility location problem (SMFLP) and the soft capacitated facility location problem (SCFLP) as special cases. As our main contribution, we propose a primal-dual based 10-approximation algorithm for the SMSCFLP. Our work also extends the applicability of the primal-dual technique.

This paper associates a dual problem to the minimization of an arbitrary linear perturbation of the robust sum function introduced in DOI 10.1007/s11228-019-00515-2. It provides an existence theorem for primal optimal solutions and, under suitable duality assumptions, characterizations of the primal-dual optimal set, the primal optimal set, and the dual optimal set, as well as a formula for the subdiffential of the robust sum function. The mentioned results are applied to get simple formulas for the robust sums of subaffine functions (a class of functions which contains the affine ones) and to obtain conditions guaranteeing the existence of best approximate solutions to inconsistent convex inequality systems., 22 pages

International audience; We propose generic acceleration schemes for a wide class of optimization and iterative schemes based on relaxation and inertia. In particular, we introduce methods that automatically tune the acceleration coefficients online and establish their convergence. This is made possible by considering classes of fixed-point iterations over averaged operators which encompass gradient methods, ADMM (Alternating Direction Method of Multipliers), primal dual algorithms and so on.

In this paper, we introduce the multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and vertex cover with submodular penalties. We present a combinatorial 3-approximation algorithm, based on the primal-dual scheme for the multicut problem in trees.

The primal--dual hybrid gradient method (PDHGM, also known as the Chambolle--Pock method) has proved very successful for convex optimization problems involving linear operators arising in image processing and inverse problems. In this paper, we analyze an extension to nonconvex problems that arise if the operator is nonlinear. Based on the idea of testing, we derive new step length parameter conditions for the convergence in infinite-dimensional Hilbert spaces and provide acceleration rules for suitably (locally and/or partially) monotone problems. Importantly, we prove linear convergence rates as well as global convergence in certain cases. We demonstrate the efficacy of these step length rules for PDE-constrained optimization problems.

Binarization of digital documents is the task of classifying each pixel in an image of the document as belonging to the background (parchment/paper) or foreground (text/ink). Historical documents are often subjected to degradations, that make the task challenging. In the current work a deep neural network architecture is proposed that combines a fully convolutional network with an unrolled primal-dual network that can be trained end-to-end to achieve state of the art binarization on four out of seven datasets. Document binarization is formulated as an energy minimization problem. A fully convolutional neural network is trained for semantic segmentation of pixels that provides labeling cost associated with each pixel. This cost estimate is refined along the edges to compensate for any over or under estimation of the foreground class using a primal-dual approach. We provide necessary overview on proximal operator that facilitates theoretical underpinning required to train a primal-dual network using a gradient descent algorithm. Numerical instabilities encountered due to the recurrent nature of primal-dual approach are handled. We provide experimental results on document binarization competition dataset along with network changes and hyperparameter tuning required for stability and performance of the network. The network when pre-trained on synthetic dataset performs better as per the competition metrics., Under consideration for Pattern Recognition Letters Special Issue on Graphonomics for e-citizens: e-health, e-society, e-education 11 pages, 10 figures, 2 tables

This paper studies the convergence of projected primal-dual dynamics under mild conditions on the (general) optimization problem. In particular, we do not require strict convexity of the objective function nor uniqueness of the optimizer. By regarding the inequality constraints as hard constraints, we construct a suitable primal-dual dynamics in the complementarity formalism. We establish pointwise asymptotic stability of the set primal-dual optimizers by a suitable invariance principle involving two different Lyapunov functions. In addition, we show how these results can be applied for online optimization in data centers.