The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems

The DC programming and its DC algorithm (DCA) address the problem of minimizing a function f=g−h (with g,h being lower semicontinuous proper convex functions on R ⁿ ) on the whole space. Based on local optimality conditions and DC duality, DCA was successfully applied to a lot of different and various nondifferentiable nonconvex optimization problems to which it quite often gave global solutions and proved to be more robust and more efficient than related standard methods, especially in the large scale setting. The computational efficiency of DCA suggests to us a deeper and more complete study on DC programming, using the special class of DC programs (when either g or h is polyhedral convex) called polyhedral DC programs. The DC duality is investigated in an easier way, which is more convenient to the study of optimality conditions. New practical results on local optimality are presented. We emphasize regularization techniques in DC programming in order to construct suitable equivalent DC programs to nondifferentiable nonconvex optimization problems and new significant questions which have to be answered. A deeper insight into DCA is introduced which really sheds new light on DCA and could partly explain its efficiency. Finally DC models of real world nonconvex optimization are reported.     

New multiplier method for solving linear complementarity problems

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {ϑ(x ^k, λ ^k)} (where {(x ^k, λ ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising. Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(2): 162–171     

A continuation method for linear complementarity problems with P 0 matrix

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.     

Symmetric indefinite systems for interior point methods

We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is instead of reducing to obtain the usualAD ² A ^T system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the productAD ² A ^T whenA has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only thatD be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense.     

A class of semi-supervised support vector machines by DC programming

This paper investigate a class of semi-supervised support vector machines ( $\text{ S }^3\mathrm{VMs}$ ) with arbitrary norm. A general framework for the $\text{ S }^3\mathrm{VMs}$ was first constructed based on a robust DC (Difference of Convex functions) program. With different DC decompositions, DC optimization formulations for the linear and nonlinear $\text{ S }^3\mathrm{VMs}$ are investigated. The resulting DC optimization algorithms (DCA) only require solving simple linear program or convex quadratic program at each iteration, and converge to a critical point after a finite number of iterations. The effectiveness of proposed algorithms are demonstrated on some UCI databases and licorice seed near-infrared spectroscopy data. Moreover, numerical results show that the proposed algorithms offer competitive performances to the existing $\text{ S }^3\mathrm{VM}$ methods.     

On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method

Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

A constructive method of solving the Liapounov equation for complex matrices

Summary This paper describes a method of solving the Liapounov equation (1)HM+M ^* H=2D, M in upper Hessenberg form,D diagonal. Initialising the first row of the matrixA arbitrarily, one can find (by solving equations with one unknown) the unknown elements ofA such that (2)AM+M ^* A ^* =2F, whereA differs from a Hermitian matrix only in that its diagonal elements need not be real.F is a diagonal matrix which is uniquely determined by the first row ofA. By solving Eq. (2) for several initial values one may generate several matricesA andF (in the most unfavourable case 2n–1A's andF's are needed) and superpose them to getn linearly independent Hermitian matricesH _j andD _j respectively for whichH _j M+M ^* H _j =2D _j is valid. Then one can solve the real system to obtain the solution of Eq. (1).This work was performed under the terms of the agreement on association between the Max-Planck-Institut für Plasmaphysik and Euratom.     

Solution of Complementarity Problems via Piecewise Linearization

My master thesis concerns the solution linear complementarity problems (LCP). The Lemke algorithm, the most commonly used algorithm for solving a LCP until this day, was compared with the piecewise Newton method (PLN algorithm). The piecewise Newton method is an algorithm to solve a piecewise linear system on the basis of damped Newton methods. The linear complementarity problem is formulated as a piecewise linear system for the applicability of the PLN algorithm. Then, different application examples will be presented, solved with the PLN algorithm. As a result of the findings (of my master thesis) it can be assumed that – under the condition of coherent orientation – the PLN-algorithm requires fewer iterations to solve a linear complementarity problem than the Lemke algorithm. The coherent orientation for piecewise linear problems corresponds for linear complementarity problems to the P-matrix-property. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Properties of two DC algorithms in quadratic programming

Some new properties of the Projection DC decomposition algorithm (we call it Algorithm A) and the Proximal DC decomposition algorithm (we call it Algorithm B) Pham Dinh et al. in Optim Methods Softw, 23(4): 609–629 (2008) for solving the indefinite quadratic programming problem under linear constraints are proved in this paper. Among other things, we show that DCA sequences generated by Algorithm A converge to a locally unique solution if the initial points are taken from a neighborhood of it, and DCA sequences generated by either Algorithm A or Algorithm B are all bounded if a condition guaranteeing the solution existence of the given problem is satisfied.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems

We consider the standard linear complementarity problem (LCP): Find (x, y) R ²ⁿ such that y = M x + q, (x, y) 0 and x _i y _i = 0 (i = 1, 2, ... , n), where M is an n × n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P ₀ LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in Newton iterations where is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.     

Multi-level spectral Galerkin method for the Navier–Stokes equations, II: time discretization

A fully discrete multi-level spectral Galerkin method in space–time for the two-dimensional nonstationary Navier–Stokes problem is considered. The method is a multi-scale method in which the fully nonlinear Navier–Stokes problem is only solved on the lowest-dimensional space with the largest time step Δt ₁; subsequent approximations are generated on a succession of higher-dimensional spaces with small time step Δt _j by solving a linearized Navier–Stokes problem about the solution on the previous level. Some error estimates are also presented for the J-level spectral Galerkin method. The scaling relations of the dimensional numbers and time mesh widths that lead to optimal accuracy of the approximate solution in H ¹-norm and L ²-norm are investigated, i.e., m _j∼m _j−1 ^3/2 , Δt _j∼Δt _j−1 ^3/2 , j=2,. . .,J. We demonstrate theoretically that a fully discrete J-level spectral Galerkin method is significantly more efficient than the standard one-level spectral Galerkin method. Mathematics subject classifications (2000) 35L70, 65N30, 76D06 Subsidized by the Special Funds for Major State Basic Research Projects G1999032801-07, NSF of China 10371095 and the City University of Hong Kong Research Project 7001093, NSF of China 50323001.     

An efficient combined DCA and B&;B using DC/SDP relaxation for globally solving binary quadratic programs

This paper addresses a new continuous approach based on the DC (Difference of Convex functions) programming and DC algorithms (DCA) to Binary quadratic programs (BQP) which play a key role in combinatorial optimization. DCA is completely different from other avalaible methods and featured by generating a convergent finite sequence of feasible binary solutions (obtained by solving linear programs with the same constraint set) with decreasing objective values. DCA is quite simple and inexpensive to handle large-scale problems. In particular DCA is explicit, requiring only matrix-vector products for Unconstrained Binary quadratic programs (UBQP), and can then exploit sparsity in the large-scale setting. To check globality of solutions computed by DCA, we introduce its combination with a customized Branch-and-Bound scheme using DC/SDP relaxation. The combined algorithm allows checking globality of solutions computed by DCA and restarting it if necessary and consequently accelerates the B&B approach. Numerical results on several series test problems provided in OR-Library (Beasley in J Global Optim, 8:429–433, 1996), show the robustness and efficiency of our algorithm with respect to standard methods. In particular DCA provides ϵ-optimal solutions in almost all cases after only one restarting and the combined DCA-B&B-SDP always provides (ϵ−)optimal solutions.     

On constructing total orders and solving vector optimization problems with total orders

In this paper, we introduce a construction method of total ordering cone on \mathbbRⁿ{\mathbb{R}^n} . It is shown that any total ordering cone on \mathbbRⁿ{\mathbb{R}^n} is isomorphic to the cone \mathbbRⁿ_lex{\mathbb{R}^n_{lex}} . Existence of a total ordering cone that contain given cone with a compact base is shown. By using this cone, a solving method of vector and set valued optimization problems is presented.     

Asynchronous Multisplitting GAOR Method and Asynchronous Multisplitting SSOR Method for Systems of Weakly Nonlinear Equations

In this article, we introduce two new asynchronous multisplitting methods for solving the system of weakly nonlinear equations Ax = G(x) in which A is an n × n real matrix and G(x) = (g ₁(x), g ₂(x), . . . , g _n (x)) ^T is a P-bounded mapping. First, by generalized accelerated overrelaxation (GAOR) technique, we introduce the asynchronous parallel multisplitting GAOR method (including the synchronous parallel multisplitting AOR method as a special case) for solving the system of weakly nonlinear equations. Second, asynchronous parallel multisplitting method based on symmetric successive overrelaxation (SSOR) multisplitting is introduced, which is called asynchronous parallel multisplitting SSOR method. Then under suitable conditions, we establish the convergence of the two introduced methods. The given results contain synchronous multisplitting iterations as a special case.     

Absolute value equation solution via concave minimization

The NP-hard absolute value equation (AVE) Ax − |x| = b where and is solved by a succession of linear programs. The linear programs arise from a reformulation of the AVE as the minimization of a piecewise-linear concave function on a polyhedral set and solving the latter by successive linearization. A simple MATLAB implementation of the successive linearization algorithm solved 100 consecutively generated 1,000-dimensional random instances of the AVE with only five violated equations out of a total of 100,000 equations.     

Implementing the 4-dimensional GLV method on GLS elliptic curves with <Emphasis Type="Italic">j</Emphasis>-invariant 0

The Gallant–Lambert–Vanstone (GLV) method is a very efficient technique for accelerating point multiplication on elliptic curves with efficiently computable endomorphisms. Galbraith et al. (J Cryptol 24(3):446–469, 2011) showed that point multiplication exploiting the 2-dimensional GLV method on a large class of curves over \mathbbF_p²{\mathbb{F}_{p^2}} was faster than the standard method on general elliptic curves over \mathbbF_p{\mathbb{F}_{p}} , and left as an open problem to study the case of 4-dimensional GLV on special curves (e.g., j (E) = 0) over \mathbbF_p²{\mathbb{F}_{p^2}} . We study the above problem in this paper. We show how to get the 4-dimensional GLV decomposition with proper decomposed coefficients, and thus reduce the number of doublings for point multiplication on these curves to only a quarter. The resulting implementation shows that the 4-dimensional GLV method on a GLS curve runs in about 0.78 the time of the 2-dimensional GLV method on the same curve and in between 0.78 − 0.87 the time of the 2-dimensional GLV method using the standard method over \mathbbF_p{\mathbb{F}_{p}} . In particular, our implementation reduces by up to 27% the time of the previously fastest implementation of point multiplication on x86-64 processors due to Longa and Gebotys (CHES2010).     

On numerical experiments with symmetric semigroups generated by three elements and their generalization

We give a simple explanation of numerical experiments of V. Arnold with two sequences of symmetric numerical semigroups, S(4,6+4k,87−4k) and S(9,3+9k,85−9k) generated by three elements. We present a generalization of these sequences by numerical semigroups S(r₁²,r₁r₂+r₁²k,r₃-r₁²k)\mathsf{S}(r_{1}^{2},r_{1}r_{2}+r_{1}^{2}k,r_{3}-r_{1}^{2}k), k∈ℤ, r ₁,r ₂,r ₃∈ℤ⁺, r ₁≥2 and gcd(r ₁,r ₂)=gcd(r ₁,r ₃)=1, and calculate their universal Frobenius number Φ(r ₁,r ₂,r ₃) for the wide range of k providing semigroups be symmetric. We show that this type of semigroups admit also nonsymmetric representatives. We describe the reduction of the minimal generating sets of these semigroups up to {r₁²,r₃-r₁²k}\{r_{1}^{2},r_{3}-r_{1}^{2}k\} for sporadic values of k and find these values by solving the quadratic Diophantine equation.     

New and efficient algorithms for transfer prices and inventory holding policies in two-enterprise supply chains

We consider a multi-period problem of fair transfer prices and inventory holding policies in two enterprise supply chains. This problem was formulated as a mixed integer non-linear program by Gjerdrum et al. (Eur J Oper Res 143:582–599, 2002). Existing global optimization methods to solve this problem are computationally expensive. We propose a continuous approach based on difference of convex functions (DC) programming and DC Algorithms (DCA) for solving this combinatorial optimization problem. The problem is first reformulated as a DC program via an exact penalty technique. Afterward, DCA, an efficient local approach in non-convex programming framework, is investigated to solve the resulting problem. For globally solving this problem, we investigate a combined DCA-Branch and Bound algorithm. DCA is applied to get lower bounds while upper bounds are computed from a relaxation problem. The numerical results on several test problems show that the proposed algorithms are efficient: DCA provides a good integer solution in a short CPU time although it works on a continuous domain, and the combined DCA-Branch and Bound finds an \(\epsilon \) -optimal solution for large-scale problems in a reasonable time.