检索结果-内蒙古大学图书馆

complexity ANALYSIS OF A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR P*(κ)-WEIGHTED LINEAR COMPLEMENTARITY PROBLEMS

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2025年第1期21卷 731-750页

作者： Chi, Xiaoni Yang, Yuping Chen, Jein-Shan Guilin Univ Elect Technol Sch Math & Comp Sci Guangxi Coll & Univ Key Lab Data Anal & Computat Guilin 541004 Peoples R China Guilin Univ Elect Technol Ctr Appl Math Guangxi GUET Sch Math & Comp Sci Guilin 541004 Peoples R China Natl Taiwan Normal Univ Dept Math Taipei 116059 Taiwan

This paper aims at a predictor-corrector interior-point algorithm for solving weighted linear complementarity problem with P-*(kappa)-matrices, which is a variant of weighted complementarity problem and has wide applications in science, engineering, and economics. We first apply the algebraic equivalent transformation technique, and then use the identity function to determine the new search directions. Under suitable conditions, the feasibility and convergence of the algorithm are established. Moreover, we show that the proposed algorithm has polynomial-time complexity. As far as we know, this is the first predictor-corrector interior-point algorithm for P-*(kappa)-weighted linear complementarity problem based on the above-mentioned search directions. Preliminary numerical results demonstrate that our algorithm performs well and efficiently on the test problems.

关键词： Predictor-corrector interior-point algorithm P-*(kappa)-weighted linear complementarity problem search direction polynomial-time complexity

来源：评论

学校读者我要写书评

暂无评论

The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第5期71卷 3854-3870页

作者： Ergen, Tolga Pilanci, Mert LG AI Res Ann Arbor MI 48105 USA Stanford Univ Elect Engn Dept Stanford CA 94305 USA

Due to the non-convex nature of training Deep Neural Network (DNN) models, their effectiveness relies on the use of non-convex optimization heuristics. Traditional methods for training DNNs often require costly empirical methods to produce successful models and do not have a clear theoretical foundation. In this study, we examine the use of convex optimization theory and sparse recovery models to refine the training process of neural networks and provide a better interpretation of their optimal weights. We focus on training two-layer neural networks with piecewise linear activations and demonstrate that they can be formulated as a finite-dimensional convex program. These programs include a regularization term that promotes sparsity, which constitutes a variant of group Lasso. We first utilize semi-infinite programming theory to prove strong duality for finite width neural networks and then we express these architectures equivalently as high dimensional convex sparse recovery models. Remarkably, the worst-case complexity to solve the convex program is polynomial in the number of samples and number of neurons when the rank of the data matrix is bounded, which is the case in convolutional networks. To extend our method to training data of arbitrary rank, we develop a novel polynomial-time approximation scheme based on zonotope subsampling that comes with a guaranteed approximation ratio. We also show that all the stationary points of the nonconvex training objective can be characterized as the global optimum of a subsampled convex program. Our convex models can be trained using standard convex solvers without resorting to heuristics or extensive hyper-parameter tuning unlike non-convex methods. Due to the convexity, optimizer hyperparameters such as initialization, batch sizes, and step size schedules have no effect on the final model. Through extensive numerical experiments, we show that convex models can outperform traditional non-convex methods and are not sensitive

关键词： Training Biological neural networks Convex functions Vectors Standards Neurons Data models Minimization Data mining Computational modeling Neural networks convex optimization polynomial-time complexity piecewise linear activations stationary points implicit regularization

来源：评论

学校读者我要写书评

暂无评论

A Barrier Lagrangian Dual Method for Multi-stage Stochastic Convex Semidefinite Optimization

引用

VIETNAM JOURNAL OF MATHEMATICS 2024年 1-24页

作者： Gafour, Asma Alzalg, Baha Univ Jordan Dept Math Amman 11942 Jordan Univ Djilali Liabes Dept Math Sidi Bel Abbes 22038 Algeria

In this paper, we present a polynomial-time barrier algorithm for solving multi-stage stochastic convex semidefinite optimization based on the Lagrangian dual method which relaxes the nonanticipativity constraints. We show that the barrier Lagrangian dual functions for our setting form self-concordant families with respect to barrier parameters. We also use the barrier function method to improve the smoothness of the dual objective function so that the Newton search directions can be exploited for usage. We finally implement the proposed algorithm on different test problems to show its effectiveness and efficiency.

关键词： Semidefinite programming Multi-stage stochastic convex programming Lagrangian dual Interior point methods polynomial-time complexity

来源：评论

学校读者我要写书评

暂无评论

An Interior Point Parameterized Central Path Following Algorithm for Linearly Constrained Convex Programming

引用

JOURNAL OF SCIENTIFIC COMPUTING 2022年第3期90卷 95页

作者： Hou, Liangshao Qian, Xun Liao, Li-Zhi Sun, Jie Hong Kong Baptist Univ Dept Math Kowloon Tong Kowloon Hong Kong Peoples R China King Abdullah Univ Sci & Technol Div Comp Elect & Math Sci & Engn Thuwal Saudi Arabia JD Explore Acad Beijing Peoples R China Curtin Univ Fac Sci & Engn Perth WA Australia Natl Univ Singapore Sch Business Singapore Singapore

An interior point algorithm is proposed for linearly constrained convex programming following a parameterized central path, which is a generalization of the central path and requires weaker convergence conditions. The convergence and polynomial-time complexity of the proposed algorithm are proved under the assumption that the Hessian of the objective function is locally Lipschitz continuous. In addition, an initialization strategy is proposed and some numerical results are provided to show the efficiency and attractiveness of the proposed algorithm.

关键词： Interior point method Path following polynomial-time complexity Convex programming

来源：评论

学校读者我要写书评

暂无评论

Computing the multilinear factors of lacunary polynomials without heights

引用

JOURNAL OF SYMBOLIC COMPUTATION 2021年 104卷 183-206页

作者： Chattopadhyay, Arkadev Grenet, Bruno Koiran, Pascal Portier, Natacha Strozecki, Yann Tata Inst Fundamental Res Sch Technol & Comp Sci Mumbai Maharashtra India Univ Montpellier CNRS LIRMM Montpellier France Univ Lyon CNRS EnsL UCBLLIP Lyon 07 France Univ Versailles St Quentin DAVID Lab Versailles France

We present a deterministic algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. Its complexity is polynomial in l(n) where l is the lacunary size of the input polynomial and nits number of variables, that is in particular polynomial in the logarithm of its degree. We also provide a randomized algorithm for the same problem of complexity polynomial in l and n. Over other fields of characteristic zero and finite fields of large characteristic, our algorithms compute the multilinear factors having at least three monomials of multivariate polynomials. Lower bounds are provided to explain the limitations of our algorithm. As a by-product, we also design polynomial-time deterministic polynomial identity tests for families of polynomials which were not known to admit any. Our results are based on so-called Gap Theorem which reduce high-degree factorization to repeated low-degree factorizations. While previous algorithms used Gap Theorems expressed in terms of the heights of the coefficients, our Gap Theorems only depend on the exponents of the polynomials. This makes our algorithms more elementary and general, and faster in most cases. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Multivariate lacunary polynomials polynomial factorization polynomial-time complexity Number fields Finite fields Wronskian determinant

来源：评论

学校读者我要写书评

暂无评论

Computational complexity for Some Problems of Two Terms Unification Based on Concatenation 7

Computational Complexity for Some Problems of Two Terms Unif...

引用

IEEE Seventh International Conference on Intelligent Computing and Information Systems (ICICIS)

作者： Kosovskii, Nikolai K. St Petersburg State Univ Comp Sci Chair SPbSU St Petersburg Russia

ISBN: (纸本)9781509019496

Tools for description of bounds for word variable values are offered. The use of these descriptions provides the conditions of a problem belonging to the class P or to the class NP. NP-completeness of an unification problem is proved. The validity of the proved bounds may make possible to create effective algorithms for unification of word terms, used in such programming language as Refal.

关键词： Equation in words unification polynomial-time complexity NP-complete problem

来源：评论

学校读者我要写书评

暂无评论

Computational complexity for some problems of two terms unification based on concatenation

Computational complexity for some problems of two terms unif...

引用

IEEE International Conference on Intelligent Computing and Information Systems (ICICIS)

作者： Nikolai K. Kosovskii SPbSU Computer Science Chair of St. Petersburg State University St. Petersburg RUSSIA

关键词： Equation in words NP-complete problem polynomial-time complexity unification Nondeterministic polynomial-time hard complexity classes Computer Programming Languages Word Bound

来源：评论

学校读者我要写书评

暂无评论

polynomial-time interior-point algorithm based on a local self-concordant finite barrier function

引用

Journal of Shanghai University(English Edition) 2009年第4期13卷 333-339页

作者：金正静白延琴 College of Sciences Shanghai University College of Sciences Zhejiang Forestry University

The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.

关键词： linear optimization self-concordant function finite barrier interior-point methods polynomial-time complexity

来源：评论

学校读者我要写书评

暂无评论

A High-Order Dikin-Type Algorithm for P＊（k）-LCPs in a Wide Neighborhood of the Central Path

引用

Journal of Mathematical Research and Exposition 2009年第1期29卷 76-84页

作者： GONG Xiao Yu ZHANG Ming Wang College of Science Maoming University Guangdong 525000 China College of Science Three Gorges University Hubei 443002 China

Based on the idea of Dikin-type primal-dual affine scaling method for linear program-ming,we describe a high-order Dikin-type algorithm for P_*(κ)-matrix linear complementarity problem in a wide neighborhood of the central path,and its polynomial-time complexity bound is ***,two numerical experiments are provided to show the effectiveness of the proposed algorithms.

关键词： complementarity problem high-order affine scaling polynomial-time complexity interior-point algorithm P＊（κ）-matrix.

来源：评论

学校读者我要写书评

暂无评论

求解P*（κ）阵线性互补问题的宽邻域Dikin型高阶内点算法（英文）

引用

Journal of Mathematical Research with Applications 2009年第1期 76-84页

作者：龚小玉张名望 College of Science Maoming University College of Science Three Gorges University

Based on the idea of Dikin-type primal-dual affine scaling method for linear program-ming,we describe a high-order Dikin-type algorithm for P（κ）-matrix linear complementarity problem in a wide neighborhood of the central path,and its polynomial-time complexity bound is ***,two numerical experiments are provided to show the effectiveness of the proposed algorithms.

关键词： complementarity problem high-order affine scaling polynomial-time complexity interior-point algorithm P*(κ)-matrix

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：