Search

Risk-averse multistage problems and their applications are gaining interest in various fields of applications. Under convexity assumptions, the resolution of these problems can be done with trajectory following dynamic programming algorithms like Stochastic Dual Dynamic Programming (SDDP) to access a deterministic lower bound, and dual SDDP for deterministic upper bounds. In this paper, we leverage the dual SDDP algorithm to compute a policy with guaranteed risk-adjusted performance for multistage stochastic linear problems. [ABSTRACT FROM AUTHOR]

This paper concerns the formulation and analysis of a new interior-point method for constrained optimization that combines a shifted primal-dual interior-point method with a projected-search method for bound-constrained optimization. The method involves the computation of an approximate Newton direction for a primal-dual penalty-barrier function that incorporates shifts on both the primal and dual variables. Shifts on the dual variables allow the method to be safely "warm started" from a good approximate solution and avoids the possibility of very large solutions of the associated path-following equations. The approximate Newton direction is used in conjunction with a new projected-search line-search algorithm that employs a flexible non-monotone quasi-Armijo line search for the minimization of each penalty-barrier function. Numerical results are presented for a large set of constrained optimization problems. For comparison purposes, results are also given for two primal-dual interior-point methods that do not use projection. The first is a method that shifts both the primal and dual variables. The second is a method that involves shifts on the primal variables only. The results show that the use of both primal and dual shifts in conjunction with projection gives a method that is more robust and requires significantly fewer iterations. In particular, the number of times that the search direction must be computed is substantially reduced. Results from a set of quadratic programming test problems indicate that the method is particularly well-suited to solving the quadratic programming subproblem in a sequential quadratic programming method for nonlinear optimization. [ABSTRACT FROM AUTHOR]

Motivated, in particular, by the entropy-regularized optimal transport problem, we consider convex optimization problems with linear equality constraints, where the dual objective has Lipschitz pth order derivatives, and develop two approaches for solving such problems. The first approach is based on the minimization of the norm of the gradient in the dual problem and then the reconstruction of an approximate primal solution. Recently, Grapiglia and Nesterov [Tensor methods for finding approximate stationary points of convex functions, Optim. Methods Softw. (2020), pp. 1–34] showed lower complexity bounds for the problem of minimizing the gradient norm of the function with Lipschitz pth order derivatives. Still, the question of optimal or near-optimal methods remained open as the algorithms presented in [Grapiglia and Nesterov, Tensor methods for finding approximate stationary points of convex functions, Optim. Methods Softw. (2020), pp. 1–34] achieve suboptimal bounds only. We close this gap by proposing two near-optimal (up to logarithmic factors) methods with complexity bounds $ \tilde {O}(\varepsilon ^{-2(p+1)/(3p+1)}) $ O~(ε−2(p+1)/(3p+1)) and $ \tilde {O}(\varepsilon ^{-2/(3p+1)}) $ O~(ε−2/(3p+1)) with respect to the initial objective residual and the distance between the starting point and solution, respectively. We then apply these results (having independent interest) to our primal–dual setting. As the second approach, we propose a direct accelerated primal–dual tensor method for convex problems with linear equality constraints, where the dual objective has Lipschitz pth order derivatives. For this algorithm, we prove $ \tilde O (\varepsilon ^{-1 / (p + 1)}) $ O~(ε−1/(p+1)) complexity in terms of the duality gap and the residual in the constraints. We illustrate the practical performance of the proposed algorithms in experiments on logistic regression, entropy-regularized optimal transport problem, and the minimal mutual information problem. [ABSTRACT FROM AUTHOR]

The primal-dual method of Chambolle and Pock is a widely used algorithm to solve various optimization problems written as convex-concave saddle point problems. Each update step involves the application of both the forward linear operator and its adjoint. However, in practical applications like computerized tomography, it is often computationally favourable to replace the adjoint operator by a computationally more efficient approximation. This leads to an adjoint mismatch in the algorithm. In this paper, we analyze the convergence of Chambolle–Pock's primal-dual method under the presence of a mismatched adjoint in the strongly convex setting. We present an upper bound on the error of the primal solution and derive stepsizes and mild conditions under which convergence to a fixed point is still guaranteed. Furthermore we show linear convergence similar to the result of Chambolle–Pock's primal-dual method without the adjoint mismatch. Moreover, we illustrate our results both for an academic and a real-world inspired application. [ABSTRACT FROM AUTHOR]

We propose a new duality scheme based on a sequence of smooth minorants of the weighted- ℓ 1 penalty function, interpreted as a parametrized sequence of augmented Lagrangians, to solve non-convex constrained optimization problems. For the induced sequence of dual problems, we establish strong asymptotic duality properties. Namely, we show that (i) the sequence of dual problems is convex and (ii) the dual values monotonically increase to the optimal primal value. We use these properties to devise a subgradient based primal–dual method, and show that the generated primal sequence accumulates at a solution of the original problem. We illustrate the performance of the new method with three different types of test problems: A polynomial non-convex problem, large-scale instances of the celebrated kissing number problem, and the Markov–Dubins problem. Our numerical experiments demonstrate that, when compared with the traditional implementation of a well-known smooth solver, our new method (using the same well-known solver in its subproblem) can find better quality solutions, i.e. 'deeper' local minima, or solutions closer to the global minimum. Moreover, our method seems to be more time efficient, especially when the problem has a large number of constraints. [ABSTRACT FROM AUTHOR]

We consider the regularized empirical risk minimization (ERM) of linear predictors, which arises in a variety of problems in machine learning and statistics. After reformulating the original ERM as a bilinear saddle‐point problem, we can apply stochastic primal–dual methods to solve it. Sampling the primal or dual coordinates with a fixed nonuniform distribution is usually employed to accelerate the convergence of the algorithm, but such a strategy only exploits the global information of the objective function. To capture its local structures, we propose an adaptive importance sampling strategy that chooses the coordinates based on delicately designed nonuniform and nonstationary distributions. When our adaptive coordinate sampling strategy is applied to the Stochastic Primal‐Dual Coordinate (SPDC), we prove that the resulting algorithm enjoys linear convergence. Moreover, we show that the ideal form of our adaptive sampling exhibits strictly sharper convergence rate under certain conditions compared with the vanilla SPDC. We also extend our sampling strategy to other algorithms including Doubly Stochastic Primal‐Dual Coordinate (DSPDC) and Stochastic Primal‐Dual with O(1) per‐iteration cost and Variance Reduction (SPD1‐VR), where both primal and dual coordinates are randomly sampled. Our experiment results show that the proposed strategy significantly improves the convergence performance of the methods when compared with existing sampling strategies. [ABSTRACT FROM AUTHOR]

This article studies the distributed composite optimization problem over relay-assisted networks (DCOP-RNs). By combining the local primal–dual updates with a data fusion strategy, an effective distributed algorithm is developed to solve the DCOP-RN. Compared with the existing linearized alternating direction method of multipliers (ADMMs), this article provides a novel interpretation of the proposed algorithm. More specifically, it is shown that the proposed algorithm can be interpreted as a simplified proximal augmented Lagrangian method. Within this framework, a simplified convergence analysis of the algorithm is conducted, based on which the convergence to an optimal solution to the DCOP-RN is proved. Further, taking into account the limited bandwidth in real networks, this article proposes a quantized distributed algorithm to solve the DCOP-RN. Especially, a relationship between the quantization resolution and the convergence accuracy of the algorithm is established. Finally, simulation examples verify the theoretical results. [ABSTRACT FROM AUTHOR]

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 a second order conic optimization (SOCO) problem with an additional complicating variable. For this new problem, we develop the necessary prerequisites, based on previous work for traditional SOCO problem. We then develop a primal–dual interior point algorithm for solving a type-2 second order conic optimization problem, based on a family of kernel functions suitable for this type-2 SOCO. We finally derive a new iteration bound for our framework.

In this paper, a new variant of accelerated gradient descent is proposed. The proposed method does not require any information about the objective function, uses exact line search for the practical accelerations of convergence, converges according to the well-known lower bounds for both convex and non-convex objective functions, possesses primal–dual properties and can be applied in the non-euclidian set-up. As far as we know this is the first such method possessing all of the above properties at the same time. We also present a universal version of the method which is applicable to non-smooth problems. We demonstrate how in practice one can efficiently use the combination of line-search and primal-duality by considering a convex optimization problem with a simple structure (for example, linearly constrained). [ABSTRACT FROM AUTHOR]

Sequential quadratic programming (SQP) methods are a popular class of methods for nonlinearly constrained optimization. They are particularly effective for solving a sequence of related problems, such as those arising in mixed-integer nonlinear programming and the optimization of functions subject to differential equation constraints. Recently, there has been considerable interest in the formulation of stabilized SQP methods, which are specifically designed to handle degenerate optimization problems. Existing stabilized SQP methods are essentially local in the sense that both the formulation and analysis focus on the properties of the methods in a neighborhood of a solution. A new SQP method is proposed that has favorable global convergence properties yet, under suitable assumptions, is equivalent to a variant of the conventional stabilized SQP method in the neighborhood of a solution. The method combines a primal-dual generalized augmented Lagrangian function with a flexible line search to obtain a sequence of improving estimates of the solution. The method incorporates a convexification algorithm that allows the use of exact second derivatives to define a convex quadratic programming (QP) subproblem without requiring that the Hessian of the Lagrangian be positive definite in the neighborhood of a solution. This gives the potential for fast convergence in the neighborhood of a solution. Additional benefits of the method are that each QP subproblem is regularized and the QP subproblem always has a known feasible point. Numerical experiments are presented for a subset of the problems from the CUTEr test collection. © 2013 Society for Industrial and Applied Mathematics.

In this paper, we investigate the homotopy path related to ℓ 1 -norm minimization problems with ℓ ∞ -norm constraints. We establish an enhanced upper bound on the number of linear segments in the path and provide an example showing that the number of segments is exponential in the number of variables in the worst case. We also use the homotopy framework to develop grid independent (cross-)validation schemes for sparse linear discriminant analysis and classification that make use of the entire path. Several numerical and statistical examples illustrate the applicability of the framework. [ABSTRACT FROM AUTHOR]

The augmented Lagrangian method (ALM) is a classical optimization tool that solves a given “difficult” (constrained) problem via finding solutions of a sequence of “easier” (often unconstrained) subproblems with respect to the original (primal) variable, wherein constraints satisfaction is controlled via the so-called dual variables. ALM is highly flexible with respect to how primal subproblems can be solved, giving rise to a plethora of different primal–dual methods. The powerful ALM mechanism has recently proved to be very successful in various large-scale and distributed applications. In addition, several significant advances have appeared, primarily on precise complexity results with respect to computational and communication costs in the presence of inexact updates and design and analysis of novel optimal methods for distributed consensus optimization. We provide a tutorial-style introduction to ALM and its variants for solving convex optimization problems in large-scale and distributed settings. We describe control-theoretic tools for the algorithms’ analysis and design, survey recent results, and provide novel insights into the context of two emerging applications: federated learning and distributed energy trading. [ABSTRACT FROM AUTHOR]

In this paper, we present a primal-dual interior point algorithm for semidefinite optimization problems based on a new class of kernel functions. These functions constitute a combination of the classic kernel function and a barrier term. We derive the complexity bounds for large and small-update methods respectively. We show that the best result of iteration bounds for large and small-update methods can be achieved, namely O (q n (log n) q + 1 q log n ε) for large-update methods and O (q 3 2 (log n) q + 1 q n log n ε) for small-update methods. We test the efficiency and the validity of our algorithm by running some computational tests, then we compare our numerical results with results obtained by algorithms based on different kernel functions. [ABSTRACT FROM AUTHOR]

We present a modification of a primal-dual algorithm based on a mixed augmented Lagrangian and a log-barrier penalty function. The goal of this new feature is to quickly detect infeasibility. An additional parameter is introduced to balance the minimization of the objective function and the realization of the constraints. The global convergence of the modified algorithm is analysed under mild assumptions. We also show that under a suitable choice of the parameters along the iterations, the rate of convergence of the algorithm to an infeasible stationary point is superlinear. This is the first local convergence result for the class of interior point methods in the infeasible case. We finally report some numerical experiments to show that this new algorithm is quite efficient to detect infeasibility and does not deteriorate the overall behavior in the general case. [ABSTRACT FROM AUTHOR]

This paper addresses the design and analysis of feedback-based online algorithms to control systems or networked systems based on performance objectives and engineering constraints that may evolve over time. The emerging time-varying convex optimization formalism is leveraged to model optimal operational trajectories of the systems, as well as explicit local and network-level operational constraints. Departing from existing batch and feed-forward optimization approaches, the design of the algorithms capitalizes on an online implementation of primal-dual projected-gradient methods; the gradient steps are, however, suitably modified to accommodate feedback from the system in the form of measurements, hence, the term “online optimization with feedback.” By virtue of this approach, the resultant algorithms can cope with model mismatches in the algebraic representation of the system states and outputs, they avoid pervasive measurements of exogenous inputs, and they naturally lend themselves to a distributed implementation. Under suitable assumptions, analytical convergence claims are established in terms of dynamic regret. Furthermore, when the synthesis of the feedback-based online algorithms is based on a regularized Lagrangian function, $\boldsymbol{Q}$ -linear convergence to solutions of the time-varying optimization problem is shown. [ABSTRACT FROM AUTHOR]

In this paper, we develop a primal-dual central trajectory interior-point algorithm for symmetric programming problems and establish its complexity analysis. The main contribution of the paper is that it uniquely equips the central trajectory algorithm with various selections of the displacement step while solving symmetric programming. To show the efficiency of the proposed algorithm, these selections of calculating the displacement step are compared in numerical examples for second-order cone programming, which is a special case of symmetric programming. [ABSTRACT FROM AUTHOR]

We study the ridge regression ( L 2 regularized least squares) problem and its dual, which is also a ridge regression problem. We observe that the optimality conditions describing the primal and dual optimal solutions can be formulated in several different but equivalent ways. The optimality conditions we identify form a linear system involving a structured matrix depending on a single relaxation parameter which we introduce for regularization purposes. This leads to the idea of studying and comparing, in theory and practice, the performance of the fixed point method applied to these reformulations. We compute the optimal relaxation parameters and uncover interesting connections between the complexity bounds of the variants of the fixed point scheme we consider. These connections follow from a close link between the spectral properties of the associated matrices. For instance, some reformulations involve purely imaginary eigenvalues; some involve real eigenvalues and others have all eigenvalues on the complex circle. We show that the deterministic Quartz method—which is a special case of the randomized dual coordinate ascent method with arbitrary sampling recently developed by Qu, Richtárik and Zhang—can be cast in our framework, and achieves the best rate in theory and in numerical experiments among the fixed point methods we study. Remarkably, the method achieves an accelerated convergence rate. Numerical experiments indicate that our main algorithm is competitive with the conjugate gradient method. [ABSTRACT FROM AUTHOR]

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

The particularities of the aircraft parts riveting process simulation necessitate the solution of a large amount of contact problems. A primal-dual interior-point method-based solver is proposed for solving such problems efficiently. The proposed method features a worst case polynomial complexity bound on the number of iterations, where n is the dimension of the problem and ε is a threshold related to desired accuracy. In practice, the convergence is often faster than this worst case bound, which makes the method applicable to large-scale problems. The computational challenge is solving the system of linear equations because the associated matrix is ill conditioned. To that end, the authors introduce a preconditioner and a strategy for determining effective initial guesses based on the physics of the problem. Numerical results are compared with ones obtained using the Goldfarb-Idnani algorithm. The results demonstrate the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In this work, we study the primal and dual formulations of the regularized least squares problem, in special norm L2, named ridge regression. We state the Gradient method for the corresponding primal-dual problem through a fixed point approach. For this formulation, we present an original convergence analysis involving the spectral radius of a suitable iteration matrix. The main contribution of this work is to accelerate the studied method by means of a memory-like strategy. Some connections with the spectral properties of the associated iteration matrices were established to prove the convergence of the accelerated method. Preliminary experiments showed the good performance of the proposed algorithm when applied to solve ill-conditioned problems, providing better results than the conjugate gradient method for this class of problems. [ABSTRACT FROM AUTHOR]

We introduce the notion of predicted decrease approximation (PDA) for constrained convex optimization, a flexible framework which includes as special cases known algorithms such as generalized conditional gradient, proximal gradient, greedy coordinate descent for separable constraints and working set methods for linear equality constraints with bounds. The new scheme allows the development of a unified convergence analysis for these methods. We further consider a partially strongly convex nonsmooth model and show that dual application of PDA-based methods yields new sublinear convergence rate estimates in terms of both primal and dual objectives. As an example of an application, we provide an explicit working set selection rule for SMO-type methods for training the support vector machine with an improved primal convergence analysis. [ABSTRACT FROM AUTHOR]

A strongly convex function of simple structure (for example, separable) is minimized under affine constraints. A dual problem is constructed and solved by applying a fast gradient method. The necessary properties of this method are established relying on which, under rather general conditions, the solution of the primal problem can be recovered with the same accuracy as the dual solution from the sequence generated by this method in the dual space of the problem. Although this approach seems natural, some previously unpublished rather subtle results necessary for its rigorous and complete theoretical substantiation in the required generality are presented. [ABSTRACT FROM AUTHOR]

We present a primal-dual algorithm for solving a constrained optimization problem. This method is based on a Newtonian method applied to a sequence of perturbed KKT systems. These systems follow from a reformulation of the initial problem under the form of a sequence of penalized problems, by introducing an augmented Lagrangian for handling the equality constraints and a log-barrier penalty for the inequalities. We detail the updating rules for monitoring the different parameters (Lagrange multiplier estimate, quadratic penalty and log-barrier parameter), in order to get strong global convergence properties. We show that one advantage of this approach is that it introduces a natural regularization of the linear system to solve at each iteration, for the solution of a problem with a rank deficient Jacobian of constraints. The numerical experiments show the good practical performances of the proposed method especially for degenerate problems. [ABSTRACT FROM AUTHOR]

Stabilized sequential quadratic programming (sSQP) methods for nonlinear optimization generate a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the local convergence analysis of an sSQP method that uses a line search with a primal-dual augmented Lagrangian merit function to enforce global convergence. The method is provably well-defined and is based on solving a strictly convex quadratic programming subproblem at each iteration. It is shown that the method has superlinear local convergence under assumptions that are no stronger than those required by conventional stabilized SQP methods. The fast local convergence is obtained by allowing a small relaxation of the optimality conditions for the quadratic programming subproblem in the neighborhood of a solution. In the limit, the line search selects the unit step length, which implies that the method does not suffer from the Maratos effect. The analysis indicates that the method has the same strong first- and second-order global convergence properties that have been established for augmented Lagrangian methods, yet is able to transition seamlessly to sSQP with fast local convergence in the neighborhood of a solution. Numerical results on some degenerate problems are reported. [ABSTRACT FROM AUTHOR]

Stabilized sequential quadratic programming (SQP) methods for nonlinear optimization are designed to provide a sequence of iterates with fast local convergence even when the active-constraint gradients are linearly dependent. This paper concerns the global convergence properties of a stabilized SQP method with a primal-dual augmented Lagrangian merit function. The proposed method incorporates two novel features. First, a flexible line search is used based on a direction formed from an approximate solution of a strictly convex quadratic programming (QP) subproblem and, when one exists, a direction of negative curvature for the primal-dual merit function. Second, when certain conditions hold, an approximate QP solution is computed by solving a single linear system defined in terms of an estimate of the optimal active set. We also establish two desirable convergence results. (i) It is shown that with an appropriate choice of termination condition, the method terminates in a finite number of iterations without the assumption of a constraint qualification. The method may be interpreted as an SQP method with an augmented Lagrangian safeguarding strategy. This safeguarding becomes relevant only when the iterates are converging to an infeasible stationary point of the norm of the constraint violations. Otherwise, the method terminates with a point that approximately satisfies certain second-order necessary conditions for optimality. In this situation, if all termination conditions are removed, then the limit points either satisfy the same secondorder necessary conditions exactly or fail to satisfy a weak second-order constraint qualification. (ii) The global convergence analysis concerns a specific algorithm that estimates the least curvature of the merit function at each step. If negative curvature directions are omitted, the analysis still applies and establishes convergence to either first-order solutions or infeasible stationary points. The superlinear convergence of the iterates and the formal local equivalence to stabilized SQP is established in a companion paper (Report CCoM 14-01, Center for Computational Mathematics, University of California, San Diego, 2014). [ABSTRACT FROM AUTHOR]

In this paper, a convex variational model for multiplicative noise removal is studied. Accelerating primal–dual method and proximal linearized alternating direction method are also discussed. An improved primal–dual method is proposed. Algorithms above produce more desired results than primal–dual algorithm when we solve the convex variational model. Inspired by the statistical property of the Gamma multiplicative noise and I-divergence, a modified convex variational model is proposed, for which the uniqueness of solution is also provided. Moreover, the property of the solution is presented. Without inner iterations, primal–dual method is efficient to the modified model, and running time can be reduced dramatically also with good restoration. When we set parameter α to 0, the convex variational model we proposed turns into the model in Steidl and Teuber (2010). By altering α , our model can be used for different noise level. [ABSTRACT FROM AUTHOR]

In this paper, we develop new subgradient methods for solving nonsmooth convex optimization problems. These methods guarantee the best possible rate of convergence for the whole sequence of test points. Our methods are applicable as efficient real-time stabilization tools for potential systems with infinite horizon. Preliminary numerical experiments confirm a high efficiency of the new schemes. [ABSTRACT FROM AUTHOR]

This paper studies distributed primal-dual strategies for adaptation and learning over networks from streaming data. Two first-order methods are considered based on the Arrow-Hurwicz (AH) and augmented Lagrangian (AL) techniques. Several revealing results are discovered in relation to the performance and stability of these strategies when employed over adaptive networks. The conclusions establish that the advantages that these methods exhibit for deterministic optimization problems do not necessarily carry over to stochastic optimization problems. It is found that they have narrower stability ranges and worse steady-state mean-square-error performance than primal methods of the consensus and diffusion type. It is also found that the AH technique can become unstable under a partial observation model, while the other techniques are able to recover the unknown under this scenario. A method to enhance the performance of AL strategies is proposed by tying the selection of the step-size to their regularization parameter. It is shown that this method allows the AL algorithm to approach the performance of consensus and diffusion strategies but that it remains less stable than these other strategies. [ABSTRACT FROM PUBLISHER]

We introduce and study two-stage stochastic symmetric programs with recourse to handle uncertainty in data defining (deterministic) symmetric programs in which a linear function is minimized over the intersection of an affine set and a symmetric cone. We present a Benders’ decomposition-based interior point algorithm for solving these problems and prove its polynomial complexity. Our convergence analysis proved by showing that the log barrier associated with the recourse function of stochastic symmetric programs behaves a strongly self-concordant barrier and forms a self-concordant family on the first stage solutions. Since our analysis applies to all symmetric cones, this algorithm extends Zhao’s results [G. Zhao, A log barrier method with Benders’ decomposition for solving two-stage stochastic linear programs, Math. Program. Ser. A 90 (2001) 507–536] for two-stage stochastic linear programs, and Mehrotra and Özevin’s results [S. Mehrotra, M.G. Özevin, Decomposition-based interior point methods for two-stage stochastic semidefinite programming, SIAM J. Optim. 18 (1) (2007) 206–222] for two-stage stochastic semidefinite programs. [ABSTRACT FROM AUTHOR]

This paper presents two classes of decomposition algorithms based on the proximal method of multipliers (PMM) introduced in the mid-1970s by Rockafellar for convex minimization. We first show that the PMM framework is at the root of many past and recent decomposition schemes suggested in the literature allowing for an elementary analysis of these methods through a unified scheme. We then prove various sublinear global convergence rate results for the two classes of PMM based decomposition algorithms for function values and constraints violation. Furthermore, under a mild assumption on the problem's data we derive rate of convergence results in terms of the original primal function values for both classes. As a by-product of our analysis we also obtain convergence of the sequences produced by the two algorithm classes to optimal primal-dual solutions. [ABSTRACT FROM AUTHOR]

Recently convex optimization models were successfully applied for solving various problems in image analysis and restoration. In this paper, we are interested in relations between convex constrained optimization problems of the form $\operatorname{argmin}\{ \varPhi(x) \mbox{ subject to } \varPsi(x) \le\tau\}$ and their penalized counterparts $\operatorname{argmin}\{\varPhi(x) + \lambda\varPsi(x)\}$. We recall general results on the topic by the help of an epigraphical projection. Then we deal with the special setting Ψ:=∥ L⋅∥ with L∈ℝ and Φ:= φ( H⋅), where H∈ℝ and φ:ℝ→ℝ∪{+∞} meet certain requirements which are often fulfilled in image processing models. In this case we prove by incorporating the dual problems that there exists a bijective function such that the solutions of the constrained problem coincide with those of the penalized problem if and only if τ and λ are in the graph of this function. We illustrate the relation between τ and λ for various problems arising in image processing. In particular, we point out the relation to the Pareto frontier for joint sparsity problems. We demonstrate the performance of the constrained model in restoration tasks of images corrupted by Poisson noise with the I-divergence as data fitting term φ and in inpainting models with the constrained nuclear norm. Such models can be useful if we have a priori knowledge on the image rather than on the noise level. [ABSTRACT FROM AUTHOR]

Problems involving estimation and inference under linear inequality constraints arise often in statistical modeling. In this article, we propose an algorithm to solve the quadratic programming problem of minimizingfor positive definiteQ, whereis constrained to be in a closed polyhedral convex cone, and them×nmatrixis not necessarily full row rank. The three-step algorithm is intuitive and easy to code. Code is provided in theRprogramming language. [ABSTRACT FROM AUTHOR]

We propose a new class of incremental primal-dual techniques for solving nonlinear programming problems with special structure. Specifically, the objective functions of the problems are sums of independent nonconvex continuously differentiable terms minimized subject to a set of nonlinear constraints for each term. The technique performs successive primal-dual increments for each decomposition term of the objective function. The primal-dual increments are calculated by performing one Newton step towards the solution of the Karush-Kuhn-Tucker optimality conditions of each subproblem associated with each objective function term. We show that the resulting incremental algorithm is q-linearly convergent under mild assumptions for the original problem. [ABSTRACT FROM AUTHOR]

We study the local behavior of a primal-dual inexact interior point methods for solving nonlinear systems arising from the solution of nonlinear optimization problems or more generally from nonlinear complementarity problems. The algorithm is based on the Newton method applied to a sequence of perturbed systems that follows by perturbation of the complementarity equations of the original system. In case of an exact solution of the Newton system, it has been shown that the sequence of iterates is asymptotically tangent to the central path (Armand and Benoist in Math. Program. 115:199-222, ). The purpose of the present paper is to extend this result to an inexact solution of the Newton system. We give quite general conditions on the different parameters of the algorithm, so that this asymptotic property is satisfied. Some numerical tests are reported to illustrate our theoretical results. [ABSTRACT FROM AUTHOR]

We propose a solution to the problem of boundary artifacts appearing in several recently published fast deblurring algorithms based on iterated shrinkage thresholding in a sparse domain and Fourier domain deconvolution. Our approach adapts an idea proposed by Reeves for deconvolution by the Wiener filter. The time of computation less than doubles. [ABSTRACT FROM AUTHOR]

In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large- and small-update methods are derived, namely, O( nlog( n/ɛ)) and $O(\sqrt n \log (n/\varepsilon ))$. This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other primal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions. [ABSTRACT FROM AUTHOR]

Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we consider the formulation of subproblems in which the objective function is a generalization of the Hestenes-Powell augmented Lagrangian function. The main feature of the generalized function is that it is minimized with respect to both the primal and the dual variables simultaneously. The benefits of this approach include: (i) the ability to control the quality of the dual variables during the solution of the subproblem; (ii) the availability of improved dual estimates on early termination of the subproblem; and (iii) the ability to regularize the subproblem by imposing explicit bounds on the dual variables. We propose two primal-dual variants of conventional primal methods: a primal-dual bound constrained Lagrangian (pdBCL) method and a primal-dual ℓ linearly constrained Lagrangian (pd ℓLCL) method. Finally, a new sequential quadratic programming (pdSQP) method is proposed that uses the primal-dual augmented Lagrangian as a merit function. [ABSTRACT FROM AUTHOR]