No abstract uploaded!

No abstract uploaded!

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

In this paper, we study the rate of convergence of the cyclic projection algorithm applied to finitely many basic semialgebraic convex sets. We establish an explicit convergence rate estimate which relies on the maximum degree of the polynomials that generate the basic semialgebraic convex sets and the dimension of the underlying space. We achieve our results by exploiting the algebraic structure of the basic semialgebraic convex sets.

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.

The free boundary value problem in obstacle problem for von Krmn equations is studied. By using the method of complementarity analysis, Rockafellar's theory of duality is generalized to the nonlinear variational problems and a complementarity theory of obstacle problem for von Krmn plates is established. We prove that the uniqueness and existence of solution directly depend on a complementary gap function. Moreover, a generalized dual extreme principle is established. We prove that the nonlinear primal variational inequality problem is eventually equivalent to a semi-quadratic dual optimization problem defined on a statically admissible space. This equivalence can be used to develop an effective numerical method for solving nonlinear free boundary value problems.

No abstract uploaded!

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.

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.

No abstract uploaded!

No abstract uploaded!

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).

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.

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!

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}).

Abstract Recently, J.-S. Chen and P. Tseng extended two merit functions for the nonlinear complementarity problem (NCP) and the semidefinite complementarity problem (SDCP) to the second-order cone commplementarity problem (SOCCP) and showed several favorable properties. In this paper, we extend a merit function for the NCP studied by Yamada, Yamashita, and Fukushima to the SOCCP and show that the SOCCP is equivalent to an unconstrained smooth minimization via this new merit function. Furthermore, we study conditions under which the new merit function provides a global error bound which plays an important role in analyzing the convergence rate of iterative methods for solving the SOCCP; and conditions under which the new merit function has bounded level sets which ensures that the sequence generated by a descent method has at least one accumulation point.

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 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.

The trust-region problem,which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.

. Motivated by block partitioned problems arising from group sparsity representation and generalized noncooperative potential games, this paper presents a basic decomposition method for a broad class of multiblock nonsmooth optimization problems subject to coupled linear constraints on the variables that may additionally be individually constrained. The objective of such an optimization problem is given by the sum of two nonseparable functions minus a sum of separable, pointwise maxima of finitely many convex differentiable functions. One of the former two nonseparable functions is of the class LC1 , i.e., differentiable with a Lipschitz gradient, while the other summand is multiconvex. The subtraction of the separable, pointwise maxima of convex functions induces a partial difference-of-convex (DC) structure in the overall objective; yet with all three terms together, the objective is nonsmooth and non-DC, but is blockwise directionally differentiable. By taking advantage of the (negative) pointwise maximum structure in the objective, the developed algorithm and its convergence result are aimed at the computation of a blockwise directional stationary solution, which arguably is the sharpest kind of stationary solutions for this class of nonsmooth problems. This aim is accomplished by combining the alternating direction method of multipliers (ADMM) with a semilinearized Gauss–Seidel scheme, resulting in a decomposition of the overall problem into subproblems each involving the individual blocks. To arrive at a stationary solution of the desired kind, our algorithm solves multiple convex subprograms at each iteration, one per convex function in each pointwise maximum. In order to lessen the potential computational burden in each iteration, a probabilistic version of the algorithm is presented and its almost sure convergence is established.

No abstract uploaded!

No abstract uploaded!

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.