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.
