Search

In this paper, we consider optimization problems over closed embedded submanifolds of Rn , which are defined by the constraints c(x) = 0. We propose a class of constraint-dissolving approaches for these Riemannian optimization problems. In these proposed approaches, solving a Riemannian optimization problem is transferred into the unconstrained minimization of a constraint-dissolving function (CDF). Different from existing exact penalty functions, the exact gradient and Hessian of CDF are easy to compute. We study the theoretical properties of CDF and prove that the original problem and CDF have the same first-order and second-order stationary points, local minimizers, and Łojasiewicz exponents in a neighborhood of the feasible region. Remarkably, the convergence properties of our proposed constraint-dissolving approaches can be directly inherited from the existing rich results in unconstrained optimization. Therefore, the proposed constraint-dissolving approaches build up short cuts from unconstrained optimization to Riemannian optimization. Several illustrative examples further demonstrate the potential of our proposed constraint-dissolving approaches. Funding: The research of N. Xiao and K.-C. Toh is supported by the Ministry of Education of Singapore Academic Research Fund Tier 3 [Grant MOE-2019-T3-1-010]. The research of X. Liu is supported in part by the National Natural Science Foundation of China [Grants 12125108, 11971466, 12288201, 12021001, and 11991021]; the National Key R&D Program of China [Grants 2020YFA0711900 and 2020YFA0711904]; and the Key Research Program of Frontier Sciences, Chinese Academy of Sciences [Grant ZDBS-LY-7022]. [ABSTRACT FROM AUTHOR]

In this paper, we consider a semidefinite programming (SDP) relaxation of the quadratic knapsack problem. After applying low-rank factorization, we get a nonconvex problem, whose feasible region is an algebraic variety with certain good geometric properties, which we analyze. We derive a rank condition under which these two formulations are equivalent. This rank condition is much weaker than the classical rank condition if the coefficient matrix has certain special structures. We also prove that, under an appropriate rank condition, the nonconvex problem has no spurious local minima without assuming linearly independent constraint qualification. We design a feasible method that can escape from nonoptimal nonregular points. Numerical experiments are conducted to verify the high efficiency and robustness of our algorithm as compared with other solvers. In particular, our algorithm is able to solve a one-million-dimensional sparse SDP problem accurately in about 20 minutes on a modest computer. Funding: The research of K.-C. Toh is supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 3 grant call [Grant MOE-2019-T3-1-010]. [ABSTRACT FROM AUTHOR]

We consider the problem of learning a graph under the Laplacian constraint with a non-convex penalty: minimax concave penalty (MCP). For solving the MCP penalized graphical model, we design an inexact proximal difference-of-convex algorithm (DCA) and prove its convergence to critical points. We note that each subproblem of the proximal DCA enjoys the nice property that the objective function in its dual problem is continuously differentiable with a semismooth gradient. Therefore, we apply an efficient semismooth Newton method to subproblems of the proximal DCA. Numerical experiments on various synthetic and real data sets demonstrate the effectiveness of the non-convex penalty MCP in promoting sparsity. Compared with the existing state-of-the-art method, our method is demonstrated to be more efficient and reliable for learning graph Laplacian with MCP. [ABSTRACT FROM AUTHOR]

This paper thoroughly investigates the bearing capacity of strip footings on sand under combined loading by using a lower-bound limit analysis in conjunction with finite elements and second-order cone programming (SOCP). Two analyses were performed: one using a constant friction angle and the other using a variable friction angle. The analyses with a constant friction angle were used to calibrate the existing results, including the classical solutions commonly used in foundation design practice and other numerical or experimental solutions. The analyses with a variable friction angle allow us to investigate the effect of footing width B on the bearing capacity of strip footings. An iteration computational procedure is employed to account for the dependency of the friction angle on the stress level. According to the numerical results, it is found that the bearing capacity factor [N.sub.[gamma]] for eccentrically or obliquely loaded strip footings linearly decreases with the increase of B on a log-log scale, where the range 0.3-5 m of footing width was considered in this paper. In addition, it is found that the footing width has a negligible effect on the shape and size of the normalized failure envelopes. Key words: bearing capacity, failure envelope, lower-bound limit analysis. Cet article presente une etude exhaustive de la capacite portante de semelles filantes sur du sable soumises a des charges combinees. L'etude est realisee avec l'analyse limite fi frontiere inferieure combinee avec les elements finis et la programmation en cone de deuxieme ordre (PCDO). Deux analyses ont ete realisees : une avec un angle de friction constant, et l'autre avec un angle de friction variable. Les analyses avec l'angle de friction constant ont servi a calibrer les resultats existants, dont les solutions classiques generalement utilisees dans la conception de fondations, et d'autres solutions numeriques ou experimentales. Les analyses avec l'angle de friction variable ont permis d'evaluer l'effet de la largeur B de la semelle sur la capacite portante de semelles filantes. Une procedure de calcul par iterations est utilisee pour considerer la dependance de l'angle de friction sur le niveau de contrainte. Selon les resultats numeriques, il a ete demontre que le facteur de capacite portante [N.sub.[gamma]] dans le cas de semelles filantes chargees de facon excentrique ou oblique diminue lineairement avec l'augmentation de B sur une echelle log-log, pour la variation de largeur de semelle consideree dans cet article, soit de 0,3 a 5 m. De plus, il a ete demontre que la largeur de la semelle a un effet negligeable sur la forme et la taille des enveloppes de rupture normalisees. [Traduit par la Redaction] Mots-cles: capacite portante, enveloppe de rupture, analyse limite a frontiere inferieure., Introduction The bearing capacity of strip footings resting on a horizontal and homogeneous sand layer (for which both surcharge and soil cohesion are zero) is usually calculated from the following [...]

The doubly nonnegative (DNN) cone, being the set of all positive semidefinite matrices whose elements are nonnegative, is a popular approximation of the computationally intractable completely positive cone. The major difficulty for implementing a Newton-type method to compute the projection of a given large-scale matrix onto the DNN cone lies in the possible failure of the constraint nondegeneracy, a generalization of the linear independence constraint qualification for nonlinear programming. Such a failure results in the singularity of the Jacobian of the nonsmooth equation representing the Karush–Kuhn–Tucker optimality condition that prevents the semismooth Newton–conjugate gradient method from solving it with a desirable convergence rate. In this paper, we overcome the aforementioned difficulty by solving a sequence of better conditioned nonsmooth equations generated by the augmented Lagrangian method (ALM) instead of solving one aforementioned singular equation. By leveraging the metric subregularity of the normal cone associated with the positive semidefinite cone, we derive sufficient conditions to ensure the dual quadratic growth condition of the underlying problem, which further leads to the asymptotically superlinear convergence of the proposed ALM. Numerical results on difficult randomly generated instances and from the semidefinite programming library are presented to demonstrate the efficiency of the algorithm for computing the DNN projection to a very high accuracy. [ABSTRACT FROM AUTHOR]