Search

This paper intends to apply the sample-average-approximation (SAA) scheme to solve a system of stochastic equations (SSE), which has many applications in a variety of fields. The SAA is an effective paradigm to address risks and uncertainty in stochastic models from the perspective of Monte Carlo principle. Nonetheless, a numerical conflict arises from the sample size of SAA when one has to make a tradeoff between the accuracy of solutions and the computational cost. To alleviate this issue, we incorporate a gradually reinforced SAA scheme into a differentiable homotopy method and develop a gradually reinforced sample-average-approximation (GRSAA) differentiable homotopy method in this paper. By introducing a series of continuously differentiable functions of the homotopy parameter $t$ ranging between zero and one, we establish a differentiable homotopy system, which is able to gradually increase the sample size of SAA as $t$ descends from one to zero. The set of solutions to the homotopy system contains an everywhere smooth path, which starts from an arbitrary point and ends at a solution to the SAA with any desired accuracy. The GRSAA differentiable homotopy method serves as a bridge to link the gradually reinforced SAA scheme and a differentiable homotopy method and retains the nice property of global convergence the homotopy method possesses while greatly reducing the computational cost for attaining a desired solution to the original SSE. Several numerical experiments further confirm the effectiveness and efficiency of the proposed method.

This paper defines a strong convertible nonconvex(SCN) function for solving the unconstrained optimization problems with the nonconvex or nonsmooth(nondifferentiable) function. First, many examples of SCN function are given, where the SCN functions are nonconvex or nonsmooth. Second, the operational properties of the SCN functions are proved, including addition, multiplication, compound operations and so on. Third, the SCN forms of some special functions common in machine learning and engineering applications are presented respectively where these SCN function optimization problems can be transformed into minmax problems with a convex and concave objective function. Fourth,a minmax optimization problem of SCN function and its penalty function are defined. The optimization condition,exactness and stability of the minmax optimization problem are proved. Finally, an algorithm of penalty function to solve the minmax optimization problem and its convergence are given. This paper provides an efficient technique for solving unconstrained nonconvex or nonsmooth(nondifferentiable) optimization problems to avoid using subdifferentiation or smoothing techniques.

The paper introduces several new concepts for solving nonconvex or nonsmooth optimization problems, including convertible nonconvex function, exact convertible nonconvex function and differentiable convertible nonconvex function. It is proved herein many nonconvex functions or nonsmooth (or discontinuous) functions are actually convertible nonconvex functions and convertible nonconvex function operations such as addition, subtraction, multiplication or division result in convertible nonconvex functions. The sufficient condition for judging a global optimal solution to unconstrained optimization problems with differentiable convertible nonconvex functions is proved, which is equivalent to Karush-Kuhn-Tucker(KKT) condition. Two Lagrange functions of differentiable convertible nonconvex function are defined with their dual problems defined accordingly. The strong duality theorem is proved, showing that the optimal objective value of the global optimal solution is equal to the optimal objective value of the dual problem, which is equivalent to KKT condition. An augmented Lagrangian penalty function algorithm is proposed and its convergence is proved. So the paper provides a new idea for solving unconstrained nonconvex or non-smooth optimization problems and avoids subdifferentiation or smoothing techniques by using some gradient search algorithms, such as gradient descent algorithm, Newton algorithm and so on.

We consider two models of computation for Tarski's order preserving function f related to fixed points in a complete lattice: the oracle function model and the polynomial function model. In both models, we find the first polynomial time algorithm for finding a Tarski's fixed point. In addition, we provide a matching oracle bound for determining the uniqueness in the oracle function model and prove it is Co-NP hard in the polynomial function model. The existence of the pure Nash equilibrium in supermodular games is proved by Tarski's fixed point theorem. Exploring the difference between supermodular games and Tarski's fixed point, we also develop the computational results for finding one pure Nash equilibrium and determining the uniqueness of the equilibrium in supermodular games.

In this paper, a new alternating direction trust region method based on conic model is used to solve unconstrained optimization problems. By use of the alternating direction method, the new conic model trust region subproblem is solved by two steps in two orthogonal directions. This new idea overcomes the shortcomings of conic model subproblem which is difficult to solve. Then the global convergence of the method under some reasonable conditions is established. Numerical experiment shows that this method may be better than the dogleg method to solve the subproblem, especially for large-scale problems., Comment: 18 pages,3 tables

Based on the numerical representations by T basic vectors of a symbolic sequence consisting of T symbols, first, we prove mathematical that the total Fourier spectrum of the sequence is the square of the length of the sequence. In the meantime, we define the indicator sequences vector. Using the orthogonal or row orthogonal transformations of the indicator sequences vector, we construct some special numerical representations of the symbolic sequence and characterize the signal-to-noise ratios of the power spectrum of the numerical representations. After calculating the discrete Fourier transform of those special numerical representations, the signal-to-noise ratios of them can be figured out. Mathematical theorems prove that the signal-to-noise ratio of the Fourier spectrum of those special representations of the symbolic sequence is T/(T-1) times the signal-to-noise ratio of the representation by T base vectors. The results are applied in analyzing the properties of the DNA sequences or protein sequences in the frequency domain, if one uses the signal-to-noise ratios of special representations as the distinguishing criterion, the distinguishing results only depend upon the distribution of the symbols in the symbolic sequence and their mathematical constructions of representations, but do not relate to the chemical or biological meanings of the representations.