斯坦福大學凸優化課程筆記-1

凸優化課程-1

introduction

• mathematical optimization
• list squares and linear programming
• convex optimization
• example
• course goals and topics
• nonlinear optimization
• brief history of conves optimization

optimization problem

objective function and optimization functoion

portfolio optimization 投資組合優化

• variables: amounts invested in different assets
• constraints: budget, investment per asset, minimum return
• objective : overall risk or return variance

device sizing in electronic circuits 電子線路的尺寸

• variables: device widths and lengths
• constraints: manufacting limits, timing requirements, maximum area
• objective : power consumption

data fitting 資料拟合 statistics estimation

• cariables: model parameters(不同之處)
• constraints: prior information, parameter limits
• objective: measure of misfit or prediction

some people use general optimization all the time

solving optimization problems (如何解決這類問題)

general optimization problem (一般的問題)

• very difficult to solve 十分難以解決
• methods involve some comprimise(very long time)

exceptions: certain problem can be solved efficiently and reliably

• least-squares problem 最小二乘問題
• linear programming problems 線性規劃問題
• convex optimization problems 凸優化問題

affine function 仿射函數

solving convex optimization problems

• no analytical solution
• reliable and efficient algorithms
• computation time (roughly) proportional to max{n3, n2m, F}, whereFis cost of evaluatingfi’s and their first and second derivatives
• almost a technology

using convex optimization

• often difficult to recognize
• many ticks for transforming problems into convex form
• surpridingly many problem can be solved via convex optimization

additional constraints: does adding 1 or 2 below complicate the problem?

• no more than half of the total power is in any 10 lamps
• no more than half of the lamps are on $ (p_j>0)$

goals

1. recognize formulate problem as convex optimization problems
2. develop code for problems of moderate size.
3. charactierize optimal solution, give limits of performance, etc.

topics

1. convex sets, functions, optimization problem
2. example and application
3. algorithms

traditional techniques for general nonconvex problems involve compremises