Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function. Linear Programming is a special case. Convex Optimization problems as a class are easier to solve numerically than general mathematical optimization problems.

The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:

  • Least squares
  • Linear programming
  • Convex quadratic minimization with linear constraints
  • Quadratic minimization with convex quadratic constraints
  • Conic optimization
  • Geometric programming
  • Second order cone programming
  • Semidefinite programming
  • Entropy maximization with appropriate constraints
7419 questions
0
votes
1 answer

Representing a convex function as the supermum of affine functions

In Section 3.2 of Convex Optimization by Stephen Boyd and Lieven Vandenberghe, it shows that a convex function could be represented as the supermum of affine functions: I don't quite understand the difference between variable $x$ and $z$ here. In…
YuzheChen
  • 189
  • 9
0
votes
0 answers

Convex Optimization Affine Linear

i'm reading a book of "Ulbrich" about Nonlinear Optimization. In the chapter about convex optimization he says, given a NLP $$\min f(x), s.t. g(x) \leq 0, h(x) = 0,$$ the NLP is convex if $f,g_i$ are convex functions and $h$ is affine ly…
Dom
  • 9
0
votes
0 answers

Projection onto closed convex sets' equivalent condition.

Prop: Let $S\subset \mathbf{R}^n$ be non–empty, closed, and convex. Given any $x\in\mathbf{R}_n$, we have $z^*=\arg\min_{z\in S}\|z-x\|_2$ iff $z^*\in S$ and $(z − z^*)^T(x − z^*)\le 0$ for all $z \in S$. For this proposition, I know how to prove…
Xuchuang
  • 49
0
votes
0 answers

Convex conjugate of a convex function composed with a linear map

Let $f: \textbf{Y}\rightarrow \bar{\mathbb{R}}$ be a proper closed convex function, $\mathcal{A}: \textbf{E}\rightarrow \textbf{Y}$ be a linear map. Define $g(x)=f(\mathcal{A}x)$. I need to show that $g^*$ is the closed envelope of the function…
kkcocoqq
  • 306
0
votes
1 answer

Is the weighted graph matching problem a convex problem?

According to Umeyama, the weighted graph matching problem can be formulated as $min_P || PA_GP^T - A_H ||$ s.t. $P$ is a doubly stochastic matrix where $A_G$ and $A_H$ are n-by-n matrices How can we show the convexity of this problem?
Rein
  • 1,174
0
votes
1 answer

How are these two optimization problems equivalent?

I'm trying to show that the two problems are equivalent Let $\Bbb A = \{A_1, \dots, A_n\}$ where $A_i \in \Bbb R^{m \times n}$ and $b\in \mathbb{R}^m$ Then $$\min_{x\in \mathbb{R}^n} \max_{i=1, \dots, k} \|A_ix - b\|$$ is equivalent to…
Oliver G
  • 4,792
0
votes
0 answers

(Geometric and arithmetic mean)How to prove the function $G(x)-\alpha A(x)$ is concave?

The geometric and arithmetic means of $x\in R^n_+$ are, respectively, $$G(x)=(\prod^n_{i=1}x_i)^{1/n},\quad A(x)=\frac{1}{n}\sum^n_{i=1}x_i$$ Suppose $0\leq \alpha\leq 1$, how to prove the function $G(x)-\alpha A(x)$ is concave? I try to solve it by…
Noilyn
  • 1
0
votes
0 answers

nonsymmetric cone and Euclidean Jordan Algebra

I have a mathematical constraint which is a summation of exponential functions: $f = e^{x + y}$. Function $f$ is obviously convex. However, when I include this constraint in my model, MOSEK complains that the constraints with equations $f$ is a non…
P. Khoza
  • 41
0
votes
1 answer

If $f$ is convex in $x$ and $z$, how is $\sup_x(x^Ty - \inf_z f(x,z)) = \sup_{x,z}(x^Ty - f(x,z))$?

From Convex Optimization by Boyd and Vanderberghe: If $f$ is convex in $x$ and $z$, then $$\sup_x(x^Ty - \inf_z f(x,z)) = \sup_{x,z}(x^Ty - f(x,z))$$ How are these equal? It seems like they would not be equal as the smallest $z$ may be different…
Oliver G
  • 4,792
0
votes
1 answer

$x^Ty \le 1$ for all $y$ with $||y||_2 = 1$ iff $||x||_2 \le 1$

$x^Ty \le 1$ for all $y$ with $||y||_2 = 1$ iff $||x||_2 \le 1$ I can prove $\Leftarrow$ but I can't see a way to prove $\Rightarrow$. I start with Cauchy's inequality and have $x^Ty \le ||x||_2 ||y||_2 \le ||x||_2$ since $||y||=1$ but I can't…
Oliver G
  • 4,792
0
votes
0 answers

Why does the solution to one system imply the other system has a negative solution?

Consider two systems A and B: A$: f_i(x) \lt 0, i=1, \dots, m, Ax = b$ B$: \min_{\{x,s\}} s$ subject to $f_i(x) - s \le 0, i = 1, \dots, m; Ax = b$ Then B has optimal value $p^* \lt 0$ iff there exists a solution to A I can prove $\Rightarrow$ but…
Oliver G
  • 4,792
0
votes
2 answers

Why is the affine function $f(x) = a^T x + b$ log-concave on $\{x | a^Tx + b \gt 0\}$?

Why is the affine function $f(x) = a^T x + b$ log-concave on $\{x | a^Tx + b \gt 0\}$? I see that for it to be log-concave we must have: $$f(\theta x + (1-\theta)y) \ge f(x)^{\theta}f(y)^{1-\theta}$$ Therefore we must have $$a^T(\theta x +…
Oliver G
  • 4,792
0
votes
0 answers

Convexity and likelihood

I have the following function: $-logL(\beta|t,X)= -\sum_{n=1}^{N} \{t_n \cdot log(y_n) +(1-t_n)\cdot log(1-y_n)\}$ where $y_n=(1+exp(-x_n'\beta))^{-1}$ and where $\beta$ and $x_n$ are both kx1 vectors and $t$ is a vector of zeros (corresponding to…
giorgio
  • 5
0
votes
1 answer

Convex function necessary condition

For a function to be convex it should have a convex domain besides the first-order, second-order conditions. Why do we need that the domain of the function should also be convex? Edit: What I am trying to say is that its possible for a function to…
Shirin
  • 465
0
votes
1 answer

How can a function increase/decrease in a point?

I am working on exercise 4.6 in the book "Convex Optimization", which is as follows: Quiz description I don't understand what the author meant by saying a function h (similarly $f_0$, $f_i$) is monotonically decreasing in $x_r$ which is an element…
hoangtuansu
  • 23
1 2 3
…
24 25