0
$\begingroup$

I am reading a tutorial about Convex Optimization and it defines the general Convex Optimization problem as:

$$ minimize_x f(x)$$ where $g_1(x) \leq 0, ... , g_m(x) \leq 0$ and $Ax=b$ and $x \in \mathbb{R}^n$. The cost function $f(x)$ and all constraint functions $g_1(x), ..., g_m(x)$ are convex functions.

I clearly see the following: The domain of the convex function $f$ is convex. Each $g_i$ defines a level set at $0$ with $\left\{x|g_i(x) \leq 0\right\}$. These sets are convex as well and the intersection of all of these are convex.

What I don't get exactly is the affine set $\left\{x|Ax = 0\right\}$. I have the following intuition: If we do not use an affine set to constrain the feasible region produced by $f$ and $g_i$ functions, then this region is always $n$ dimensional (has a basis of $n$ vectors). An affine set of $n-1$ dimensions is a hyperplane, an affine set with a dimension lesser than $n-1$ is an intersection of some hyperplanes. Additionally, an affine set is always convex. So, if we further constrain the feasible region generated by $f$ and $g_i$ functions with such an affine set, then we kind of "reduce" the dimensionality of the feasible region, without damaging its convexity (since the affine set is convex).

Is my idea correct? If not, what role does the affine set play here? Why do we need it in the determination of the feasible region?

$\endgroup$
2
$\begingroup$

The constraints of optimization problems are typically written as a system of equations and inequalities.

In order to ensure that the feasible region is convex, one assumes that the $g_i$ are convex, and the equation constraints are affine linear. That said, linear affine equations always yield a convex feasible set. Nonlinear equations as constraints might yield non-convex (and even disconnected) feasible sets.

$\endgroup$
  • $\begingroup$ Right. In fact, nonlinear equality constraints almost always produce nonconvex results. There is no requirement that a convex optimization problem has equality constraints; but if it does, they must be linear. $\endgroup$ – Michael Grant Oct 2 '14 at 12:36
  • 1
    $\begingroup$ So, since the only the affine equation constrains make up convex sets, we only use them as equations in our optimization system, is that right? $\endgroup$ – Ufuk Can Bicici Oct 2 '14 at 14:34
  • 1
    $\begingroup$ Yes, it is a class of functions that guarantee convex feasible sets. $\endgroup$ – daw Oct 2 '14 at 18:34
  • $\begingroup$ One more question: Are we allowed to use only a single affine equation constraint or more than one? I keep seeing such problems are formulated with many inequality constraints ($ g_i $ s) but I only see a single affine equation constraint. Couldn't it be the case that the feasible region determined by $ f $ and $ g_i $ s are intersected with more than one affine sets, determined by more than one $ Ax=b $ equations? $\endgroup$ – Ufuk Can Bicici Oct 3 '14 at 23:02
  • 1
    $\begingroup$ You can achieve that by enlarging the matrix $A$ and vector $b$. $\endgroup$ – daw Oct 4 '14 at 11:24

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.