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

learn more… | top users | synonyms

0
votes
1answer
28 views

Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem: $$ ||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0 $$ where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is ...
0
votes
2answers
36 views

Nonempty interior feature of a proper cone

one of feature of proper cone is solid which means a proper cone has nonempty interior what dose nonempty interior mean ? I was reading Boyd convex optimization and I saw this term "Nonempty ...
0
votes
2answers
56 views

Solution in general for a seemingly simple problem

Let $\mathbb{S}$ be a closed, bounded, convex set in $\mathbb{R}^N$. Let $\mathbb{x}=[x_1,\dots,x_N]$ be any arbitrary vector in $\mathbb{S}$. Then what can we comment on the problem \begin{align} ...
0
votes
0answers
27 views

Prove that a point is optimal in LP-problem

I have the following LP-problem: Minimize $B_1^t Y_1 + B_2^t Y_2 + B_3^t Y_3$ subject to $$ (C_1,C_2,I) \begin{pmatrix} Y_1 \\ Y_2 \\ Y_3 \end{pmatrix}\geq 2 \text{ and } Y\geq 0 $$ where $B_1$ is ...
0
votes
1answer
44 views

How can the sum of two closed cones be not closed?

Can there be two closed cones $K_1$ and $K_2$ in $\mathbb{R}^3$ such that $K_1+K_2$ need not be closed?
0
votes
1answer
9 views

Conic hull of a proper function

Suppose $f$ is a proper function pn $\mathbb{R}^{n}$with $f(0)>0$.Now consider $$ g(x) = \text{inf}\{t: (t,x) \in \text{cl(cone(epi(}f)))\} $$ Can I always say that $\exists y \in \mathbb{R}^{n} : ...
2
votes
1answer
54 views

Difference between maximize $\sum\limits_{k=1}^Kg_k(\mathbf{x})$ and $\sum\limits_{k=1}^{K}\log(1+g_k(\mathbf{x}))$ in convex optimization

I have a problem of the following form: maximize $\;\;\;\,\sum\limits_{k=1}^Kg_k(\mathbf{x})$ subject to: $\;\,\,f_i(\mathbf{x})\leq\,1\,\forall\,i\in\{1, 2, \dotsc, m\}$ ...
0
votes
0answers
41 views

Expressing rank condition of a matrix in terms of its elements

Let $x \in \mathbb{R}^{n}$, define $X = xx^{T}$. I have an optimization problem with some linear constraints and few quadratic constraints, and I have to solve for $x$. Using $X$ as the unknown ...
0
votes
1answer
60 views

Semi-positive definite Hessian matrix and local minimum

Suppose we have a function $F(x)$ defined as \begin{equation} F(x) = \frac{1}{2}x^TAx + b^Tx +c, \end{equation} where \begin{equation} A = \begin{bmatrix} 4 & 2 \\ 2 & 1 \\ ...
0
votes
0answers
16 views

Sparse coding with local sparseness of dictionary

The title is probably pretty unclear, I hope I am able to explain it better here. I am currently working on a problem in the field of sparse coding, that is Principal Component Analysis, Non-negative ...
1
vote
2answers
27 views

Is this a polyhedron?

Is $S$ a polyhedron? $$S=\{x\in\mathbb{R}^n|\|x-x_0\|\le\|x-x_1\|\}$$ where $x_0, x_1$ are given. $S$ is the set of points that are closer to $x_0$ than to $x_1$. I was thinking the ...
0
votes
1answer
18 views

Quadratic Program over Box Constraints

Consider $f:\mathbb{R}^n \rightarrow \mathbb{R}$ defined as $$ f(x) := x^\top x + c^\top x $$ for some $c \in \mathbb{R}^n$. Define the (compact) "Box" $$X := \{ x \in \mathbb{R}^n \mid x_i \in [ ...
2
votes
1answer
69 views

Is the following objective function jointly convex?

I have the following optimization problem: $$ \begin{aligned} & \underset{\alpha, \gamma}{\text{minimize}} & & \end{aligned} \frac{1}{2} \|y - \sum\limits_{i=1}^{S}\gamma_{i}\cdot ...
7
votes
2answers
106 views

Derivative of nuclear norm

I'm trying to take the derivative of nuclear norm with respect to its argument. nuclear norm is defined in the following way: $$\|x\|_*=\mathrm{tr}(\sqrt{x^Tx})$$ I'm trying to calculate: ...
0
votes
0answers
34 views

KKT conditions for nonsmooth convex problems

What are the KKT conditions for a non-smooth convex function? Is the vanishing gradient of Lagrangian, replaced by $0$ in sub-differential of the Lagrangian, and all other things remain the same? I ...
1
vote
0answers
24 views

Reference table of “tricks” for converting problems to standard LP, QP, SOCP, etc. form?

Where can I find a decent source/reference that which I can use to look up the various standard "tricks" for converting typical problems to standard form in LP, QP, SOCP, etc.? The Charnes-Cooper ...
0
votes
1answer
57 views

Explain the convexity by looking the hessian matrix of a function

The hessian matrix of a function is given by, $$ H = \begin{bmatrix} a & b & c \\[0.3em] b & b & 0\\[0.3em] c & 0 & c \end{bmatrix} $$ where, ...
0
votes
0answers
20 views

As a beginner, I would like to solve convex quadratic maximization problem with a gradient descent variant in probability simplex?

I know the basics of gradient approaches to optimize the function iteratively, but for this case have have a equality constraint as $\sum_{i=1}^Nx_i = 1$ where each $x_i \geq 0$ with the objective ...
1
vote
1answer
37 views

How to find a positive semi-definite linear combination?

Suppose we are given two explicit symmetric matrices $X$ and $Y$ and we'd like to find a non-zero real linear combination $aX+bY$ that is positive semi-definite (if possible). Is there a way to go ...
0
votes
0answers
11 views

NNLS for under determined system

I have system of equations to solve Ax=B under x>=0. I read that Non Negative least Square(NNlS) algorithm proposed by Lawson and Hanson could solve this system for over determined case( number of ...
0
votes
1answer
48 views

How to solve this optimization problem?

Suppose I have the following problem: Maximize: $\quad\quad x_1+x_2+x_3+x_4$ Subject to: $\quad\quad \dfrac{\gamma\;a_1\;x_1}{\gamma\;a_2\;x_4+1}\geq1$, $\quad\quad\quad\quad\;\;\quad\quad ...
1
vote
1answer
46 views

Partial derivative on convex set

If we have a function $f:U \rightarrow R$ ($U \subset R^n$) which is partially differentiable on a convex set U with $\frac{\delta f}{\delta x_1} = 0$ for all $x \in U$. How can we prove that $f$ ...
1
vote
1answer
59 views

Proof of the Moreau decomposition property of proximal operators?

Given the prox operator i.e. $ prox_h (x) = arg min_u (h(u) + 1/2 ||u-x||^2_2) $ the Moreau decomposition property says that $ x = prox_h (x) + prox_{h^*} (x) $ where $h^*$ is the conjugate of ...
0
votes
2answers
34 views

Lagrangian with inequalities

I have a toy question on SVM , where i have to find the weight $w$ by solving the Lagrangian multiplier method by hand . I know Lagrangain with equalities only . Here I have to deal with inequalities ...
0
votes
1answer
31 views

Express a function as difference of convex functions (DC)

is there a way to express the function $$1-\exp \Big( \frac{-\max(0,x)^2}{\alpha} \Big)$$ as the difference of two convex functions (DC)? Thanks
0
votes
1answer
39 views

Minimize $L_2$-norm of $x1-b$ where $x \in R, b \in R^n$

Minimize $L_2$-norm of $x1-b$ where $x \in R, b \in R^n$ $||x1-b||_2 \rightarrow ||x1-b||^2_2=||x1-b||^T||x1-b||$ (squaring $L_2$-norm doesn't change outcome and yields quadratic) ...
1
vote
1answer
16 views

Null space and minimization

Let $x^*\in\text{argmin }f(x)=\text{argmin }\frac{1}{2}\|Ax-b\|^2$ where $A$ is a linear operator. Show that $\text{argmin }f=x^*+\text{Null}(A)$. For $x\in x^*+\text{Null}(A)$ we have ...
0
votes
1answer
34 views

Relax equality into inequality in convex problem

Let $\mathbf{x}, \mathbf{z}, \underline{\mathbf{x}}, \overline{\mathbf{x}} \in \mathbb{R}^{I}$, where the first two are variables and the last two are given data. I have the following problem: ...
1
vote
1answer
33 views

Minimizing difference and individual variables in convex problem

Let's say I have the following optimization problem: $$ \begin{align*} \min_{\mathbf{x},\mathbf{y}} & \sum_i x_i-y_i \\ \mathrm{s.t.} & \{\mathbf{x},\mathbf{y}\} \in ...
0
votes
1answer
25 views

Prove that the intersection of convex sets is convex using the following three points…

I want to prove each point, then, use points (1) and (2) to prove (3). $C_{1} = \lbrace x \in \mathbb{R}^{n} \mid h(x) = 0 \rbrace $ is convex iff $h(x)$ is affine in $C_{1}$ $C_{2} = \lbrace x ...
3
votes
1answer
51 views

Prove that $e^{tx} \le xe^t + 1-x$

Prove that $$e^{tx} \le xe^t + 1-x$$ for $t \ge 1$ and $0 \le x \le 1$ I think I need to use the fact that e is convex? But I can't quite see it. Any help appreciated Thanks.
0
votes
1answer
49 views

Solution to a Quadratic Minimization with Norm Constraint

How do I solve the optimization problem \begin{align} &\min_{\mathbf{x}\in\mathbb{C}^N}\mathbf{x}^H\mathbf{A}\mathbf{x}+2\Re\{\mathbf{b}^H\mathbf{x}\} \\ \mbox{subject to }\\ ...
3
votes
3answers
53 views

Logistic function as “difference of convex functions” (DC)

is there a way to express the logistic function $$\frac{1}{1+\exp(-x)}$$ as the difference of two convex functions? Thanks
1
vote
2answers
46 views

Why is this weighted least squares cost function a function of weights?

Here is a picture from my book regarding weighted least squares: Totally lost here, so I extracted the main nested issues confusing me: First Question: I know that in any LSE we want to minimize ...
1
vote
1answer
26 views

How to obtain primal problem from Lagrangian?

If you're trying to optimize $\min_x f_0(x)$ subject to $f_i(x) \leq 0$ then the Lagrangian would be $$L(x, \lambda) = f_0(x) + \sum_i \lambda_i f_i(x)$$ The dual problem is $\max_\lambda g(y)$ ...
2
votes
1answer
38 views

“Support function of a set” and supremum question.

I have already learned about what a supremum means from wikipedia and from another answer here. However I am not quite sure what 'supremum over a set of functions' means exactly. As an example, my ...
0
votes
2answers
50 views

Inequality involving max is confusing me.

I am trying to understand one line in a derivation here. Simply put, the statement is that: $$ max\{\theta \ f_1(x) + (1-\theta) \ f_1(y) \ , \ \theta \ f_2(x) + (1-\theta) \ f_2(y)\} \leq \theta \ ...
1
vote
1answer
45 views

Examples of affine functions and convex sets

I'm just learning about convexity and affineness, and I've read over some similar questions asked here, but those were more about general properties. I need some help applying those properties to a ...
0
votes
0answers
16 views

Conic Farkas lemma for dual programm

Suppose $C\subset \mathbb{R}^n$ is a regular cone (convex, closed) and $C^*=\{y\in\mathbb{R}^n \mid y^Tx\geq 0\}$ the dual cone and $A\in\mathbb{R}^{m \times n}$. I want to show that 1) There exist ...
1
vote
1answer
30 views

Could anyone give me an example of non-smooth strong convex function? [closed]

Could anyone give me an example of non-smooth strong convex function? I cannot figure out one.
1
vote
1answer
47 views

Confusion related to augmented lagrangian multiplier method

I have this confusion related to the augmented lagrangian multiplier method from this tutorial How come the gradient wrt y is equal to $\rho(Ax^{k+1}-b)$
3
votes
2answers
73 views

Singular Values of Matrix as Optimization Problem

Assume that $A$ is a positive semidefinite symmetric matrix. It is known that $$\max_{||y||\leq1} \quad y^TAy$$ Has an analytical solution which is the maximum eigenvalue of $A$. This isn't hard ...
0
votes
1answer
50 views

SDP formulation of noisy low rank matrix completion (2)

Thank you Michael for the answering my previous question, SDP formulation of noisy low rank matrix completion. It seems that I overlooked the problems in my initial question. I didn't recognize the ...
0
votes
0answers
20 views

Linear least squares with sparse inequality constraints for support function estimation

The initial problem is the following: $$ ||h - h^{0}|| \to min \; \; s.t. Qh \leq 0 $$ where $h^{0} \in \mathbb{R}^{n}$ is known vector and $Q$ is a $m \times n$ matrix. The problem arises in specific ...
0
votes
0answers
27 views

optimization problem in mathmetical finance using convex duality

I'm interested in the application of stochastic processes and stochastic calculus in mathematical finance. In my lecture I often see a certain optimization problem usually of a convex function. ...
0
votes
1answer
28 views

A question on convex

I am thinking about this without solutions. I would like you to give hints. Let $Q$ be a polyhedron with $Q=convex.hull (X)$ for some $X \subset R^n$. Let $E$ be a face of $Q$. Prove that $E \cap X ...
1
vote
1answer
28 views

An equation related to covariance matrix, square root of the matrix, and Euclidean norm.

How can I prove this equation: $${ ({ x }^{ T }\Sigma x) }^{ 1/2 }={ \left\| { \Sigma }^{ 1/2 }x \right\| }_{ 2 }$$ In which $\Sigma $ is a covariance matrix. I tried some numerical examples in ...
0
votes
0answers
64 views

Calculation of the set for the polar tangent cone?

I have the following theorem in my book. Assume that $\tilde{x}$ is a local minimum from a minimization problem and that f(.) is differentible at $\tilde{x}$ Let $T_X(\tilde{x})$ be the tangent cone ...
0
votes
2answers
49 views

Is the geometric-to-arithmetic function convex or concave?

Consider a vector $\mathbf{x} \in \mathbb{R}_{++}^N$. Also consider two functions, $g(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, and $a(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, ...
0
votes
3answers
66 views

Concave function divided by a convex function. What is the result?

Let us say that I have a function $f(x)$ that we know is a concave. And let us also say that we have another function $g(x)$ that is a convex. If I make a new function, $h(x) = \frac{f(x)}{g(x)}$, ...