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
1
vote
0 answers

local minima and critical point for a convex function

I have learnt that all local extrema occur at critical points, but not all critical points occur at local extrema. That is the rationale where we find critical points when optimization a convex function. But consider $f(x) = x^2$ with $1\leq x\leq…
user155214
  • 804
1
vote
0 answers

Confusion related to derivation of soft thresholding

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf. It says the three unique solutions for $\operatorname{arg min} \|x-b\|_2^2 + \lambda\|x\|_1$ is given…
user34790
  • 4,192
1
vote
0 answers

Is the following optimization problem convex? something like a cosine similarity measure.

$$\begin{array}{ll} \underset{W}{\text{minimize}} & - \displaystyle\sum_{t=1}^T \frac{W^\top A a_t}{\| W^\top A \|_2 \| a_t \|_2}\\ \text{subject to} & \sum_{t=1}^T w_t =1\\ & w_t \geq 0 \text { for } t \in T\end{array}$$ where $W = [w_1,…
Alan
  • 13
  • 4
1
vote
1 answer

A list of techniques to find optimal point of an optimization problem algorithmically?

I am interested to collect and analyze a list of technique to find an optimal point of an optimization problem algorithmically as follows: Problem: Find a point where the gradient has non-negative inner product with any feasible direction at the…
Lakshman
  • 69
1
vote
1 answer

Related to Problem 2.12-e of Convex Optimization book (by Boyd)

I have a question from Boyd book - The set of points closer to one set than another, i.e., $\{x|\text{dist}(x,S) ≤ \text{dist}(x,T)\}$, where $S,T⊆R^n$, and $\text{dist(x,S)} = \inf\{|x−z|_2|z\in S\}$. In the solution manual of the convex…
XYZ
  • 35
1
vote
1 answer

Fenchel conjugate of $f(x)=\frac{1}{2}\|x-y\|^2$

Let $f(x)=\frac{1}{2}\|x-y\|^2$ and $\|\cdot\|$ be 2-norm. $x,y \in R^n$ Let the fenchel conjugate be defined as $f(z)=\sup_x(z^Tx -\frac{1}{2}\|x-y\|^2)$. Taking the derivative w.r.t. $x$ and setting it $0$: $z - (x-y)=0$ and $x=z+y$ Then the…
Emin Ozkan
  • 187
1
vote
1 answer

Strong convexity of $L_p$ induced Bregman divergence

I encountered the following claim regarding the strong convexity of Bregman divergence. Let $d$ be a sufficiently large integer. Let $p=1+1/\ln d\in (1,2]$ for sufficiently large $d$. For any $x,y\in\mathbb R^d_+$, define $D(x,y)$ as $$ D(x,y) :=…
Yining Wang
  • 1,279
  • 7
  • 23
1
vote
0 answers

K is proper cone. K is pointed?

In Boyd-Vandenberghe Convex Optimization and had a question about the proper cone. The following is the property of a proper cone: • K is convex. • K is closed. • K is solid, which means it has a nonempty interior. • K is pointed, which means that…
Art of Juking
  • 73
1
vote
0 answers

Search-space of a symmetric (in two variables) and a monotone vector function in $\mathbb{R}^3_{+}$

I have a function that is defined on only positive orthant $\mathbb{R}^3_{+}$. The function is monotonic increasing along any of three axis. (This is the same monotone vector function as defined on page 108 in Convex Optimization by Boyd…
kaka
  • 1,896
1
vote
0 answers

A bounded differentiable convex function is constant

I have to show that a bounded differentiable convex function $f: \Bbb R \rightarrow \Bbb R $ is constant. When a function $f$ is differentiable and convex, then I have a Theorem in my book that says, that: $ f(y) \ge f(x) + f'(x)(y-x) \quad \forall…
Hisaab1
  • 47
1
vote
1 answer

Proving variation of log-sum-exp is convex

Let $S$ be a proper subset of $\{1,\ldots,n\}$ and consider a function $$f(x_1,\ldots,x_n) = \log \sum_{i=1}^n e^{x_i} - \log \sum_{i \in S} e^{x_i},$$ so that the first term is a log-sum-exp function of n variables, and the second term is a…
Asterix
  • 567
1
vote
0 answers

Which methods of function continuation admit polynomial-time convex minimization?

The function $f$ maps the positive integer lattice in $\mathbb{R}^n$ (i.e. the vectors in $\mathbb{R}^n$ whose coordinates are all integers) to $\mathbb{R}$. We know that $f$ is convex. I want to come up with a function $g$ that is a continuation…
GMB
  • 4,186
1
vote
0 answers

Normal cone of a vertex

could someone please help me on the following exercise: Let $P ⊂ \mathbb{R}^n$ a polyhedron and $v$ a vertex of $P$. Show: $\textrm{dim}(N_P(v))=n$
MathStudent2
  • 21
1
vote
0 answers

Train Time-Table Optimization

A problem from Stephen Boyd's Convex Optimization class. It's a bit long, beware. The original of the problem is here, 18.22. Problem: We consider a transit system with $K$ trains, denoted $k = 1,..,K$. Each train $k$ travels over a route, which is…
BBSysDyn
  • 16,115
1
vote
1 answer

How would one show that the convex combinations of points from a convex set are also in that convex set.

I am aware of the theorem "a set C is convex iff any convex combination of points in C is in C" but I was wondering how to prove one side of this theorem, if a set C is convex how would you show that the convex combination of any points in C is also…
Abstract1999
  • 35
1 2 3
…
24 25