Search

This paper considers the relaxed Peaceman-Rachford (PR) splitting method for finding an approximate solution of a monotone inclusion whose underlying operator consists of the sum of two maximal strongly monotone operators. Using general results obtained in the setting of a non-Euclidean hybrid proximal extragradient framework, we extend a previous convergence result on the iterates generated by the relaxed PR splitting method, as well as establish new pointwise and ergodic convergence rate results for the method whenever an associated relaxation parameter is within a certain interval. An example is also discussed to demonstrate that the iterates may not converge when the relaxation parameter is outside this interval. [ABSTRACT FROM AUTHOR]

In this paper we consider a mathematical model for magmatic mixtures based on the Gibbs free energy. Different reformulations of the problem are presented and some theoretical results about the existence and number of solutions are derived. Finally, two homotopy methods and a global optimization one are introduced and computationally tested. One of the homotopy methods returns a single solution of the problem, while the other is able to return multiple solutions (often all of them). The global optimization method is a branch-and-reduce one with a theoretical guarantee of detecting all the solutions, although some numerical difficulties, resulting in a loss of a few of them, may have to be faced. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a variety of approaches to obtain lower bounds for multi-level production planning problems with big bucket capacities, i.e., problems in which multiple items compete for the same resources. We give an extensive survey of both known and new methods, and also establish relationships between some of these methods that, to our knowledge, have not been presented before. As will be highlighted, understanding the substructures of difficult problems provide crucial insights on why these problems are hard to solve, and this is addressed by a thorough analysis in the paper. We conclude with computational results on a variety of widely used test sets, and a discussion of future research. [ABSTRACT FROM AUTHOR]

This paper demonstrates a customized application of the classical proximal point algorithm (PPA) to the convex minimization problem with linear constraints. We show that if the proximal parameter in metric form is chosen appropriately, the application of PPA could be effective to exploit the simplicity of the objective function. The resulting subproblems could be easier than those of the augmented Lagrangian method (ALM), a benchmark method for the model under our consideration. The efficiency of the customized application of PPA is demonstrated by some image processing problems. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers (ADMM) recently has found many applications in various domains whose models can be represented or reformulated as a separable convex minimization model with linear constraints and an objective function in sum of two functions without coupled variables. For more complicated applications that can only be represented by such a multi-block separable convex minimization model whose objective function is the sum of more than two functions without coupled variables, it was recently shown that the direct extension of ADMM is not necessarily convergent. On the other hand, despite the lack of convergence, the direct extension of ADMM is empirically efficient for many applications. Thus we are interested in such an algorithm that can be implemented as easily as the direct extension of ADMM, while with comparable or even better numerical performance and guaranteed convergence. In this paper, we suggest correcting the output of the direct extension of ADMM slightly by a simple correction step. The correction step is simple in the sense that it is completely free from step-size computing and its step size is bounded away from zero for any iterate. A prototype algorithm in this prediction-correction framework is proposed; and a unified and easily checkable condition to ensure the convergence of this prototype algorithm is given. Theoretically, we show the contraction property, prove the global convergence and establish the worst-case convergence rate measured by the iteration complexity for this prototype algorithm. The analysis is conducted in the variational inequality context. Then, based on this prototype algorithm, we propose a class of specific ADMM-based algorithms that can be used for three-block separable convex minimization models. Their numerical efficiency is verified by an image decomposition problem. [ABSTRACT FROM AUTHOR]

In this paper we present a new algorithmic realization of a projection-based scheme for general convex constrained optimization problem. The general idea is to transform the original optimization problem to a sequence of feasibility problems by iteratively constraining the objective function from above until the feasibility problem is inconsistent. For each of the feasibility problems one may apply any of the existing projection methods for solving it. In particular, the scheme allows the use of subgradient projections and does not require exact projections onto the constraints sets as in existing similar methods. We also apply the newly introduced concept of superiorization to optimization formulation and compare its performance to our scheme. We provide some numerical results for convex quadratic test problems as well as for real-life optimization problems coming from medical treatment planning. [ABSTRACT FROM AUTHOR]

Structure-enforced matrix factorization (SeMF) represents a large class of mathematical models appearing in various forms of principal component analysis, sparse coding, dictionary learning and other machine learning techniques useful in many applications including neuroscience and signal processing. In this paper, we present a unified algorithm framework, based on the classic alternating direction method of multipliers (ADMM), for solving a wide range of SeMF problems whose constraint sets permit low-complexity projections. We propose a strategy to adaptively adjust the penalty parameters which is the key to achieving good performance for ADMM. We conduct extensive numerical experiments to compare the proposed algorithm with a number of state-of-the-art special-purpose algorithms on test problems including dictionary learning for sparse representation and sparse nonnegative matrix factorization. Results show that our unified SeMF algorithm can solve different types of factorization problems as reliably and as efficiently as special-purpose algorithms. In particular, our SeMF algorithm provides the ability to explicitly enforce various combinatorial sparsity patterns that, to our knowledge, has not been considered in existing approaches. [ABSTRACT FROM AUTHOR]

In this paper, we propose, analyze and test primal and dual versions of the alternating direction algorithm for the sparse signal reconstruction from its major noise contained observation data. The algorithm minimizes a convex non-smooth function consisting of the sum of ℓ-norm regularization term and ℓ-norm data fidelity term. We minimize the corresponding augmented Lagrangian function alternatively from either primal or dual forms. Both of the resulting subproblems admit explicit solutions either by using a one-dimensional shrinkage or by an efficient Euclidean projection. The algorithm is easily implementable and it requires only two matrix-vector multiplications per-iteration. The global convergence of the proposed algorithm is established under some technical conditions. The extensions to the non-negative signal recovery problem and the weighted regularization minimization problem are also discussed and tested. Numerical results illustrate that the proposed algorithm performs better than the state-of-the-art algorithm YALL1. [ABSTRACT FROM AUTHOR]

This paper develops a Bregman operator splitting algorithm with variable stepsize (BOSVS) for solving problems of the form $\min\{\phi(Bu) +1/2\|Au-f\|_{2}^{2}\}$, where ϕ may be nonsmooth. The original Bregman Operator Splitting (BOS) algorithm employed a fixed stepsize, while BOSVS uses a line search to achieve better efficiency. These schemes are applicable to total variation (TV)-based image reconstruction. The stepsize rule starts with a Barzilai-Borwein (BB) step, and increases the nominal step until a termination condition is satisfied. The stepsize rule is related to the scheme used in SpaRSA (Sparse Reconstruction by Separable Approximation). Global convergence of the proposed BOSVS algorithm to a solution of the optimization problem is established. BOSVS is compared with other operator splitting schemes using partially parallel magnetic resonance image reconstruction problems. The experimental results indicate that the proposed BOSVS algorithm is more efficient than the BOS algorithm and another split Bregman Barzilai-Borwein algorithm known as SBB. [ABSTRACT FROM AUTHOR]

In this paper, a restricted additive Schwarz method is introduced for solving the linear complementarity problem that involves an H-matrix. We show that the sequence generated by the restricted additive Schwarz method converges to the unique solution of the problem without any restriction on the initial point. Moreover, the comparison theorem is given between different versions of the restricted additive Schwarz method by using the weighted max-norm. We also show that the restricted additive Schwarz method is much better than the corresponding additive Schwarz variants in terms of the iteration number and the execution time. [ABSTRACT FROM AUTHOR]

This paper is concerned with the numerical solution of a class of variational inequalities of the second kind, involving the p-Laplacian operator. This kind of problems arise, for instance, in the mathematical modelling of non-Newtonian fluids. We study these problems by using a regularization approach, based on a Huber smoothing process. Well posedness of the regularized problems is proved, and convergence of the regularized solutions to the solution of the original problem is verified. We propose a preconditioned descent method for the numerical solution of these problems and analyze the convergence of this method in function spaces. The existence of admissible descent directions is established by variational methods and admissible steps are obtained by a backtracking algorithm which approximates the objective functional by polynomial models. Finally, several numerical experiments are carried out to show the efficiency of the methodology here introduced. [ABSTRACT FROM AUTHOR]

This paper presents a comparative computational study of the variance reduction techniques antithetic variates and Latin hypercube sampling when used for assessing solution quality in stochastic programming. Three Monte Carlo sampling-based procedures that provide point and interval estimators of optimality gap are considered: one that uses multiple replications, and two others with an alternative sample variance estimator that use single or two replications. Theoretical justification for using these alternative sampling techniques is discussed. In particular, we discuss asymptotic properties of the resulting estimators using Latin hypercube sampling for single- and two-replication procedures in detail. These theoretical considerations result in some subtle changes in the implementation of the procedures. A collection of two-stage stochastic linear test problems with different characteristics is used to empirically compare the three procedures for assessing solution quality with these variance reduction techniques. [ABSTRACT FROM AUTHOR]

In this paper, we propose an augmented Lagrangian method based on the accelerated proximal gradient (APG) strategy for an inverse damped gyroscopic eigenvalue problem (IDGEP), which is a special case of the classical inverse quadratic eigenvalue problem. Under mild conditions, we show that the whole sequence of iterations generated by the proposed algorithm converges to the unique solution of the IDGEP. In view of the iteration-complexity, the proposed algorithm requires at most $$O(\log (\varepsilon ^{-1}))$$ outer iterations and at most $$O(\varepsilon ^{-1})$$ APG calls to obtain an $$\varepsilon $$ -feasible and $$\varepsilon $$ -optimal solution of the IDGEP. Numerical results indicate that the proposed algorithm can solve the test problems efficiently. [ABSTRACT FROM AUTHOR]

In this paper the authors consider a parameter estimation problem for a nonlinear systems, which consists of one parabolic equation for the concentration and two elliptic equations for the potentials. The measurements are given as boundary values for one of the potentials. For its numerical solution the Gauss Newton method is applied. To speed up the solution process, a reduced-order approach based on proper orthogonal decomposition is utilized, where the accuracy is controlled by error estimators. Parameters, which can not be identified from the measurements, are identified by the subset selection method with $$QR$$ pivoting. Numerical examples show the efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper presents a Nash equilibrium model where the underlying objective functions involve uncertainty and nonsmoothness. The well-known sample average approximation method is applied to solve the problem and the first order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a statistical estimator (a Nash equilibrium or a Nash-C-stationary point) obtained from sample average approximate equilibrium problem converges to its true counterpart. Moreover, under some calmness conditions of the Clarke generalized derivatives, it is shown that with probability approaching one exponentially fast by increasing sample size, the Nash-C-stationary point converges to a weak Nash-C-stationary point of the true problem. Finally, the model is applied to stochastic Nash equilibrium problem in the wholesale electricity market. [ABSTRACT FROM AUTHOR]

The aim of this paper is to develop an efficient algorithm for solving a class of unconstrained nondifferentiable convex optimization problems in finite dimensional spaces. To this end we formulate first its Fenchel dual problem and regularize it in two steps into a differentiable strongly convex one with Lipschitz continuous gradient. The doubly regularized dual problem is then solved via a fast gradient method with the aim of accelerating the resulting convergence scheme. The theoretical results are finally applied to an l regularization problem arising in image processing. [ABSTRACT FROM AUTHOR]

We consider the convex minimization problem with linear constraints and a block-separable objective function which is represented as the sum of three functions without coupled variables. To solve this model, it is empirically effective to extend straightforwardly the alternating direction method of multipliers (ADM for short). But, the convergence of this straightforward extension of ADM is still not proved theoretically. Based on ADM's straightforward extension, this paper presents a new splitting method for the model under consideration, which is empirically competitive to the straightforward extension of ADM and meanwhile the global convergence can be proved under standard assumptions. At each iteration, the new method corrects the output of the straightforward extension of ADM by some slight correction computation to generate a new iterate. Thus, the implementation of the new method is almost as easy as that of ADM's straightforward extension. We show the numerical efficiency of the new method by some applications in the areas of image processing and statistics. [ABSTRACT FROM AUTHOR]

Optimization problems using total variation frequently appear in image analysis models, in which the sharp edges of images are preserved. Direct gradient descent methods usually yield very slow convergence when used for such optimization problems. Recently, many duality-based gradient projection methods have been proposed to accelerate the speed of convergence. In this dual formulation, the cost function of the optimization problem is singular, and the constraint set is not a polyhedral set. In this paper, we establish two inequalities related to projected gradients and show that, under some non-degeneracy conditions, the rate of convergence is linear. [ABSTRACT FROM AUTHOR]

In recent years, convex optimization methods were successfully applied for various image processing tasks and a large number of first-order methods were designed to minimize the corresponding functionals. Interestingly, it was shown recently in Grewenig et al. () that the simple idea of so-called 'superstep cycles' leads to very efficient schemes for time-dependent (parabolic) image enhancement problems as well as for steady state (elliptic) image compression tasks. The 'superstep cycles' approach is similar to the nonstationary (cyclic) Richardson method which has been around for over sixty years. In this paper, we investigate the incorporation of superstep cycles into the projected gradient method. We show for two problems in compressive sensing and image processing, namely the LASSO approach and the Rudin-Osher-Fatemi model that the resulting simple cyclic projected gradient algorithm can numerically compare with various state-of-the-art first-order algorithms. However, due to the nonlinear projection within the algorithm convergence proofs even under restrictive assumptions on the linear operators appear to be hard. We demonstrate the difficulties by studying the simplest case of a two-cycle algorithm in ℝ with projections onto the Euclidean ball. [ABSTRACT FROM AUTHOR]

In this paper efficient computational strategies are presented to speed-up the analysis of random media and components. In particular, a Hybrid Stochastic Optimization (HSO) tool, based on the synergy between various algorithms, i.e. Genetic Algorithms, Simulated Annealing as well as Tabu-list is suggested to reconstruct a set of microstructures starting from probabilistic descriptors. The subsequent analysis (e.g. Finite Element analysis) can be performed to obtain the desired macroscopic quantity of interest and, providing a link between the micro- and the macro-scale. Different computational speed-up strategies are also presented. The proposed simulation approach is highly parallelizable, flexible and scalable. It can be adopted by other fields as well where an optimization analysis is required and a set of different solutions should be identified in order to perform computational experiments. Numerical examples demonstrate the applicability of the proposed strategies for realistic problems. [ABSTRACT FROM AUTHOR]

The paper considers the problem of covering compact polygonal set by identical circles of minimal radius. A mathematical model of the problem based on Voronoi polygons is constructed and its characteristics are investigated. On the ground of the characteristics a modification of the Zoutendijk feasible directions method is developed to search local minima. A special approach is suggested to choose starting points. Many computational examples are given. [ABSTRACT FROM AUTHOR]

In this paper, we study an extension of the Linear Multiple Choice Knapsack (LMCK) Problem that considers two objectives. The problem can be used to find the optimal allocation of an available resource to a group of disjoint sets of activities, while also ensuring that a certain balance on the resource amounts allocated to the activity sets is attained. The first objective maximizes the profit incurred by the implementation of the considered activities. The second objective minimizes the maximum difference between the resource amounts allocated to any two sets of activities. We present the mathematical formulation and explore the fundamental properties of the problem. Based on these properties, we develop an efficient algorithm that obtains the entire nondominated frontier. The algorithm is more efficient than the application of the general theory of multiple objective linear programming (MOLP), although there is a close underlying relationship between the two. We present theoretical findings which provide insight into the behavior of the algorithm, and report computational results which demonstrate its efficiency for randomly generated problems. [ABSTRACT FROM AUTHOR]

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature. [ABSTRACT FROM AUTHOR]

In last decades, there has been much effort on the solution and the analysis of the nonlinear complementarity problem (NCP) by reformulating NCP as an unconstrained minimization involving an NCP function. In this paper, we propose a family of new NCP functions, which include the Fischer-Burmeister function as a special case, based on a p-norm with p being any fixed real number in the interval (1,+∞), and show several favorable properties of the proposed functions. In addition, we also propose a descent algorithm that is indeed derivative-free for solving the unconstrained minimization based on the merit functions from the proposed NCP functions. Numerical results for the test problems from MCPLIB indicate that the descent algorithm has better performance when the parameter p decreases in (1,+∞). This implies that the merit functions associated with p ∈ (1, 2), for example p = 1.5, are more effective in numerical computations than the Fischer-Burmeister merit function, which exactly corresponds to p = 2. [ABSTRACT FROM AUTHOR]

A mathematical model of portfolio optimization is usually quantified with mean-risk models offering a lucid form of two criteria with possible trade-off analysis. In the classical Markowitz model the risk is measured by a variance, thus resulting in a quadratic programming model. Following Sharpe's work on linear approximation to the mean-variance model, many attempts have been made to linearize the portfolio optimization problem. There were introduced several alternative risk measures which are computationally attractive as (for discrete random variables) they result in solving linear programming (LP) problems. Typical LP computable risk measures, like the mean absolute deviation (MAD) or the Gini's mean absolute difference (GMD) are symmetric with respect to the below-mean and over-mean performances. The paper shows how the measures can he further combined to extend their modeling capabilities with respect to enhancement of the below-mean downside risk aversion. The relations of the below-mean downside stochastic dominance are formally introduced and the corresponding techniques to enhance risk measures ale derived. The resulting mean-risk models generate efficient solutions with respect to second degree stochastic dominance, while at the same time preserving simplicity and LP computability of the original models. The models are tested on real-life historical data. [ABSTRACT FROM AUTHOR]

In this part of the two-part series of papers, algorithms for solving some variable programming (VP) problems proposed in Part I are investigated. It is demonstrated that the non-differentiability and the discontinuity of the maximum objective function, as well as the summation objective function in the VP problems constitute difficulty in finding their solutions, Based on the principle of statistical mechanics, we derive smooth functions to approximate these non-smooth objective functions with specific activated feasible sets. By transforming the minimax problem and the corresponding variable programming problems into their smooth versions we can solve the resulting problems by some efficient algorithms for smooth functions. Relevant theoretical underpinnings about the smoothing techniques are established. The algorithms, in which the minimization of the smooth functions is carried out by the standard quasi-Newton method with BFGS formula, are tested on some standard minimax and variable programming problems. The numerical results show that the smoothing techniques yield accurate optimal solutions and that the algorithms proposed are feasible and efficient. [ABSTRACT FROM AUTHOR]

In this two-part series of papers, a new generalized minimax optimization model, termed variable programming (VP), is developed to solve dynamically a class of multi-objective optimization problems with non-decomposable structure. It is demonstrated that such type of problems is more general than existing optimization models. In this part, the VP model is proposed first, and the relationship between variable programming and the general constrained nonlinear programming is established. To illustrate its practicality, problems on investment and the low-side-lobe conformal antenna array pattern synthesis to which VP can be appropriately applied are discussed for substantiation. Then, theoretical underpinnings of the VP problems are established. Difficulties in dealing with the VP problems are discussed. With some mild assumptions, the necessary conditions for the unconstrained VP problems with arbitrary and specific activated feasible sets are derived respectively. The necessary conditions for the corresponding constrained VP problems with the mild hypotheses are also examined. Whilst discussion in this part is concentrated on the formulation of the VP model and its theoretical underpinnings, construction of solution algorithms is discussed in Part II. [ABSTRACT FROM AUTHOR]

The classical multi-set split feasibility problem seeks a point in the intersection of finitely many closed convex domain constraints, whose image under a linear mapping also lies in the intersection of finitely many closed convex range constraints. Split feasibility generalizes important inverse problems including convex feasibility, linear complementarity, and regression with constraint sets. When a feasible point does not exist, solution methods that proceed by minimizing a proximity function can be used to obtain optimal approximate solutions to the problem. We present an extension of the proximity function approach that generalizes the linear split feasibility problem to allow for non-linear mappings. Our algorithm is based on the principle of majorization-minimization, is amenable to quasi-Newton acceleration, and comes complete with convergence guarantees under mild assumptions. Furthermore, we show that the Euclidean norm appearing in the proximity function of the non-linear split feasibility problem can be replaced by arbitrary Bregman divergences. We explore several examples illustrating the merits of non-linear formulations over the linear case, with a focus on optimization for intensity-modulated radiation therapy. [ABSTRACT FROM AUTHOR]

We propose a method for finding approximate solutions to multiple-choice knapsack problems. To this aim we transform the multiple-choice knapsack problem into a bi-objective optimization problem whose solution set contains solutions of the original multiple-choice knapsack problem. The method relies on solving a series of suitably defined linearly scalarized bi-objective problems. The novelty which makes the method attractive from the computational point of view is that we are able to solve explicitly those linearly scalarized bi-objective problems with the help of the closed-form formulae. The method is computationally analyzed on a set of large-scale problem instances (test problems) of two categories: uncorrelated and weakly correlated. Computational results show that after solving, in average 10 scalarized bi-objective problems, the optimal value of the original knapsack problem is approximated with the accuracy comparable to the accuracies obtained by the greedy algorithm and an exact algorithm. More importantly, the respective approximate solution to the original knapsack problem (for which the approximate optimal value is attained) can be found without resorting to the dynamic programming. In the test problems, the number of multiple-choice constraints ranges up to hundreds with hundreds variables in each constraint. [ABSTRACT FROM AUTHOR]

The optimal control of a system of nonlinear reaction-diffusion equations is considered that covers several important equations of mathematical physics. In particular equations are covered that develop traveling wave fronts, spiral waves, scroll rings, or propagating spot solutions. Well-posedness of the system and differentiability of the control-to-state mapping are proved. Associated optimal control problems with pointwise constraints on the control and the state are discussed. The existence of optimal controls is proved under weaker assumptions than usually expected. Moreover, necessary first-order optimality conditions are derived. Several challenging numerical examples are presented that include in particular an application of pointwise state constraints where the latter prevent a moving localized spot from hitting the domain boundary. [ABSTRACT FROM AUTHOR]

We revisit the gradient projection method in the framework of nonlinear optimal control problems with bang-bang solutions. We obtain the strong convergence of the iterative sequence of controls and the corresponding trajectories. Moreover, we establish a convergence rate, depending on a constant appearing in the corresponding switching function and prove that this convergence rate estimate is sharp. Some numerical illustrations are reported confirming the theoretical results. [ABSTRACT FROM AUTHOR]

We study large-scale extended trust-region subproblems ( eTRS) i.e., the minimization of a general quadratic function subject to a norm constraint, known as the trust-region subproblem ( TRS) but with an additional linear inequality constraint. It is well known that strong duality holds for the TRS and that there are efficient algorithms for solving large-scale TRS problems. It is also known that there can exist at most one local non-global minimizer ( LNGM) for TRS. We combine this with known characterizations for strong duality for eTRS and, in particular, connect this with the so-called hard case for TRS. We begin with a recent characterization of the minimum for the TRS via a generalized eigenvalue problem and extend this result to the LNGM. We then use this to derive an efficient algorithm that finds the global minimum for eTRS by solving at most three generalized eigenvalue problems. [ABSTRACT FROM AUTHOR]

Quasi-Monte Carlo algorithms are studied for designing discrete approximations of two-stage linear stochastic programs with random right-hand side and continuous probability distribution. The latter should allow for a transformation to a distribution with independent marginals. The two-stage integrands are piecewise linear, but neither smooth nor lie in the function spaces considered for QMC error analysis. We show that under some weak geometric condition on the two-stage model all terms of their ANOVA decomposition, except the one of highest order, are continuously differentiable and that first and second order ANOVA terms have mixed first order partial derivatives and belong to $$L_{2}$$ . Hence, randomly shifted lattice rules (SLR) may achieve the optimal rate of convergence $$O(n^{-1+\delta })$$ with $$\delta \in (0,\frac{1}{2}]$$ and a constant not depending on the dimension if the effective superposition dimension is at most two. We discuss effective dimensions and dimension reduction for two-stage integrands. The geometric condition is shown to be satisfied almost everywhere if the underlying probability distribution is normal and principal component analysis (PCA) is used for transforming the covariance matrix. Numerical experiments for a large scale two-stage stochastic production planning model with normal demand show that indeed convergence rates close to the optimal are achieved when using SLR and randomly scrambled Sobol' point sets accompanied with PCA for dimension reduction. [ABSTRACT FROM AUTHOR]

Based on previous work in rolling stock scheduling problems (Alfieri et al. in Transp Sci 40:378-391, ; Cacchiani et al. in Math Progr B 124:207-231, ; Lin and Kwan in Electron Notes Discret Math 41:165-172, ; Schrijver in CWI Q 6:205-217, ; Ziarati et al. in Manag Sci 45:1156-1168, ), we generalize a local convex hull method for a class of integer multicommodity flow problems, and discuss its feasibility range in high dimensional cases. Suppose a local convex hull can be divided into an up hull, a main hull and a down hull if certain conditions are met, it is shown theoretically that the main hull can only have at most two nonzero facets. The numbers of points in the up and down hull are explored mainly on an empirical basis. The above properties of local convex hulls have led to a slightly modified QuickHull algorithm (the '2-facet QuickHull') based on the original version proposed by Barber et al. (ACM Trans Math Softw 22:469-483, ). As for the feasibility in applying this method to rolling stock scheduling, our empirical experiments show that for the problem instances of ScotRail and Southern Railway, two major train operating companies in the UK, even in the most difficult real-world or artificial conditions (e.g. supposing a train can be served by any of 11 compatible types of self-powered unit), the standard QuickHull (Barber et al. in ACM Trans Math Softw 22:469-483, ) can easily compute the relevant convex hulls. For some even more difficult artificial instances that may fall outside the scope of rolling stock scheduling (e.g. a node in a graph can be covered by more than 11 kinds of compatible commodities), there is evidence showing that the '2-facet QuickHull' can be more advantageous over the standard QuickHull for our tested instances. When the number of commodity types is even higher (e.g. >19), or the number of points in a high dimensional space (e.g. 15 dimensions) is not small (e.g. >2000), the local convex hulls cannot be computed either by the standard or the 2-facet QuickHull methods within practical time. [ABSTRACT FROM AUTHOR]

A class of trust-region algorithms is developed and analyzed for the solution of optimization problems with nonlinear equality and inequality constraints. These algorithms are developed for problem classes where the constraints are not available in an open, equation-based form, and constraint Jacobians are of high dimension and are expensive to calculate. Based on composite-step trust region methods and a filter approach, the resulting algorithms do not require the computation of exact Jacobians; only Jacobian vector products are used along with approximate Jacobian matrices. With these modifications, we show that the algorithm is globally convergent. Also, as demonstrated on numerical examples, our algorithm avoids direct computation of exact Jacobians and has significant potential benefits on problems where Jacobian calculations are expensive. [ABSTRACT FROM AUTHOR]

This article considers the computation of Bertrand-Nash equilibrium prices when the consumer population has finite purchasing power. The literal KKT conditions for equilibria contain 'spurious' solutions that are not equilibria but can be computed by existing software, even with prominent regularization strategies for ill-posed problems. We prove a reformulated complementarity problem based on a fixed-point representation of equilibrium prices improves computational reliability and provide computational evidence of its efficiency on an empirically-relevant problem. Scientific inferences from empirical Bertrand competition models with explicit limits on individual purchasing power will benefit significantly from our proposed methods for computing equilibrium prices. An analysis of floating-point computations also implies that any model will have finite purchasing power when implemented on existing computing machines, and thus the techniques discussed here have general value. We discuss a heuristic to identify, and potentially mitigate, the impact of computationally-imposed finite purchasing power on computations of equilibrium prices in any model. [ABSTRACT FROM AUTHOR]

We analyze a combined regularization-discretization approach for a class of linear-quadratic optimal control problems. By choosing the regularization parameter $$\alpha $$ with respect to the mesh size $$h$$ of the discretization we approximate the optimal bang-bang control. Under weaker assumptions on the structure of the switching function we generalize existing convergence results and prove error estimates of order $${\mathcal {O}}(h^{1/(k+1)})$$ with respect to the controllability index $$k$$ . [ABSTRACT FROM AUTHOR]

Interactive multiobjective optimization methods have provided promising results in the literature but still their implementations are rare. Here we introduce a core structure of interactive methods to enable their convenient implementation. We also demonstrate how this core structure can be applied when implementing an interactive method using a modeling environment. Many modeling environments contain tools for single objective optimization but not for interactive multiobjective optimization. Furthermore, as a concrete example, we present GAMS-NIMBUS Tool which is an implementation of the classification-based NIMBUS method for the GAMS modeling environment. So far, interactive methods have not been available in the GAMS environment, but with the GAMS-NIMBUS Tool we open up the possibility of solving multiobjective optimization problems modeled in the GAMS modeling environment. Finally, we give some examples of the benefits of applying an interactive method by using the GAMS-NIMBUS Tool for solving multiobjective optimization problems modeled in the GAMS environment. [ABSTRACT FROM AUTHOR]

We present a second order image decomposition model to perform denoising and texture extraction. We look for the decomposition f= u+ v+ w where u is a first order term, v a second order term and w the (0 order) remainder term. For highly textured images the model gives a two-scale texture decomposition: u can be viewed as a macro-texture (larger scale) whose oscillations are not too large and w is the micro-texture (very oscillating) that may contain noise. We perform mathematical analysis of the model and give numerical examples. [ABSTRACT FROM AUTHOR]

We introduce a class of adaptive non-smooth convex variational problems for image denoising in terms of a common data fitting term and a support functional as regularizer. Adaptivity is modeled by a set-valued mapping with closed, compact and convex values, that defines and steers the regularizer depending on the variational solution. This extension gives rise to a class of quasi-variational inequalities. We provide sufficient conditions for the existence of fixed points as solutions, and an algorithm based on solving a sequence of variational problems. Denoising experiments with spatial and spatio-temporal image data and an adaptive total variation regularizer illustrate our approach. [ABSTRACT FROM AUTHOR]

Regularization methods for inverse problems formulated in Hilbert spaces usually give rise to over-smoothness, which does not allow to obtain a good contrast and localization of the edges in the context of image restoration. On the other hand, regularization methods recently introduced in Banach spaces allow in general to obtain better localization and restoration of the discontinuities or localized impulsive signals in imaging applications. We present here an expository survey of the topic focused on the iterative Landweber method. In addition, preconditioning techniques previously proposed for Hilbert spaces are extended to the Banach setting and numerically tested. [ABSTRACT FROM AUTHOR]

The proximal method is a standard regularization approach in optimization. Practical implementations of this algorithm require (i) an algorithm to compute the proximal point, (ii) a rule to stop this algorithm, (iii) an update formula for the proximal parameter. In this work we focus on (ii), when smoothness is present-so that Newton-like methods can be used for (i): we aim at giving adequate stopping rules to reach overall efficiency of the method. Roughly speaking, usual rules consist in stopping inner iterations when the current iterate is close to the proximal point. By contrast, we use the standard paradigm of numerical optimization: the basis for our stopping test is a 'sufficient' decrease of the objective function, namely a fraction of the ideal decrease. We establish convergence of the algorithm thus obtained and we illustrate it on some ill-conditioned problems. The experiments show that combining the proposed inexact proximal scheme with a standard smooth optimization algorithm improves the numerical behaviour of the latter for those ill-conditioned problems. [ABSTRACT FROM AUTHOR]

A mathematical model of a physical system is never perfect; therefore, robust control laws are necessary for guaranteed stabilization of the nominal model and also 'nearby' systems, including hopefully the actual physical system. We consider the computation of a robust control law for large-scale finite dimensional linear systems and a class of linear distributed parameter systems. The controller is robust with respect to left coprime factor perturbations of the nominal system. We present an algorithm based on balanced proper orthogonal decomposition to compute the nonstandard features of this robust control law. Convergence theory is given, and numerical results are presented for two partial differential equation systems. [ABSTRACT FROM AUTHOR]

The contribution of this work is twofold. Firstly, we introduce a new channel assignment model for GSM radio networks. In this model both spatial and temporal variations of traffic are taken into account in order to improve network capacity and robustness. Secondly, using this model, we develop an original and effective hybrid algorithm to get high quality frequency plans. This algorithm combines a problem specific crossover and a Tabu search procedure. The proposed model and hybrid algorithm are evaluated using both artificial and real data. Computational results allow us to confirm the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

The problem of covering a compact polygonal region, called target region, with a finite family of rectangles is considered. Tools for mathematical modeling of the problem are provided. Especially, a function, called Γ-function, is introduced which indicates whether the rectangles with respect to their configuration form a cover of the target region or not. The construction of the Γ-function is similar to that of Φ-functions which have been proved to be an efficient tool for packing problems. A mathematical model of the covering problem based on the Γ-function is proposed as well as a solution strategy. The approach is illustrated by an example and some computational results are presented. [ABSTRACT FROM AUTHOR]

We propose a descent method via gap functions for solving nonsmooth variational inequalities with a locally Lipschitz operator. Assuming monotone operator (not necessarily strongly monotone) and bounded domain, we show that the method with an Armijo-type line search is globally convergent. Finally, we report some numerical experiments. [ABSTRACT FROM AUTHOR]

We discuss possible scenarios of behaviour of the dual part of sequences generated by primal-dual Newton-type methods when applied to optimization problems with nonunique multipliers associated to a solution. Those scenarios are: (a) failure of convergence of the dual sequence; (b) convergence to a so-called critical multiplier (which, in particular, violates some second-order sufficient conditions for optimality), the latter appearing to be a typical scenario when critical multipliers exist; (c) convergence to a noncritical multiplier. The case of mathematical programs with complementarity constraints is also discussed. We illustrate those scenarios with examples, and discuss consequences for the speed of convergence. We also put together a collection of examples of optimization problems with constraints violating some standard constraint qualifications, intended for preliminary testing of existing algorithms on degenerate problems, or for developing special new algorithms designed to deal with constraints degeneracy. [ABSTRACT FROM AUTHOR]

We prove Kantorovich’s theorem on Newton’s method using a convergence analysis which makes clear, with respect to Newton’s method, the relationship of the majorant function and the non-linear operator under consideration. This approach enables us to drop out the assumption of existence of a second root for the majorant function, still guaranteeing Q-quadratic convergence rate and to obtain a new estimate of this rate based on a directional derivative of the derivative of the majorant function. Moreover, the majorant function does not have to be defined beyond its first root for obtaining convergence rate results. [ABSTRACT FROM AUTHOR]

For Principal Component Analysis in Reproducing Kernel Hilbert Spaces (KPCA), optimization over sets containing only linear combinations of all n-tuples of kernel functions is investigated, where n is a positive integer smaller than the number of data. Upper bounds on the accuracy in approximating the optimal solution, achievable without restrictions on the number of kernel functions, are derived. The rates of decrease of the upper bounds for increasing number n of kernel functions are given by the summation of two terms, one proportional to n −1/2 and the other to n −1, and depend on the maximum eigenvalue of the Gram matrix of the kernel with respect to the data. Primal and dual formulations of KPCA are considered. The estimates provide insights into the effectiveness of sparse KPCA techniques, aimed at reducing the computational costs of expansions in terms of kernel units. [ABSTRACT FROM AUTHOR]

This article combines techniques from two fields of applied mathematics: optimization theory and inverse problems. We investigate a generalized conditional gradient method and its connection to an iterative shrinkage method, which has been recently proposed for solving inverse problems. The iterative shrinkage method aims at the solution of non-quadratic minimization problems where the solution is expected to have a sparse representation in a known basis. We show that it can be interpreted as a generalized conditional gradient method. We prove the convergence of this generalized method for general class of functionals, which includes non-convex functionals. This also gives a deeper understanding of the iterative shrinkage method. [ABSTRACT FROM AUTHOR]