Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

1
vote
1answer
65 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
1
vote
1answer
46 views

A minimization problem [duplicate]

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \|\frac{w}{x}\|,~w,u\in R^n$$ where $$\frac{w}{x}=(\frac{w_1}{x_1},\dots, \frac{w_n}{x_n})$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ Given $u$, $x$ and $\beta$, ...
1
vote
1answer
89 views

Supporting hyperplanes Theorem in Boyd's Convex Optimization

On page 51, the authors applied the separating hyperplane theorem to the sets ${x_0}$ and the interior of $C$ to prove the supporting hyperplanes theorem (assuming the interior of $C$ is nonempty). ...
1
vote
1answer
51 views

Is this function convex or not?

Is this function convex ? $$ f(\mathbf y) = { \left| \sum_{i=1}^{K} y_i^2e^{-j\frac{2\pi}Np_il} \right| \over\sum_{i=1}^{K}y_i^2} $$ where : $ P = \{p_1,p_2,\cdots,p_K\} \subset\{1,2,\cdots,N\} $ I ...
1
vote
1answer
286 views

Convexity of the squared Frobenius norm of a matrix

I was reading this paper where the define an optimization problem as where K and L are kernel matrices and $\pi$ is the permutation matrix. They have explained that the function is convex because ...
0
votes
0answers
44 views

Confusion related to convexity of a quadratic function

Lets say I have the following function of X $f(X) = (AX^TBX)$ I didn't get why matrices A and B need to be psd to make f(X) convex. Clarifications guys
1
vote
0answers
53 views

Duality in Chebychev approximation

I got messed up with this problem and can't find any clue to solve this. Hope some one here can help me. Let $A$ be an $m \times n$ matrix an let $b$ be a vector in $R^{m}$. We consider the ...
2
votes
1answer
33 views

Confusion related to explanation of convexity of a function

I was reading this paper where the define an optimization problem as where K and L are kernel matrices and $\pi$ is the permutation matrix. They have explained that the function is convex because ...
0
votes
1answer
678 views

Optimization of a function of two variables.

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant ...
1
vote
0answers
39 views

Looking for a “Neat” Transform to Yield a Convex Set

Optimizing on a unit sphere $\mathbb{S}^n$ is almost a convex problem (if the function is convex in the new set) if we make our "new" set $\mathbb{R}^n$, via the stereographic projection. Clearly ...
2
votes
2answers
118 views

Prove Convexity of Recursively Defined Function

Let $\mathbf{x}=[x_1, x_2, \dots, x_K]\in\mathbb{R}^K_{++}$ and $E_1>E_2>\dots>E_K>0$ are positive constants. If $$f_i:\mathbb{R}^K_{++}\rightarrow\mathbb{R}_{++}\quad\forall1\leq i\leq ...
1
vote
0answers
125 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
3
votes
1answer
108 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
1
vote
1answer
46 views

suggest globally quasi-convex function

Can you suggest a function $f:R^2\to R, f\in C^2$, such that $f$ is globally quasi-convex (all its group sets are convex), but at no point convex?
1
vote
0answers
66 views

Maximum of the expectation of a concave function

Let's have a function $f(x, \theta)$, and some probability distribution on $x$. Let's say I have found $\theta^* = \operatorname{argmax}(f(E[x], \theta) $, and $f$ is concave in $x$. I would like to ...
1
vote
0answers
25 views

An Optimization problem related with $(-1)^{N-1}\sum_{i=1}^M\frac{\ln x_{i}}{x_{i}^N}\prod_{j\neq i}\frac{x_i}{x_i-x_j}$

I encountered an optimization problem \begin{align} f(x)=(-1)^{N-1}\sum_{i=1}^M\frac{\ln x_{i}}{x_{i}^N}\prod_{j\neq i}\frac{x_i}{x_i-x_j} \end{align} where $N$ is a positive integer, $x_i>0$ for ...
2
votes
0answers
81 views

are elementary symmetric polynomials concave on probability distributions?

Let $S_{n,k}=\sum_{S\subset[n],|S|=k}\prod_{i\in S} x_i$ be the elementary symmetric polynomial of degree $k$ on $n$ variables. Consider this polynomial as a function, in particular a function on ...
1
vote
2answers
67 views

When $\min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y)$?

When $$ \min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y) \qquad? $$ I mean when we are minimizing a function with respect to two variables, under what conditions we are allowed to ...
1
vote
1answer
68 views

Is this function involving matrices convex?

Let $X\in \mathbb{R}^{n \times n}$. Then, is the function $$ \text{Tr}\left( (X^T X )^{-1} \right)$$ convex in $X$? ($\text{Tr}$ denotes the trace operator)
2
votes
0answers
57 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
1
vote
1answer
67 views

Quadratic integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
2
votes
1answer
137 views

Find conjugate indicator function

I'm doubt with this problem. Let $C=\left\{(x,y)\in \mathbb{R}^2|x+\frac{y^2}{2}\le 0\right\}$. I have to find $I_C^{*}(Y)$ defined by $I_C^{*}(Y)=\sup_{X \in \mathbb{R}^2} \left\{\langle ...
1
vote
1answer
111 views

Convex conjugate of absolute affine function?

Let $f:\mathbb{R}^n \rightarrow \mathbb{R} \cup \{ \infty \}$ be a convex function. The convex conjugate of $f$, which we call $f^*$ is defined as $f^*(y)=\sup \, \left \{ \langle y,x \rangle -f(x) ...
2
votes
1answer
75 views

Convex analysis problem

I have the following problem. Let $f:[a,b]\to \mathbb{R}$ be continuously convex. I have to prove that there exists $c\in (a,b)$ such that $$\frac{f(a)-f(b)}{b-a}\in \partial f(c)$$ Firstly, I'm ...
6
votes
1answer
107 views

Can we test whether a polynomial only takes non-negative values on the non-negative orthant?

EDIT: Feel free to replace "non-negative on the non-negative orthant" with "non-negative on a convex set, cone, or any other class of sets that includes the orthant". A popular way to establish that ...
3
votes
1answer
61 views

Rewrite constrained optimization objective

I wanted to ask, under which conditions can one rewrite the optimization objective $\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$ as $\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$ I have particular interest ...
1
vote
1answer
160 views

Characterization of Subset Sum via Linear Programming

I have a sample subset sum problem. Given numbers $x_1, x_2... x_N$ and a target value to sum to $x_S$ Minimize $x_S - x_1y_1 - x_2y_2 - x_3y_3 ... x_Ny_N$ such that 0 <= $y_1$ <= 1 0 <= ...
3
votes
1answer
128 views

optimizing a logdet function with respect to a scalar and the Hessian matrix

Given a logdet function $\mathcal{L}(\gamma)$, $$ \mathcal{L}(\gamma) = \log\vert \mathbf{I} + \gamma\mathbf{S} \vert - \mathbf{q}^T(\gamma^{-1}\mathbf{I} + \mathbf{S})^{-1} \mathbf{q}, $$ where ...
2
votes
0answers
20 views

Analogue of Helly’s theorem for non-exact interpolation

Let $\overrightarrow{x}=(x_1,x_2, \ldots ,x_n),\overrightarrow{a}=(a_1,a_2, \ldots ,a_n)$ and $\overrightarrow{b}=(b_1,b_2, \ldots ,b_n)$ be vectors in ${\mathbb R}^n$, with $a_k \leq b_k$ for every ...
1
vote
2answers
71 views

How many methods for smoothing an unsmoothed function?

Which is the simplest one? For example, we smooth $f(x)=|x|$ to $$f(x)=\begin{cases} \frac{x^2}{\epsilon}+\frac{\epsilon}{2} & |x| \le \epsilon\\ |x| & |x|\ge epsilon ...
0
votes
2answers
46 views

Distance between convex set and non-convex set?

So in http://en.m.wikipedia.org/wiki/Shapley%E2%80%93Folkman_lemma there is some talk about distance between a mintowksi sum and a convex set. But I couldn't get how distance is being defined. Can ...
1
vote
0answers
223 views

Error on optimization problem, maximize log determinant on CVX

$A$ is an $N \times N$ complex matrix $W$ is an $N \times N$ complex matrix $C$ is an $N \times N$ complex diagonal matrix $u$ is a scalar $V$ is an $N \times N$ complex matrix, whose diagonal elects ...
0
votes
1answer
52 views

A reference to learn about duality

I am interested in learning about duality in convex optimization. I am looking for something to read which is: Reasonably short. Fairly self-contained (if it is a chapter in a textbook, I would ...
0
votes
1answer
62 views

convex function, inequality

If $f: R^n\rightarrow R$ is convex and $f(\alpha x)=\alpha f(x), \alpha \geq 0$, show that: a) $f(x+y)\leq f(x)+f(y)$ for all $x,y\in R^n$ b) $f(0)\geq 0$ c) $f(-x)\geq -f(x)$ for all $x\in R^n$ d) ...
1
vote
1answer
50 views

Proof of convexity of a function

I have to prove that function $J(x)=e^{x^3+x^2+1}$ is convex on $[0,\infty]$. I used a Theorem which says: **$U\subset R^n$ is convex set with non-empty interior and $J\in C^2(U)$. Function $J$ is ...
1
vote
2answers
616 views

Carathéodory's theorem

Carathéodory's theorem says "If $C\subset R^n$, then every point from ${\rm conv}\; C$ can be expressed as a convex combination at the most of $n+1$ elements from $C$" In every proof I found, it ...
1
vote
0answers
105 views

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 ...
2
votes
2answers
182 views

Optimize a log det function with respect to a matrix, and the saddle point analysis

Suppose I want to to find the local minima of a logdet function $\mathcal{L}$ with respect to a Matrix $\mathbf{A}$, $$ \mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - ...
1
vote
1answer
134 views

Sparse least-squares fitting of discrete probability distributions

I have an optimization problem involving $n$ discrete probability distributions and I am looking for a suitable solution for this problem that I can implement as computer program. Let the vector ...
0
votes
1answer
39 views

convexity of two linear spaces connected by a convex equality constraint

If there are two sets of linear constraints in different variables, Ax <= b with x_l <= x <= x_u and Cy <= d with y_l <= y <= y_u, and a set of equality constraints of a specific ...
0
votes
1answer
91 views

maximization of a Strictly convex function

The things we know, usually minimization of a convex function, unique solution will exist. My question is, maximization of a strictly convex function, will that give an unique maximum? If so how we ...
1
vote
1answer
157 views

formulate this scheduling problem as linear programming problem

Sorry if this very silly, but i am something new to optimization theory: We have $m$ identical Machines and $n$ jobs. A job $j$ can be done in any of the identical machines in $p_{j}$ time units. ...
0
votes
1answer
92 views

Composition of a convex function

If $f:[a,b]\rightarrow R$ is convex function and $f'(x)\geq 0$ for all $x\in [a,b]$ and $g:U\rightarrow [a,b]$ is convex function, how to show that $f(g(u)), u\in U$ is convex function?
2
votes
1answer
35 views

supremum of an array of a convex functions

If $\{J_n\}$ is an array of a convex functions on a convex set $U$ and $G(u)=\sup J_i(u), u\in U$, how to show that $G(u)$ is convex too? I've done this, but I am not sure about properties of a ...
1
vote
0answers
104 views

Confusion related to optimization of log(det(X)) function

I have this confusion related to optimization of the log(det(X)) function. I didn't get how it implicitly maintains the constraint of X being positive definite. For eg if I have a matrix ...
1
vote
1answer
46 views

Convexity of expected value

I am trying to understand if the expected value of a variable is convex in that variable or not. I know that expectation is a linear operator, so must be convex. But I do not see why it does not ...
0
votes
1answer
230 views

Convex homogeneous function

Prove (or disprove) that any CONVEX function $f$, with the property that $\forall \alpha\ge 0, f(\alpha x) \le \alpha f(x)$, is positively homogeneous; i.e. $\forall \alpha\ge 0, f(\alpha x) = \alpha ...
3
votes
1answer
207 views

Show that any convex function is locally bounded

Show that a convex function $f:\mathbb{R}^n \rightarrow \overline{\mathbb{R}}$ is bounded in a neighborhood of $x\in \text{ri}(\text{dom}(f))$. Showing that it has an upper bound is not difficult ...
1
vote
1answer
116 views

Is the following optimization problem convex?

I'm not an mathematician so sorry for the possibly trivial question. I have written the following integer programming model: \begin{align} \max z &= \sum_{i=1}^M \left(\sum_{j=1}^N b_j x_{ij}- ...
0
votes
1answer
30 views

in the derivation of support vector classifier

I was studying the Stephen Boyd's textbook on convex optimization and have a question on the support vector classifier. The book says the following: In linear discrimination, we seek an affine ...