🎯

Convex Optimization Problems

Standard forms, optimality conditions, and problem transformations.

📋

1. Standard Form

The Optimization Problem

minimize    \( f_0(x) \)

subject to   \( f_i(x) \leq 0, \quad i=1, \dots, m \)

                   \( h_i(x) = 0, \quad i=1, \dots, p \)

  • \( x \): Optimization Variable
  • \( f_0 \): Objective Function (or Cost Function)
  • \( f_i(x) \leq 0 \): Inequality Constraints
  • \( h_i(x) = 0 \): Equality Constraints
Domain: \( \mathcal{D} = \bigcap \textbf{dom } f_i \cap \bigcap \textbf{dom } h_i \)

Feasibility

  • Feasible Point: An \( x \in \mathcal{D} \) satisfying all constraints.
  • Feasible Set: The set of all feasible points.
  • Infeasible: If the feasible set is empty (\( p^* = \infty \)).

Optimal Value \( p^* \)

\[ p^* = \inf \{ f_0(x) \mid x \text{ is feasible} \} \]

If \( p^* = -\infty \), the problem is unbounded below.

💡

2. Simple Examples

\( f_0(x) = 1/x \)

Domain: \( \mathbb{R}_{++} \)

Feasible Set: \( (0, \infty) \)
Optimal Value \( p^* \): 0
Achieved? No

Approaches 0 but never reaches it.

\( f_0(x) = -\log x \)

Domain: \( \mathbb{R}_{++} \)

Feasible Set: \( (0, \infty) \)
Optimal Value \( p^* \): \( -\infty \)
Bounded Below? No

\( f_0(x) = x \log x \)

Domain: \( \mathbb{R}_{++} \)

Feasible Set: \( (0, \infty) \)
Optimal Value \( p^* \): \( -1/e \)
Achieved? Yes

At \( x = 1/e \).

🔄

3. Equivalent Problems

Two problems are equivalent if the solution of one can be easily found from the solution of the other.

Common Transformations

  • Scaling: Minimizing \( f_0(x) \) is equivalent to minimizing \( \alpha f_0(x) \) for \( \alpha > 0 \).
  • Change of Variables: Let \( x = \phi(z) \) where \( \phi \) is one-to-one. Solve for \( z \), then get \( x \).
  • Monotone Transformation: Minimizing \( f_0(x) \) is equivalent to minimizing \( \psi(f_0(x)) \) if \( \psi \) is increasing (e.g., \( \log \), \( \exp \)).

Example: Box Constraints

Constraints \( l_i \leq x_i \leq u_i \) can be rewritten in standard form:

\( l_i - x_i \leq 0 \)
\( x_i - u_i \leq 0 \)

Slack Variables

Convert inequality \( f_i(x) \leq 0 \) to equality by adding a non-negative slack variable \( s_i \geq 0 \):

\[ f_i(x) + s_i = 0 \]
💎

4. Convex Optimization Problem

Definition

A standard optimization problem is a Convex Optimization Problem if:

  1. The objective function \( f_0(x) \) is convex.
  2. The inequality constraints \( f_i(x) \) are convex.
  3. The equality constraints \( h_i(x) = a_i^T x - b_i \) are affine.

🔍 Spot the Mistake!

Consider this problem:

minimize    \( x_1^2 + x_2^2 \)
subject to   \( x_1 / (1 + x_2^2) \leq 0 \)
                   \( (x_1 + x_2)^2 = 0 \)

Is this a convex optimization problem in standard form?

Yes, because the objective is convex.
No, the equality constraint is not affine.

5. Quasiconvex Optimization

A problem is quasiconvex if:

  • The inequality constraints \( f_i(x) \) are convex.
  • The equality constraints are affine.
  • The objective function \( f_0(x) \) is quasiconvex.

Quasiconvex functions have convex sublevel sets (e.g., "bowl-shaped" but maybe flat or monotonic).

🔑

6. Optimality Conditions

General Criterion

For a differentiable convex objective \( f_0 \), a point \( x \) is optimal if and only if \( x \) is feasible and:

\[ \nabla f_0(x)^T (y - x) \geq 0 \quad \text{for all feasible } y \]

Geometric interpretation: The gradient makes an obtuse angle with any vector pointing into the feasible set.

Unconstrained Problem

If there are no constraints, the condition reduces to:

\[ \nabla f_0(x) = 0 \]

Necessary and sufficient for convex problems.

Equality Constraints Only

Minimize \( f_0(x) \) subject to \( Ax = b \).

Optimality condition (Lagrange):

\[ \nabla f_0(x) + A^T \nu = 0 \]

Gradient must be orthogonal to the nullspace of A.

Example: Unconstrained Quadratic

Minimize \( f_0(x) = \frac{1}{2}x^T P x + q^T x + r \) with \( P \succeq 0 \).

Optimality condition: \( Px + q = 0 \).

  • If \( P \succ 0 \), unique solution \( x^* = -P^{-1}q \).
  • If \( P \) is singular, solution exists only if \( q \in \mathcal{R}(P) \).
📚

7. Optimization Model Classes

Linear Programming (LP)

Objective and constraints are all affine.

minimize    c^T x + d
subject to   Gx \leq h
                   Ax = b
Example: The Diet Problem

Find the cheapest diet satisfying nutrient requirements.

  • Variables: Amounts of different foods \( x_j \).
  • Objective: Minimize cost \( c^T x \).
  • Constraints: Nutrient intake \( \geq \) required limits; \( x \geq 0 \).

Quadratic Programming (QP)

Convex quadratic objective, affine constraints.

minimize    (1/2)x^T P x + q^T x + r
subject to   Gx \leq h, \quad Ax = b
Quadratically Constrained QP (QCQP)

Constraints are also convex quadratics (intersections of ellipsoids).

subject to   (1/2)x^T P_i x + q_i^T x + r_i \leq 0

Second Order Cone Programming (SOCP)

Includes constraints on the norm of affine functions (cones).

subject to   || A_i x + b_i ||_2 \leq c_i^T x + d_i

Generalizes LP and QCQP.

Semidefinite Programming (SDP)

Optimization over the cone of positive semidefinite matrices.

minimize    tr(C X)
subject to   tr(A_i X) = b_i, \quad X \succeq 0

Constraints are Linear Matrix Inequalities (LMIs).

←

Previous Chapter

Convex Functions

Next Chapter

Duality

→