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

32nd Conference on Learning theory (COLT) part of the ACM Federated Computing Research Conference

作者： Lee, Yin Tat Song, Zhao Zhang, Qiuyi Univ Washington Seattle WA 98195 USA Microsoft Res Redmond Redmond WA 98052 USA UT Austin Austin TX USA Univ Calif Berkeley Berkeley CA USA

Many convex problems in machine learning and computer science share the same form: min(x) Sigma(i) f(i)(A(i)x + b(i)), where f(i) are convex functions on R-ni with constant n(i), A(i) is an element of R-nixd, b(i) is an element of R-ni and Sigma(i) n(i) = n. This problem generalizes linear programming and includes many problems in empirical risk minimization. In this paper, we give an algorithm that runs in time O* ((n(omega) + n(2.5-alpha/2) + n(2+1/6)) log(n/delta)) where omega is the exponent of matrix multiplication, alpha is the dual exponent of matrix multiplication, and delta is the relative accuracy. Note that the runtime has only a log dependence on the condition numbers or other data dependent parameters and these are captured in delta. For the current bound omega similar to 2.38 [Vassilevska Williams'12, Le Gall'14] and alpha similar to 0.31 [Le Gall, Urrutia'18], our runtime O*(n(omega) log(n/delta)) matches the current best for solving a dense least squares regression problem, a special case of the problem we consider. Very recently, [Alman'18] proved that all the current known techniques can not give a better omega below 2.168 which is larger than our 2 + 1/6. Our result generalizes the very recent result of solving linear programs in the current matrix multiplication time [Cohen, Lee, Song'19] to a more broad class of problems. Our algorithm proposes two concepts which are different from [Cohen, Lee, Song'19] : center dot We give a robust deterministic central path method, whereas the previous one is a stochastic central path which updates weights by a random sparse vector. center dot We propose an efficient data-structure to maintain the central path of interior point methods even when the weights update vector is dense.

关键词： linear programming

来源：评论

学校读者我要写书评

暂无评论

An interior-point method-based solver for simulation of aircraft parts riveting

引用

ENGINEERING OPTIMIZATION 2018年第5期50卷 781-796页

作者： Stefanova, Maria Yakunin, Sergey Petukhova, Margarita Lupuleac, Sergey Kokkolaras, Michael Peter Great St Petersburg Polytech Univ Dept Appl Math St Petersburg Russia Charles III Univ Madrid Dept Mat Sci & Engn & Chem Engn Madrid Spain McGill Univ Grp Etud & Rech Anal Decis GERAD Montreal PQ Canada McGill Univ Dept Mech Engn Montreal PQ Canada

The particularities of the aircraft parts riveting process simulation necessitate the solution of a large amount of contact problems. A primal-dual interior-point method-based solver is proposed for solving such problems efficiently. The proposed method features a worst case polynomial complexity bound O(root n ln c(-1)) on the number of iterations, where n is the dimension of the problem and epsilon is a threshold related to desired accuracy. In practice, the convergence is often faster than this worst case bound, which makes the method applicable to large-scale problems. The computational challenge is solving the system of linear equations because the associated matrix is ill conditioned. To that end, the authors introduce a preconditioner and a strategy for determining effective initial guesses based on the physics of the problem. Numerical results are compared with ones obtained using the Goldfarb-Idnani algorithm. The results demonstrate the efficiency of the proposed method.

关键词： interior-point methods primal-dual methods quadratic programming initial guesses preconditioning

来源：评论

学校读者我要写书评

暂无评论

A MULTIGRID APPROACH TO SDP RELAXATIONS OF SPARSE POLYNOMIAL OPTIMIZATION PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第1期28卷 1-29页

作者： Campos, Juan S. Parpas, Panos Imperial Coll London Dept Comp London SW7 2AZ England

We propose a multigrid approach for the global optimization of polynomial optimization problems with sparse support. The problems we consider arise from the discretization of infinite dimensional optimization problems, such as PDE optimization problems, boundary value problems, and some global optimization applications. In many of these applications, the level of discretization can be used to obtain a hierarchy of optimization models that capture the underlying infinite dimensional problem at different degrees of fidelity. This approach, inspired by multigrid methods, has been successfully used for decades to solve large systems of linear equations. However, multi grid methods are difficult to apply to semidefinite programming (SDP) relaxations of polynomial optimization problems. The main difficulty is that the information between grids is lost when the original problem is approximated via an SDP relaxation. Despite the loss of information, we develop a multigrid approach and propose prolongation operators to relate the primal and dual variables of the SDP relaxation between lower and higher levels in the hierarchy of discretizations. We develop sufficient conditions for the operators to be useful in practice. Our conditions are easy to verify, and we discuss how they can be used to reduce the complexity of infeasible interior point methods. Our preliminary results highlight two promising advantages of following a multigrid approach compared to a pure interior point method: the percentage of problems that can be solved to a high accuracy is much greater, and the time necessary to find a solution can be reduced significantly, especially for large scale problems.

关键词： multigrid semidefinite programming sparse polynomial optimization differential equations

来源：评论

学校读者我要写书评

暂无评论

Equilibria and Weighted Complementarity Problems 1

引用

4th International Conference on Numerical Analysis and Optimization (NAO) - theory, methods, Applications and Technology Transfer (NAOIV)

作者： Potra, Florian A. Univ Maryland Baltimore Cty Dept Math & Stat 1000 Hilltop Circle Baltimore MD 22150 USA

ISBN: (数字)9783319900261

ISBN: (纸本)9783319900261;9783319900254

We review some results about market equilibria and weighted complementarity problems (wCP). The latter problem consists in finding a pair of vectors (x, s) belonging to the intersection of a manifold with a cone, such that their product in a certain algebra, x. s, equals a given weight vector w. When w is the zero vector, then wCP reduces to a Complementarity Problem (CP). The motivation for introducing the more general notion of a wCP lies in the fact that several equilibrium problems in economics can be formulated in a natural way as wCP. Moreover, those formulations lend themselves to the development of highly efficient algorithms for solving the corresponding equilibrium problems. For example, Fisher's competitive market equilibrium model can be formulated as a wCP that can be efficiently solved by interior-point methods. The Quadratic programming and Weighted Centering problem, which generalizes the notion of a linear programming and Weighted Centering problem proposed by Anstreicher, can also be formulated as a special linear monotone wCP. The paper summarizes some previous results about the convergence of two interior-point methods for general monotone linear wCP and a corrector-predictor method for sufficient linear wCP. Some recent smoothing Newton methods for monotone linear wCP are also presented.

关键词： Weighted complementarity interior-point Path-following Fisher equilibrium

来源：评论

学校读者我要写书评

暂无评论

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

New Algorithmic Paradigms for Discrete Problems using Dynami...

引用

作者： Damian Mateusz STRASZAK ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE

学位级别：博士

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most sophisticated tasks involving decision making, can be reduced to solving certain optimization problems. These advances however, bring several new challenges to the field of algorithm design. The first of them is related to the ever-growing size of instances, these optimization problems need to be solved for. In practice, this forces the algorithms for these problems to run in time linear or nearly linear in their input size. The second challenge is related to the emergence of new, harder and harder problems which need to be dealt with. These problems in most cases are considered computationally intractable because of complexity barriers such as NP completeness, or because of non-convexity. Therefore, efficiently computable relaxations for these problems are typically desired. The material of this thesis is divided into two parts. In the first part we attempt to address the first challenge. The recent tremendous progress in developing fast algorithm for such funda- mental problems as maximum flow or linear programming, demonstrate the power of continuous techniques and tools such as electrical flows, fast Laplacian solvers and interior point methods. In this thesis we study new algorithms of this type based on continuous dynamical systems inspired by the study of a slime mold Physarum polycephalum. We perform a rigorous mathematical analysis of these dynamical systems and extract from them new, fast algorithms for problems such as minimum cost flow, linear programming and basis pursuit. In the second part of the thesis we develop new tools to approach the second challenge. To- wards this, we study a very general form of discrete optimization problems and its extension to sampling and counting, capturing a host of imp

关键词： Discrete Problems Dynamical Systems Polynomials Counting Sampling Optimization Continuous Relaxations Physarum Polycephalum linear programming Convex Optimization Real Stable Polynomials Anti-Concentration Determinantal point Processes Maximum Entropy Distributions

来源：评论

学校读者我要写书评

暂无评论

Exact Algorithms for Semidefinite Programs with Degenerate Feasible Set 18

Exact Algorithms for Semidefinite Programs with Degenerate F...

引用

43rd ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Henrion, Didier Naldi, Simone El Din, Mohab Safey Univ Toulouse LAAS CNRS Toulouse France CTU Fac Elect Engn Prague Czech Republic Univ Limoges XLIM UMR 7252 F-87000 Limoges France Sorbonne Univ CNRS INRIA LIP6Equipe PolSys 4 Pl Jussieu F-75252 Paris 05 France

ISBN: (纸本)9781450355506

Let A(0),..., A(n) be m x m symmetric matrices with entries in Q, and let A(x) be the linear pencil A(0) + x(1)A(1) + ... + x(n)A(n), where x = (x(1),..., x(n)) are unknowns. The linear matrix inequality (LMI) A(x) >= 0 defines the subset of R-n, called spectrahedron, containing all points x such that A(x) has non-negative eigenvalues. The minimization of linear functions over spectrahedra is called semidefinite programming (SDP). Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for solving SDP are mostly based on the interior point method, assuming some non-degeneracy properties such as the existence of interior points in the admissible set. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice but we prove that solving such problems can be done in polynomial time if either n orm is fixed.

关键词： Semidefinite programming Polynomial optimization Exact computation Homotopy

来源：评论

学校读者我要写书评

暂无评论

Stability and Accuracy of Inexact interior point methods for Convex Quadratic programming

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2017年第2期175卷 450-477页

作者： Morini, Benedetta Simoncini, Valeria Univ Florence Florence Italy Univ Bologna Bologna Italy IMATI CNR Pavia Italy

We consider primal-dual interior point methods where the linear system arising at each iteration is formulated in the reduced (augmented) form and solved approximately. Focusing on the iterates close to a solution, we analyze the accuracy of the so-called inexact step, i.e., the step that solves the unreduced system, when combining the effects of both different levels of accuracy in the inexact computation and different processes for retrieving the step after block elimination. Our analysis is general and includes as special cases sources of inexactness due either to roundoff and computational errors or to the iterative solution of the augmented system using typical procedures. In the roundoff case, we recover and extend some known results.

关键词： Convex quadratic programming Primal-dual interior point methods Inexact interior point steps

来源：评论

学校读者我要写书评

暂无评论

內點法的直觀看法、理論分析與演算法實作

內點法的直觀看法、理論分析與演算法實作

引用

作者：劉正鴻成功大學

学位级别：碩士

自从1984年 Narendra Karmakar [5]，线性规划的内点法已经有许多变形。这篇论文专注於原始-对偶可行路径追踪演算法的其中一种变形，这个演算法的初始值可行，而且有目前已知最好的多项式复杂度 [1] [3] [10]。为了解释内点法的想法，... 详细信息

自从1984年 Narendra Karmakar [5]，线性规划的内点法已经有许多变形。这篇论文专注於原始-对偶可行路径追踪演算法的其中一种变形，这个演算法的初始值可行，而且有目前已知最好的多项式复杂度 [1] [3] [10]。为了解释内点法的想法，我们画了具启发性的图来说明单形法和内点法的直观看法。路径追踪演算法最重要的概念是中心路径。我们也画图说明几何概念。在实务演算法程式实作，我们从Netlib网站挑选了超过50个真实问题来测试，而我们挑选的问题当中，除了那些问题规模太大、超过电脑硬体负荷的问题，所有问题都能被演算法正确解出。这篇论文提供一个亦於理解内点法的方式，从直观概念到数学理论证明，再到实务应用。

关键词：內點法原始-對偶可行路徑追蹤演算法屏障問題中心路徑內點法直觀內點法演算法內點法程式內點法實務

来源：评论

学校读者我要写书评

暂无评论

Fast interior point solution of quadratic programming problems arising from PDE-constrained optimization

引用

NUMERISCHE MATHEMATIK 2017年第4期137卷 959-999页

作者： Pearson, John W. Gondzio, Jacek Univ Kent Sch Math Stat & Actuarial Sci Sibson BldgParkwood Rd Canterbury CT2 7FS Kent England Univ Edinburgh Sch Math James Clerk Maxwell BldgKings Bldg Edinburgh EH9 3FD Midlothian Scotland NASK Res Inst Kolska 12 PL-01045 Warsaw Poland

interior point methods provide an attractive class of approaches for solving linear, quadratic and nonlinear programming problems, due to their excellent efficiency and wide applicability. In this paper, we consider PDE-constrained optimization problems with bound constraints on the state and control variables, and their representation on the discrete level as quadratic programming problems. To tackle complex problems and achieve high accuracy in the solution, one is required to solve matrix systems of huge scale resulting from Newton iteration, and hence fast and robust methods for these systems are required. We present preconditioned iterative techniques for solving a number of these problems using Krylov subspace methods, considering in what circumstances one may predict rapid convergence of the solvers in theory, as well as the solutions observed from practical computations.

关键词： 65F08 65F10 65F50 76D55 93C20

来源：评论

学校读者我要写书评

暂无评论

Exact Conic programming Relaxations for a Class of Convex Polynomial Cone Programs

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2017年第1期172卷 156-178页

作者： Jeyakumar, Vaithilingam Li, Guoyin Univ New South Wales Sydney NSW 2052 Australia

In this paper, under a suitable regularity condition, we establish a broad class of conic convex polynomial optimization problems, called conic sum-of-squares convex polynomial programs, exhibiting exact conic programming relaxation, which can be solved by various numerical methods such as interior point methods. By considering a general convex cone program, we give unified results that apply to many classes of important cone programs, such as the second-order cone programs, semidefinite programs, and polyhedral cone programs. When the cones involved in the programs are polyhedral cones, we present a regularity-free exact semidefinite programming relaxation. We do this by establishing a sum-of-squares polynomial representation of positivity of a real sum-of-squares convex polynomial over a conic sum-of-squares convex system. In many cases, the sum-of-squares representation can be numerically checked via solving a conic programming problem. Consequently, we also show that a convex set, described by a conic sum-of-squares convex polynomial, is (lifted) conic linear representable in the sense that it can be expressed as (a projection of) the set of solutions to some conic linear systems.

关键词： Convex cone programs Convex polynomial optimization Conic programming Semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：