Like the matrix-valued functions used in solutions methods for semidefinite programs (SDPs) and semidefinite complementarity problems (SDCPs), the vector-valued functions associated with second-order cones are defined analogously and also used in solutions methods for second-order-cone programs (SOCPs) and second-order-cone complementarity problems (SOCCPs). In this article, we study further about these vector-valued functions associated with second-order cones (SOCs). In particular, we define the so-called SOC-convex and SOC-monotone functions for any given function . We discuss the SOC-convexity and SOC-monotonicity for some simple functions, e.g., <i>f</i>(<i>t</i>) = <i>t</i> ² <i>t</i> ³ 1/<i>t</i> <i>t</i> ^1/2, |<i>t</i>|, and [<i>t</i>]₊. Some characterizations of SOC-convex and SOC-monotone functions are studied, and some conjectures about the relationship between SOC-convex and SOC-monotone functions are proposed.

The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend the ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of more than two separable convex functions. However, the convergence of this extension has been missing for a long time—neither an affirmative convergence proof nor an example showing its divergence is known in the literature. In this paper we give a negative answer to this long-standing open question: The direct extension of ADMM is not necessarily convergent. We present a sufficient condition to ensure the convergence of the direct extension of ADMM, and give an example to show its divergence.

This paper discusses how to solve filtering problem for a class of continuous nonlinear time-varying systems via Duncan-Mortensen-Zakai (DMZ) equation. In this paper, the original DMZ equation is changed into Kolmogorov forward equation (KFE) by exponential transformations in each time interval, and then under some assumptions, the KFE can be transformed into time-varying Schr\"odinger equation which can be solved explicitly. The novelty of this paper lies in how to transform the KFE into Schr\"odinger equation. As a direct application, the results of \cite{yau 2004} are extended for time-varying Yau systems.

No abstract uploaded!

No abstract uploaded!

Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we call delay, is the number of times it has been updated since its creation. Almost all recent works prove convergence under the assumption of a finite maximum delay and set their stepsize parameters accordingly. However, the maximum delay is practically unknown. This paper presents convergence analysis of an async-parallel method from a probabilistic viewpoint, and it allows for large unbounded delays. An explicit formula of stepsize that guarantees convergence is given depending on delays’ statistics. With p+1 identical processors, we empirically measured that delays closely follow the Poisson distribution with parameter p, matching our theoretical model, and thus, the stepsize can be set accordingly. Simulations on both convex and nonconvex optimization problems demonstrate the validness of our analysis and also show that the existing maximum-delay-induced stepsize is too conservative, often slows down the convergence of the algorithm.

The multiple-input multiple-output (MIMO) detection problem, a fundamental problem in modern digital communications, is to detect a vector of transmitted symbols from the noisy outputs of a fading MIMO channel. The maximum likelihood detector can be formulated as a complex least-squares problem with discrete variables, which is NP-hard in general. Various semidefinite relaxation (SDR) methods have been proposed in the literature to solve the problem due to their polynomial-time worst-case complexity and good detection error rate performance. In this paper, we consider two popular classes of SDR-based detectors and study the conditions under which the SDRs are tight and the relationship between different SDR models. For the enhanced complex and real SDRs proposed recently by Lu et al., we refine their analysis and derive the necessary and sufficient condition for the complex SDR to be tight, as well as a necessary condition for the real SDR to be tight. In contrast, we also show that another SDR proposed by Mobasher et al. is not tight with high probability under mild conditions. Moreover, we establish a general theorem that shows the equivalence between two subsets of positive semidefinite matrices in different dimensions by exploiting a special "separable" structure in the constraints. Our theorem recovers two existing equivalence results of SDRs defined in different settings and has the potential to find other applications due to its generality.

We investigate some properties related to the generalized Newton method for the Fischer-Burmeister (FB) function over second-order cones, which allows us to reformulate the second-order cone complementarity problem (SOCCP) as a semismooth system of equations. Specifically, we characterize the B-subdifferential of the FB function at a general point and study the condition for every element of the B-subdifferential at a solution being nonsingular. In addition, for the induced FB merit function, we establish its coerciveness and provide a weaker condition than Chen and Tseng (Math. Program. 104:293327, 2005) for each stationary point to be a solution, under suitable Cartesian <i>P</i>-properties of the involved mapping. By this, a damped Gauss-Newton method is proposed, and the global and superlinear convergence results are obtained. Numerical results are reported for the second-order cone programs

We study inhomogeneous random graphs in the subcritical case. Among other results, we derive an exact formula for the size of the largest connected component scaled by log$n$, with$n$being the size of the graph. This generalizes a result for the “rank-1 case”. We also investigate branching processes associated with these graphs. In particular, we discover that the same well-known equation for the survival probability, whose positive solution determines the asymptotics of the size of the largest component in the supercritical case, also plays a crucial role in the subcritical case. However, now it is the$negative$solutions that come into play. We disclose their relationship to the distribution of the progeny of the branching process.

No abstract uploaded!

Yuan’s theorem of the alternative is an important theoretical tool in optimization, which provides a checkable certificate for the infeasibility of a strict inequality system involving two homogeneous quadratic functions. In this paper, we provide a tractable extension of Yuan’s theorem of the alternative to the symmetric tensor setting. As an application, we establish that the optimal value of a class of nonconvex polynomial optimization problems with suitable sign structure (or more explicitly, with essentially nonpositive coefficients) can be computed by a related convex conic programming problem, and the optimal solution of these nonconvex polynomial optimization problems can be recovered from the corresponding solution of the convex conic programming problem. Moreover, we obtain that this class of nonconvex polynomial optimization problems enjoy exact sum-of-squares relaxation, and so, can be solved via a single semidefinite programming problem.

In this ar ti cle, the authors de vel oped an al ter na tive meth od ol ogy to cal cu late theoption- adjusted spread for the mortgage- backed se cu ri ties us ing par tial dif fer ential equa tion tech nique. The nu meri cal im ple men ta tion is dis cussed in de tail, includ ing the con ver gence and er ror analy sis. This ap proach pro vides us a fast andac cu rate way to pric ing MBS.

No abstract uploaded!

This paper is devoted to studying an augmented Lagrangian method for solving a class of manifold optimization problems, which have nonsmooth objective functions and non-negative constraints. Under the constant positive linear dependence condition on manifolds, we show that the proposed method converges to a stationary point of the nonsmooth manifold optimization problem. Moreover, we propose a globalized semismooth Newton method to solve the augmented Lagrangian subproblem on manifolds efficiently. The local superlinear convergence of the manifold semismooth Newton method is also established under some suitable conditions. We also prove that the semismoothness on submanifolds can be inherited from that in the ambient manifold. Finally, numerical experiments on compressed modes and (constrained) sparse principal component analysis illustrate the advantages of the proposed method.

No abstract uploaded!

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

It is well known that the nonlinear filtering problem has important applications in both military and civil industries. The central problem of nonlinear filtering is to solve the Duncan-Mortensen-Zakai (DMZ) equation in real time and in a memoryless manner. In this paper, we shall extend the algorithm developed previously by S.-T. Yau and the second author to the most general setting of nonlinear filterings, where the explicit time-dependence is in the drift term, observation term, and the variance of the noises could be a matrix of functions of both time and the states. To preserve the off-line virture of the algorithm, necessary modifications are illustrated clearly. Moreover, it is shown rigorously that the approximated solution obtained by the algorithm converges to the real solution in the $L^1$ sense. And the precise error has been estimated. Finally, the numerical simulation support the feasibility and efficiency of our algorithm.

In Nash bargaining problem, due to fairness concerns of players, instead of maximizing the sum of utilities of all players, an implementable solution should satisfy some axioms or characterizations. Such a solution can result in the so-called price of fairness, because of the reduction in the sum of utilities of all players. An important issue is to quantify the system efficiency loss under axiomatic solutions through the price of fairness. Based on Perles–Maschler solution of two-player Nash bargaining problem, this paper deals with the extended Perles–Maschler solution of multi-player Nash bargaining problem.We give lower bounds of threemeasures of the system efficiency for this solution, and show that the lower bounds are asymptotically tight.

Many iterative methods in optimization are fixed-point iterations with averaged operators. As such methods converge at an O(1/k) rate with the constant determined by the averagedness coefficient, establishing small averagedness coefficients for operators is of broad interest. In this paper, we show that the averagedness coefficients of the composition of averaged operators by Ogura and Yamada (Numer Func Anal Opt 32(1–2):113–137, 2002) and the threeoperator splitting by Davis and Yin (Set Valued Var Anal 25(4):829–858, 2017) are tight. The analysis relies on the scaled relative graph, a geometric tool recently proposed by Ryu, Hannah, and Yin (arXiv:1902.09788, 2019).

We observe that Sturm’s error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of O(k^{-1/(2^{d+1}-2)}), where d is the singularity degree of the problem—the minimal number of facial reduction iterations needed to induce Slater’s condition. Consequently, for almost all such problems (in the sense of Lebesgue measure), alternating projections converge at a worst-case rate of O(1/k^{0.5}).

Recently Tseng (Math Program 83:159185, 1998) extended a class of merit functions, proposed by Luo and Tseng (<i>A new class of merit functions for the nonlinear complementarity problem</i>, in Complementarity and Variational Problems: State of the Art, pp. 204225, 1997), for the nonlinear complementarity problem (NCP) to the semidefinite complementarity problem (SDCP) and showed several related properties. In this paper, we extend this class of merit functions to the second-order cone complementarity problem (SOCCP) and show analogous properties as in NCP and SDCP cases. In addition, we study another class of merit functions which are based on a slight modification of the aforementioned class of merit functions. Both classes of merit functions provide an error bound for the SOCCP and have bounded level sets.

No abstract uploaded!

It is well known that the second-order cone and the circular cone have many analogous properties. In particular, there exists an important distance inequality associated with the second-order cone and the circular cone. The inequality indicates that the distances of arbitrary points to the second-order cone and the circular cone are equivalent, which is crucial in analyzing the tangent cone and normal cone for the circular cone. In this paper, we provide an alternative approach to achieve the aforementioned inequality. Although the proof is a bit longer than the existing one, the new approach offers a way to clarify when the equality holds. Such a clarification is helpful for further study of the relationship between the second-order cone programming problems and the circular cone programming problems.

First-order methods have been popularly used for solving large-scale problems. However, many existing works only consider unconstrained problems or those with simple constraint. In this paper, we develop two first-order methods for constrained convex programs, for which the constraint set is represented by affine equations and smooth nonlinear inequalities. Both methods are based on the classic augmented Lagrangian function. They update the multipliers in the same way as the augmented Lagrangian method (ALM) but employ different primal variable updates. The first method, at each iteration, performs a single proximal gradient step to the primal variable, and the second method is a block update version of the first one.

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