Convex Optimization II

Incarcat la data: 19 Aprilie 2011

Autor: Admin

By Stephen Boyd - Stanford University
Licence: Creative Commons Attribution-NonCommercial-ShareAlike 3.0

Course Description:
Continuation of Convex Optimization I.Topics include: Subgradient, cutting-plane, and ellipsoid methods. Decentralized convex optimization via primal and dual decomposition. Alternating projections. Exploiting problem structure in implementation. Convex relaxations of hard problems, and global optimization via branch & bound. Robust optimization. Selected applications in areas such as control, circuit design, signal processing, and communications.
Lectures:

Lecture 1 - Basic Rules for Subgradient Calculus

Course Logistics, Course Organization, Course Topics, Subgradients, Basic Inequality, Subgradient Of A Function, Subdifferential, Subgradient Calculus, Some Basic Rules (For Subgradient Calculus), Pointwise Supremum, Weak Rule For Pointwise Supremum, Expectation, Minimization, Composition, Subgradients And Sublevel Sets, Quasigradients

 
Lecture 2 - Recap: Subgradients

Recap: Subgradients, Subgradients And Sublevel Sets, Quasigradients, Optimality Conditions - Unconstrained, Example: Piecewise Linear Minimization, Optimality Conditions - Constrained, Directional Derivative And Subdifferential, Descent Directions, Subgradients And Distance To Sublevel Sets, Descent Directions And Optimality, Subgradient Method, Step Size Rules, Assumptions, Convergence Results, Aside: Example: Applying Subgradient Method To Abs(X)

 
Lecture 3 - Convergence Proof, Stopping Criterion

Convergence Proof, Stopping Criterion, Example: Piecewise Linear Minimization, Optimal Step Size When F* Is Known, Finding A Point In The Intersection Of Convex Sets, Alternating Projections, Example: Positive Semidefinite Matrix Completion, Speeding Up Subgradient Methods, A Couple Of Speedup Algorithms, Subgradient Methods For Constrained Problems, Projected Subgradient Method, Linear Equality Constraints, Example: Least L_1-Norm

 
Lecture 4 - Project Subgradient For Dual Problem

Project Subgradient For Dual Problem, Subgradient Of Negative Dual Function, Example (Strictly Convex Quadratic Function Over Unit Box), Subgradient Method For Constrained Optimization, Convergence, Example: Inequality Form LP, Stochastic Subgradient Method, Noisy Unbiased Subgradient, Stochastic Subgradient Method, Assumptions, Convergence Results, Convergence Proof, Stochastic Programming

 
Lecture 5 - Stochastic Programming

Stochastic Programming, Variations (Of Stochastic Programming), Expected Value Of A Convex Function, Example: Expected Value Of Piecewise Linear Function, On-Line Learning And Adaptive Signal Processing, Example: Mean-Absolute Error Minimization, Localization And Cutting-Plane Methods, Cutting-Plane Oracle, Neutral And Deep Cuts, Unconstrained Minimization, Deep Cut For Unconstrained Minimization, Feasibility Problem, Inequality Constrained Problem, Localization Algorithm, Example: Bisection On R, Specific Cutting-Plane Methods, Center Of Gravity Algorithm, Convergence Of CG Cutting-Plane Method

 
Lecture 6 - Addendum: Hit-And-Run CG Algorithm

Addendum: Hit-And-Run CG Algorithm, Maximum Volume Ellipsoid Method, Chebyshev Center Method, Analytic Center Cutting-Plane Method, Extensions (Of Cutting-Plane Methods), Dropping Constraints, Epigraph Cutting-Plane Method, PWL Lower Bound On Convex Function, Lower Bound, Analytic Center Cutting-Plane Method, ACCPM Algorithm, Constructing Cutting-Planes, Computing The Analytic Center, Infeasible Start Newton Method Algorithm, Properties (Of Infeasible Start Newton Method Algorithm), Pruning Constraints, PWL Lower Bound On Convex Function, Lower Bound In ACCPM, Stopping Criterion, Example: Piecewise Linear Minimization

 
Lecture 7 - Example: Piecewise Linear Minimization

Example: Piecewise Linear Minimization, ACCPM With Constraint Dropping, Epigraph ACCPM, Motivation (For Ellipsoid Method), Ellipsoid Algorithm For Minimizing Convex Function, Properties Of Ellipsoid Method, Example (Using Ellipsoid Method), Updating The Ellipsoid, Simple Stopping Criterion, Basic Ellipsoid Algorithm, Interpretation (Of Basic Ellipsoid Algorithm), Example (Of Ellipsoid Method)

 
Lecture 8 - Recap: Ellipsoid Method

Recap: Ellipsoid Method, Improvements (To Ellipsoid Method), Proof Of Convergence, Interpretation Of Complexity, Deep Cut Ellipsoid Method, Ellipsoid Method With Deep Objective Cuts, Inequality Constrained Problems, Stopping Criterion, Epigraph Ellipsoid Method, Epigraph Ellipsoid Example, Summary: Methods For Handling, Nondifferentiable Convex Optimization Problems Directly, Decomposition Methods, Separable Problem, Complicating Variable, Primal Decomposition, Primal Decomposition Algorithm, Example (Using Primal Decomposition), Aside: Newton's Method With A Complicating Variable, Dual Decomposition, Dual Decomposition Algorithm

 
Lecture 9 - Comments: Latex Typesetting Style

Comments: Latex Typesetting Style, Recap: Primal Decomposition, Dual Decomposition, Dual Decomposition Algorithm, Finding Feasible Iterates, Interpretation, Decomposition With Constraints, Primal Decomposition (With Constraints) Algorithm, Example (Primal Decomposition With Constraints), Dual Decomposition (With Constraints), Dual Decomposition (With Constraints) Algorithm, General Decomposition Structures, General Form, Primal Decomposition (General Structures), Dual Decomposition (General Structures), A More Complex Example, Aside: Pictorial Representation Of Primal And Dual Decomposition

 
Lecture 10 - Decomposition Applications

Decomposition Applications, Rate Control Setup, Rate Control Problem, Rate Control Lagrangian, Aside: Utility Functions, Rate Control Dual, Dual Decomposition Rate Control Algorithm, Generating Feasible Flows, Convergence Of Primal And Dual Objectives, Maximum Capacity Violation, Single Commodity Network Flow Setup, Network Flow Problem, Network Flow Lagrangian, Network Flow Dual, Recovering Primal From Dual, Dual Decomposition Network Flow Algorithm, Electrical Network Analogy, Example: Minimum Queueing Delay, Optimal Flow, Convergence Of Dual Function, Convergence Of Primal Residual, Convergence Of Dual Variables, Aside: More Complicated Problems

 
Lecture 11 - Sequential Convex Programming

Sequential Convex Programming, Methods For Nonconvex Optimization Problems, Sequential Convex Programming (SCP), Basic Idea Of SCP, Trust Region, Affine And Convex Approximations Via Taylor Expansions, Particle Method, Fitting Affine Or Quadratic Functions To Data, Quasi-Linearization, Example (Nonconvex QP), Lower Bound Via Lagrange Dual, Exact Penalty Formulation, Trust Region Update, Nonlinear Optimal Control, Discretization, SCP Progress, Convergence Of J And Torque Residuals, Predicted And Actual Decreases In Phi, Trajectory Plan, 'Difference Of Convex' Programming, Convex-Concave Procedure

 
Lecture 12 - Recap: 'Difference Of Convex' Programming

Recap: 'Difference Of Convex' Programming, Alternating Convex Optimization, Nonnegative Matrix Factorization, Comment: Nonconvex Methods, Conjugate Gradient Method, Three Classes Of Methods For Linear Equations, Symmetric Positive Definite Linear Systems, CG Overview, Solution And Error, Residual, Krylov Subspace, Properties Of Krylov Sequence, Cayley-Hamilton Theorem, Spectral Analysis Of Krylov Sequence

 
Lecture 13 - Recap: Conjugate Gradient Method

Recap: Conjugate Gradient Method, Recap: Krylov Subspace, Spectral Analysis Of Krylov Sequence, A Bound On Convergence Rate, Convergence, Residual Convergence, CG Algorithm, Efficient Matrix-Vector Multiply, Shifting, Preconditioned Conjugate Gradient Algorithm, Choice Of Preconditioner, CG Summary, Truncated Newton Method, Approximate Or Inexact Newton Methods, CG Initialization, Hessian And Gradient, Methods, Convergence Versus Iterations, Convergence Versus Cumulative CG Steps, Truncated PCG Newton Method, Extensions

 
Lecture 14 - Methods (Truncated Newton Method)

Methods (Truncated Newton Method), Convergence Versus Iterations, Convergence Versus Cumulative CG Steps, Truncated PCG Newton Method, Truncated Newton Interior-Point Methods, Network Rate Control, Dual Rate Control Problem, Primal-Dual Search Direction (BV Section 11.7), Truncated Netwon Primal-Dual Algorithm, Primal And Dual Objective Evolution, Relative Duality Gap Evolution, Relative Duality Gap Evolution (N = 10^6), L_1-Norm Methods For Convex-Cardinality Problems, L_1-Norm Heuristics For Cardinality Problems, Cardinality, General Convex-Cardinality Problems, Solving Convex-Cardinality Problems, Boolean LP As Convex-Cardinality Problem, Sparse Design, Sparse Modeling / Regressor Selection, Estimation With Outliers, Minimum Number Of Violations, Linear Classifier With Fewest Errors, Smallest Set Of Mutually Infeasible Inequalities, Portfolio Investment With Linear And Fixed Costs, Piecewise Constant Fitting, Piecewise Linear Fitting, L_1-Norm Heuristic, Example: Minimum Cardinality Problem, Polishing, Regressor Selection

 
Lecture 15 - Recap: Example: Minimum Cardinality Problem

Recap: Example: Minimum Cardinality Problem, Interpretation As Convex Relaxation, Interpretation Via Convex Envelope, Weighted And Asymmetric L_1 Heuristics, Regressor Selection, Sparse Signal Reconstruction, L_1-Norm Methods For Convex-Cardinality Problems Part II, Total Variation Reconstruction, Total Variation Reconstruction, TV Reconstruction, L_2 Reconstruction, Iterated Weighted L_1 Heuristic, Sparse Solution Of Linear Inequalities, Detecting Changes In Time Series Model, Time Series And True Coefficients, TV Heuristic And Iterated TV Heuristic, Extension To Matrices, Factor Modeling, Trace Approximation Results, Summary: L_1-Norm Methods

 
Lecture 16 - Model Predictive Control

Model Predictive Control, Linear Time-Invariant Convex Optimal Control, Greedy Control, 'Solution' Via Dynamic Programming, Linear Quadratic Regulator, Finite Horizon Approximation, Cost Versus Horizon, Trajectories, Model Predictive Control (MPC), MPC Performance Versus Horizon, MPC Trajectories, Variations On MPC, Explicit MPC, MPC Problem Structure, Fast MPC, Supply Chain Management, Constraints And Objective, MPC And Optimal Trajectories, Variations On Optimal Control Problem

 
Lecture 17 - Stochastic Model Predictive Control

Stochastic Model Predictive Control, Causal State-Feedback Control, Stochastic Finite Horizon Control, 'Solution' Via Dynamic Programming, Independent Process Noise, Linear Quadratic Stochastic Control, Certainty Equivalent Model Predictive Control, Stochastic MPC: Sample Trajectory, Cost Histogram, Simple Lower Bound For Quadratic Stochastic Control, Branch And Bound Methods, Methods For Nonconvex Optimization Problems, Branch And Bound Algorithms, Comment: Example Problem

 
Lecture 18 - Recap: Branch And Bound Methods, Basic Idea, Unconstrained, Nonconvex Minimization

Announcements, Recap: Branch And Bound Methods, Basic Idea, Unconstrained, Nonconvex Minimization, Lower And Upper Bound Functions, Branch And Bound Algorithm, Comment: Picture Of Branch And Bound Algorithm In R^2, Comment: Binary Tree, Example, Pruning, Convergence Analysis, Bounding Condition Number, Small Volume Implies Small Size, Mixed Boolean-Convex Problem, Solution Methods, Lower Bound Via Convex Relaxation, Upper Bounds, Branching, New Bounds From Subproblems, Branch And Bound Algorithm (Mixed Boolean-Convex Problem), Minimum Cardinality Example, Bounding X, Relaxation Problem, Algorithm Progress, Global Lower And Upper Bounds, Portion Of Non-Pruned Sparsity Patterns, Number Of Active Leaves In Tree, Global Lower And Upper Bounds,

 


Source: http://academicearth.org/courses/convex-optimization-ii

Textul de mai sus reprezinta un extras din "Convex Optimization II". Pentru versiunea completa a documentului apasa butonul Download si descarca fisierul pe calculatorul tau. Prin descarcarea prezentei lucrari stiintifice, orice utilizator al site-ului www.studentie.ro declara si garanteaza ca este de acord cu utilizarile permise ale acesteia, in conformitate cu prevederile legale ablicabile in domeniul proprietatii intelectuale si in domeniul educatiei din legislatia in vigoare.

In cazul in care intampini probleme la descarcarea fisierului sau documentul nu este nici pe departe ceea ce se doreste a fi te rugam sa ne anunti. Raporteaza o eroare

Important!

Referatele si lucrarile oferite de Studentie.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Jacheta usoara verde oliv inchis Jacheta usoara verde oliv inchis Descriere produs:Tip: jachetaCuloare: verde oliv inchisMaterial: usorDetalii: margini...
Jacheta usoara violet inchis Jacheta usoara violet inchis Descriere produs:Tip: jachetaCuloare: violet inchisMaterial: usorDetalii: margini...
Camasa alba in dungi Camasa alba in dungi Descriere produs:- camasa alba cu dungi albastre- imprimeu text pe partea din spate- guler...