Search

Solving feasibility problems is a central task in mathematics and the applied sciences. One particularly successful method is the Douglas--Rachford algorithm. In this paper, we provide many new conditions sufficient for finite convergence. Numerou s examples illustrate our results. [ABSTRACT FROM AUTHOR]

Motivated by an obstacle problem for a membrane subject to cohesion forces, constrained minimization problems involving a nonconvex and nondifferentiable objective functional representing the total potential energy are considered. The associated first-order optimality system leads to a hemivaxiational inequality, which can also be interpreted as a special complementarity problem in function space. Besides an analytical investigation of first-order optimality, a primal-dual active set solver is introduced. It is associated to a limit case of a semismooth Newton method for a regularized version of the underlying problem class. For the numerical algorithms studied in this paper, global as well as local convergence properties are derived and verified numerically. [ABSTRACT FROM AUTHOR]

Gould and Robinson [SIAM J. Optim., 20 (2010), pp. 2023-2048] proved global convergence of a second derivative SQP method for minimizing the exact ℓ1-merit function for a fixed value of the penalty parameter. This result required the properties of a so-called Cauchy step, which was itself computed from a so-called predictor step. In addition, they allowed for the additional computation of a variety of (optional) accelerator steps that were intended to improve the efficiency of the algorithm. The main purpose of this paper is to prove that a nonmonotone variant of the algorithm is quadratically convergent for two specific realizations of the accelerator step; this is verified with preliminary numerical results on the Hock and Schittkowski test set. Once fast local convergence is established, we consider two specific aspects of the algorithm that are important for an efficient implementation. First, we discuss a strategy for defining the positive-definite matrix Bk used in computing the predictor step that is based on a limited-memory BFGS update. Second, we provide a simple strategy for updating the penalty parameter based on approximately minimizing the ℓ1-penalty function over a sequence of increasing values of the penalty parameter. [ABSTRACT FROM AUTHOR]

This paper presents a new method for the numerical solution of nonlinear multiobjective optimization problems with an arbitrary partial ordering in the objective space induced by a closed pointed convex cone. This algorithm is based on the well-known scalarization approach by Pascoletti and Serafini and adaptively controls the scalarization parameters using new sensitivity results. The computed image points give a nearly equidistant approximation of the whole Pareto surface. The effectiveness of this new method is demonstrated with various test problems and an applied problem from medicine. [ABSTRACT FROM AUTHOR]

We introduce two-stage stochastic semidefinite programs with recourse and present an interior point algorithm for solving these problems using Bender's decomposition. This decomposition algorithm and its analysis extend Zhao's results [Math. Program., 90 (2001), pp. 507-536] for stochastic linear programs. The convergence results are proved by showing that the logarithmic barrier associated with the recourse function of two-stage stochastic semidefinite programs with recourse is a strongly self-concordant barrier on the first stage solutions. The short-step variant of the algorithm requires O(√p + Kr ln μ0/∈) Newton iterations to follow the first stage central path from a starting value of the barrier parameter μ0 to a terminating value ∈. The long-step variant requires O((p + Kr) lnμ0/∈) damped Newton iterations. The calculation of the gradient and Hessian of the recourse function and the first stage Newton direction decomposes across the second stage scenarios. [ABSTRACT FROM AUTHOR]

The problem of the singular value decomposition of a matrix can be brought into an optimization problem on the product of two Stiefel manifolds of different sizes. The steepest descent, the conjugate gradient, and Newton's methods for the problem are developed and applied with several numerical experiments. These algorithms do not need the preconditioning that is inevitable in the usual singular value decomposition algorithm. The present Newton's method can serve to make more accurate the singular value decomposition obtained by other existing algorithms. In addition, degenerate optimal solutions are studied, together with numerical experiments, to show that those solutions form a disconnected submanifold. [ABSTRACT FROM AUTHOR]

Computational convex analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of computational convex analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is to disseminate widely the most efficient numerical algorithms useful for applications in image processing (computing the distance transform, the generalized distance transform, and mathematical morphology operators), partial differential equations (solving Hamilton--Jacobi equations and using differential equations numerical schemes to compute the convex envelope), max-plus algebra (computing the equivalent of the fast Fourier transform), multifractal analysis, etc. The fields of applications include, among others, computer vision, robot navigation, thermodynamics, electrical networks, medical imaging, and network communication. [ABSTRACT FROM AUTHOR]

We study some methods of subgradient projections for solving a convex feasibility problem with general (not necessarily hyperplanes or half-spaces) convex sets in the inconsistent case and propose a strategy that controls the relaxation parameters in a specific self-adapting manner. This strategy leaves enough user flexibility but gives a mathematical guarantee for the algorithm's behavior in the inconsistent case. We present the numerical results of computational experiments that illustrate the computational advantage of the new method. [ABSTRACT FROM AUTHOR]

We study the convergence of an iterative projection/reflection algorithm originally proposed for solving what are known as phase retrieval problems in optics. There are two features that frustrate any analysis of iterative methods for solving the phase retrieval problem: nonconvexity and infeasibility. The algorithm that we developed, called relaxed averaged alternating reflections (RAAR), was designed primarily to address infeasibility, though our strategy has advantages for nonconvex problems as well. In the present work we investigate the asymptotic behavior of the RAAR algorithm for the general problem of finding points that achieve the minimum distance between two closed convex sets in a Hilbert space with empty intersection, and for the problem of finding points that achieve a local minimum distance between one closed convex set and a closed prox-regular set, also possibly nonintersecting. The nonconvex theory includes and expands prior results limited to convex sets with nonempty intersection. To place the RAAR algorithm in context, we develop parallel statements about the standard alternating projections algorithm and gradient descent. All of the various algorithms are unified as instances of iterated averaged alternating proximal reflectors applied to a sum of regularized maximal monotone mappings. [ABSTRACT FROM AUTHOR]

A class of trust-region methods is presented for solving unconstrained nonlinear and possibly nonconvex discretized optimization problems, like those arising in systems governed by partial differential equations. The algorithms in this class make use of the discretization level as a means of speeding up the computation of the step. This use is recursive, leading to true multilevel/multiscale optimization methods reminiscent of multigrid methods in linear algebra and the solution of partial differential equations. A simple algorithm of the class is then described and its numerical performance is shown to be numerically promising. This observation then motivates a proof of global convergence to first-order stationary points on the fine grid that is valid for all algorithms in the class. [ABSTRACT FROM AUTHOR]

An interior-point trust-region algorithm is proposed for minimizing a general (nonconvex) quadratic objective function in the intersection of a symmetric cone and an affine subspace. The algorithm uses a trust-region model to ensure descent on a suitable merit function. Global first-order and second-order convergence results are proved. Numerical results are presented. [ABSTRACT FROM AUTHOR]

An active set algorithm (ASA) for box constrained optimization is developed. The algorithm consists of a nonmonotone gradient projection step, an unconstrained optimization step, and a set of rules for branching between the two steps. Global convergence to a stationary point is established. For a nondegenerate stationary point, the algorithm eventually reduces to unconstrained optimization without restarts. Similarly, for a degenerate stationary point, where the strong second order sufficient optimality condition holds, the algorithm eventually reduces to unconstrained optimization without restarts. A specific implementation of the ASA is given which exploits the recently developed cyclic Barzilai-Borwein (CBB) algorithm for the gradient projection step and the recently developed conjugate gradient algorithm CG_DESCENT for unconstrained optimization. Numerical experiments are presented using box constrained problems in the CUTEr and MINPACK-2 test problem libraries. [ABSTRACT FROM AUTHOR]

Interior point methods for nonlinear programs (NLPs) are adapted for solution of mathematical programs with complementarity constraints (MPCCs). The constraints of the MPCC are suitably relaxed so as to guarantee a strictly feasible interior for the inequality constraints. The standard primal-dual algorithm has been adapted with a modified step calculation. The algorithm is shown to be superlinearly convergent in the neighborhood of the solution set under assumptions of MPCC-LICQ, strong stationarity and upper level strict complementarity. The modification can be easily accommodated within most nonlinear programming interior point algorithms with identical local behavior. Numerical experience is also presented and holds promise for the proposed method. [ABSTRACT FROM AUTHOR]

We present a primal-dual interior-point algorithm for solving optimization problems with nonlinear inequality constraints. The algorithm has some of the theoretical properties of trust region methods, but works entirely by line search. Global convergence properties are derived without assuming regularity conditions. The penalty parameter ρ in the merit function is updated adaptively and plays two roles in the algorithm. First, it guarantees that the search directions are descent directions of the updated merit function. Second, it helps to determine a suitable search direction in a decomposed SQP step. It is shown that if ρ is bounded for each barrier parameter μ, then every limit point of the sequence generated by the algorithm is a Karush -- Kuhn -- Tucker point, whereas if ρ is unbounded for some μ, then the sequence has a limit point which is either a Fritz -- John point or a stationary point of a function measuring the violation of the constraints. Numerical results confirm that the algorithm produces the correct results for some hard problems, including the example provided by Wächter and Biegler, for which many of the existing line search--based interior-point methods have failed to find the right answers. [ABSTRACT FROM AUTHOR]