-
作者：Khanh, Pham Duy; Mordukhovich, Boris S.; Phat, Vo Thanh
作者单位：Wayne State University; University of North Dakota Grand Forks
摘要：This paper proposes and develops new Newton-type methods to solve structured nonconvex and nonsmooth optimization problems with justifying their fast local and global convergence by means of advanced tools of variational analysis and generalized differentiation. The objective functions belong to a broad class of prox-regular functions with specification to constrained optimization of nonconvex structured sums. We also develop a novel line search method, which is an extension of the proximal gr...
-
作者：Fukuda, Ellen H.; Iwata, Satoru; Nakagawa, Itsuki
作者单位：Kyoto University; University of Tokyo; Hokkaido University
摘要：In this paper, we deal with two ingredients that, as far as we know, have not been combined until now: multiobjective optimization and discrete convex analysis. First, we show that the entire Pareto optimal value set can be obtained in polynomial time for biobjective optimization problems with discrete convex functions, in particular, involving an M-#-convex function and a linear function with binary coefficients. We also observe that a more efficient algorithm can be obtained in the special c...
-
作者：Luo, Yuetian; Garcia Trillos, Nicolas
作者单位：Rutgers University System; Rutgers University New Brunswick; University of Wisconsin System; University of Wisconsin Madison
摘要：In this paper we study the landscape of a general matrix optimization problem with a fixed-rank positive semidefinite (PSD) constraint. We perform the Burer-Monteiro factorization, i.e., factorize a PSD matrix X as YY inverted perpendicular , and consider a particular Riemannian quotient geometry in a search space that has a total space equipped with the Euclidean metric. When the original objective f satisfies standard restricted strong convexity and smoothness properties, we characterize the...
-
作者：He, Kerry; Saunderson, James; Fawzi, Hamza
作者单位：Monash University; University of Cambridge
摘要：Barrier methods play a central role in the theory and practice of convex optimization. One of the most general and successful analyses of barrier methods for convex optimization, due to Nesterov and Nemirovskii, relies on the notion of self-concordance. While an extremely powerful concept, proving self-concordance of barrier functions can be very difficult. In this paper we give a simple way to verify that the natural logarithmic barrier of a convex nonlinear constraint is self-concordant via ...
-
作者：Lou, Mengqi; Verchand, Kabir Aladin; Pananjady, Ashwin
作者单位：University System of Georgia; Georgia Institute of Technology; University of Southern California; University System of Georgia; Georgia Institute of Technology
摘要：Motivated by the desire to understand stochastic algorithms for nonconvex optimization that are robust to their hyperparameter choices, we analyze a mini-batched prox-linear iterative algorithm for the canonical problem of recovering an unknown rank-1 matrix from rank-1 Gaussian measurements corrupted by noise. We derive a deterministic recursion that predicts the error of this method and show, using a non-asymptotic framework, that this prediction is accurate for any batch-size and a large ra...
-
作者：Dubois-Taine, Benjamin; d'Aspremont, Alexandre
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS)
摘要：We consider separable nonconvex optimization problems under affine constraints. For these problems, the Shapley-Folkman theorem provides an upper bound on the duality gap as a function of the nonconvexity of the objective functions, but does not provide a systematic way to construct primal solutions satisfying that bound. In this work, we develop a two-stage approach to do so. The first stage approximates the optimal dual value with a large set of primal feasible solutions. In the second stage...
-
作者：Khanh, Pham Duy; Mordukhovich, Boris S.; Tran, Dat Ba
作者单位：Wayne State University
摘要：This paper addresses the study of nonconvex derivative-free optimization problems, where only information of either smooth objective functions or their noisy approximations is available. General derivative-free methods are proposed for minimizing differentiable (not necessarily convex) functions with globally Lipschitz continuous gradients, where the accuracy of approximate gradients is interacting with stepsizes and exact gradient values. Analysis in the noiseless case guarantees convergence ...
-
作者：Csendes, Tibor; Toth, Boglarka G.; Locatelli, Marco
作者单位：Szeged University; University of Parma
-
作者：Li, Jiajin; Zhu, Linglingzhi; So, Anthony Man-Cho
作者单位：University of British Columbia; University System of Georgia; Georgia Institute of Technology; Chinese University of Hong Kong
摘要：Nonconvex-nonconcave minimax optimization has gained widespread interest over the last decade. However, most existing works focus on variants of gradient descent-ascent (GDA) algorithms, which are only applicable to smooth nonconvex-concave settings. To address this limitation, we propose a novel algorithm named smoothed proximal linear descent-ascent (smoothed PLDA), which can effectively handle a broad range of structured nonsmooth nonconvex-nonconcave minimax problems. Specifically, we cons...
-
作者：Chen, Bo; Liu, Jia
作者单位：Xi'an Jiaotong University
摘要：We develop a preference elicitation method for a Von Neumann-Morgenstern (VNM)-type decision-maker from pairwise comparison data in the presence of response errors. We apply the maximum likelihood estimation (MLE) method to jointly elicit the non-parametric systematic VNM utility function and the scale parameter of the response error, assuming a Gumbel distribution. We incorporate structural preference information known in advance about the decision-maker's risk attitude through linear constra...
