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

learn more… | top users | synonyms

1
vote
2answers
72 views

Absract convergence of a suboptimal version of steepest descent

I'm looking for a citable reference to fill in a gap in an intermediate step of a proof which requires convergence of a suboptimal version of steepest descent. The function $f:\bf{R}^n\to\bf{R}^n$ I ...
1
vote
1answer
117 views

Convex functions and Hahn-Banach application

Let $Z$ be a convex subset of a real vector space, and $f:Z \to \mathbb{R}^m$ be such that every component $f_i:Z \to \mathbb{R}$ is a convex function. Let $S:\mathbb{R}^m \to \mathbb{R}$ be defined ...
1
vote
1answer
47 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
100 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
367 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 ...
1
vote
1answer
47 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
1answer
70 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
145 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 ...
1
vote
1answer
192 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. ...
1
vote
1answer
52 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 ...
1
vote
1answer
129 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}- ...
1
vote
1answer
204 views

Convex set, continuous function

Show that set of continuous functions $f$ on interval $[a,b]\subset R$ such that $|f(x)|\leq 1$, $x\in [a,b]$, is convex in $C[a,b]$. I've done this: $f_1 (x)$, $f_2 (x)$ are continuous ...
1
vote
1answer
240 views

Why does the non-negative matrix factorization problem non-convex?

Supposing $\mathbf{X}\in\mathbb{R}_+^{m\times n}$, $\mathbf{Y}\in\mathbb{R}_+^{m\times r}$, $\mathbf{W}\in\mathbb{R}_+^{r\times n}$, the non-negative matrix factorization problem is defined as: ...
1
vote
1answer
41 views

Robust feasibility with halfspace?

Consider a convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$, such that for all $x \in \mathbb{R}^n$ we have $$ a_1^\top x + b_1 \leq f(x) \leq a_2^\top x + b_2 $$ for some given $a_1, a_2 ...
1
vote
1answer
48 views

Explain about convexity in geometry and in optimization.

My question is 'what is a difference between convexity in geometry and optimization?'
1
vote
1answer
188 views

Are these convex optimization problems equivalent?

Consider the optimization problem $$ \mathcal{P}_1: \qquad \min_{x \in \mathbb{R}^n} c^\top x \quad \text{sub. to } \ g(x,y_i) \leq 0 \ \ \forall i = 1,2,...,M$$ where $c \in \mathbb{R}^n$, and ...
1
vote
1answer
90 views

Convergence rate when solving L1 regularized optimization via coordinate descent with tiny step?

Wondering if there is an established result for the convergence rate when solving L1 regularized optimization via coordinate descent with tiny step? By "tiny step" I mean the step is always set to a ...
1
vote
1answer
225 views

Strongly convex function

There is a $\sigma$-strongly convex function, $f(x')\ge f(x)+ \langle x'-x,\mu\rangle +\frac{\sigma}{2}\left|x'-x\right|^2$ where $\mu \in \partial f(x)$, $\mu ' \in \partial f(x')$. How could I get ...
1
vote
1answer
88 views

Distance between a point to a $2d$ ellipse in $3d$ ambient space

Suppose we are working in the 3D Euclidean space. We are given an arbitrary point $p$ and a 2d ellipse: $$E=\{x:x^TQx\leq1,x^Tq=0\},$$ where $Q$ is a positive definite matrix and $q$ is an ...
1
vote
1answer
532 views

How to prove this function is quasi-convex/concave?

this is the function: $$\displaystyle f(a,b) = \frac{b^2}{4(1+a)}$$
1
vote
1answer
53 views

How does one verify if a vector is really recovered?

In compressed sensing, how to verify if a vector is really recovered or how does one plot the figures on recovery rate? Since in numerical experiments, there is always a difference between the ...
1
vote
1answer
75 views

Is $ \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 $ convex?

Over at How many points to find a polynomial? it was suggested to minimize $$ f(a,b,c,d,e) = \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 .$$ However I don't know if it is possible to find ...
1
vote
1answer
218 views

Convex Functions: Proofs

Let $f$ be a monotone nondecreasing function of a single variable which is also convex. Let $g$ be a convex function defined on a convex set $G$. Is it true that the composition of these functions ...
1
vote
1answer
134 views

Unboundedness of Quadratic Function

I was reading about Trust Region Methods for solving Nonlinear Optimization problems are came across this statement in my notes: If the quadratic approximation to the function $f(x)$ which is given ...
1
vote
4answers
240 views

Bounded linear function implication

In Stephen Boyd's book boyd uses the theorem that a linear function is bounded below on $R^m$ only when it is zero. I can't really digest this. Csn someone tell me why this holds? I mean if I take a ...
1
vote
2answers
275 views

Affine dimension of a simplex

In Stephen Boyd's book on Convex optimization he points out that k+1 affinely independent points form a simplex with affine dimension k. My understanding of affinely independent points is that no 3 ...
1
vote
2answers
288 views

Positive Second derivative and convexity

Let $f:\mathbb R\to\mathbb R$, maps a point $x \in \mathbb R$. $f$ is twice differentiable. Show that if second derivative is positive for all $x$ then $f$ is convex Is there anyway to prove this ...
1
vote
1answer
54 views

Does the following relation always hold?

Given two functions $$f_1(x)=g_1(x)+h(x)$$ and $$f_2(x)=g_2(x)+h(x)$$ I know that $f_1(x)$ and $f_2(x)$ are monotone increasing. If $g_2(x)<g_3(x)<g_1(x)$, then is it true that ...
1
vote
1answer
54 views

SVT algorithm and the value of tau.

SVT stands for singular value thresholding. It is an algorithm used in "matrix completion" problems. see http://svt.stanford.edu/ for basics. What is the meaning of "for large values of [tau]..." ...
1
vote
1answer
51 views

Showing that $T+S$ is firmly nonexpansive

Show that $T+S$ is firmly nonexpansive considering that $T$ and $S$ are firmly nonexpansive mappings from $\mathbb R^n$ to $\mathbb R^n$. Definition: We say that $F$ is firmly nonexpansive if: ...
1
vote
1answer
29 views

Does linearity decompose down convex sums?

I'm doing some convex optimisation where I'm minimising sum function $f(x) = \sum g_i(x)$, where the $g$'s are convex (and hence so is $f$) and the sum is finite. In doing so it turns out that $f$ is ...
1
vote
1answer
110 views

how can I proof the GLOBAL optimality of a problem where the feasible region is disjoint?

I want to minimize the following function. It has two variable, $x$ and $y$ are real. I want proof the global optimality. But the feasible region of the variables are disjoint. My question is, how can ...
1
vote
1answer
216 views

Max function on a closed compact convex set.

Consider a closed convex compact subset $\mathbb{S}$ of $\mathbb{R}^N$ while we denote any of its point by $x=[x_1,x_2,\ldots,x_N]^T$. Define the function \begin{align} f(x)=max(x_1,x_2,\ldots,x_N) ...
1
vote
2answers
192 views

What does the statement “Optimality condition for convex problem” mean? KKT or other condition?

I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with ...
1
vote
1answer
123 views

Convex Combination of Hermitian Matrices

Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
1
vote
2answers
355 views

Gradient of Moreau-Yosida Regularization

Let $f(x):\Re^n\rightarrow \Re$ be a proper and closed convex function. Its Moreau-Yosida regularization is defined as $F(x)=\min_yf(y)+\frac{1}{2}\|y-x\|_2^2$ $Prox_f(x)=\arg\min_y ...
1
vote
1answer
184 views

Is concave quadratic + linear a concave function?

Basic question about convexity/concavity: Is the difference of a concave quadratic function of a matrix $X$ given by f(X) and a linear function l(X), a concave function? i.e, is f(X)-l(X) concave? ...
1
vote
1answer
439 views

projected gradient method, multiple constraints

I am trying to minimize convex objective $f(X)$, for matrix $X$ s.t. $X\ge 0$ component-wise, and $X1^T = 1^T$. I want to use projected gradient descent. However, I only know how to project on ...
1
vote
1answer
2k views

what are Smooth and Non Smooth Problem in optimization?

I am trying to understand the difference between the optimization problem types which are basically smooth and non smooth. I also found this question what does a smooth curve mean? I understand that ...
1
vote
1answer
159 views

Continuity of a Parametric Linear Program

Consider the convex optimization problem $$ \min_{x \in X, \ y \in Y } x $$ $$ \text{sub. to } \ x A + B y + C = 0 $$ where $X = [0,1] \subset \mathbb{R}$, $Y \subset \mathbb{R}^M $ are compact ...
1
vote
2answers
2k views

maximum area of rectangle inscribed in a circle using geometric programming

need to find maximum area of rectangle that can be inscribed in a circle of radius r but need to use geometric programming of optimization to this for the maximum area the function is $ xy $ (if x ...
1
vote
1answer
149 views

$\epsilon$-normals to convex sets

I am reading the book by B. Mordukhovich, Variational analysis and generalized differentiation I. On page 6 it is stated the following inclusion: $$ \hat{N}_{\varepsilon }\left( \bar{x};\Omega ...
1
vote
1answer
210 views

Quasi convexity and strong duality

Is there a possibility to prove the strong duality (Lagrangian duality) if the primal problem is quasiconvex? Or is there a technique that proves that the primal problem is convex instead of ...
1
vote
1answer
111 views

establish that a minimization problem is indeed a convex minimization problem and then solve it

I have a minimization problem of the following form : $$\underset{\lambda (x) \in [0,1]}{min} \int_\Omega (1- \lambda(x))C_s(x)dx + \int_\Omega \lambda(x)C_t(x)dx + \alpha\int_\Omega ...
1
vote
1answer
740 views

Trace Eigenvalue Relation

I am reading Boyd's Convex Optimization text, and I am looking at a relation between the trace and the eigenvalue of a matrix. It is on page 92, example 3.23, line 7. The matrix $Y$ (apparently) has ...
1
vote
2answers
656 views

Converse supporting hyperplane theorem

Exercise 2.27 in Boyd and Vanderberghe: Suppose the set C is closed, has nonempty interior, and has a supporting hyperplane at every point in its boundary. Show that C is convex. Seems to me one ...
1
vote
0answers
10 views

Fenchel Conjugate of a norm squared

I was wondering if the fenchel conjugate of the $\frac{1}{2}||u||^2$, is the $\frac{1}{2}||u||_*^2$, where $||.||_*$ is the dual norm of $||.||$. This seems to be true for the $\ell_2$ norm. However, ...
1
vote
1answer
19 views

How do I set a lower bound to the solution's norm in a QP problem

I know that LASSO-regularization can be used to scale into an $L_1$ upper bound for a solution. But what if I want the norm to be within a specific range $[a,b]$? ie. I also want to set a lower bound? ...
1
vote
0answers
23 views

Convexity over a line given a convex interval [duplicate]

Let $f : \mathbb{R}^n \to \mathbb{R}_∞$ be a function. I want to prove that $f$ is convex over the line $L_{v,x_0}$ iff $\psi : \mathbb{R} \to \mathbb{R}_∞$ $\psi(t) := f (x_0 + tv)$, is convex ...
1
vote
2answers
18 views

Showing coercivity of a function

I am well attuned to the definition for a function to be coerce, which is that $\lim_{\|x\| \to \infty}f(x) = \infty$ ie the values of $f$ go to infinity as the norm goes to infinity. So Ex.1 ...