1. Motivation and basic concepts In this note, we consider two signomial functions whose convexity play important roles in some recent papers [4, 6, 7, 8, 9] dealing with geometric programming problems. However, the verifications therein contain some certain flaws and those incorrect arguments are repeatedly appeared and cited. From point of scientific researchs view, we hereby provide correct proofs for them.
In this article, we consider the Lorentz cone complementarity problems in infinite-dimensional real Hilbert space. We establish several results that are standard and important when dealing with complementarity problems. These include proving the same growth of the FishcherBurmeister merit function and the natural residual merit function, investigating property of bounded level sets under mild conditions via different merit functions, and providing global error bounds through the proposed merit functions. Such results are helpful for further designing solution methods for the Lorentz cone complementarity problems in Hilbert space.
This paper is devoted to the study of the proximal point algorithm for solving monotone and nonmonotone nonlinear complementarity problems. The proximal point algorithm is to generate a sequence by solving subproblems that are regularizations of the original problem. After given an appropriate criterion for approximate solutions of subproblems by adopting a merit function, the proximal point algorithm is verified to have global and superlinear convergence properties. For the purpose of solving the subproblems efficiently, we introduce a generalized Newton method and show that only one Newton step is eventually needed to obtain a desired approximate solution that approximately satisfies the appropriate criterion under mild conditions. The motivations of this paper are twofold. One is analyzing the proximal point algorithm based on the generalized Fischer-Burmeister function which includes the Fischer-Burmeister function as special case, another one is trying to see if there are relativistic change on numerical performance when we adjust the parameter in the generalized Fischer-Burmeister.
Merit function approach is a popular method to deal with complementarity problems, in which the complementarity problem is recast as an unconstrained minimization via merit function or complementarity function. In this paper, for the complementarity problem associated with <i>p</i>-order cone, which is a type of nonsymmetric cone complementarity problem, we show the readers how to construct merit functions for solving <i>p</i>-order cone complementarity problem. In addition, we study the conditions under which the level sets of the corresponding merit functions are bounded, and we also assert that these merit functions provide an error bound for the <i>p</i>-order cone complementarity problem. These results build up a theoretical basis for the merit method for solving <i>p</i>-order cone complementarity problem.
In this article, we extend two classes of merit functions for the second-order complementarity problem (SOCP) to infinite-dimensional SOCP. These two classes of merit functions include several popular merit functions, which are used in nonlinear complementarity problem, (NCP)/(SDCP) semidefinite complementarity problem, and SOCP, as special cases. We give conditions under which the infinite-dimensional SOCP has a unique solution and show that all these merit functions provide an error bound for infinite-dimensional SOCP and have bounded level sets. These results are very useful for designing solution methods for infinite-dimensional SOCP.
It is well known that second-order cone (SOC) programming can be regarded as a special case of positive semidefinite programming using the arrow matrix. This paper further studies the relationship between SOCs and positive semidefinite matrix cones. In particular, we explore the relationship to expressions regarding distance, projection, tangent cone, normal cone and the KKT system. Understanding these relationships will help us see the connection and difference between the SOC and its PSD reformulation more clearly.
In this paper, we study the existence of local and global saddle points for nonlinear second-order cone programming problems. The existence of local saddle points is developed by using the second-order sufficient conditions, in which a sigma-term is added to reflect the curvature of second-order cone. Furthermore, by dealing with the perturbation of the primal problem, we establish the existence of global saddle points, which can be applicable for the case of multiple optimal solutions. The close relationship between global saddle points and exact penalty representations are discussed as well.
In this paper, we study the properties of the penalized Fischer-Burmeister (FB) second-order cone (SOC) complementarity function. We show that the function possesses similar desirable properties of the FB SOC complementarity function for local convergence; for example, with the function the second-order cone complementarity problem (SOCCP) can be reformulated as a (strongly) semismooth system of equations, and the corresponding nonsmooth Newton method has local quadratic convergence without strict complementarity of solutions. In addition, the penalized FB merit function has bounded level sets under a rather weak condition which can be satisfied by strictly feasible monotone SOCCPs or SOCCPs with the Cartesian <i>R</i> <sub>01</sub>-property, although it is not continuously differentiable. Numerical results are included to illustrate the theoretical considerations.
This paper is devoted to the study of the proximal point algorithm for solving monotone second-order cone complementarity problems. The proximal point algorithm is to generate a sequence by solving subproblems that are regularizations of the original problem. After given an appropriate criterion for approximate solutions of subproblems by adopting a merit function, the proximal point algorithm is verified to have global and superlinear convergence properties. For the purpose of solving the subproblems efficiently, we introduce a generalized Newton method and show that only one Newton step is eventually needed to obtain a desired approximate solution that approximately satisfies the appropriate criterion under mild conditions. Numerical comparisons are also made with the derivative-free descent method used by Pan and Chen (Optimization 59:11731197, 2010), which confirm the theoretical results
In this paper, we consider a type of cone-constrained convex program in finite-dimensional space, and are interested in characterization of the solution set of this convex program with the help of the Lagrange multiplier. We establish necessary conditions for a feasible point being an optimal solution. Moreover, some necessary conditions and sufficient conditions are established which simplifies the corresponding results in Jeyakumar et al. (J Optim Theory Appl 123(1), 83103, 2004). In particular, when the cone reduces to three specific cones, that is, the p -order cone, p cone and circular cone, we show that the obtained results can be achieved by easier ways by exploiting the special structure of those three cones.
It is well known that complementarity functions play an important role in dealing with complementarity problems. In this paper, we propose a few new classes of complementarity functions for nonlinear complementarity problems and second-order cone complementarity problems. The constructions of such new complementarity functions are based on discrete generalization which is a novel idea in contrast to the continuous generalization of FischerBurmeister function. Surprisingly, these new families of complementarity functions possess continuous differentiability even though they are discrete-oriented extensions. This feature enables that some methods like derivative-free algorithm can be employed directly for solving nonlinear complementarity problems and second-order cone complementarity problems. This is a new discovery to the literature and we believe that such new complementarity functions
We make a unified analysis of interior proximal methods of solving convex second-order cone programming problems. These methods use a proximal distance with respect to second-order cones which can be produced with an appropriate closed proper univariate function in three ways. Under some mild conditions, the sequence generated is bounded with each limit point being a solution, and global rates of convergence estimates are obtained in terms of objective values. A class of regularized proximal distances is also constructed which can guarantee the global convergence of the sequence to an optimal solution. These results are illustrated with some examples. In addition, we also study the central paths associated with these distance-like functions, and for the linear SOCP we discuss their relations with the sequence generated by the interior proximal methods. From this, we obtain improved convergence
Given a Hilbert space H, the infinite-dimensional Lorentz/second-order cone K is introduced. For any x H, a spectral decomposition is introduced, and for any function f: R R, we define a corresponding vector-valued function f H (x) on Hilbert space H by applying f to the spectral values of the spectral decomposition of x H with respect to K. We show that this vector-valued function inherits from f the properties of continuity, Lipschitz continuity, differentiability, smoothness, as well as s-semismoothness. These results can be helpful for designing and analyzing solution methods for solving infinite-dimensional second-order cone programs and complementarity problems.
We introduce an entropy-like proximal algorithm for the problem of minimizing a closed proper convex function subject to symmetric cone constraints. The algorithm is based on a distance-like function that is an extension of the Kullback-Leiber relative entropy to the setting of symmetric cones. Like the proximal algorithms for convex programming with nonnegative orthant cone constraints, we show that, under some mild assumptions, the sequence generated by the proposed algorithm is bounded and every accumulation point is a solution of the considered problem. In addition, we also present a dual application of the proposed algorithm to the symmetric cone linear program, leading to a multiplier method which is shown to possess similar properties as the exponential multiplier method (Tseng and Bertsekas in Math. Program. 60:119, 1993) holds.
We propose a primal-dual continuation approach for the capacitated multi-facility Weber problem (CMFWP) based on its nonlinear second-order cone program (SOCP) reformulation. The main idea of the approach is to reformulate the CMFWP as a nonlinear SOCP with a nonconvex objective function, and then introduce a logarithmic barrier term and a quadratic proximal term into the objective to construct a sequence of convexified subproblems. By this, this class of nondifferentiable and nonconvex optimization problems is converted into the solution of a sequence of nonlinear convex SOCPs. In this paper, we employ the semismooth Newton method proposed in Kanzow etal. (SIAM Journal of Optimization 20:297320, 2009) to solve the KKT system of the resulting convex SOCPs. Preliminary numerical results are reported for eighteen test instances, which indicate that the continuation approach is
We provide an affirmative answer to an question that the Fischer-Burmeister complementarity function associated with symmetric cones, named the FB SC complementarity function, is globally Lipschitz continuous and strongly semismooth everywhere for Hn and Qn. This is achieved with the help of embedding Hn and Qn into certain Sm.
We consider an extended second-order cone linear complementarity problem (SOCLCP), including the generalized SOCLCP, the horizontal SOCLCP, the vertical SOCLCP, and the mixed SOCLCP as special cases. In this paper, we present some simple second-order cone constrained and unconstrained reformulation problems, and under mild conditions prove the equivalence between the stationary points of these optimization problems and the solutions of the extended SOCLCP. Particularly, we develop a proximal gradient descent method for solving the second-order cone constrained problems. This method is very simple and at each iteration makes only one Euclidean projection onto second-order cones. We establish global convergence and, under a local Lipschitzian error bound assumption, linear rate of convergence. Numerical comparisons are made with the limited-memory BFGS method for the
For the symmetric cone complementarity problem, we show that each stationary point of the unconstrained minimization reformulation based on the FischerBurmeister merit function is a solution to the problem, provided that the gradient operators of the mappings involved in the problem satisfy column monotonicity or have the Cartesian P 0-property. These results answer the open question proposed in the article that appeared in Journal of Mathematical Analysis and Applications 355 (2009) 195215.
In contrast to the generalized FischerBurmeister function that is a natural extension of the popular FischerBurmeister function NCP-function, the generalized natural residual NCP-function based on discrete extension, recently proposed by Chen, Ko, and Wu, does not possess symmetric graph. In this paper we symmetrize the generalized natural residual NCP-function, and construct not only new NCP-functions and merit functions for the nonlinear complementarity problem, but also provide parallel functions to the generalized FischerBurmeister function.
In this paper, we consider complementarity problem associated with circular cone, which is a type of nonsymmetric cone complementarity problem. The main purpose of this paper is to show the readers how to construct complementarity functions for such nonsymmetric cone complementarity problem, and propose a few merit functions for solving such a complementarity problem. In addition, we study the conditions under which the level sets of the corresponding merit functions are bounded, and we also show that these merit functions provide an error bound for the circular cone complementarity problem. These results ensure that the sequence generated by descent methods has at least one accumulation point, and build up a theoretical basis for designing the merit function method for solving circular cone complementarity problem.
In the solution methods of the symmetric cone complementarity problem (SCCP), the squared norm of a complementarity function serves naturally as a merit function for the problem itself or the equivalent system of equations reformulation. In this paper, we study the growth behavior of two classes of such merit functions, which are induced by the smooth EP complementarity functions and the smooth implicit Lagrangian complementarity function, respectively. We show that, for the linear symmetric cone complementarity problem (SCLCP), both the EP merit functions and the implicit Lagrangian merit function are coercive if the underlying linear transformation has the <i>P</i>-property; for the general SCCP, the EP merit functions are coercive only if the underlying mapping has the uniform Jordan <i>P</i>-property, whereas the coerciveness of the implicit Lagrangian merit function requires an additional condition for the
We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the FischerBurmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function <sub>FB</sub> as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan <i>P</i>-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by Chen and Tseng (<i>An unconstrained smooth minimization reformulation of the second-order cone complementarity problem</i>, Math. Program. 104(2005), pp
It has been an open question whether the family of merit functions $\psi _p\(p> 1) $, the generalized Fischer-Burmeister (FB) merit function, associated to the second-order cone is smooth or not. In this paper we answer it partly, and show that \psi _p is smooth for \psi _p , and we provide the condition for its coerciveness. Numerical results are reported to illustrate the influence of \psi _p on the performance of the merit function method based on \psi _p .
We propose a class of interior proximal-like algorithms for the second-order cone program, which is to minimize a closed proper convex function subject to general second-order cone constraints. The class of methods uses a distance measure generated by a twice continuously differentiable strictly convex function on (0,+\infty), and includes as a special case the entropy-like proximal algorithm [Eggermont, <i>Linear Algebra Appl.</i>, 130 (1990), pp. 2542], which was originally proposed for minimizing a convex function subject to nonnegative constraints. Particularly, we consider an approximate version of these methods, allowing the inexact solution of subproblems. Like the entropy-like proximal algorithm for convex programming with nonnegative constraints, we, under some mild assumptions, establish the global convergence expressed in terms of the objective values for the proposed algorithm, and we show that the
Recently this author studied several merit functions systematically for the second-order cone complementarity problem. These merit functions were shown to enjoy some favorable properties, to provide error bounds under the condition of strong monotonicity, and to have bounded level sets under the conditions of monotonicity as well as strict feasibility. In this paper, we weaken the condition of strong monotonicity to the so-called uniform <i>P</i> <sup>*</sup>-property, which is a new concept recently developed for linear and nonlinear transformations on Euclidean Jordan algebra. Moreover, we replace the monotonicity and strict feasibility by the so-called <i>R</i> <sub>01</sub> or <i>R</i> <sub>02</sub>-functions to keep the property of bounded level sets.