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.

  • $\begingroup$ Hey man, math.se is for questions you haven't already answered for yourself! :-) Just kidding. Your thinking is sound. Keep in mind however that what you're looking at is a particular standard form for convex optimization. Alternatives include, for instance, maximizing a concave function, or more general inequality constraints $f(x)\leq g(x)$ where $f$ is convex and $g$ is concave. But yes, if you have equality constraints, they must involve affine expressions. $\endgroup$ Oct 30, 2014 at 17:05
  • $\begingroup$ Thanks for the answer, my questions go mostly unanswered these days :) Is it correct that as affine expressions for equality constraints we need to use $h(x)=w^Tx + b$ type "hyperplane" equations? For example, an another source says we can have an affine set constraint of the type $\{x|Ax=b\}$ instead, which is the solution set of a non-homogeneous system. But I think this set can be the shown as the intersection many $h_i(x)=w_i^T x + b_i$ type hyperplane equations to begin with. $\endgroup$ Oct 30, 2014 at 17:27
  • 1
    $\begingroup$ Yes, those are equivalent. Each $h_i(x)$ would just be a row of $Ax-b$. $\endgroup$ Oct 30, 2014 at 18:13
  • $\begingroup$ Thanks, that solved the connection for me! I would upvote your comment twice if it were possible :) $\endgroup$ Oct 30, 2014 at 19:13

1 Answer 1

  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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .