Search

The optimization problems with a sparsity constraint is a class of important global optimization problems. A typical type of thresholding algorithms for solving such a problem adopts the traditional full steepest descent direction or Newton-like direction as a search direction to generate an iterate on which a certain thresholding is performed. Traditional hard thresholding discards a large part of a vector, and thus some important information contained in a dense vector has been lost in such a thresholding process. Recent study (Zhao in SIAM J Optim 30(1): 31–55, 2020) shows that the hard thresholding should be applied to a compressible vector instead of a dense vector to avoid a big loss of information. On the other hand, the optimal k-thresholding as a novel thresholding technique may overcome the intrinsic drawback of hard thresholding, and performs thresholding and objective function minimization simultaneously. This motivates us to propose the so-called partial gradient optimal thresholding (PGOT) method and its relaxed versions in this paper. The PGOT is an integration of the partial gradient and the optimal k-thresholding technique. The solution error bound and convergence for the proposed algorithms have been established in this paper under suitable conditions. Application of our results to the sparse optimization problems arising from signal recovery is also discussed. Experiment results from synthetic data indicate that the proposed algorithm is efficient and comparable to several existing algorithms.

The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted $$\ell _{1}$$ ℓ 1 -algorithms for a class of $$\ell _{0}$$ ℓ 0 -minimization models which can be used to model a wide range of practical problems. This class of algorithms is based on certain convex relaxations of the reformulation of the underlying $$\ell _{0}$$ ℓ 0 -minimization model. Such a reformulation is a special bilevel optimization problem which, in theory, is equivalent to the underlying $$\ell _{0}$$ ℓ 0 -minimization problem under the assumption of strict complementarity. Some basic properties of these algorithms are discussed, and numerical experiments have been carried out to demonstrate the efficiency of the proposed algorithms. Comparison of numerical performances of the proposed methods and the classic reweighted $$\ell _1$$ ℓ 1 -algorithms has also been made in this paper.

The sparse optimization problems arise in many areas of science and engineering, such as compressed sensing, image processing, statistical and machine learning. The l 0 -minimization problem is one...

Sparse signals can be possibly reconstructed by an algorithm which merges a traditional nonlinear optimization method and a certain thresholding technique. Different from existing thresholding methods, a novel thresholding technique referred to as the optimal k-thresholding was recently proposed by Zhao (SIAM J Optim 30(1):31–55, 2020). This technique simultaneously performs the minimization of an error metric for the problem and thresholding of the iterates generated by the classic gradient method. In this paper, we propose the so-called Newton-type optimal k-thresholding (NTOT) algorithm which is motivated by the appreciable performance of both Newton-type methods and the optimal k-thresholding technique for signal recovery. The guaranteed performance (including convergence) of the proposed algorithms is shown in terms of suitable choices of the algorithmic parameters and the restricted isometry property (RIP) of the sensing matrix which has been widely used in the analysis of compressive sensing algorithms. The simulation results based on synthetic signals indicate that the proposed algorithms are stable and efficient for signal recovery.

When a tensor is partitioned into subtensors, some tensor norms of these subtensors form a tensor called a norm compression tensor. Norm compression inequalities for tensors focus on the relation of the norm of this compressed tensor to the norm of the original tensor. We prove that for the tensor spectral norm, the norm of the compressed tensor is an upper bound of the norm of the original tensor. This result can be extended to a general class of tensor spectral norms. We discuss various applications of norm compression inequalities for tensors. These inequalities improve many existing bounds of tensor norms in the literature, in particular tightening the general bound of the tensor spectral norm via tensor partitions. We study the extremal ratio between the spectral norm and the Frobenius norm of a tensor space, provide a general way to estimate its upper bound, and in particular, improve the current best upper bound for third order nonnegative tensors and symmetric tensors. We also propose a faster approach to estimate the spectral norm of a large tensor or matrix via sequential norm compression inequalities with theoretical and numerical evidence. For instance, the complexity of our algorithm for the matrix spectral norm is$$O\left( n^{2+\epsilon }\right) $$On2+ϵwhere$$\epsilon $$ϵranges from 0 to 1 depending on the partition and the estimate ranges correspondingly from some close upper bound to the exact spectral norm.

Compressed sensing is a signal processing technique whereby the limits imposed by the Shannon--Nyquist theorem can be exceeded provided certain conditions are imposed on the signal. Such conditions occur in many real-world scenarios, and compressed sensing has emerging applications in medical imaging, big data, and statistics. Finding practical matrix constructions and computationally efficient recovery algorithms for compressed sensing is an area of intense research interest. Many probabilistic matrix constructions have been proposed, and it is now well known that matrices with entries drawn from a suitable probability distribution are essentially optimal for compressed sensing. Potential applications have motivated the search for constructions of sparse compressed sensing matrices (i.e., matrices containing few non-zero entries). Various constructions have been proposed, and simulations suggest that their performance is comparable to that of dense matrices. In this paper, extensive simulations are presented which suggest that sparsification leads to a marked improvement in compressed sensing performance for a large class of matrix constructions and for many different recovery algorithms.

The optimal k -thresholding (OT) and optimal k -thresholding pursuit (OTP) are newly introduced frameworks of thresholding techniques for compressed sensing and signal approximation. Such frameworks motivate the practical and efficient algorithms called relaxed optimal k -thresholding ( ROT ω ) and relaxed optimal k -thresholding pursuit ( ROTP ω ) which are developed through the tightest convex relaxations of OT and OTP, where ω is a prescribed integer number. The preliminary numerical results demonstrated in Zhao (2020) indicate that these approaches can stably reconstruct signals with a wide range of sparsity levels. However, the guaranteed performance of these algorithms with parameter ω ≥ 2 has not yet established in Zhao (2020). The purpose of this paper is to show the guaranteed performance of OT and OTP in terms of the restricted isometry property (RIP) of nearly optimal order for the sensing matrix governing the k -sparse signal recovery, and to establish the first guaranteed performance result for ROT ω and ROTP ω with ω ≥ 2 . In the meantime, we provide a numerical comparison between ROTP ω and several existing thresholding methods.

In this paper, we study the generalized Hadamard well-posedness of infinite vector optimization problems (IVOP). Without the assumption of continuity with respect to the first variable, the upper semicontinuity and closedness of constraint set mappings are established. Under weaker assumptions, sufficient conditions of generalized Hadamard well-posedness for IVOP are obtained under perturbations of both the objective function and the constraint set. We apply our results to the semi-infinite vector optimization problem and the semi-infinite multi-objective optimization problem.

The ℓ0-minimization problem that seeks the sparsest point of a polyhedral set is a long-standing, challenging problem in the fields of signal and image processing, numerical linear algebra, and mathematical optimization. The weighted ℓ1-method is one of the most plausible methods for solving this problem. In this paper we develop a new weighted ℓ1-method through the strict complementarity theory of linear programs. More specifically, we show that locating the sparsest point of a polyhedral set can be achieved by seeking the densest possible slack variable of the dual problem of weighted ℓ1-minimization. As a result, ℓ0-minimization can be transformed, in theory, to ℓ0-maximization in dual space through some weight. This theoretical result provides a basis and an incentive to develop a new weighted ℓ1-algorithm, which is remarkably distinct from existing sparsity-seeking methods. The weight used in our algorithm is computed via a certain convex optimization instead of being determined locally at an iterate. The guaranteed performance of this algorithm is shown under some conditions, and the numerical performance of the algorithm has been demonstrated by empirical simulations.

The simulations indicate that the existing hard thresholding technique independent of the residual function may cause a dramatic increase or numerical oscillation of the residual. This inherit drawback of the hard thresholding renders the traditional thresholding algorithms unstable and thus generally inefficient for solving practical sparse optimization problems. How to overcome this weakness and develop a truly efficient thresholding method is a fundamental question in this field. The aim of this paper is to address this question by proposing a new thresholding technique based on the notion of optimal $k$-thresholding. The central idea for this new development is to connect the $k$-thresholding directly to the residual reduction during the course of algorithms. This leads to a natural design principle for the efficient thresholding methods. Under the restricted isometry property (RIP), we prove that the optimal thresholding based algorithms are globally convergent to the solution of sparse optimization problems. The numerical experiments demonstrate that when solving sparse optimization problems, the traditional hard thresholding methods have been significantly transcended by the proposed algorithms which can even outperform the classic $\ell_1$-minimization method in many situations.

Berberine (BBR) is an isoquinoline alkaloid extracted from Rhizoma coptidis and has been used for treating type 2 diabetes mellitus (T2DM) in China. The development of T2DM is often associated with insulin resistance and impaired glucose uptake in peripheral tissues. In this study, we examined whether BBR attenuated glucose uptake dysfunction through the cholinergic anti-inflammatory pathway in HepG2 cells. Cellular glucose uptake, quantified by the 2-[N-(7-Nitrobenz-2-oxa-1,3-diazol-4-yl)-amino]-2-deoxy-D-glucose (2-NBDG), was inhibited by 21% after HepG2 cells were incubated with insulin (10(-6) mol/L) for 36 h. Meanwhile, the expression of alpha7 nicotinic acetylcholine receptor (α7nAChR) protein was reduced without the change of acetylcholinesterase (AChE) activity. The level of interleukin-6 (IL-6) in the culture supernatant, the ratio of phosphorylated I-kappa-B kinase-β (IKκβ) Ser181/IKKβ and the expression of nuclear factor-kappa B (NF-κB) p65 protein were also increased. However, the treatment with BBR enhanced the glucose uptake, increased the expression of α7nAChR protein and inhibited AChE activity. These changes were also accompanied with the decrease of the ratio of pIKKβ Ser181/IKKβ, NF-κB p65 expression and IL-6 level. Taken together, these results suggest that BBR could enhance glucose uptake, and relieve insulin resistance and inflammation in HepG2 cells. The mechanism may be related to the cholinergic anti-inflammatory pathway and the inhibition of AChE activity.

As one of the most plausible convex optimization methods for sparse data reconstruction, l1-minimization plays a fundamental role in the development of sparse optimization theory. The stability of ...

Fly ash from sludge incineration was separated into five different sizes (1 μm, 1-2.5 μm, 2.5-10 μm, 10-50 μm, and50 μm) by high-precision air classification equipment. The leaching of heavy metals was contrastively studied using the HJT 299-2007-sulfuric acid/nitric acid method, HJ 557-2009-Horizontal Oscillation Method, toxicity characteristic leaching procedure (TCLP), and European standard protocol (EN 12457-3) for the different size fractions of the fly ash. Based on the leaching results, an evaluation method for the comprehensive toxicity of heavy metal leaching was established. The results show that the content of heavy metals and the amount of leaching from the fly ash decrease with the increase in fly ash particle size. The leaching of the heavy metals Zn and Cu in the1 μm particle size range of TCLP leaching method was the highest, at 107.34 mg·kg

The connection between the sparsest solution to an underdetermined system of linear equations and the weighted $\ell_1$-minimization problem is established in this paper. We show that seeking the sparsest solution to a linear system can be transformed to searching for the densest slack variable of the dual problem of weighted $\ell_1$-minimization with all possible choices of nonnegative weights. Motivated by this fact, a new reweighted $\ell_1$-algorithm for the sparsest solutions of linear systems, going beyond the framework of existing sparsity-seeking methods, is proposed in this paper. Unlike existing reweighted $\ell_1$-methods that are based on the weights defined directly in terms of iterates, the new algorithm computes a weight in dual space via certain convex optimization and uses such a weight to locate the sparsest solutions. It turns out that the new algorithm converges to the sparsest solutions of linear systems under some mild conditions that do not require the uniqueness of the sparsest so...

We consider a class of nonsmooth convex optimization problems where the objective function is a convex differentiable function regularized by the sum of the group reproducing kernel norm and $$\ell _1$$l1-norm of the problem variables. This class of problems has many applications in variable selections such as the group LASSO and sparse group LASSO. In this paper, we propose a proximal Landweber Newton method for this class of convex optimization problems, and carry out the convergence and computational complexity analysis for this method. Theoretical analysis and numerical results show that the proposed algorithm is promising.

Many practical problems can be formulated as $$\ell _0$$ -minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $$\ell _1$$ -minimization is efficient for solving $$\ell _0$$ -minimization problems. From a mathematical point of view, however, the understanding of the relationship between $$\ell _0$$ - and $$\ell _1$$ -minimization remains incomplete. In this paper, we further address several theoretical questions associated with these two problems. We prove that the fundamental strict complementarity theorem of linear programming can yield a necessary and sufficient condition for a linear system to admit a unique least $$\ell _1$$ -norm nonnegative solution. This condition leads naturally to the so-called range space property (RSP) and the “full-column-rank” property, which altogether provide a new and broad understanding of the equivalence and the strong equivalence between $$ \ell _0$$ - and $$\ell _1$$ -minimization. Motivated by these results, we introduce the concept of “RSP of order $$K$$ ” that turns out to be a full characterization of uniform recovery of all $$K$$ -sparse nonnegative vectors. This concept also enables us to develop a nonuniform recovery theory for sparse nonnegative vectors via the so-called weak range space property.

The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest solutions. The coherence rank of a matrix with normalized columns is the maximum number of absolute entries in a row of its Gram matrix that are equal to the mutual coherence. The main result of this paper claims that when the coherence rank of a matrix is low, the mutual-coherence-based uniqueness conditions for the sparsest solution of a linear system can be improved. Furthermore, we prove that the Babel-function-based uniqueness can be also improved by the so-called sub-Babel function. Moreover, we show that the scaled-coherence-based uniqueness conditions can be developed, and that the right-hand-side vector $b$ of a linear system, the support overlap of solutions, the orthogonal matrix out of the singular value decomposition of a matrix, and the range property of a transposed matrix can be also integrated into the criteria for the uniqueness of the sparsest solution of an underdetermined linear system.

The problem of finding a rank-one solution to a system of linear matrix equations arises from many practical applications. Given a system of linear matrix equations, however, such a low-rank solution does not always exist. In this paper, we aim at developing some sufficient conditions for the existence of a rank-one solution to the system of homogeneous linear matrix equations (HLME) over the positive semidefinite cone. First, we prove that an existence condition of a rank-one solution can be established by a homotopy invariance theorem. The derived condition is closely related to the so-called P"@A property of the function defined by quadratic transformations. Second, we prove that the existence condition for a rank-one solution can be also established through the maximum rank of the (positive semidefinite) linear combination of given matrices. It is shown that an upper bound for the rank of the solution to a system of HLME over the positive semidefinite cone can be obtained efficiently by solving a semidefinite programming (SDP) problem. Moreover, a sufficient condition for the nonexistence of a rank-one solution to the system of HLME is also established in this paper.

Numerical experiments have indicated that the reweighted $\ell_1$-minimization performs exceptionally well in locating sparse solutions of underdetermined linear systems of equations. We show that reweighted $\ell_1$-methods are intrinsically associated with the minimization of the so-called merit functions for sparsity, which are essentially concave approximations to the cardinality function. Based on this observation, we further show that a family of reweighted $\ell_1$-algorithms can be systematically derived from the perspective of concave optimization through the linearization technique. In order to conduct a unified convergence analysis for this family of algorithms, we introduce the concept of the range space property (RSP) of a matrix and prove that if its adjoint has this property, the reweighted $\ell_1$-algorithm can find a sparse solution to the underdetermined linear system provided that the merit function for sparsity is properly chosen. In particular, some convergence conditions for the Can...

A novel high-performance liquid chromatography (HPLC) method based on the internal standard method was established for assaying the tumour necrosis factor-α converting enzyme (TACE) activity and matrix metalloprotease-9 (MMP-9) activity, and was used to evaluate the inhibitive effectiveness of inhibitors to TACE and MMP-9. In the assay method for TACE and MMP-9, peptides labelled with the ultraviolet group-Dpa were used as substrates. Alanine-Dpa was synthesised and was used as the internal standard for quantitative analysis. After the peptide substrates were hydrolysed by TACE (MMP-9) for 15 min (25 min) at 37 °C, the amount of remaining substrates were determined by reversed-phased HPLC with UV detection at 353 nm. The relative peak area of the substrate was linearly dependent on the substrate concentration. This method was then applied to determine the 50% inhibitory concentration (IC₅₀) of GM6001 and inhibitor A for both TACE and MMP-9.

We consider spline interpolation problems where information about the approximated function is given by means of interval estimates for the function values over ranges of x-values instead of specific knots. We propose two robust univariate spline models formulated as convex semi-infinite optimization problems. We present simplified equivalent formulations of both models as finite explicit convex optimization problems for splines of degrees up to 3. This makes it possible to use existing convex optimization algorithms and software.

While the product of finitely many convex functions has been investigated in the field of global optimization, some fundamental issues such as the convexity condition and the Legendre-Fenchel transform for the product function remain unresolved. Focusing on quadratic forms, this paper is aimed at addressing the question: When is the product of finitely many positive definite quadratic forms convex, and what is the Legendre-Fenchel transform for it? First, we show that the convexity of the product is determined intrinsically by the condition number of so-called ‘scaled matrices’ associated with quadratic forms involved. The main result claims that if the condition number of these scaled matrices are bounded above by an explicit constant (which depends only on the number of quadratic forms involved), then the product function is convex. Second, we prove that the Legendre-Fenchel transform for the product of positive definite quadratic forms can be expressed, and the computation of the transform amounts to finding the solution to a system of equations (or equally, finding a Brouwer’s fixed point of a mapping) with a special structure. Thus, a broader question than the open “Question 11” in Hiriart-Urruty (SIAM Rev. 49, 225–273, 2007) is addressed in this paper.

It is well known that the Legendre-Fenchel conjugate of a positive definite quadratic form can be explicitly expressed as another positive definite quadratic form and that the conjugate of the sum of several positive definite quadratic forms can be expressed via inf-convolution. However, the Legendre-Fenchel conjugate of the product of two positive definite quadratic forms is not clear at present. Hiriart-Urruty posted it as an open question in the field of nonlinear analysis and optimization [Question 11 in SIAM Rev., 49 (2007), pp. 255-273]. From a convex analysis point of view, it is interesting and important to address such a question. The purpose of this paper is to answer this question and to provide a formula for the conjugate of the product of two positive definite quadratic forms. We prove that the computation of the conjugate can be implemented via finding a root of a certain univariate polynomial equation, and we also identify the situations in which the conjugate can be explicitly expressed as a single function without involving any parameter. Some other issues, including the convexity condition for the product function, are also investigated as well. Our analysis shows that the relationship between the matrices of quadratic forms plays a vital role in determining whether the conjugate can be explicitly expressed or not.

Traditional univariate cubic spline models assume that the position and function value of each knot are given precisely. It has been observed that errors in data could result in significant fluctuations of the resulting spline. To handle situations that involve uncertainty only in measurements of function values, the concept of a robust spline has been developed in the literature. We propose a more general concept of a PH-robust cubic spline that takes into account also uncertainty in positions of measurements (knots or boundary points) using the paradigm of robust optimization. This bridges the robustness concepts developed in the interpolation/approximation and the optimization communities. Our model handles the case of "coordinated" variations of positions of measurements. It is formulated as a semi-infinite convex optimization problem. We develop a reformulation of the model as a finite explicit convex optimization problem, which makes it possible to use standard convex optimization algorithms for computation.

We consider a rather general class of mathematical programming problems with data uncertainty, where the uncertainty set is represented by a system of convex inequalities. We prove that the robust counterparts of this class of problems can be reformulated equivalently as finite and explicit optimization problems. Moreover, we develop simplified reformulations for problems with uncertainty sets defined by convex homogeneous functions. Our results provide a unified treatment of many situations that have been investigated in the literature and are applicable to a wider range of problems and more complicated uncertainty sets than those considered before. The analysis in this paper makes it possible to use existing continuous optimization algorithms to solve more complicated robust optimization problems. The analysis also shows how the structure of the resulting reformulation of the robust counterpart depends both on the structure of the original nominal optimization problem and on the structure of the uncertainty set.

We establish two global bounds measuring the distance from any vector to the solution set of the co-coercive variational inequality. To prove our results, we use the fact that the co-coercivity condition is sufficient for the (strong) monotonicity of (perturbed) fixed point and normal maps associated with variational inequalities.

With the objective of generating "shape-preserving" smooth interpolating curves that represent data with abrupt changes in magnitude and/or knot spacing, we study a class of first-derivative-based $$\mathcal{C}^1$$ -smooth univariate cubic L 1 splines. An L 1 spline minimizes the L 1 norm of the difference between the first-order derivative of the spline and the local divided difference of the data. Calculating the coefficients of an L 1 spline is a nonsmooth non-linear convex program. Via Fenchel's conjugate transformation, the geometric dual program is a smooth convex program with a linear objective function and convex cubic constraints. The dual-to-primal transformation is accomplished by solving a linear program.

Homogeneous programming is an important class of optimization problems. The purpose of this note is to give a truly equivalent characterization of KKT points of homogeneous programming problems, correcting a result given by Lasserre and Hiriart-Urruty in Ref. 1.

Based on the recent theoretical results of Zhao and Li [Math. Oper. Res., 26 (2001), pp. 119--146], we present in this paper a new path-following method for nonlinear P* complementarity problems. Different from most existing interior-point algorithms that are based on the central path, this algorithm tracks the "regularized central path" which exists for any continuous P* problem. It turns out that the algorithm is globally convergent for any P* problem provided that its solution set is nonempty. By different choices of the parameters in the algorithm, the iterative sequence can approach to different types of points of the solution set. Moreover, local superlinear convergence of this algorithm can also be achieved under certain conditions.

The generalized mean function has been widely used in convex analysis and mathematical programming. This paper studies a further generalization of such a function. A necessary and sufficient condition is obtained for the convexity of a generalized function. Additional sufficient conditions that can be easily checked are derived for the purpose of identifying some classes of functions which guarantee the convexity of the generalized functions. We show that some new classes of convex functions with certain regularity (such as S*-regularity) can be used as building blocks to construct such generalized functions.

It is well known that the so-called first-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. However, the best known iteration complexity of this type of method is $O(n \log\frac{(x^0)^Ts^0}{\varepsilon})$. It is of interest to investigate whether the complexity of first-order predictor-corrector type methods can be further improved. In this paper, based on a specific self-regular proximity function, we define a new large neighborhood of the central path. In particular, we show that the new neighborhood matches the standard large neighborhood that is defined by the infinity norm and widely used in the IPM literature. A new first-order predictor-corrector method for LO that uses a search direction induced by self-regularity in corrector steps is proposed. We prove that our predictor-corrector algorithm, working in a large neighborhood, has an $O(\sqrt{n}\log n \log\frac{(x^0)^Ts^0}{\varepsilon})$ iteration bound. Local superlinear convergence of the algorithm is also established.

We study several properties of a homotopy solution path associated with continuous nonlinear quasi-monotone complementarity problems. We use Poincare-Bohn's homotopy invariance theorem of degree to derive an alternative theorem. Based on this result, a sufficient condition is established to assure the existence and boundedness of this homotopy solution path. Our results provide a theoretical basis to develop a new computational method for quasi-monotone complementarity problems.

Based on the concept of the regularized central path, a new non--interior-point path-following algorithm is proposed for solving the P0 linear complementarity problem (P0 LCP). The condition ensuring the global convergence of the algorithm for P0 LCPs is weaker than most conditions previously used in the literature. This condition can be satisfied even when the strict feasibility condition, which has often been assumed in most existing non--interior-point algorithms, fails to hold. When the algorithm is applied to P* and monotone LCPs, the global convergence of this method requires no assumption other than the solvability of the problem. The local superlinear convergence of the algorithm can be achieved under a nondegeneracy assumption. The effectiveness of the algorithm is demonstrated by our numerical experiments.

A linear program has a unique least 2-norm solution, provided that the linear program has a solution. To locate this solution, most of the existing methods were devised to solve certain equivalent perturbed quadratic programs or unconstrained minimization problems. We provide in this paper a new theory which is different from these traditional methods and is an effective numerical method for seeking the least 2-norm solution of a linear program. The essence of this method is a (interior-point-like) path-following algorithm that traces a newly introduced regularized central path that is fairly different from the central path used in interior-point methods. One distinguishing feature of our method is that it imposes no assumption on the problem. The iterates generated by this algorithm converge to the least 2-norm solution whenever the linear program is solvable; otherwise, the iterates converge to a point which gives a minimal KKT residual when the linear program is unsolvable.

Let K be a closed convex subset in Rn, and let f; g and h be three functions from Rn into itself. We consider the following nonlinear projection equation (NPE): h(x) = :K (g(x)− f(x)); x ∈ R; (1) where :K (·) is the orthogonal projection operator onto the set K . This equation provides a uni

Most known continuation methods for P0 complementarity problems require some restrictive assumptions, such as the strictly feasible condition and the properness condition, to guarantee the existence and the boundedness of certain homotopy continuation trajectory. To relax such restrictions, we propose a new homotopy formulation for the complementarity problem based on which a new homotopy continuation trajectory is generated. For P0 complementarity problems, the most promising feature of this trajectory is the assurance of the existence and the boundedness of the trajectory under a condition that is strictly weaker than the standard ones used widely in the literature of continuation methods. Particularly, the often-assumed strictly feasible condition is not required here. When applied to P* complementarity problems, the boundedness of the proposed trajectory turns out to be equivalent to the solvability of the problem, and the entire trajectory converges to the (unique) least element solution provided that it exists. Moreover, for monotone complementarity problems, the whole trajectory always converges to a least 2-norm solution provided that the solution set of the problem is nonempty. The results presented in this paper can serve as a theoretical basis for constructing a new path-following algorithm for solving complementarity problems, even for the situations where the solution set is unbounded.

For P0-complementarity problems, most existing non--interior-point path-following methods require the existence of a strictly feasible point. (For a P*-complementarity problem, the existence of a strictly feasible point is equivalent to the nonemptyness and the boundedness of the solution set.) In this paper, we propose a new homotopy formulation for complementarity problems by which a new non--interior-point continuation trajectory is generated. The existence and the boundedness of this non--interior-point trajectory for P0-complementarity problems are proved under a very mild condition that is weaker than most conditions used in the literature. One prominent feature of this condition is that it may hold even when the often-assumed strict feasibility condition fails to hold. In particular, for a P*-problem it turns out that the new non--interior-point trajectory exists and is bounded if and only if the problem has a solution. We also study the convergence of this trajectory and characterize its limiting point as the parameter approaches zero.

We prove sufficient conditions for the monotonicity and the strong monotonicity of fixed point and normal maps associated with variational inequality problems over a general closed convex set. Sufficient conditions for the strong monotonicity of their perturbed versions are also shown. These results include some well known in the literature as particular instances. Inspired by these results, we propose a modified Solodov and Svaiter iterative algorithm for the variational inequality problem whose fixed point map or normal map is monotone.

Strict feasibility plays an important role in the development of the theoryand algorithms of complementarity problems. In this paper, we establishsufficient conditions to ensure strict feasibility of a nonlinearcomplementarity problem. Our analysis method, based on a newly introducedconcept of μ-exceptional sequence, can be viewed as a unified approachfor proving the existence of a strictly feasible point. Some equivalentconditions of strict feasibility are also developed for certaincomplementarity problems. In particular, we show that aP*-complementarity problem is strictly feasible if and only ifits solution set is nonempty and bounded.

Quasi-P*-maps and P(τ, α, β)-maps defined in this paper are two large classes of nonlinear mappings which are broad enough to include P*-maps as special cases. It is of interest that the class of quasi-P*-maps also encompasses quasimonotone maps (in particular, pseudomonotone maps) as special cases. Under a strict feasibility condition, it is shown that the nonlinear complementarity problem has a solution if the function is a nonlinear quasi-P*-map or P(τ, α, β)-map. This result generalizes a classical Karamardian existence theorem and a recent result concerning quasimonotone maps established by Hadjisawas and Schaible, but restricted to complementarity problems. A new existence result under an exceptional regularity condition is also established. Our method is based on the concept of exceptional family of elements for a continuous function, which is a powerful tool for investigating the solvability of complementarity problems.

In this paper, an alternative theorem, and hence a sufficient solution condition, is established for generalized variational inequality problems. The concept of exceptional family for generalized variational inequality is introduced. This concept is general enough to include as special cases the notions of exceptional family of elements and the D-orientation sequence for continuous functions. Particularly, we apply the alternative theorem for investigating the solvability of the nonlinear complementarity problems with so-called quasi-P^M"*-maps, which are broad enough to encompass the quasi-monotone maps and P"*-maps as the special cases. An existence theorem for this class of complementarity problems is established, which significantly generalizes several previous existence results in the literature.

Using the homotopy invariance property of the degree and a newly introduced concept of the interior-point-$\varepsilon$-exceptional family for continuous functions, we prove an alternative theorem concerning the existence of a certain interior-point of a continuous complementarity problem. Based on this result, we develop several sufficient conditions to assure some desirable properties (nonemptyness, boundedness, and upper-semicontinuity) of a multivalued mapping associated with continuous (nonmonotone) complementarity problems corresponding to semimonotone, P$(\tau, \alpha, \beta)$-, quasi-P*-, and exceptionally regular maps. The results proved in this paper generalize well-known results on the existence of central paths in continuous P0 complementarity problems.

We introduce the new concept of d-orientation sequence for continuous functions. It is shown that if there does not exist a d-orientation sequence for a continuous function, then the corresponding complementarity problem (CP) has a solution. We believe that such a result characterizes an intrinsic property of CPs. As the concept of ''exceptional family of elements'', the notion of ''d-orientation sequence of a function'' is also a powerful tool for investigating the existence theorems of CPs. We use this new tool to establish, among other things, a new existence result for a class of P"*-mapping CPs.