A fast dual proximal gradient algorithm for convex minimization and applications

We consider the convex composite problem of minimizing the sum of a strongly convex function and a general extended valued convex function. We present a dual-based proximal gradient scheme for solving this problem. We show that although the rate of convergence of the dual objective function sequence converges to the optimal value with the rate O(1/k²)$O(1/k^2)$, the rate of convergence of the primal sequence is of the order O(1/k)$O(1/k)$.     

Time discretization and quantization methods for optimal multiple switching problem

In this paper, we study probabilistic numerical methods based on optimal quantization algorithms for computing the solution to optimal multiple switching problems with regime-dependent state process. We first consider a discrete-time approximation of the optimal switching problem, and analyse its rate of convergence. Given a time step h$h$, the error is in general of order (hlog(1/h))^1/2${(hlog(1/h))}^{1/2}$, and of order h^1/2$h^{1/2}$ when the switching costs do not depend on the state process. We next propose quantization numerical schemes for the space discretization of the discrete-time Euler state process. A Markovian quantization approach relying on the optimal quantization of the normal distribution arising in the Euler scheme is analysed. In the particular case of uncontrolled state process, we describe an alternative marginal quantization method, which extends the recursive algorithm for optimal stopping problems as in Bally (2003) [1]. A priori L^p$L^p$-error estimates are stated in terms of quantization errors. Finally, some numerical tests are performed for an optimal switching problem with two regimes.     

Branch-and-reduce algorithm for convex programs with additional multiplicative constraints

This article presents a branch-and-reduce algorithm for globally solving for the first time a convex minimization problem (P) with p?1$p?1$ additional multiplicative constraints. In each of these p   additional constraints, the product of two convex functions is constrained to be less than or equal to a positive number. The algorithm works by globally solving a 2p$2p$-dimensional master problem (MP) equivalent to problem (P). During a typical stage k of the algorithm, a point is found that minimizes the objective function of problem (MP) over a nonconvex set F^k$F^k$ that contains the portion of the boundary of the feasible region of the problem where a global optimal solution lies. If this point is feasible in problem (MP), the algorithm terminates. Otherwise, the algorithm continues by branching and creating a new, reduced nonconvex set F^k+1$F^{k+1}$ that is a strict subset of F^k$F^k$. To implement the algorithm, all that is required is the ability to solve standard convex programming problems and to implement simple algebraic steps. Convergence properties of the algorithm are given, and results of some computational experiments are reported.     

A unified approach for scheduling with convex resource consumption functions using positional penalties

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n³)$O(n^3)$ time. Furthermore, we show how the unified model can be used repeatedly as a subroutine to solve all problems from the second group in O(n⁴)$O(n^4)$ time. In addition, we also show that faster algorithms exist for several special cases.     

The spectral method for high order problems with proper simulations of asymptotic behaviors at infinity

In this paper, we investigate new spectral and multidomain spectral methods for high order problems. We introduce a family of new generalized Laguerre functions, which are mutually orthogonal with the weight function x^α(δ+x)^−γ$x^{\alpha }{(\delta +x)}^{-\gamma }$, δ>0$\delta >0$,α$\alpha$ and γ$\gamma$ being arbitrary real numbers. The corresponding quasi-orthogonal approximation and Laguerre–Gauss–Radau type interpolation are proposed. The spectral and multidomain spectral schemes are provided for several model problems, which not only fit the mixed inhomogeneous boundary conditions on the fixed boundary exactly, but also match the asymptotic behaviors at infinity reasonably. Numerical results demonstrate the efficiency of suggested algorithms, and confirm the analysis well.     

Global existence and causality for a hyperbolic transmission problem with a repulsive nonlinearity

It is well known that the solution of the classical linear wave equation with an initial condition with compact support and vanishing initial velocity also has a compact support included in a set depending on time: the support of the solution at time t$t$ is causally related to that of the initial condition. Reed and Simon have shown that for a real-valued Klein–Gordon equation with (nonlinear) right-hand side −λu³$-\lambda u^3$ (λ>0$\lambda >0$), causality still holds. We show the same property for a one-dimensional Klein–Gordon problem but with transmission and with a more general repulsive nonlinear right-hand side F(u)$F\left(u\right)$. We also prove the global existence of a solution using the repulsiveness of F$F$. In the particular case F(u)=−λu³$F\left(u\right)=-\lambda u^3$, the problem is a relativistic model for a quantum particle with repulsive self-interaction and tunnel effect at a semi-infinite potential step.     

L -decay rates of planar viscous rarefaction wave for scalar conservation law with degenerate viscosity in n -dimensions

We investigate the Cauchy problem and the initial-boundary value problem for multi-dimensional conservation laws with degenerate viscosity in the whole space and in the half-space respectively. We give the optimal decay estimates in the W^1,p(1≤p≤∞)$W^{1,p}(1\le p\le \infty )$ norm for the perturbation from the planar viscous rarefaction wave. The analysis based on the new L^p$L^p$-energy method and L¹$L^1$-estimates.     

Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion

For the no-wait flowshop scheduling problem with maximum lateness criterion, properties are developed to speed up three kinds of basic operations generating candidate solutions, i.e., the insertion of a new job into a partial sequence, and the insertion and exchange neighborhood moves. The properties reduce the time to evaluate a candidate from O(nm)$O(\mathit{nm})$ to O  (1) and simplify the implementation of the heuristics based on the basic operations by evaluating candidates before their generation. The properties also reduce from O(n³m)$O(n^{3}m)$ to O(n²)$O(n^2)$ the time complexity of well-known NEH heuristic and the complete evaluation of the insertion and exchange neighborhoods. Tabu search (TS) is applied to the considered problem, since TS tries to find the best neighbor of the current solution in each iteration and therefore can much benefit from the speedups. Three different ways to use insertion and exchange neighborhoods are compared in TS. Computational experiments show that the speedups are more helpful as job number increases and all proposed TS algorithms are more effective and robust than the existing algorithms. Although two- and single-neighborhood TS algorithms are not significantly different, two-neighborhood TS algorithms are more preferable.     

Property of positive solutions and its applications for Sturm–Liouville singular boundary value problems

This paper is concerned with the property of the positive solutions for Sturm–Liouville singular boundary value problems with the linear conditions. We obtain a relation between the solutions and Green’s function. It implies a necessary condition for the C¹[0,1]$C^1[0,1]$ positive solutions. We apply the result to conclude that the given equation has no C¹[0,1]$C^1[0,1]$ positive solutions.     

Regularity in a one-phase free boundary problem for the fractional Laplacian

For a one-phase free boundary problem involving a fractional Laplacian, we prove that “flat free boundaries” are C^1,α$C^{1,\alpha }$. We recover the regularity results of Caffarelli for viscosity solutions of the classical Bernoulli-type free boundary problem with the standard Laplacian.     

Approximation numbers of Sobolev embeddings—Sharp constants and tractability

We investigate optimal linear approximations (approximation numbers) in the context of periodic Sobolev spaces H^s(T^d)$H^s\left({\mathbb{T}}^d\right)$ of fractional smoothness s>0$s>0$ for various equivalent norms including the classical one. The error is always measured in _L2(T^d)$L_2\left({\mathbb{T}}^d\right)$. Particular emphasis is given to the dependence of all constants on the dimension d$d$. We capture the exact decay rate in n$n$ and the exact decay order of the constants with respect to d$d$, which is in fact polynomial. As a consequence we observe that none of our considered approximation problems suffers from the curse of dimensionality. Surprisingly, the square integrability of all weak derivatives up to order three (classical Sobolev norm) guarantees weak tractability of the associated multivariate approximation problem.     

Improved Newton’s method with exact line searches to solve quadratic matrix equation

In this paper, we study the matrix equation AX²+BX+C=0$A{X}^2+BX+C=0$, where A,B$A,B$ and C$C$ are square matrices. We give two improved algorithms which are better than Newton’s method with exact line searches to calculate the solution. Some numerical examples are reported to illustrate our algorithms.     

Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity

This paper addresses a single machine scheduling problem in which the actual job processing times are determined by resource allocation function, its position in a sequence and a rate-modifying activity simultaneously. We discuss two objective functions with two resource allocation functions under the consideration of a rate-modifying activity. We show that the problems are solvable in O(n⁴)$O(n^4)$ time for a linear resource allocation function and are solvable in O(n²logn)$O(n^2\mathit{logn})$ time for a convex resource allocation function.     

Nonautonomous stochastic search for global minimum in continuous optimization

Various iterative stochastic optimization schemes can be represented as discrete-time Markov processes defined by the nonautonomous equation _Xt+1=_Tt(_Xt,_Yt)$X_{t+1}=T_t(X_t,Y_t)$, where _Yt$Y_t$ is an independent sequence and _Tt$T_t$ is a sequence of mappings. This paper presents a general framework for the study of the stability and convergence of such optimization processes. Some applications are given: the mathematical convergence analysis of two optimization methods, the elitist evolution strategy (μ+λ)$(\mu +\lambda )$ and the grenade explosion method, is presented.