斯坦福大学凸优化课程笔记-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

example

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)$

course goals and topics

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

nonlinear optimization

traditional techniques for general nonconvex problems involve compremises