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

Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions

引用

MATHEMATICAL programming 2017年第1-2期166卷 207-240页

作者： Liu, Hongcheng Yao, Tao Li, Runze Ye, Yinyu Penn State Univ Harold & Inge Marcus Dept Ind & Mfg Engn University Pk PA 16802 USA Penn State Univ Dept Stat University Pk PA 16802 USA Penn State Univ Methodol Ctr University Pk PA 16802 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

This paper concerns the folded concave penalized sparse linear regression (FCPSLR), a class of popular sparse recovery methods. Although FCPSLR yields desirable recovery performance when solved globally, computing a global solution is NP-complete. Despite some existing statistical performance analyses on local minimizers or on specific FCPSLR-based learning algorithms, it still remains open questions whether local solutions that are known to admit fully polynomial-time approximation schemes (FPTAS) may already be sufficient to ensure the statistical performance, and whether that statistical performance can be non-contingent on the specific designs of computing procedures. To address the questions, this paper presents the following threefold results: (1) Any local solution (stationary point) is a sparse estimator, under some conditions on the parameters of the folded concave penalties. (2) Perhaps more importantly, any local solution satisfying a significant subspace second-order necessary condition (SONC), which is weaker than the second-order KKT condition, yields a bounded error in approximating the true parameter with high probability. In addition, if the minimal signal strength is sufficient, the SONC solution likely recovers the oracle solution. This result also explicates that the goal of improving the statistical performance is consistent with the optimization criteria of minimizing the suboptimality gap in solving the non-convex programming formulation of FCPSLR. (3) We apply (2) to the special case of FCPSLR with minimax concave penalty and show that under the restricted eigenvalue condition, any SONC solution with a better objective value than the Lasso solution entails the strong oracle property. In addition, such a solution generates a model error (ME) comparable to the optimal but exponential-time sparse estimator given a sufficient sample size, while the worst-case ME is comparable to the Lasso in general. Furthermore, to guarantee the SONC admits FPTA

关键词： Sparse recovery non-convex programming NP-completeness Folded concave penalty Lasso

来源：评论

学校读者我要写书评

暂无评论

CAPACITATED TWO-STAGE TIME MINIMIZATION TRANSPORTATION PROBLEM WITH RESTRICTED FLOW

引用

RAIRO-OPERATIONS RESEARCH 2017年第2期51卷 447-467页

作者： Kaur, Prabhjot Verma, Vanita Dahiya, Kalpana Panjab Univ Univ Inst Engn & Technol Chandigarh 160014 India Panjab Univ Dept Math Chandigarh 160014 India

This paper discusses a capacitated time minimization transportation problem in which transportation operation takes place in two stages. In the first stage, due to some constraints, only a specified flow F-1 is transported from available sources to various destinations and in the second stage, a flow F-2 is transported depending upon the total demand of the destinations. The current problem is motivated by a production system of a steel industry where semi-finished jobs, initially located at various bins in its warehouse, are transported to various manufacturing facilities by transporters for the final processing and finishing. Due to some additional constraints, it is not possible to transport the number of semi-finished jobs equal to the exact number of final products to be manufactured, in one go. Therefore the transportation operation has to take place in two stages. Further, a capacity is associated with each bin-machine link which makes the current problem, a capacitated, two stage time minimization transportation problem with restricted flow. The objective is to minimize the sum of the transportation times for Stage-I and Stage-II. A polynomial time iterative algorithm is proposed that within each iteration, solves a restricted version of a related standard capacitated time minimization transportation problem and generates a pair of Stage-I and Stage-II times with Stage-II time strictly less than the Stage-II time of the previous iteration, whereas Stage-I time may increase. Out of these generated pairs, a pair with the minimum sum of transportation times of Stage-I and Stage-II is selected that gives the global optimal solution. Numerical illustration is included in the support of the theory.

关键词： non-convex programming combinatorial optimization time transportation problem capacitated transportation problem flow constraint

来源：评论

学校读者我要写书评

暂无评论

A modification of the alpha BB method for box-constrained optimization and an application to inverse kinematics

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2016年第1期4卷 93-121页

作者： Eichfelder, Gabriele Gerlach, Tobias Sumi, Susanne Tech Univ Ilmenau Inst Math POB 10 05 65 D-98684 Ilmenau Germany Tech Univ Ilmenau Tech Mech Grp POB 10 05 65 D-98684 Ilmenau Germany

For many practical applications it is important to determine not only a numerical approximation of one but a representation of the whole set of globally optimal solutions of a non-convex optimization problem. Then one element of this representation may be chosen based on additional information which cannot be formulated as a mathematical function or within a hierarchical problem formulation. We present such an application in the field of robotic design. This application problem can be modeled as a smooth box-constrained optimization problem. We extend the well-known alpha BB method such that it can be used to find an approximation of the set of globally optimal solutions with a predefined quality. We illustrate the properties and give a proof for the finiteness and correctness of our modified alpha BB method.

关键词： non-convex programming Global optimization Optimal solution set alpha BB method Robotic design

来源：评论

学校读者我要写书评

暂无评论

On controlling the total flow in two stage time minimizing transportation problem 2

On controlling the total flow in two stage time minimizing t...

引用

2nd International Conference on Recent Advances in Engineering

作者： Dahiya, Kalpana Kaur, Prabhjot Verma, Vanita Panjab Univ Univ Inst Engn & Technol Chandigarh 160014 India Panjab Univ Dept Math Chandigarh 160014 India

ISBN: (纸本)9781467382533

Transportation Problem is an important aspect which has been widely studied in Operations Research domain. A good and efficient transport is a key factor in mass production where the goods can reach the consumer from the production site or factory which may be situated many miles away. It has been studied with the objective of minimizing cost and the time to simulate different real life problems. In this paper, we study a time minimizing transportation problem in which the exact total demand of the destinations cannot be satisfied in one go. Due to some reasons, only a particular amount less than the exact total demand, can be transported first and therefore, rest of the amount has to be transported later. It gives rise to a two stage time minimizing transportation problem in which the stage-I flow is restricted. The present study proposes an iterative algorithm which concentrates on minimizing the total time of transportation of both the stages. At each iteration, a pair of times of Stage-I and Stage-II is generated with Stage-II time strictly less than the Stage-II time of the previous iteration. The pair with the minimum sum of Stage-I and Stage-II times is considered as the optimal pair and the corresponding transportation schedule is considered as the optimal solution of the problem.

关键词： Time transportation problem Combinatorial optimization non-convex programming Flow constraints

来源：评论

学校读者我要写书评

暂无评论

Robust Adaptive Beamforming With Positive Semi-Definite Constraint Using Single Variable Minimization

Robust Adaptive Beamforming With Positive Semi-Definite Cons...

引用

International Conference on Industrial Instrumentation and Control

作者： Patil, Suraj Prakash Nagrale, V. D. AISSMS COE Dept Elect Engn Pune 411001 Maharashtra India

ISBN: (纸本)9781479971657

In this paper, we propose a new method to solve the robust adaptive beamforming problem for the general rank signal model with positive semi-definite constraint. On applying the worst-case performance optimization approach, the considered robust adaptive beamforming problem generates a non-convex optimization problem. Here, we propose a two step closed form solution of the formulated problem, wherein a new single variable minimization problem is constructed. Result of this minimization is used to solve the robust adaptive beamforming problem. Simulation results verify the improvement in the performance by the proposed method over the current robust adaptive beamforming methods for general-rank signal model.

关键词： Robust adaptive beamforming general-rank signal model worst-case performance optimization non-convex programming

来源：评论

学校读者我要写书评

暂无评论

On controlling the total flow in two stage time minimizing transportation problem

On controlling the total flow in two stage time minimizing t...

引用

International Conference on Recent Advances in Engineering & Computational Sciences

作者： Kalpana Dahiya Prabhjot Kaur Vanita Verma University Institute of Engineering & Technology Panjab University Department of Mathematics Panjab University

ISBN: (纸本)9781467382540

关键词： Time transportation problem Combinatorial optimization non-convex programming Flow constraints

来源：评论

学校读者我要写书评

暂无评论

An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set

引用

OPERATIONS RESEARCH LETTERS 2013年第2期41卷 191-196页

作者： Goyal, Vineet Ravi, R. Columbia Univ New York NY 10027 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

We consider the problem of minimizing a class of quasi-concave functions over a convex set. Quasi-concave functions are generalizations of concave functions and NP-hard to minimize in general. We present a simple fully polynomial time approximation scheme (FPTAS) for minimizing a class of low-rank quasi-concave functions. Our algorithm solves a polynomial number of linear minimization problems and computes an extreme point near-optimal solution. Therefore, it applies directly to combinatorial 0-1 problems where the convex hull of feasible solutions is known. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Quasi-concave programming non-linear programming non-convex programming Polynomial approximation schemes

来源：评论

学校读者我要写书评

暂无评论

Robust Adaptive Beamforming for General-Rank Signal Model With Positive Semi-Definite Constraint via POTDC

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2013年第23期61卷 6103-6117页

作者： Khabbazibasmenj, Arash Vorobyov, Sergiy A. Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 2V4 Canada Aalto Univ Dept Signal Proc & Acoust FI-00076 Aalto Finland

The robust adaptive beamforming (RAB) problem for general-rank signal model with an additional positive semi-definite constraint is considered. Using the principle of the worst-case performance optimization, such RAB problem leads to a difference-of-convex functions (DC) optimization problem. The existing approaches for solving the resulted non-convex DC problem are based on approximations and find only suboptimal solutions. Here, we aim at finding the globally optimal solution for the non-convex DC problem and clarify the conditions under which the solution is guaranteed to be globally optimal. Particularly, we rewrite the problem as the minimization of a one-dimensional optimal value function (OVF). Then, the OVF is replaced with another equivalent one, for which the corresponding optimization problem is convex. The new one-dimensional OVF is minimized iteratively via polynomial time DC (POTDC) algorithm. We show that the POTDC converges to a point that satisfies Karush-Kuhn-Tucker (KKT) optimality conditions, and such point is the global optimum under certain conditions. Towards this conclusion, we prove that the proposed algorithm finds the globally optimal solution if the presumed norm of the mismatch matrix that corresponds to the desired signal covariance matrix is sufficiently small. The new RAB method shows superior performance compared to the other state-of-the-art general-rank RAB methods.

关键词： Difference-of-convex functions (DC) programming non-convex programming semi-definite programming relaxation robust adaptive beamforming general-rank signal model polynomial time DC (POTDC)

来源：评论

学校读者我要写书评

暂无评论

A globally convergent interior point algorithm for non-convex nonlinear programming

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2009年第2期224卷 622-627页

作者： Fan, Xiaona Nanjing Univ Posts & Telecommun Coll Math & Phys Nanjing 210046 Jiangsu Peoples R China

in this paper, a new algorithm for tracing the combined homotopy path of the non-convex nonlinear programming problem is proposed. The algorithm is based on the techniques of beta-cone neighborhood and a combined homotopy interior point method. The residual control criteria, which ensures that the obtained iterative points are interior points, is given by the condition that ensures the beta-cone neighborhood to be included in the interior part of the feasible region. The global convergence and polynomial complexity are established under some hypotheses. (c) 2008 Elsevier B.V. All rights reserved.

关键词： non-convex programming Combined interior homotopy Path following algorithm Global convergence

来源：评论

学校读者我要写书评

暂无评论

Sum-Rate Maximization in Two-Way AF MIMO Relaying: Polynomial Time Solutions to a Class of DC programming Problems

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2012年第10期60卷 5478-5493页

作者： Khabbazibasmenj, Arash Roemer, Florian Vorobyov, Sergiy A. Haardt, Martin Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 2V4 Canada Ilmenau Univ Technol Commun Res Lab D-98693 Ilmenau Germany

Sum-rate maximization in two-way amplify-and-forward (AF) multiple-input multiple-output (MIMO) relaying belongs to the class of difference-of-convex functions (DC) programming problems. DC programming problems occur also in other signal processing applications and are typically solved using different modifications of the branch-and-bound method which, however, does not have any polynomial time complexity guarantees. In this paper, we develop two efficient polynomial time algorithms for the sum-rate maximization in two-way AF MIMO relaying. The first algorithm guarantees to find at least a Karush-Kuhn-Tucker (KKT) solution. There is a strong evidence, however, that such a solution is actually globally optimal. The second algorithm that is based on the generalized eigenvectors shows the same performance as the first one with reduced computational complexity. The objective function of the problem is represented as a product of quadratic fractional ratios and parameterized so that its convex part (versus the concave part) contains only one (or two) optimization variables. One of the algorithms is called POlynomial Time DC (POTDC) and is based on semi-definite programming (SDP) relaxation, linearization, and an iterative Newton-type search over a single parameter. The other algorithm is called RAte-maximization via Generalized EigenvectorS (RAGES) and is based on the generalized eigenvectors method and an iterative search over two (or one, in its approximate version) optimization variables. We derive an upper-bound for the optimal value of the corresponding optimization problem and show by simulations that this upper-bound is achieved by both algorithms. It provides an evidence that the algorithms find a global optimum. The proposed methods are also superior to other state-of-the-art algorithms.

关键词： Difference-of-convex functions (DC) programming non-convex programming semi-definite programming relaxation sum-rate maximization two-way relaying

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：