Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 6

Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 6

Quasi-convex Optimization

  • Be cautious as local minima may not be global minima.
  • To solve, introduce a function whose zero sublevel set is the T sublevel set of the original function. This function must be convex.
  • Use bisection to find the optimal value of the objective.

Linear Programming (LP)

  • Minimize an affine function subject to a set of affine inequality constraints.
  • Equivalent to minimizing a linear function over a polyhedron.
  • Widely used in various fields such as scheduling and supply chain management.
  • Historical example: the diet problem (choosing quantities of different foods to meet certain nutrient requirements at the lowest cost).

Piece-wise Linear Minimization Problems

  • Can be converted to LPs using the epigraph form.

Finding the Largest Inscribed Ball in a Polyhedron (Chebyshev Center)

  • Involves maximizing an inner product over a ball, which can be solved efficiently.

Quadratic Programs (QP)

  • Have linear constraints and a convex quadratic objective.
  • Can be used to solve linear programming problems with linear constraints.
  • Can also be used to solve problems with random costs.
  • Risk-adjusted cost is used to account for the variance of the cost induced by the choice of variables.
  • Minimizing risk-adjusted cost with a positive risk aversion parameter is called risk-averse optimization, while minimizing risk-adjusted cost with a negative risk aversion parameter is called risk-seeking optimization.
  • Don't use gamma as -0.1 as it makes the problem non-convex.

QCQP (Quadratically Constrained Quadratic Programming)

  • An optimization problem with convex quadratic constraints.

SOCP (Second-Order Cone Programming)

  • A generalization of LP (Linear Programming) that includes QCQP and many other problems.
  • Often used to solve problems that can be reduced to it, even if they don't appear to be SOCP at first glance.

Robust Linear Programming

  • Deals with uncertain inequalities by fitting ellipsoids to the uncertain parameters.

Stochastic Models

  • Consider random variables and aim to satisfy constraints with a specified probability.

Geometric Programming (GP)

  • Involves transforming a non-convex problem into an equivalent convex problem through a change of variables.
  • Has its own terminology, such as "monomial" and "posynomial", which differ from standard mathematical definitions.
  • Involves minimizing a posynomial objective function subject to equality constraints.
  • Practical applications are found in fields such as wireless systems, circuit design, and engineering design.

Semi-definite Programming (SDP)

  • A type of conic form problem where the cone K is the cone of positive semi-definite matrices.
  • Extends LP and SOCP.
  • Can be used to solve problems such as minimizing the maximum eigenvalue of a matrix or minimizing the induced two-norm of a matrix over an affine set.

Overwhelmed by Endless Content?