Authors:Christoph Buchheim; Renke Kuhlmann; Christian Meyer Pages: 641 - 675 Abstract: Optimal control problems (OCPs) containing both integrality and partial differential equation (PDE) constraints are very challenging in practice. The most wide-spread solution approach is to first discretize the problem, which results in huge and typically nonconvex mixed-integer optimization problems that can be solved to proven optimality only in very small dimensions. In this paper, we propose a novel outer approximation approach to efficiently solve such OCPs in the case of certain semilinear elliptic PDEs with static integer controls over arbitrary combinatorial structures, where we assume the nonlinear part of the PDE to be non-decreasing and convex. The basic idea is to decompose the OCP into an integer linear programming (ILP) master problem and a subproblem for calculating linear cutting planes. These cutting planes rely on the pointwise concavity or submodularity of the PDE solution with respect to the control variables. The decomposition allows us to use standard solution techniques for ILPs as well as for PDEs. We further benefit from reoptimization strategies for the PDE solution due to the iterative structure of the algorithm. Experimental results show that the new approach is capable of solving the combinatorial OCP of a semilinear Poisson equation with up to 180 binary controls to global optimality within a 5 h time limit. In the case of the screened Poisson equation, which yields semi-infinite integer linear programs, problems with as many as 1400 binary controls are solved. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9993-2 Issue No:Vol. 70, No. 3 (2018)

Authors:Eduardo Casas; Christopher Ryll; Fredi Tröltzsch Pages: 677 - 707 Abstract: 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. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9986-1 Issue No:Vol. 70, No. 3 (2018)

Authors:Dimitri P. Bertsekas Pages: 709 - 736 Abstract: In this paper we consider large fixed point problems and solution with proximal algorithms. We show that for linear problems there is a close connection between proximal iterations, which are prominent in numerical analysis and optimization, and multistep methods of the temporal difference type such as TD( \(\lambda \) ), LSTD( \(\lambda \) ), and LSPE( \(\lambda \) ), which are central in simulation-based exact and approximate dynamic programming. One benefit of this connection is a new and simple way to accelerate the standard proximal algorithm by extrapolation towards a multistep iteration, which generically has a faster convergence rate. Another benefit is the potential for integration into the proximal algorithmic context of several new ideas that have emerged in the approximate dynamic programming context, including simulation-based implementations. Conversely, the analytical and algorithmic insights from proximal algorithms can be brought to bear on the analysis and the enhancement of temporal difference methods. We also generalize our linear case result to nonlinear problems that involve a contractive mapping, thus providing guaranteed and potentially substantial acceleration of the proximal and forward backward splitting algorithms at no extra cost. Moreover, under certain monotonicity assumptions, we extend the connection with temporal difference methods to nonlinear problems through a linearization approach. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9990-5 Issue No:Vol. 70, No. 3 (2018)

Authors:Aviv Gibali; Karl-Heinz Küfer; Daniel Reem; Philipp Süss Pages: 737 - 762 Abstract: 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. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9991-4 Issue No:Vol. 70, No. 3 (2018)

Authors:Renato D. C. Monteiro; Chee-Khian Sim Pages: 763 - 790 Abstract: 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. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9996-z Issue No:Vol. 70, No. 3 (2018)

Authors:Bingsheng He; Xiaoming Yuan Pages: 791 - 826 Abstract: 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. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9994-1 Issue No:Vol. 70, No. 3 (2018)

Authors:Min Tao; Xiaoming Yuan Pages: 827 - 839 Abstract: The proximal point algorithm (PPA) is a fundamental method in optimization and it has been well studied in the literature. Recently a generalized version of the PPA with a step size in (0, 2) has been proposed. Inheriting all important theoretical properties of the original PPA, the generalized PPA has some numerical advantages that have been well verified in the literature by various applications. A common sense is that larger step sizes are preferred whenever the convergence can be theoretically ensured; thus it is interesting to know whether or not the step size of the generalized PPA can be as large as 2. We give a negative answer to this question. Some counterexamples are constructed to illustrate the divergence of the generalized PPA with step size 2 in both generic and specific settings, including the generalized versions of the very popular augmented Lagrangian method and the alternating direction method of multipliers. A by-product of our analysis is the failure of convergence of the Peaceman–Rachford splitting method and a generalized version of the forward–backward splitting method with step size 1.5. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9992-3 Issue No:Vol. 70, No. 3 (2018)

Authors:Nguyen Hieu Thao Pages: 841 - 863 Abstract: This paper proposes an algorithm for solving structured optimization problems, which covers both the backward–backward and the Douglas–Rachford algorithms as special cases, and analyzes its convergence. The set of fixed points of the corresponding operator is characterized in several cases. Convergence criteria of the algorithm in terms of general fixed point iterations are established. When applied to nonconvex feasibility including potentially inconsistent problems, we prove local linear convergence results under mild assumptions on regularity of individual sets and of the collection of sets. In this special case, we refine known linear convergence criteria for the Douglas–Rachford (DR) algorithm. As a consequence, for feasibility problem with one of the sets being affine, we establish criteria for linear and sublinear convergence of convex combinations of the alternating projection and the DR methods. These results seem to be new. We also demonstrate the seemingly improved numerical performance of this algorithm compared to the RAAR algorithm for both consistent and inconsistent sparse feasibility problems. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9989-y Issue No:Vol. 70, No. 3 (2018)

Authors:Laureano F. Escudero; María Araceli Garín; Celeste Pizarro; Aitziber Unzueta Pages: 865 - 888 Abstract: In this work we present two matheuristic procedures to build good feasible solutions (frequently, the optimal one) by considering the solutions of relaxed problems of large-sized instances of the multi-period stochastic pure 0–1 location-assignment problem. The first procedure is an iterative one for Lagrange multipliers updating based on a scenario cluster Lagrangean decomposition for obtaining strong (lower, in case of minimization) bounds of the solution value. The second procedure is a sequential one that works with the relaxation of the integrality of subsets of variables for different levels of the problem, so that a chain of (lower, in case of minimization) bounds is generated from the LP relaxation up to the integer solution value. Additionally, and for both procedures, a lazy heuristic scheme, based on scenario clustering and on the solutions of the relaxed problems, is considered for obtaining a (hopefully good) feasible solution as an upper bound of the solution value of the full problem. Then, the same framework provides for the two procedures lower and upper bounds on the solution value. The performance is compared over a set of instances of the stochastic facility location-assignment problem. It is well known that the general static deterministic location problem is NP-hard and, so, it is the multi-period stochastic version. A broad computational experience is reported for 14 instances, up to 15 facilities, 75 customers, 6 periods, over 260 scenarios and over 420 nodes in the scenario tree, to assess the validity of proposals made in this work versus the full use of a state-of the-art IP optimizer. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9995-0 Issue No:Vol. 70, No. 3 (2018)

Authors:Ewa M. Bednarczuk; Janusz Miroforidis; Przemysław Pyzel Pages: 889 - 910 Abstract: 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. PubDate: 2018-07-01 DOI: 10.1007/s10589-018-9988-z Issue No:Vol. 70, No. 3 (2018)

Authors:Anwa Zhou; Jinyan Fan Pages: 419 - 441 Abstract: In this paper, we introduce the CP-nuclear value of a completely positive (CP) tensor and study its properties. A semidefinite relaxation algorithm is proposed for solving the minimal CP-nuclear-value tensor recovery. If a partial tensor is CP-recoverable, the algorithm can give a CP tensor recovery with the minimal CP-nuclear value, as well as a CP-nuclear decomposition of the recovered CP tensor. If it is not CP-recoverable, the algorithm can always give a certificate for that, when it is regular. Some numerical experiments are also presented. PubDate: 2018-06-01 DOI: 10.1007/s10589-018-0003-5 Issue No:Vol. 70, No. 2 (2018)

Authors:Jianqiang Cheng; Richard Li-Yang Chen; Habib N. Najm; Ali Pinar; Cosmin Safta; Jean-Paul Watson Pages: 479 - 502 Abstract: Increasing penetration levels of renewables have transformed how power systems are operated. High levels of uncertainty in production make it increasingly difficulty to guarantee operational feasibility; instead, constraints may only be satisfied with high probability. We present a chance-constrained economic dispatch model that efficiently integrates energy storage and high renewable penetration to satisfy renewable portfolio requirements. Specifically, we require that wind energy contribute at least a prespecified proportion of the total demand and that the scheduled wind energy is deliverable with high probability. We develop an approximate partial sample average approximation (PSAA) framework to enable efficient solution of large-scale chance-constrained economic dispatch problems. Computational experiments on the IEEE-24 bus system show that the proposed PSAA approach is more accurate, closer to the prescribed satisfaction tolerance, and approximately 100 times faster than standard sample average approximation. Finally, the improved efficiency of our PSAA approach enables solution of a larger WECC-240 test system in minutes. PubDate: 2018-06-01 DOI: 10.1007/s10589-018-0006-2 Issue No:Vol. 70, No. 2 (2018)

Authors:Gabriel Haeser Pages: 615 - 639 Abstract: We develop a new notion of second-order complementarity with respect to the tangent subspace related to second-order necessary optimality conditions by the introduction of so-called tangent multipliers. We prove that around a local minimizer, a second-order stationarity residual can be driven to zero while controlling the growth of Lagrange multipliers and tangent multipliers, which gives a new second-order optimality condition without constraint qualifications stronger than previous ones associated with global convergence of algorithms. We prove that second-order variants of augmented Lagrangian (under an additional smoothness assumption based on the Lojasiewicz inequality) and interior point methods generate sequences satisfying our optimality condition. We present also a companion minimal constraint qualification, weaker than the ones known for second-order methods, that ensures usual global convergence results to a classical second-order stationary point. Finally, our optimality condition naturally suggests a definition of second-order stationarity suitable for the computation of iteration complexity bounds and for the definition of stopping criteria. PubDate: 2018-06-01 DOI: 10.1007/s10589-018-0005-3 Issue No:Vol. 70, No. 2 (2018)

Authors:Yoshihiro Kanno Abstract: The robust truss topology optimization against the uncertain static external load can be formulated as mixed-integer semidefinite programming. Although a global optimal solution can be computed with a branch-and-bound method, it is very time-consuming. This paper presents an alternative formulation, semidefinite programming with complementarity constraints, and proposes an efficient heuristic. The proposed method is based upon the concave–convex procedure for difference-of-convex programming. It is shown that the method can often find a practically reasonable truss design within the computational cost of solving some dozen of convex optimization subproblems. PubDate: 2018-06-09 DOI: 10.1007/s10589-018-0013-3

Authors:S. Bonettini; M. Prato; S. Rebegoldi Abstract: In this paper we propose an alternating block version of a variable metric linesearch proximal gradient method. This algorithm addresses problems where the objective function is the sum of a smooth term, whose variables may be coupled, plus a separable part given by the sum of two or more convex, possibly nonsmooth functions, each depending on a single block of variables. Our approach is characterized by the possibility of performing several proximal gradient steps for updating every block of variables and by the Armijo backtracking linesearch for adaptively computing the steplength parameter. Under the assumption that the objective function satisfies the Kurdyka-Łojasiewicz property at each point of its domain and the gradient of the smooth part is locally Lipschitz continuous, we prove the convergence of the iterates sequence generated by the method. Numerical experience on an image blind deconvolution problem show the improvements obtained by adopting a variable number of inner block iterations combined with a variable metric in the computation of the proximal operator. PubDate: 2018-06-09 DOI: 10.1007/s10589-018-0011-5

Authors:F. Carrabs; R. Cerulli; R. Pentangelo; A. Raiconi Abstract: Given an undirected weighted graph, in which each vertex is assigned to a color and one of them is identified as source, in the all-colors shortest path problem we look for a minimum cost shortest path that starts from the source and spans all different colors. The problem is known to be NP-Hard and hard to approximate. In this work we propose a variant of the problem in which the source is unspecified and show the two problems to be computationally equivalent. Furthermore, we propose a mathematical formulation, a compact representation for feasible solutions and a VNS metaheuristic that is based on it. Computational results show the effectiveness of the proposed approach for the two problems. PubDate: 2018-06-08 DOI: 10.1007/s10589-018-0014-2

Authors:Petra Renáta Rigó; Zsolt Darvay Abstract: We propose a new primal-dual infeasible interior-point method for symmetric optimization by using Euclidean Jordan algebras. Different kinds of interior-point methods can be obtained by using search directions based on kernel functions. Some search directions can be also determined by applying an algebraic equivalent transformation on the centering equation of the central path. Using this method we introduce a new search direction, which can not be derived from a usual kernel function. For this reason, we use the new notion of positive-asymptotic kernel function which induces the class of corresponding barriers. In general, the main iterations of the infeasible interior-point methods are composed of one feasibility and several centering steps. We prove that in our algorithm it is enough to take only one centering step in a main iteration in order to obtain a well-defined algorithm. Moreover, we conclude that the algorithm finds solution in polynomial time and has the same complexity as the currently best known infeasible interior-point methods. Finally, we give some numerical results. PubDate: 2018-06-07 DOI: 10.1007/s10589-018-0012-4

Authors:Martin Branda; Max Bucher; Michal Červinka; Alexandra Schwartz Abstract: We consider general nonlinear programming problems with cardinality constraints. By relaxing the binary variables which appear in the natural mixed-integer programming formulation, we obtain an almost equivalent nonlinear programming problem, which is thus still difficult to solve. Therefore, we apply a Scholtes-type regularization method to obtain a sequence of easier to solve problems and investigate the convergence of the obtained KKT points. We show that such a sequence converges to an S-stationary point, which corresponds to a local minimizer of the original problem under the assumption of convexity. Additionally, we consider portfolio optimization problems where we minimize a risk measure under a cardinality constraint on the portfolio. Various risk measures are considered, in particular Value-at-Risk and Conditional Value-at-Risk under normal distribution of returns and their robust counterparts under moment conditions. For these investment problems formulated as nonlinear programming problems with cardinality constraints we perform a numerical study on a large number of simulated instances taken from the literature and illuminate the computational performance of the Scholtes-type regularization method in comparison to other considered solution approaches: a mixed-integer solver, a direct continuous reformulation solver and the Kanzow–Schwartz regularization method, which has already been applied to Markowitz portfolio problems. PubDate: 2018-02-21 DOI: 10.1007/s10589-018-9985-2

Authors:Christoph Brauer; Dirk A. Lorenz; Andreas M. Tillmann Abstract: In this paper we propose a primal-dual homotopy method for \(\ell _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. PubDate: 2018-02-15 DOI: 10.1007/s10589-018-9983-4

Authors:Andreas Rademacher; Korinna Rosin Abstract: In this article, we present a-posteriori error estimations in context of optimal control of contact problems; in particular of Signorini’s problem. Due to the contact side-condition, the solution operator of the underlying variational inequality is not differentiable, yet we want to apply Newton’s method. Therefore, the non-smooth problem is regularized by penalization and afterwards discretized by finite elements. We derive optimality systems for the regularized formulation in the continuous as well as in the discrete case. This is done explicitly for Signorini’s contact problem, which covers linear elasticity and linearized surface contact conditions. The latter creates the need for treating trace-operations carefully, especially in contrast to obstacle contact conditions, which exert in the domain. Based on the dual weighted residual method and these optimality systems, we deduce error representations for the regularization, discretization and numerical errors. Those representations are further developed into error estimators. The resulting error estimator for regularization error is defined only in the contact area. Therefore its computational cost is especially low for Signorini’s contact problem. Finally, we utilize the estimators in an adaptive refinement strategy balancing regularization and discretization errors. Numerical results substantiate the theoretical findings. We present different examples concerning Signorini’s problem in two and three dimensions. PubDate: 2018-01-31 DOI: 10.1007/s10589-018-9982-5