Affine Functions as Equality Constraints in Convex Optimization Problems

3.8k Views Asked by At

I am studying an introduction to convex optimization. When defining a convex optimization problem, we have a convex objective function, $f(x)$, a set of convex functions $g_i(x)$ where the feasible region is the intersection of their $0$-sublevel sets, $G_i=\{x \mid g_i(x) \leq 0\}$.

We can have equality constraints as well, which are defined using affine functions $h_i$, where the constrained sets are $H_i=\{x \mid h_i(x)=0\}$. So the final feasible region for that problem should be $G_1 \cap G_2 \cap \dots \cap G_n \cap H_1 \cap \dots \cap H_m$. For $n$ inequality and $m$ equality constraints.

I have two questions about this definition of the convex optimization problem.

  1. As far as I know, in very general, an affine function is defined as $h(x) = Ax + b$, where $A$ is a $m \times n$ matrix and $x \in \mathbb{R}^n$. But since here we deal with scalar valued functions, due to the nature of the optimization problem, I assume that $h(x)$ functions should have the form of $h(x) = w^Tx + b$ where $b$ is just a scalar. Is this true?

  2. I have the following understanding about introducing the affine equality constraints into the problem. When the domain of the problem is $D$ dimensional, equality constraints introduce a $D-1$ dimensional surface limitation into the feasible region. This is a line in a two dimensional problem, a plane in a three dimensional problem and a hyperplane for higher dimensions, due to the form of the constraint $h(x) = w^Tx + b = 0$, assuming my first question is valid. Since the subset of $\mathbb{R}^D$ which belongs to a constraint must constitute a convex set, and a function of the form $h(x)=0$ defines a $D-1$ dimensional level surface in $\mathbb{R}^D$, the only way to make this surface convex is to define it as a hyperplane, which is what the affine function defines. Is this view about affine constraints correct?

Thanks in advance.

1

There are 1 best solutions below

0
On
  1. Collection of Scalar Linear Equations $ \left\{ {a}_{i}^{T} x - {b}_{i} = 0 \right\}_{i = 1}^{n} $ are equivalent of the system $ A x = b $ where $ {a}_{i} $ are the rows of $ A $.

  2. Correct.