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

Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary

引用

MATHEMATICAL programming 2019年第1-2期178卷 263-299页

作者： Haeser, Gabriel Liu, Hongcheng Ye, Yinyu Univ Sao Paulo Inst Math & Stat Dept Appl Math Sao Paulo SP Brazil Stanford Univ Dept Radiat Oncol Stanford CA 94305 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

In this paper we consider the minimization of a continuous function that is potentially not differentiable or not twice differentiable on the boundary of the feasible region. By exploiting an interior point technique, we present first- and second-order optimality conditions for this problem that reduces to classical ones when the derivative on the boundary is available. For this type of problems, existing necessary conditions often rely on the notion of subdifferential or become non-trivially weaker than the KKT condition in the (twice-)differentiable counterpart problems. In contrast, this paper presents a new set of first- and second-order necessary conditions that are derived without the use of subdifferential and reduce to exactly the KKT condition when (twice-)differentiability holds. As a result, these conditions are stronger than some existing ones considered for the discussed minimization problem when only non-negativity constraints are present. To solve for these optimality conditions in the special but important case of linearly constrained problems, we present two novel interior point trust-region algorithms and show that their worst-case computational efficiency in achieving the potentially stronger optimality conditions match the best known complexity bounds. Since this work considers a more general problem than those in the literature, our results also indicate that best known existing complexity bounds are actually held for a wider class of nonlinear programming problems. This new development is significant since optimality conditions play a fundamental role in computational optimization and more and more nonlinear and nonconvex problems need to be solved in practice.

关键词： Constrained optimization nonconvex programming Interior point method First order algorithm Nonsmooth problems

来源：评论

学校读者我要写书评

暂无评论

Multiple Flat Projections for Cross-Manifold Clustering

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第8期52卷 7704-7718页

作者： Bai, Lan Shao, Yuan-Hai Wang, Zhen Chen, Wei-Jie Deng, Nai-Yang Inner Mongolia Univ Sch Math Sci Hohhot 010021 Peoples R China Hainan Univ Sch Management Haikou 570228 Hainan Peoples R China Jilin Univ Minist Educ Key Lab Symbol Computat & Knowledge Engn Changchun 130012 Peoples R China Zhejiang Univ Technol Zhijiang Coll Hangzhou 310014 Peoples R China China Agr Univ Coll Sci Beijing 100083 Peoples R China

Cross-manifold clustering is an extreme challenge learning problem. Since the low-density hypothesis is not satisfied in cross-manifold problems, many traditional clustering methods failed to discover the cross-manifold structures. In this article, we propose multiple flat projections clustering (MFPC) for cross-manifold clustering. In our MFPC, the given samples are projected into multiple localized flats to discover the global structures of implicit manifolds. Thus, the intersected clusters are distinguished in various projection flats. In MFPC, a series of nonconvex matrix optimization problems is solved by a proposed recursive algorithm. Furthermore, a nonlinear version of MFPC is extended via kernel tricks to deal with a more complex cross-manifold learning situation. The synthetic tests show that our MFPC works on the cross-manifold structures well. Moreover, experimental results on the benchmark datasets and object tracking videos show excellent performance of our MFPC compared with some state-of-the-art manifold clustering methods.

关键词： Manifolds Clustering methods Support vector machines Periodic structures Optimization Indexes Elongation Clustering cross-manifold clustering flat-based clustering manifold clustering nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

A note on the complexity of L_p minimization

引用

MATHEMATICAL programming 2011年第2期129卷 285-299页

作者： Ge, Dongdong Jiang, Xiaoye Ye, Yinyu Shanghai Jiao Tong Univ Antai Sch Econ & Management Shanghai 200052 Peoples R China Stanford Univ Inst Computat & Math Engn Stanford CA 94305 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We discuss the L-p (0 <= p < 1) minimization problem arising from sparse solution construction and compressed sensing. For any fixed 0 < p < 1, we prove that finding the global minimal value of the problem is strongly NP-Hard, but computing a local minimizer of the problem can be done in polynomial time. We also develop an interior-point potential reduction algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm.

关键词： nonconvex programming Global optimization Interior-point method Sparse solution reconstruction

来源：评论

学校读者我要写书评

暂无评论

ON THE CONVERGENCE OF MIRROR DESCENT BEYOND STOCHASTIC CONVEX programming

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第1期30卷 687-716页

作者： Zhou, Zhengyuan Mertikopoulos, Panayotis Bambos, Nicholas Boyd, Stephen P. Glynn, Peter W. IBM Res Yorktown Hts NY 10598 USA NYU Stern Sch Business 550 1St Ave New York NY 10012 USA Univ Grenoble Alpes CNRS Grenoble INP InriaLIG F-38000 Grenoble France Stanford Univ Dept Elect Engn Dept Management Sci & Engn Stanford CA 94305 USA

In this paper, we examine the convergence of mirror descent in a class of stochastic optimization problems that are not necessarily convex (or even quasi-convex) and which we call variationally coherent. Since the standard technique of "ergodic averaging" offers no tangible benefits beyond convex programming, we focus directly on the algorithm's last generated sample (its "last iterate"), and we show that it converges with probabiility 1 if the underlying problem is coherent. We further consider a localized version of variational coherence which ensures local convergence of Stochastic mirror descent (SMD) with high probability. These results contribute to the landscape of nonconvex stochastic optimization by showing that (quasi-)convexity is not essential for convergence to a global minimum: rather, variational coherence, a much weaker requirement, suffices. Finally, building on the above, we reveal an interesting insight regarding the convergence speed of SMD: in problems with sharp minima (such as generic linear programs or concave minimization problems), SMD reaches a minimum point in a finite number of steps (a.s.), even in the presence of persistent gradient noise. This result is to be contrasted with existing black-box convergence rate estimates that are only asymptotic.

关键词： mirror descent nonconvex programming stochastic optimization stochastic approximation variational coherence

来源：评论

学校读者我要写书评

暂无评论

HYPERSPECTRAL SUPER-RESOLUTION VIA LOW RANK TENSOR TRIPLE DECOMPOSITION

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2024年第3期20卷 942-966页

作者： Cui, Xiaofei Chang, Jingya Guangdong Univ Technol Sch Math & Stat Guangzhou Peoples R China

Hyperspectral image (HSI) and multispectral image (MSI) fusion aims at producing a super-resolution image (SRI). In this paper, we establish a nonconvex optimization model for image fusion problem through low rank tensor triple decomposition. Using the limited memory BFGS (L-BFGS) approach, we develop a first-order optimization algorithm for obtaining the desired super-resolution image (TTDSR). Furthermore, two detailed methods are provided for calculating the gradient of the objective function. With the aid of the KurdykaLojasiewicz property, the iterative sequence is proved to converge to a stationary point. Finally, experimental results on different datasets show the effectiveness of our proposed approach.

关键词： Key words and phrases. Tensor triple decomposition nonconvex programming Kurdyka-Lojasiewicz property image fusion hyperspectral image multispectral image

来源：评论

学校读者我要写书评

暂无评论

DC programming: Overview

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1999年第1期103卷 1-43页

作者： Horst, R Thoai, NV Univ Trier Dept Math Trier Germany

Mathematical programming problems dealing with functions, each of which can be represented as a difference of two convex functions, are called DC programming problems. The purpose of this overview is to discuss main theoretical results, some applications, and solution methods for this interesting and important class of programming problems. Some modifications and new results on the optimality conditions and development of algorithms are also presented.

关键词： DC functions DC programming global optimization nonconvex programming optimality conditions

来源：评论

学校读者我要写书评

暂无评论

A FINITE, NONADJACENT EXTREME-POINT SEARCH ALGORITHM FOR OPTIMIZATION OVER THE EFFICIENT SET

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1992年第1期73卷 47-64页

作者： BENSON, HP UNIV FLORIDA COLL BUSINESS ADMGAINESVILLEFL 32611 USA

The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.

关键词： MULTIPLE-CRITERIA DECISION MAKING EXTREME-POINT SEARCH GLOBAL OPTIMIZATION EFFICIENT SET nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

Self-adaptive algorithms for quasiconvex programming and applications to machine learning

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2024年第4期43卷 1-16页

作者： Thang, Tran Ngoc Hai, Trinh Ngoc Hanoi Univ Sci & Technol Sch Appl Math & Informat Hanoi Vietnam

For solving a broad class of nonconvex programming problems on an unbounded constraint set, we provide a self-adaptive step-size strategy that does not include line-search techniques and establishes the convergence of a generic approach under mild assumptions. Specifically, the objective function may not satisfy the convexity condition. Unlike descent line-search algorithms, it does not need a known Lipschitz constant to figure out how big the first step should be. The crucial feature of this process is the steady reduction of the step size until a certain condition is fulfilled. In particular, it can provide a new gradient projection approach to optimization problems with an unbounded constrained set. To demonstrate the effectiveness of the proposed technique for large-scale problems, we apply it to some experiments on machine learning, such as supervised feature selection, multi-variable logistic regressions and neural networks for classification.

关键词： nonconvex programming Gradient descent algorithms Quasiconvex functions Pseudoconvex functions Self-adaptive step-sizes

来源：评论

学校读者我要写书评

暂无评论

An LMI-based algorithm for designing suboptimal static H₂/H_∞ output feedback controllers

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2001年第6期39卷 1711-1735页

作者： Leibfritz, F Univ Trier FB Malth 4 D-54286 Trier Germany

We consider the problem of designing a suboptimal H-2/H-infinity feedback control law for a linear time-invariant control system when a complete set of state variables is not available. This problem can be necessarily restated as a nonconvex optimization problem with a bilinear, multiobjective functional under suitably chosen linear matrix inequality (LMI) constraints. To solve such a problem, we propose an LMI-based procedure which is a sequential linearization programming approach. The properties and the convergence of the algorithm are discussed in detail. Finally, several numerical examples for static H-2/H-infinity output feedback problems demonstrate the applicability of the considered algorithm and also verify the theoretical results numerically.

关键词： static controllers output feedback suboptimal control robust control linear systems linear matrix inequalities nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

CONSTRUCTION OF TEST PROBLEMS FOR A CLASS OF REVERSE CONVEX-PROGRAMS

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1994年第2期81卷 343-354页

作者： MOSHIRVAZIRI, K UNIV CALIF LOS ANGELES LOS ANGELES CA 90024 USA

A method of constructing test problems with known global solution for a class of reverse convex programs or linear programs with an additional reverse convex constraint is presented. The initial polyhedron is assumed to be a hypercube. The method then systematically generates cuts that slice the cube in such a way that a prespecified global solution on its edge remains intact. The proposed method does not require the solution of linear programs or systems of linear equations as is often required by existing techniques.

关键词： REVERSE CONVEX programming nonconvex programming NONLINEAR programming LINEAR programming TEST PROBLEMS GLOBAL OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：