Solving nonconvex nonlinear programming problems via a new aggregate constraint homotopy method

In this paper, by introducing C² mappings ξ_i(x,z_i),i=1,…,m and using the idea of the aggregate function method, a new aggregate constraint homotopy method is proposed to solve the Karush-Kuhn-Tucker (KKT) point of nonconvex nonlinear programming problems. Compared with the previous results, the choice scope of initial points is greatly enlarged, so use of the new aggregate constraint homotopy method may improve the computational efficiency of reduced predictor-corrector algorithms.     

Homotopy method for solving variational inequalities with bounded box constraints

In this paper, using the Gabriel–Moré smoothing function of the median function, a smooth homotopy method for solving nonsmooth equation reformulation of bounded box constrained variational inequality problem VIP(l,u,F$l,u,F$) is given. Without any monotonicity condition on the defining map F$F$, for starting point chosen almost everywhere in Rⁿ$R^n$, existence and convergence of the homotopy pathway are proven. Nevertheless, it is also proven that, if the starting point is chosen to be an interior point of the box, the proposed homotopy method can also serve as an interior point method.     

A globally convergent interior point algorithm for non-convex nonlinear programming

In this paper, a new algorithm for tracing the combined homotopy path of the non-convex nonlinear programming problem is proposed. The algorithm is based on the techniques of β$\beta$-cone neighborhood and a combined homotopy interior point method. The residual control criteria, which ensures that the obtained iterative points are interior points, is given by the condition that ensures the β$\beta$-cone neighborhood to be included in the interior part of the feasible region. The global convergence and polynomial complexity are established under some hypotheses.     

On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids

Given A?{a¹,…,a^m}⊂R^d whose affine hull is R^d, we study the problems of computing an approximate rounding of the convex hull of A and an approximation to the minimum-volume enclosing ellipsoid of A. In the case of centrally symmetric sets, we first establish that Khachiyan's barycentric coordinate descent (BCD) method is exactly the polar of the deepest cut ellipsoid method using two-sided symmetric cuts. This observation gives further insight into the efficient implementation of the BCD method. We then propose a variant algorithm which computes an approximate rounding of the convex hull of A, and which can also be used to compute an approximation to the minimum-volume enclosing ellipsoid of A. Our algorithm is a modification of the algorithm of Kumar and Y?ld?r?m, which combines Khachiyan's BCD method with a simple initialization scheme to achieve a slightly improved polynomial complexity result, and which returns a small “core set.” We establish that our algorithm computes an approximate solution to the dual optimization formulation of the minimum-volume enclosing ellipsoid problem that satisfies a more complete set of approximate optimality conditions than either of the two previous algorithms. Furthermore, this added benefit is achieved without any increase in the improved asymptotic complexity bound of the algorithm of Kumar and Y?ld?r?m or any increase in the bound on the size of the computed core set. In addition, the “dropping idea” used in our algorithm has the potential of computing smaller core sets in practice. We also discuss several possible variants of this dropping technique.     

Solving the Karush–Kuhn–Tucker system of a nonconvex programming problem on an unbounded set

In the papers [G.C. Feng, B. Yu, Combined homotopy interior point method for nonlinear programming problems, in: H. Fujita, M. Yamaguti (Eds.), Advances in Numerical Mathematics; Proceedings of the Second Japan–China Seminar on Numerical Mathematics, in: Lecture Notes in Numerical and Applied Analysis, vol. 14, Kinokuniya, Tokyo, 1995, pp. 9–16; G.C. Feng, Z.H. Lin, B. Yu, Existence of an interior pathway to a Karush–Kuhn–Tucker point of a nonconvex programming problem, Nonlinear Analysis 32 (1998) 761–768; Z.H. Lin, B. Yu, G.C. Feng, A combined homotopy interior point method for convex programming problem, Applied Mathematics and Computation 84 (1997) 193–211], a combined homotopy interior method was presented and global convergence results obtained for nonconvex nonlinear programming when the feasible set is bounded and satisfies the so called normal cone condition. However, for when the feasible set is not bounded, no result has so far been obtained. In this paper, a combined homotopy interior method for nonconvex programming problems on the unbounded feasible set is considered. Under suitable additional assumptions, boundedness of the homotopy path, and hence global convergence, is proven.     

Necessary conditions of the isolated zero-points with nonzero degree and choice of initial approximations for the secant method in the n-dimensional case

Necessary conditions of isolated zero-points with nonzero degree (in particular, point of local minimum or maximum either saddlepoint) in R ⁿ which is an extension of the rule that the first derivative of a function changes a sign in every neighborhood of an isolated point of local minimum or maximum in JR1 and connected with this choice of initial approximations for the secant method are given and proved. Most of the statements are given through using the basic topological facts such as degree, the fiberings of a finite dimensional sphere, homotopy, quotient topology, etc.     

On the symmetry function of a convex set

We attempt a broad exploration of properties and connections between the symmetry function of a convex set S ${S \subset\mathbb{R}^n}We attempt a broad exploration of properties and connections between the symmetry function of a convex set S and other arenas of convexity including convex functions, convex geometry, probability theory on convex sets, and computational complexity. Given a point , let sym(x,S) denote the symmetry value of x in S: , which essentially measures how symmetric S is about the point x, and define x ^* is called a symmetry point of S if x ^* achieves the above maximum. The set S is a symmetric set if sym (S)=1. There are many important properties of symmetric convex sets; herein we explore how these properties extend as a function of sym (S) and/or sym (x,S). By accounting for the role of the symmetry function, we reduce the dependence of many mathematical results on the strong assumption that S is symmetric, and we are able to capture and otherwise quantify many of the ways that the symmetry function influences properties of convex sets and functions. The results in this paper include functional properties of sym (x,S), relations with several convex geometry quantities such as volume, distance, and cross-ratio distance, as well as set approximation results, including a refinement of the L?wner-John rounding theorems, and applications of symmetry to probability theory on convex sets. We provide a characterization of symmetry points x ^* for general convex sets. Finally, in the polyhedral case, we show how to efficiently compute sym(S) and a symmetry point x ^* using linear programming. The paper also contains discussions of open questions as well as unproved conjectures regarding the symmetry function and its connection to other areas of convexity theory. Dedicated to Clovis Gonzaga on the occasion of his 60th birthday.     

Modifying the BFGS update by a new column scaling technique

LetB be a positive definite symmetric approximation to the second derivative matrix of the objective function of a minimization calculation. We study modifications of the BFGS method that apply a scaling technique to the columns of a conjugate direction matrixZ satisfyingZ ^T BZ = I. For a simple scaling technique similar to the ones considered by Powell (1987) and (1989) we show that, due to a two iteration cycle, linear convergence can occur when the method is applied to a quadratic function and Wolfe's line search is employed, although for exact line searches quadratic termination can be proved. We then suggest a different scaling technique that prevents certain columns thought to contain important curvature information from being scaled. For this algorithm we prove global and superlinear convergence and demonstrate the superiority of our method over the BFGS formula on a range of illconditioned optimization problems. Moreover, we present an implementation of our algorithm that requires only 3n ² +O(n) multiplications per iteration.     

Embedded associated primes of powers of square-free monomial ideals

An ideal I in a Noetherian ring R is normally torsion-free if Ass(R/I^t)=Ass(R/I) for all t≥1. We develop a technique to inductively study normally torsion-free square-free monomial ideals. In particular, we show that if a square-free monomial ideal I is minimally not normally torsion-free then the least power t such that I^t has embedded primes is bigger than β₁, where β₁ is the monomial grade of I, which is equal to the matching number of the hypergraph H(I) associated to I. If, in addition, I fails to have the packing property, then embedded primes of I^t do occur when t=β₁+1. As an application, we investigate how these results relate to a conjecture of Conforti and Cornuéjols.     

Lipschitz gradients for global optimization in a one-point-based partitioning scheme

A global optimization problem is studied where the objective function f(x)$f\left(x\right)$ is a multidimensional black-box function and its gradient f^′(x)$f^{\prime }\left(x\right)$ satisfies the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant K$K$. Different methods for solving this problem by using an a priori given estimate of K$K$, its adaptive estimates, and adaptive estimates of local Lipschitz constants are known in the literature. Recently, the authors have proposed a one-dimensional algorithm working with multiple estimates of the Lipschitz constant for f^′(x)$f^{\prime }\left(x\right)$ (the existence of such an algorithm was a challenge for 15 years). In this paper, a new multidimensional geometric method evolving the ideas of this one-dimensional scheme and using an efficient one-point-based partitioning strategy is proposed. Numerical experiments executed on 800 multidimensional test functions demonstrate quite a promising performance in comparison with popular DIRECT-based methods.     

Asymptotic formulas for the derivatives of probability functions and their Monte Carlo estimations

One of the key problems in chance constrained programming for nonlinear optimization problems is the evaluation of derivatives of joint probability functions of the form P(x)=P(_gp(x,Λ)?_cp,p=1,…,_Nc)$P(x)=\mathbb{P}(g_p(x\text{,}\Lambda )?c_p\text{,}p=1\text{,}\dots \text{,}{N}_c)$. Here x∈R^_Nx$x\in {\mathbb{R}}^{N_x}$ is the vector of physical parameters, Λ∈R^_NΛ$\Lambda \in {\mathbb{R}}^{N_{\Lambda }}$ is a random vector describing the uncertainty of the model, g:R^_Nx×R^_NΛ→R^_Nc$g:{\mathbb{R}}^{N_x}\times {\mathbb{R}}^{N_{\Lambda }}\to {\mathbb{R}}^{N_c}$ is the constraints mapping, and c∈R^_Nc$c\in {\mathbb{R}}^{N_c}$ is the vector of constraint levels. In this paper specific Monte Carlo tools for the estimations of the gradient and Hessian of P(x)$P(x)$ are proposed when the input random vector Λ$\Lambda$ has a multivariate normal distribution and small variances. Using the small variance hypothesis, approximate expressions for the first- and second-order derivatives are obtained, whose Monte Carlo estimations have low computational costs. The number of calls of the constraints mapping g   for the proposed estimators of the gradient and Hessian of P(x)$P(x)$ is only 1+2_Nx+2_NΛ$1+2N_x+2N_{\Lambda }$.     

Convergence rate of Newton's method for L 2 spectral estimation

In the paper, we prove the Hölder continuous property of the Jacobian of the function generated from the dual of the power spectrum estimation problem. It follows that the convergence of the Newton method for the problem is at least of order where m is the order of the trigonometric bases. This result theoretically confirms the numerical observation by Potter (1990) and Cole and Goodrich (1993).     

Second-order conditions in C 1,1 constrained vector optimization

We consider the constrained vector optimization problem min _C f(x), g(x) ∈ ?K, where f:? ⁿ →? ^m and g:? ⁿ →? ^p are C ^1,1 functions, and C ? ^m and K ? ^p are closed convex cones with nonempty interiors. Two type of solutions are important for our considerations, namely w-minimizers (weakly efficient points) and i-minimizers (isolated minimizers). We formulate and prove in terms of the Dini directional derivative second-order necessary conditions for a point x ⁰ to be a w-minimizer and second-order sufficient conditions for x ⁰ to be an i-minimizer of order two. We discuss the reversal of the sufficient conditions under suitable constraint qualifications of Kuhn-Tucker type. The obtained results improve the ones in Liu, Neittaanmäki, K?í?ek [21].     

Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems

In this paper, we propose a new family of NCP-functions and the corresponding merit functions, which are the generalization of some popular NCP-functions and the related merit functions. We show that the new NCP-functions and the corresponding merit functions possess a system of favorite properties. Specially, we show that the new NCP-functions are strongly semismooth, Lipschitz continuous, and continuously differentiable; and that the corresponding merit functions have SC¹$S{C}^1$ property (i.e., they are continuously differentiable and their gradients are semismooth) and LC¹$L{C}^1$ property (i.e., they are continuously differentiable and their gradients are Lipschitz continuous) under suitable assumptions. Based on the new NCP-functions and the corresponding merit functions, we investigate a derivative free algorithm for the nonlinear complementarity problem and discuss its global convergence. Some preliminary numerical results are reported.     

Filled function method for nonlinear equations

Systems of nonlinear equations are ubiquitous in engineering, physics and mechanics, and have myriad applications. Generally, they are very difficult to solve. In this paper, we will present a filled function method to solve nonlinear systems. We will first convert the nonlinear systems into equivalent global optimization problems with the property: x^∗ is a global minimizer if and only if its function value is zero. A filled function method is proposed to solve the converted global optimization problem. Numerical examples are presented to illustrate our new techniques.     

Solvability of Newton equations in smoothing-type algorithms for the SOCCP

In this paper, we first investigate the invertibility of a class of matrices. Based on the obtained results, we then discuss the solvability of Newton equations appearing in the smoothing-type algorithm for solving the second-order cone complementarity problem (SOCCP). A condition ensuring the solvability of such a system of Newton equations is given. In addition, our results also show that the assumption that the Jacobian matrix of the function involved in the SOCCP is a P₀-matrix is not enough for ensuring the solvability of such a system of Newton equations, which is different from the one of smoothing-type algorithms for solving many traditional optimization problems in ℜⁿ.     

Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems

Many problems in the areas of scientific computing and engineering applications can lead to the solution of the linear complementarity problem LCP (M,q). It is well known that the matrix multisplitting methods have been found very useful for solving LCP (M,q). In this article, by applying the generalized accelerated overrelaxation (GAOR) and the symmetric successive overrelaxation (SSOR) techniques, we introduce two class of synchronous matrix multisplitting methods to solve LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Also the monotone convergence of the new methods is established. Finally, the numerical results show that the introduced methods are effective for solving the large and sparse linear complementary problems.     

A proximal iterative approach to a non-convex optimization problem

We consider a variable Krasnosel’skii-Mann algorithm for approximating critical points of a prox-regular function or equivalently for finding fixed-points of its proximal mapping prox_λf. The novelty of our approach is that the latter is not non-expansive any longer. We prove that the sequence generated by such algorithm (via the formula x_k+1=(1−α_k)x_k+α_kprox_λkfx_k, where (α_k) is a sequence in (0,1)), is an approximate fixed-point of the proximal mapping and converges provided that the function under consideration satisfies a local metric regularity condition.     

Approximation of the solution of certain nonlinear ODEs with linear complexity

We study the positive stationary solutions of a standard finite-difference discretization of the semilinear heat equation with nonlinear Neumann boundary conditions. We prove that there exists a unique solution of such a discretization, which approximates the unique positive stationary solution of the “continuous” equation. Furthermore, we exhibit an algorithm computing an ε-approximation of such a solution by means of a homotopy continuation method. The cost of our algorithm is linear in the number of nodes involved in the discretization and the logarithm of the number of digits of approximation required.