2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Michael Grant Oct 30 '14 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$ – Ufuk Can Bicici Oct 30 '14 at 17:27
  • 1
    $\begingroup$ Yes, those are equivalent. Each $h_i(x)$ would just be a row of $Ax-b$. $\endgroup$ – Michael Grant Oct 30 '14 at 18:13
  • $\begingroup$ Thanks, that solved the connection for me! I would upvote your comment twice if it were possible :) $\endgroup$ – Ufuk Can Bicici Oct 30 '14 at 19:13
2
$\begingroup$
  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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.