2026

最新文章

• Quantum computing inspired iterative refinement for semidefinite optimization AI翻译
  作者：Mohammadisiahroudi, Mohammadhossein; Augustino, Brandon; Sampourmahani, Pouya; Terlaky, Tamas
  作者单位：Lehigh University
  摘要：Iterative Refinement (IR) is a classical computing technique for obtaining highly precise solutions to linear systems of equations, as well as linear optimization problems. In this paper, motivated by the limited precision of quantum solvers, we develop the first IR scheme for solving semidefinite optimization (SDO) problems and explore two major impacts of the proposed IR scheme. First, we prove that the proposed IR scheme exhibits quadratic convergence of the optimality gap without any assum...
• Coderivative-Based Newton Methods in Structured Nonconvex and Nonsmooth Optimization AI翻译
  作者：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...
• Biobjective optimization with M-convex functions AI翻译
  作者：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...
• Nonconvex matrix factorization is geodesically convex: global landscape analysis for fixed-rank matrix optimization from a Riemannian perspective AI翻译
  作者：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...
• Operator convexity along lines, self-concordance, and sandwiched Rényi entropies AI翻译
  作者：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 ...
• Frank-Wolfe meets Shapley-Folkman: a systematic approach for solving nonconvex separable problems with linear constraints AI翻译
  作者：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...
• Globally convergent derivative-free methods in nonconvex optimization with and without noise AI翻译
  作者：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 ...
• Eliciting Von Neumann-Morgenstern utility from discrete choices with response error AI翻译
  作者：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...
• A Reliability Theory of Compromise Decisions for Large-Scale Stochastic Programs AI翻译
  作者：Diao, Shuotao; Sen, Suvrajeet
  作者单位：Great Bay University; University of Southern California; University of Arizona; Birla Institute of Technology & Science Pilani (BITS Pilani)
  摘要：Stochastic programming models can lead to very large-scale optimization problems for which it may be impossible to enumerate all possible scenarios. In such cases, one adopts a sampling-based solution methodology in which case the reliability of the resulting decisions may be suspect. For such instances, it is advisable to adopt methodologies that promote variance reduction. One such approach goes under a framework known as compromise decision, which requires multiple replications of the solut...
• Efficient branching rules for optimizing range and order-based objective functions AI翻译
  作者：van Rossum, Bart; Chen, Rui; Lodi, Andrea
  作者单位：Eindhoven University of Technology; The Chinese University of Hong Kong, Shenzhen
  摘要：We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch and price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and can be used on top ...