Convex Optimization
- 格式：pdf
- 大小：148.86 KB
- 文档页数：12
文档推荐
-
Convex_Hull页数:12
-
Convex Optimization页数:12
-
第3讲凸集凸函数凸规划页数:15
-
凸函数的性质及其在证明不等式中的应用页数:18
-
1 凸集页数:18
下载文档原格式
合集下载
convex optimization中译本
一、导论随着科技的发展和应用，凸优化在各个领域中发挥着越来越重要的作用。
其在工程、金融、计算机科学等领域的应用不断扩展和深化。
对于凸优化的理论和方法的研究，以及文献的翻译与传播变得尤为重要。
本文旨在对凸优化中的一些重要主题和内容进行介绍和讨论，希望能够为相关领域的研究者和读者提供一些参考和帮助。
二、凸优化基本概念1. 凸集与凸函数凸集和凸函数是凸优化中非常基础且重要的概念。
凸集是指集合中任意两个点的线段都在该集合内部的集合。
凸函数则是定义在凸集上的实值函数，其函数图像上的任意两点组成的线段都在函数图像上方。
凸集和凸函数的性质为凸优化问题的理论和方法提供了基础。
2. 凸优化问题的一般形式凸优化问题的一般形式可以表示为：minimize f(x)subject to g_i(x) <= 0, i = 1,2,...,mh_j(x) = 0, j = 1,2,...,p其中，f(x)是要优化的目标函数，g_i(x)和h_j(x)分别为不等式约束和等式约束。
凸优化问题通常要求目标函数和约束函数都是凸的。
三、凸优化中的常见算法1. 梯度下降法梯度下降法是一种常用的优化算法，尤其适用于凸优化问题。
其基本思想是通过计算目标函数的梯度方向，并沿着梯度的负方向进行迭代，以逐步逼近最优解。
2. 拉格朗日乘子法拉格朗日乘子法主要用于处理约束优化问题，通过构建拉格朗日函数并对其进行优化，得到原始优化问题的最优解。
拉格朗日乘子法在凸优化问题中得到了广泛的应用。
3. 内点法内点法是一类迭代法，主要用于求解线性规划和二次规划等凸优化问题。
其优点在于可以较快地收敛到最优解，尤其适用于大规模的凸优化问题。
四、凸优化在科学与工程中的应用凸优化在科学与工程中有着广泛的应用，如在信号处理中的最小二乘问题、在机器学习中的支持向量机、在通信系统中的功率分配问题等。
这些应用不仅推动了凸优化理论的发展，也为实际问题的解决提供了有效的工具和方法。
凸优化课程详
课程简介，凸优化问题介绍
2. 凸集，凸函数， 3学时
凸集和凸函数的定义和判别
3. 数值代数基础， 3学时
向量，矩阵，范数，子空间，Cholesky分解，QR分解，特征值分解，奇异值分解
4. 凸优化问题， 6学时
典型的凸优化问题，线性规划和半定规划问题
5. 凸优化模型语言和算法软件，3学时
模型语言：AMPL, CVX, YALMIP; 典型算法软件： SDPT3, Mosek, CPLEX, Gruobi
随着科学与工程的发展，凸优化理论与方法的研究迅猛发展，在科学与工程计算，数据科学，信号和图像处理，管理科学等诸多领域中得到了广泛应用。通过本课程的学习，掌握凸优化的基本概念，对偶理论，典型的几类凸优化问题的判别及其计算方法，熟悉相关计算软件
本课程面向高. 凸优化简介， 3学时
Numerical Optimization,Jorge Nocedal and Stephen Wright,Springer,2006,2nd ed.,978-0-387-40065-5；
最优化理论与方法,袁亚湘，孙文瑜,科学出版社,2003,
参考书
1st ed.,9787030054135；
教学大纲
（2） 课程项目： 60%
要求：
作业和课程项目必须按时提交，迟交不算成绩，抄袭不算成绩
教学评估
文再文：
凸优化课程详细信息
课程号
00136660
学分
3
英文名称
Convex Optimization
先修课程
数学分析（高等数学），高等代数（线性代数）
中文简介
凸优化是一种广泛的，越来越多地应用于科学与工程计算，经济学，管理学，工业等领域的学科。它涉及建立恰当的数学模型来描述问题，设计合适的计算方法来寻找问题的最优解，研究模型和算法的理论性质，考察算法的计算性能。该入门课程??适合于数学，统计，计算机科学，电子工程，运筹学等学科的高年级本科生和研究生。教学内容包括凸集，凸函数和凸优化问题的介绍；凸分析的基础知识； 对偶理论；梯度算法，近似梯度算法，Nesterov加速方法，交替方向乘子法；内点算法，统计，信号处理和机器学习中的应用。
2. 凸集，凸函数， 3学时
凸集和凸函数的定义和判别
3. 数值代数基础， 3学时
向量，矩阵，范数，子空间，Cholesky分解，QR分解，特征值分解，奇异值分解
4. 凸优化问题， 6学时
典型的凸优化问题，线性规划和半定规划问题
5. 凸优化模型语言和算法软件，3学时
模型语言：AMPL, CVX, YALMIP; 典型算法软件： SDPT3, Mosek, CPLEX, Gruobi
随着科学与工程的发展，凸优化理论与方法的研究迅猛发展，在科学与工程计算，数据科学，信号和图像处理，管理科学等诸多领域中得到了广泛应用。通过本课程的学习，掌握凸优化的基本概念，对偶理论，典型的几类凸优化问题的判别及其计算方法，熟悉相关计算软件
本课程面向高. 凸优化简介， 3学时
Numerical Optimization,Jorge Nocedal and Stephen Wright,Springer,2006,2nd ed.,978-0-387-40065-5；
最优化理论与方法,袁亚湘，孙文瑜,科学出版社,2003,
参考书
1st ed.,9787030054135；
教学大纲
（2） 课程项目： 60%
要求：
作业和课程项目必须按时提交，迟交不算成绩，抄袭不算成绩
教学评估
文再文：
凸优化课程详细信息
课程号
00136660
学分
3
英文名称
Convex Optimization
先修课程
数学分析（高等数学），高等代数（线性代数）
中文简介
凸优化是一种广泛的，越来越多地应用于科学与工程计算，经济学，管理学，工业等领域的学科。它涉及建立恰当的数学模型来描述问题，设计合适的计算方法来寻找问题的最优解，研究模型和算法的理论性质，考察算法的计算性能。该入门课程??适合于数学，统计，计算机科学，电子工程，运筹学等学科的高年级本科生和研究生。教学内容包括凸集，凸函数和凸优化问题的介绍；凸分析的基础知识； 对偶理论；梯度算法，近似梯度算法，Nesterov加速方法，交替方向乘子法；内点算法，统计，信号处理和机器学习中的应用。
内点法介绍(Interior Point Method)
内点法介绍（Interior Point Method）在面对无约束的优化命题时，我们可以采用牛顿法等方法来求解。
而面对有约束的命题时，我们往往需要更高级的算法。
单纯形法（Simplex Method）可以用来求解带约束的线性规划命题（LP），与之类似的有效集法（Active Set Method）可以用来求解带约束的二次规划（QP），而内点法（Interior Point Method）则是另一种用于求解带约束的优化命题的方法。
而且无论是面对LP还是QP，内点法都显示出了相当的极好的性能，例如多项式的算法复杂度。
本文主要介绍两种内点法，障碍函数法（Barrier Method）和原始对偶法（Primal-Dual Method）。
其中障碍函数法的内容主要来源于Stephen Boyd与Lieven Vandenberghe的Convex Optimization一书，原始对偶法的内容主要来源于Jorge Nocedal和Stephen J. Wright的Numerical Optimization一书（第二版）。
为了便于与原书对照理解，后面的命题与公式分别采用了对应书中的记法，并且两者方法针对的是不同的命题。
两种方法中的同一变量可能在不同的方法中有不同的意义，如μ。
在介绍玩两种方法后会有一些比较。
障碍函数法Barrier MethodCentral Path举例原始对偶内点法Primal Dual Interior Point Method Central Path举例几个问题障碍函数法（Barrier Method）对于障碍函数法，我们考虑一个一般性的优化命题：minsubject tof0(x)fi(x)≤0,i=1,...,mAx=b(1) 这里f0,...,fm:Rn→R 是二阶可导的凸函数。
同时我也要求命题是有解的，即最优解x 存在，且其对应的目标函数为p。
此外，我们还假设原命题是可行的（feasible）。
西安电子科技大学优质课程《凸优化及其在信号处理中的应用》课程教学大纲
课程教学大纲课程编号：G00TE1204课程名称：凸优化及其在信号处理中的应用课程英文名称：Convex Optimization and Its Applications in Signal Processing开课单位：通信工程学院教学大纲撰写人：苏文藻课程学分：2学分课内学时：32学时课程类别：硕士/博士/专业学位课程性质：任选授课方式：讲课考核方式：作业，考试适用专业：通信与信息系统、信号与信息处理先修课程：教学目标：同学应：1.掌握建立基本优化模型技巧2.掌握基本凸分析理论3.掌握凸优化问题的最优条件及对偶理论4.认识凸优化在信号处理的一些应用英文简介：In this course we will develop the basic machineries for formulating and analyzing various optimization problems. Topics include convex analysis, linear and conic linear programming, nonlinear programming, optimality conditions, Lagrangian duality theory, and basics of optimization algorithms. Applications from signal processing will be used to complement the theoretical developments. No prior optimization background is required for this class. However, students should have workable knowledge in multivariable calculus, real analysis, linear algebra and matrix theory.课程主要内容：Part I: Introduction-Problem formulation-Classes of optimization problemsPart II: Theory-Basics of convex analysis-Conic linear programming and nonlinear programming: Optimality conditions and duality theory-Basics of combinatorial optimizationPart III: Selected Applications in Signal Processing-Transmit beamforming-Network localization-Sparse/Low-Rank Regression参考书目：1.Ben-Tal, Nemirovski: Optimization I-II: Convex Analysis, Nonlinear ProgrammingTheory, Nonlinear Programming Algorithms, 2004.2.Boyd, Vandenberghe: Convex Optimization, Cambridge University Press, 2004.3.Luenberger, Ye: Linear and Nonlinear Programming (3rd Edition), 2008.4.Nemirovski: Lectures on Modern Convex Optimization, 2005.。
凸优化练习题与解答(1)台大考古题
Convex Optimization Midterm, Thursday April 19, 2018.
Exam policy: Open book. You can bring any books, handouts, and any kinds of paper-based notes with you, but electronic devices (including cellphones, laptops, tablets, etc.) are strictly prohibited.
2. (18%) Determine whether each of the following sets is a convex function, quasi-convex
function, concave function. Write your answer as a table of 6 rows and 3 columns, with
z, X1z ≥ 1 z, X2z ≥ 1
Then, for 0 ≤ θ ≤ 1,
z, θX1 + (1 − θ)X2 z =θ z, X1 + (1 − θ) z, X2 ≥θ · 1 + (1 − θ) · 1 =1.
As required in definition of S10. To see it is not a cone, consider z = (1, 0, . . . , 0), and X = I ∈ Sn (symmetric matrices). Here z, Xz = 1, but z, 2Iz = 2 The reason that it is not affine is the same, by considering 2I = 2 · I + (−1) · O, the “line” containing O (all-0 matrix) and I. It follows that it is not a subspace. 11. S11 = x ∈ Rn ||P x + q||2 ≤ cT x + r given any P ∈ Rm×n, q ∈ Rm, c ∈ Rn, and r ∈ R. T, F, F, F To show convexity, if
Exam policy: Open book. You can bring any books, handouts, and any kinds of paper-based notes with you, but electronic devices (including cellphones, laptops, tablets, etc.) are strictly prohibited.
2. (18%) Determine whether each of the following sets is a convex function, quasi-convex
function, concave function. Write your answer as a table of 6 rows and 3 columns, with
z, X1z ≥ 1 z, X2z ≥ 1
Then, for 0 ≤ θ ≤ 1,
z, θX1 + (1 − θ)X2 z =θ z, X1 + (1 − θ) z, X2 ≥θ · 1 + (1 − θ) · 1 =1.
As required in definition of S10. To see it is not a cone, consider z = (1, 0, . . . , 0), and X = I ∈ Sn (symmetric matrices). Here z, Xz = 1, but z, 2Iz = 2 The reason that it is not affine is the same, by considering 2I = 2 · I + (−1) · O, the “line” containing O (all-0 matrix) and I. It follows that it is not a subspace. 11. S11 = x ∈ Rn ||P x + q||2 ≤ cT x + r given any P ∈ Rm×n, q ∈ Rm, c ∈ Rn, and r ∈ R. T, F, F, F To show convexity, if
分布式多智能体网络的优化的小综述
分布式多智能体网络的优化大量的多智能体的控制与决策问题可以归结为一个优化问题。
例如，在通信网络中，资源分配的最大使用效率、无线传感器网络的最优估计等等。
与传统的分布式优化相比，这里更加关注改进计算的效率与可扩展性。
因为新的应用中，每个节点的计算能力非常有限，且有限的通信环境下，所以需要设计简单的优化机制（算法）。
个体目标函数和的优化问题分布式多智能体网络中，每个多智能体都有一个自己的凸目标函数。
优化的目标是最优化所有节点目标函数的和。
我们需要设计一个优化算法，它是分布式。
也就是说没有一个中央协调器。
还有，每个节点都只知道自己的目标函数和邻居节点的有限信息[1]-[4][7]。
()()1minimize subject to XN i i f x f x x =∈∑目前这类型的研究已有一些工作，有部分文章考虑异步算法：I. Lobel 将分布式梯度算法应用于随机网络当中[2], M. Zhong and C. G. Cassandras 考虑了通讯为事件驱动的多智能体网络的分布式优化问题，A. Nedich 利用广播通信算法实现网络的分布式优化。
但目前对各种通信约束考虑不足，并且此类研究多提出的是高度抽象的网络优化模型[2]-[3]，结合某些具体的背景的文献尚不多见。
拓扑结构的优化在许多应用当中，我们需要对拓扑结构进行权衡优化。
例如，在多智能体系统的一致性研究当中，高连通性代表着快速的收敛；但是，高连通性也意味着更高的通信成本与能量消耗。
如果一味的追求低连通性，那么收敛度又会非常慢。
优化拓扑结构是在许多应用中一个亟待解决的问题。
有一些研究单纯关注收敛速度的优化，也就是说设计一个拓扑结构使得相应的连通性最高（即使2λ最小），如斯坦福大学S.Boyd 利用半定规划方法设计了相应的最优网络（无向）拓扑[5] 。
也有部分学者关注于通讯成本[6]。
存在的问题1. 目前大部分的优化问题，都是以个体目标和为目标函数。
凸函数1
Figure 1: Examples of a convex set (a) and a nons
• All of Rn . It should be fairly obvious that given any x, y ∈ Rn , θx + (1 − θ)y ∈ Rn . • The non-negative orthant, Rn + . The non-negative orthant consists of all vectors in n R whose elements are all non-negative: Rn + = {x : xi ≥ 0 ∀i = 1, . . . , n}. To show that this is a convex set, simply note that given any x, y ∈ Rn + and 0 ≤ θ ≤ 1, (θx + (1 − θ)y )i = θxi + (1 − θ)yi ≥ 0 ∀i. • Norm balls. Let · be some norm on Rn (e.g., the Euclidean norm, x 2 = n n 2 i=1 xi ). Then the set {x : x ≤ 1} is a convex set. To see this, suppose x, y ∈ R , with x ≤ 1, y ≤ 1, and 0 ≤ θ ≤ 1. Then θx + (1 − θ)y ≤ θx + (1 − θ)y = θ x + (1 − θ) y ≤ 1 where we used the triangle inequality and the positive homogeneity of norms. • Affine subspaces and polyhedra. Given a matrix A ∈ Rm×n and a vector b ∈ Rm , an affine subspace is the set {x ∈ Rn : Ax = b} (note that this could possibly be empty if b is not in the range of A). Similarly, a polyhedron is the (again, possibly empty) set {x ∈ Rn : Ax b}, where ‘ ’ here denotes componentwise inequality (i.e., all the entries of Ax are less than or equal to their corresponding element in b).1 To prove this, first consider x, y ∈ Rn such that Ax = Ay = b. Then for 0 ≤ θ ≤ 1, A(θx + (1 − θ)y ) = θAx + (1 − θ)Ay = θb + (1 − θ)b = b. Similarly, for x, y ∈ Rn that satisfy Ax ≤ b and Ay ≤ b and 0 ≤ θ ≤ 1, A(θx + (1 − θ)y ) = θAx + (1 − θ)Ay ≤ θb + (1 − θ)b = b.
凸优化一阶和二阶条件的证明
2
First and second order characterizations of convex functions
Theorem 2. Suppose f : Rn → R is twice differentiable over an open domain. Then, the following are equivalent: (i) f is convex. (ii) f (y ) ≥ f (x) + ∇f (x)T (y − x), for all x, y ∈ dom(f ). (iii) ∇2 f (x) 0, for all x ∈ dom(f ).
• The theorem simplifies many basic proofs in convex analysis but it does not usually make verification of convexity that much easier as the condition needs to hold for all lines (and we have infinitely many). • Many algorithms for convex optimization iteratively minimize the function over lines. The statement above ensures that each subproblem is also a convex optimization problem. 4
1.4
Examples of multivariate convex functions
• Affine functions: f (x) = aT x + b (for any a ∈ Rn , b ∈ R). They are convex, but not strictly convex; they are also concave: ∀λ ∈ [0, 1], f (λx + (1 − λ)y ) = aT (λx + (1 − λ)y ) + b = λaT x + (1 − λ)aT y + λb + (1 − λ)b = λf (x) + (1 − λ)f (y ). In fact, affine functions are the only functions that are both convex and concave. • Some quadratic functions: f (x) = xT Qx + cT x + d. – Convex if and only if Q 0. 0.
凸优化、半定规划相关Matlab工具包总结(部分为C C++)
SoftwareFor some codes a benchmark on problems from SDPLIB is available at Arizona State University.∙CSDP 4.9, by Brian Borchers (report 1998, report 2001). He also maintains a problem library, SDPLIB.∙CVX, version 1.1, by M. Grant and S. Boyd.Matlab software for disciplined convex programming.∙DSDP 5.6 , by S. J. Benson and Y. Ye, parallel dual-scaling interior point code in C (manual); source and excutables available fromBenson's homepages.∙GloptiPoly3, by D. Henrion, J.-B. Lasserre and J. Loefberg;a Matlab/SeDuMi add-on for LMI-relaxations of minimization problemsover multivariable polynomial functions subject to polynomial or integer constraints.∙LMITOOL-2.0 of the Optimization and Control Group at ENSTA.∙MAXDET, by Shao-po Wu, L. Vandenberghe, and S. Boyd. Software for determinant maximization. (see also rmd)∙NCSOStools, by K. Cafuta, I. Klep, and J. Povh. An open source Matlab toolbox for symbolic computation with polynomials in noncommutingvariables, to be used in combination with sdp solvers.∙PENNON-1.1 by M. Kocvara and M. Stingl. It implements a penalty method for (large-scale, sparse) nonlinear and semidefiniteprogramming (see their report), and is based on the PBM method ofBen-Tal and Zibulevsky.∙PENSDP v2.0 and PENBMI v2.0, by TOMLAB Optimization Inc., a MATLAB interface for PENNON.∙rmd , by the Geometry of Lattices and Algorithms group at University of Magdeburg, for making solutions of MAXDET rigorous byapproximating primal and dual solution by rationals and testing forfeasibility.∙SBmethod (Version 1.1.3), by C. Helmberg. A C++ implementation of the spectral bundle method for eigenvalue optimization.∙SDLS by D. Henrion and J. Malick.Matlab package for solving least-squares problems over convexsymmetric cones.∙SDPA (version 7.1.2), initiated by the group around Masakazu Kojima.∙SDPHA does not seem to be available any more (it was package by F.A. Potra, R. Sheng, and N. Brixius for use with MATLAB).∙SDPLR (version 1.02, May 2005) by Sam Burer, a C package for solving large-scale semidefinite programming problems.∙SDPpack is no longer supported, but still available. Version 0.9 BETA, by F. Alizadeh, J.-P. Haeberly, M. V. Nayakkankuppam, M. L. Overton, and S. Schmieta, for use with MATLAB.∙SDPSOL (version beta), by Shao-po Wu & Stephen Boyd (May 20, 1996). A parser/solver for SDP and MAXDET problems with matrixstructure.∙SDPT3 (version 4.0), high quality MATLAB package by K.C. Toh, M.J.Todd, and R.H. Tütüncü. See the optimization online reference.∙SeDuMi, a high quality package with MATLAB interface for solving optimization problems over self-dual homogeneous cones started byJos F. Sturm.Now also available: SeDuMi Interface 1.04 by Dimitri Peaucelle.∙SOSTOOLS, by S. Prajna, A. Papachristodoulou, and P. A. Parrilo. A SEDUMI based MATLAB toolbox for formulating and solving sums ofsquares (SOS) optimization programs(also available at Caltech).∙SP (version 1.1), by L. Vandenberghe, Stephen Boyd, and Brien Alkire.Software for Semidefinite Programming.∙SparseCoLO, by the group of M. Kojima, a matlab package for conversion methods for LMIs having sparse chordal graph structure,see the Research report B-453.∙SparsePOP, by H. Waki, S. Kim, M. Kojima and M. Muramatsu, is a MATLAB implementation of a sparse semidefinite programmingrelaxation method proposed for polynomial optimization problems.∙VSDP: Verified SemiDefinite Programmin, by Christian Jansson.MATLAB software package for computing verified results ofsemidefinite programming problems. See the optimization onlinereference.∙YALMIP, free MATLAB Toolbox by J. Löfberg for rapid optmization modeling with support for, e.g., conic programming, integerprogramming, bilinear optmization, moment optmization and sum ofsquares. Interfaces about 20 solvers, including most modern SDPsolvers.Reports on software:∙M. Yamashita, K. Fujisawa, M. Fukuda, K. Nakata and M. Nakata."Parallel solver for semidefinite programming problem having sparseSchur complement matrix",Research Report B-463, Dept. of Math. and Comp. Sciences, TokyoInstitute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552,September 2010.opt-online∙Hans D. Mittelmann."The state-of-the-art in conic optimization software",Arizona State University, August 2010, written for the "Handbook ofSemidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications".opt-online∙K.-C. Toh, M. J. Todd, and R. H. Tütüncü."On the implementation and usage of SDPT3 -- a Matlab softwarepackage for semidefinite-quadratic-linear programming, version 4.0", Preprint, National University of Singapore, June, 2010.opt-online∙K. Cafuta, I. Klep and J. Povh."NCSOSTOOLS: A Computer Algebra System for Symbolic andNumerical Computation with Noncommutative Polynomials",University of Ljubljana, Faculty of Mathematics and Physics, Slovenia, May 2010.opt-online∙I. D. Ivanov and E. De Klerk."Parallel implementation of a semidefinite programming solver based on CSDP on a distributed memory cluster",Optimization Methods and Software, Volume 25, Issue 3 June 2010 , pages 405 - 420 .OMS∙M. Yamashita, K. Fujisawa, K. Nakata, M. Nakata, M. Fukuda, K.Kobayashi and Kazushige Goto."A high-performance software package for semidefinite programs:SDPA 7",Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, January, 2010.opt-online∙Sunyoung Kim, Masakazu Kojima, Hayato Waki and Makoto Yamashita."SFSDP: a Sparse Version of Full SemiDefinite ProgrammingRelaxation for Sensor Network Localization Problems",Report B-457, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, July 2009.opt-online∙K. Fujisawa, S. Kim, M. Kojima, Y. Okamoto and M. Yamashita."ser's Manual for SparseCoLO: Conversion Methods for SparseConic-form Linear Optimization Problems",Research report B-453, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama,Meguro-ku, Tokyo 152-8552 Japan, February 2009.opt-online∙Sunyoung Kim, Masakazu Kojima, Martin Mevissen, Makoto Yamashita."Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities viaPositive Semidefinite Matrix Completion",Research Report B-452, Department of Mathematical and ComputingSciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, Japan, November 2008.opt-online∙ D. Henrion, J. B. Lasserre, and J. Löfberg."GloptiPoly 3: moments, optimization and semidefinite programming", LAAS-CNRS, University of Toulouse, 2007.opt-online∙Didier Henrion and J茅r么me Malick."SDLS: a Matlab package for solving conic least-squares problems", LAAS-CNRS, University of Toulouse, 2007.opt-online∙M. Grant and S. Boyd."Graph Implementations for Nonsmooth Convex Programs",Stanford University, 2007.opt-online∙K. K. Sivaramakrishnan."A PARALLEL interior point decomposition algorithm for block-angular semidefinite programs",Technical Report, Department of Mathematics, North Carolina State University, Raleigh, NC, 27695, December 2006. Revised in June 2007 and August 2007.opt-online∙Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuhide Nakata."Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs", Research Report B-415, Tokyo Institute of Technology, 2-12-1,Oh-okayama, Meguro-ku, Tokyo, Japan, March 2005.opt-online∙ B. Borchers and J. Young."How Far Can We Go With Primal-Dual Interior Point Methods forSDP?",New Mexico Tech, February 2005.opt-online∙H. Waki, S. Kim, M. Kojima and M. Muramatsu."SparsePOP : a Sparse Semidefinite Programming Relaxation ofPolynomial Optimization Problems",Research Report B-414, Dept. of Mathematical and ComputingSciences, Tokyo Institute of Technology, Oh-Okayama, Meguro152-8552, Tokyo, Japan, March 2005.opt-online∙M. Kocvara and M. Stingl."PENNON: A code for convex nonlinear and semidefinite programming", Optimization Methods and Software (OMS), Volume 18, Number 3,317-333, June 2003.∙Brian Borchers."CSDP 4.0 User's Guide",user's guide, New Mexico Tech, Socorro, NM 87801, 2002.opt-online∙M. Yamashita, K. Fujisawa, and M. Kojima."SDPARA : SemiDefinite Programming Algorithm PARAllel Version", Parallel Computing Vol.29 (8) 1053-1067 (2003).opt-online∙J. Sturm."Implementation of Interior Point Methods for Mixed Semidefinite and Second Order Cone Optimization Problems",Optimization Methods and Software, Volume 17, Number 6, 1105-1154, December 2002.optimization-online∙S. Benson and Y. Ye."DSDP4 Software User Guide",ANL/MCS-TM-248; Mathematics and Computer Science Division;Argonne National Laboratory; Argonne, IL; March 2002.opt-online∙S. Benson."Parallel Computing on Semidefinite Programs",Preprint ANL/MCS-P939-0302; Mathematics and Computer Science Division Argonne National Laboratory 9700 S. Cass Avenue Argonne, IL, 60439; March 2002.opt-online∙ D. Henrion and J. B. Lasserre."GloptiPoly - Global Optimization over Polynomials with Matlab andSeDuMi",LAAS-CNRS Research Report, February 2002.opt-online∙M. Kocvara and M. Stingl."PENNON - A Generalized Augmented Lagrangian Method forSemidefinite Programming",Research Report 286, Institute of Applied Mathematics, University of Erlangen, 2001.opt-online∙ D. Peaucelle, D. Henrion, and Y. Labit."User's Guide for SeDuMi Interface 1.01", Technical report number01445 LAAS-CNRS : 7 av. du Colonel Roche, 31077 Toulouse Cedex 4, FRANCE November 2001.opt-online∙Jos F. Sturm."Using SEDUMI 1.02, a MATLAB Toolbox for Optimization OverSymmetric Cones (Updated for Version 1.05)",October 2001.opt-online∙Hans D. Mittelmann."An Independent Benchmarking of SDP and SOCP Solvers",Technical Report, Dept. of Mathematics, Arizona State University, July2001.opt-online∙K. Fujisawa, M. Fukuda, M. Kojima and K. Nakata."Numerical Evaluation of SDPA",Research Report B-330, Department of Mathematical and ComputingSciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku,Tokyo 152, September 1997.ps.Z-file (ftp) or dvi.Z-file (ftp)∙L. Mosheyev and M. Zibulevsky."Penalty/Barrier Multiplier Algorithm for Semidefinite Programming:Dual Bounds and Implementation",Research Report #1/96, Optimization Laboratory, Technion, November 1996.ps-file (http)Due to several requests I have asked G. Rinaldi for permission to put his graph generator on this page. Here it is: rudy (tar.gz-file)Last modified: Tue Oct 26 15:10:14 CEST 2010。
凸优化2017课件Lecture4_convex_problems
5
Implicit Constraints
The standard form optimization problem has an explicit constraint:
m p
x∈D=
i=0
dom fi ∩
i=1
dom hi
D is the domain of the problem The constraints fi (x) ≤ 0, hi (x) = 0 are the explicit constraints A problem is unconstrained if it has no explicit constraints Example: minimize
Convex Optimization Problems
Spring 2016-2017
Yuanming Shi ShanghaiTech University
Outline
1 Optimization Problems 2 Convex Optimization 3 Quasi-Convex Optimization 4 Classes of Convex Problems: LP, QP, SOCP, SDP 5 Multicriterion Optimization (Pareto Optimality)
4
Global and Local Optimality
A feasible x is optimal if f0 (x) = p ; Xopt is the set of optimal points. A feasible x is locally optimal if it is optimal within a ball, i.e., there is an R > 0 such that x is optimal for minimize
Implicit Constraints
The standard form optimization problem has an explicit constraint:
m p
x∈D=
i=0
dom fi ∩
i=1
dom hi
D is the domain of the problem The constraints fi (x) ≤ 0, hi (x) = 0 are the explicit constraints A problem is unconstrained if it has no explicit constraints Example: minimize
Convex Optimization Problems
Spring 2016-2017
Yuanming Shi ShanghaiTech University
Outline
1 Optimization Problems 2 Convex Optimization 3 Quasi-Convex Optimization 4 Classes of Convex Problems: LP, QP, SOCP, SDP 5 Multicriterion Optimization (Pareto Optimality)
4
Global and Local Optimality
A feasible x is optimal if f0 (x) = p ; Xopt is the set of optimal points. A feasible x is locally optimal if it is optimal within a ball, i.e., there is an R > 0 such that x is optimal for minimize
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(a)
(b)
Figure 1: Examples of a convex set (a) and a non-convex set (b).
2.1
Examples
• All of Rn . It should be fairly obvious that given any x, y ∈ Rn , θx + (1 − θ)y ∈ Rn . • The non-negative orthant, Rn + . The non-negative orthant consists of all vectors in Rn whose elements are all non-negative: Rn + = {x : xi ≥ 0 ∀i = 1, . . . , n}. To show that this is a convex set, simply note that given any x, y ∈ Rn + and 0 ≤ θ ≤ 1, (θx + (1 − θ)y )i = θxi + (1 − θ)yi ≥ 0 ∀i. • Norm balls. Let · be some norm on Rn (e.g., the Euclidean norm, x 2 = n n 2 i=1 xi ). Then the set {x : x ≤ 1} is a convex set. To see this, suppose x, y ∈ R , with x ≤ 1, y ≤ 1, and 0 ≤ θ ≤ 1. Then θx + (1 − θ)y ≤ θx + (1 − θ)y = θ x + (1 − θ) y ≤ 1 where we used the triangle inequality and the positive homogeneity of norms. • Affine subspaces and polyhedra. Given a matrix A ∈ Rm×n and a vector b ∈ Rm , an affine subspace is the set {x ∈ Rn : Ax = b} (note that this could possibly be empty if b is not in the range of A). Similarly, a polyhedron is the (again, possibly empty) set {x ∈ Rn : Ax b}, where ‘ ’ here denotes componentwise inequality (i.e., all the entries of Ax are less than or equal to their corresponding element in b).1 To prove this, first consider x, y ∈ Rn such that Ax = Ay = b. Then for 0 ≤ θ ≤ 1, A(θx + (1 − θ)y ) = θAx + (1 − θ)Ay = θb + (1 − θ)b = b. Similarly, for x, y ∈ Rn that satisfy Ax ≤ b and Ay ≤ b and 0 ≤ θ ≤ 1, A(θx + (1 − θ)y ) = θAx + (1 − θ)Ay ≤ θb + (1 − θ)b = b.
Convex Optimization Overview
Zico Kolter October 19, 2007
1
Introduction
Many situations arise in machine learning where we would like to optimize the value of some function. That is, given a function f : Rn → R, we want to find x ∈ Rn that minimizes (or maximizes) f (x). We have already seen several examples of optimization problems in class: least-squares, logistic regression, and support vector machines can all be framed as optimization problems. It turns out that in the general case, finding the global optimum of a function can be a very difficult task. However, for a special class of optimization problems, known as convex optimization problems , we can efficiently find the global solution in many cases. Here, “efficiently” has both practical and theoretical connotations: it means that we can solve many real-world problems in a reasonable amount of time, and it means that theoretically we can solve problems in time that depends only polynomially on the problem size. The goal of these section notes and the accompanying lecture is to give a very brief overview of the field of convex optimization. Much of the material here (including some of the figures) is heavily based on the book Convex Optimization [1] by Stephen Boyd and Lieven Vandenberghe (available for free online), and EE364, a class taught here at Stanford by Stephen Boyd. If you are interested in pursuing convex optimization further, these are both excellent resources.
2
• Intersections of convex sets. Suppose C1 , C2 , . . . , Ck are convex sets. Then their intersection
k
Ci = {x : x ∈ Ci ∀i = 1, . . . , k }
i=1
is also a convex set. To see this, consider x, y ∈
2
Convex Sets
We begin our look at convex optimization with the notion of a convex set . Definition 2.1 A set C is convex if, for any x, y ∈ C and θ ∈ R with 0 ≤ θ ≤ 1, θx + (1 − θ)y ∈ C. Intuitively, this means that if we take any two elements in C , and draw a line segment between these two elements, then every point on that line segment also belongs to C . Figure 1 shows an example of one convex and one non-convex set. The point θx + (1 − θ)y is called a convex combination of the points x and y . 1
3
Convex Functions
A central element in convex optimization is the notion of a convex function . Definition 3.1 A function f : Rn → R is convex if its domain (denoted D(f )) is a convex set, and if, for all x, y ∈ D(f ) and θ ∈ R, 0 ≤ θ ≤ 1, f (θx + (1 − θ)y ) ≤ θf (x) + (1 − θ)f (y ). Intuitively, the way to think about this definition is that if we pick any two points on the graph of a convex function and draw a straight line between then, then the portion of the function between these two points will lie below this straight line. This situation is pictured in Figure 2.2 We say a function is strictly convex if Definition 3.1 holds with strict inequality for x = y and 0 < θ < 1. We say that f is concave if −f is convex, and likewise that f is strictly concave if −f is strictly convex.