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

learn more… | top users | synonyms

0
votes
0answers
15 views

A strange sufficient condition for quasiconcavity

I think I learned this from a lecture today If a multivariate C2 function is increasing and its bordered Hessian has positive determinant, then f is quasiconcave. ...
0
votes
0answers
7 views

Verification of the Approach to a given non-convex integer programming problem

I need to verify my approach to a non-convex integer programming problem. It would be interesting to see other approaches as well. Let $\mathbf{C}_1,\dots,\mathbf{C}_R$ be $N\times N$ hermitian ...
0
votes
0answers
32 views

Least squares and simplex

I am interested in the linear least square problem with the solution with the following constraints : $$ \min_x \|Ax-b\|^2$$ subject to $0 \le x_i \le 1$ and $\Sigma_{i=1}^n x_i= 1$. Because of the ...
1
vote
0answers
71 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
0
votes
1answer
31 views

LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
2
votes
1answer
43 views

normal cone to sublevel set

I came across the following interesting and important result: Let $f$ be a proper convex function and $\bar{x}$ be an interior point of ${\rm dom} f$. Denote the sublevel set $\{x:f(x)\leq ...
2
votes
1answer
56 views

min : sum of L2 norm and squared-L2 norm.

Is there a closed-form solution of the following convex problem: $$\min_x \| x - u \| + C \| x - v \|^2$$ where $\| \cdot \|$ is the L2 norm.
0
votes
1answer
63 views

$x^2+y^2+z^2 +3 \geq 2(xy+xz+yz)$, for $xyz=1$ [closed]

$x,y,z > 0$ such that $xyz=1$ can you prove that $x^2+y^2+z^2 +3 \geq 2(xy+xz+yz)$ without lagrange multiplier Thanks
0
votes
1answer
29 views

A question Kolmogrov's generalized inequality for projection onto convex sets

Kolmogrov's inequality says that, if $C$ is a convex set, and $P_C(x)$ is an operator for projecting point $x$ into the convex set $C$, if $z = P_C(x)$, then for any $y \in C$ we have $$ (z - y).(x - ...
0
votes
0answers
34 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
1
vote
1answer
39 views

Projection onto hypercube [0,1]^n

Given a positive n-dimensional vector $\mathbf{z}$ (all its elements are positive), my goal is to project it to a unit hyperplane $[0,1]^n$. However my projection is defined with respect to ...
2
votes
1answer
274 views

Karush-Kuhn-Tucker (KKT) conditions

I am having difficulties understanding the graphical interpretation as well as why the two following KKT conditions is necessary for a point x* being a minimum. It is my understanding that the (d) ...
0
votes
1answer
58 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
0
votes
1answer
27 views

Why Am i standing in a global minimum?

I`been asked the following in optimization If I am located in a point where all the possible factible directions turn out to be worse for the function, Am I located in a global minimum? The answer is ...
1
vote
0answers
24 views

Lagrange multipliers for minimax optimization

Does the equally constrained minimax optimization can be solved by using Lagrange multiplier method? Thanks in advance.
0
votes
0answers
17 views

Let $P \subseteq R^n$ be a polyhedron. Why does $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for some $x \in P$ imply $d$ is a recession direction?

Suppose we have a polyhedron $P \subseteq R^n$ and let $d \in P$ be a recession direction, that is $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for all $x \in P$. Why does $\{ x + \alpha d \mid ...
5
votes
1answer
165 views

Is this function concave or can it be made concave?

I am working with a point process with an event arrival rate of: $$ \lambda(t) = \mu + \sum\limits_{t_i<t}{\alpha e^{-\beta(t-t_i)}}$$ where $ t_1,..t_n $ are the event arrival times. The log ...
3
votes
3answers
136 views

Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$ \min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y) $$ $$ \text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i $$ ...
2
votes
0answers
59 views

Complexity analysis of convex optimization problem

I am studying an optimization problem \begin{equation} \mathbf{x}^*=\text{argmax}\quad\sum_{d=1}^{D}\log(\mathbf{a}_d^T\mathbf{x}+b)+\mathbf{c}_d^T\mathbf{x}+f_d\\ \text{subject to}\quad ...
0
votes
0answers
19 views

Frobenius norm and Gaussian noise

Why Frobenius norm is considered to a good tool for dealing with Gaussian noise?
0
votes
1answer
31 views

closed form vs gradient descent baseed methods

I am a beginner to optimization. Could anybody give me a simple example to illustrate when I should use closed form and when I should use iterative methods like gradient descent? Thanks in advance.
0
votes
1answer
111 views

Closed form solution

I have the following optimization problem: $$\min_{\mathbf{G}} \|\mathbf{B(A+G)\|_F^2} \quad{} \\\text{subject to} \quad{} \mathbf{\|C^T(A+G)\|_F^2\leq \gamma \|A^T(A+G)\|_F^2 } \quad{}, \\ ...
0
votes
0answers
20 views

Are iterations involving quantization going to converge?

For $i = 1,2,3$, let $~f_i(y_i)~$ be a convex and differentiable function and $y_i$ a scalar variable. Consider the following iteration $$\left[ \begin{array}{c} \nabla f_1(y_1^{k+1}) \\ \nabla ...
0
votes
1answer
24 views

how to differentiate to optimize this function?

I have an optimization function in the following form: $E = \operatorname*{argmin}_{A} \sum_j \| A\bf{x}_j - B \|_2^2 + \mu\sum_i a_{ii}^2$ Where, A is an unknown diagonal matrix with elements ...
0
votes
1answer
41 views

Convex matrix function

Please give me some hints for the following problem: Let $S = \{D \in R^{m \times n}, \|d_i\| \leq 1, i = 1, 2, \dots, n \}$. Find condition of $F \in R^{m \times m}$ such that the function: $ f(D) ...
0
votes
1answer
40 views

how to check an optimization function is convex or not

This is the sparse coding optimization function: $\operatorname*{argmin}_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$ I read in the literature that this ...
0
votes
0answers
48 views

Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
0
votes
1answer
71 views

Convex optimization approximation

Consider the optimization problem $\mathcal{P}_0$ $$ \min_{x \in \mathbb{R}^2} \left\| x-p \right\|^2 $$ $$ \text{sub. to: } \ A x \leq b, \ \ x_1^2 + x_2^2 = 1 $$ where $p \in \mathbb{R}^2$ is a ...
1
vote
0answers
45 views

Farthest point on a parallelotope from the origin

I have two related questions. First, consider a maximal independent set of vectors $\{v_1,\cdots,v_k\}$ in $k$ dimensional space. The rows of a square matrix $A$ are from those vectors. The origin is ...
0
votes
0answers
49 views

How to derive dual of this L1 norm approximation problem?

I am working through a question in Convex Optimization by Boyd and Vandenberghe. I've made an image with the original question, and the part of the solution I don't understand: how the dual is ...
0
votes
2answers
19 views

Solving for gradient of Frobenius norm term

Let's first define a couple of variables: $A,B,C \in \mathbb{R}^{m \times n}, D \in \mathbb{R}^{n \times n}$, and $\mu$ is a scalar. Say I have an ADMM sub-problem that looks like this: $\arg ...
0
votes
2answers
49 views

$\max \{\sum \limits_{i=1}^n z_i w_i \}$ where $\sum \limits_{j=1}^n |w_j| = 1$

How can we find $\max \{\sum \limits_{i=1}^n z_i w_i \}$ where $\sum \limits_{i=1}^n |w_j| = 1$? $z, w \in \mathbb{R}^n$
0
votes
0answers
43 views

Shrinkage operator for matrices

Here http://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf, on page 188, you can see the derivation of the soft thresholding operator or shrinkage operator for the case of vectors using Moreau ...
0
votes
1answer
33 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
6
votes
1answer
159 views

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
0
votes
1answer
33 views

Reentrant constraints in active set algorithm?

Problem definition Supposing you're trying to solve a quadratic program: $$ \min_x f(x) = \frac{1}{2}x^T Q x + c^T x \\ \mbox{s.t} \, \; A x \ge b$$ Where Q is square ($n$x$n$), positive semi ...
0
votes
0answers
38 views

Firm non-expansiveness in the context of proximal operators

$\newcommand{\prox}{\operatorname{prox}}$ Probably the most remarkable property of the proximal operator is the fixed point property: The point $x^*$ minimizes $f$ if and only if $x^* = \prox_f(x^*) ...
0
votes
0answers
26 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where ...
0
votes
3answers
59 views

Optimizing an expression containing sum of square roots of squared terms

For optimization problems involving square root, it is common to optimize the squared expression instead of that containing the square root. What if we have sum of squared expressions ? Consider the ...
3
votes
2answers
143 views

Convexity of Quadratic equation Inequality?

Solving an inequality of the form $x^TAx\geq0$ or $x^TAx\leq0$ is straightforward. I mean we have to check if A is positive semidefinite or negative semidefinite. But what would be the solution to the ...
1
vote
2answers
143 views

What is a convex optimisation problem? Objective function convex, domain convex or codomain convex?

My teacher in the course Mat-2.3139 did not want to answer this question because it would take too much time. So what does a convex optimisation problem actually mean? Convex objective function? ...
0
votes
1answer
60 views

$F(x) = f(x) + g(x) + h(x)$, where h(x) is strongly convex , is also strongly convex

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\Tr}{\operatorname{Tr}}$ Suppose $g: \mathbb{R}^n \rightarrow \mathbb{R}$ is a continuous convex ...
2
votes
2answers
57 views

Augmented Lagrangian

Consider the following equality constraint minimization problem: minimize $\text{ }f(x)$ subject to $Ax=b$ Its Lagrangian is then: $L(x,y) = f(x) + y^T(Ax-b)$ We can use then gradient ascent to ...
0
votes
1answer
52 views

Model $\min \frac{1}{2} \parallel Ax-B \parallel_2 + \lambda_1 \parallel Cx \parallel_1 + \lambda_2 \parallel Dx \parallel_\infty $ into standard form

I need to solve the following convex optimization problem: $\min \frac{1}{2} \parallel Ax-B \parallel_2 + \lambda_1 \parallel Cx \parallel_1 + \lambda_2 \parallel Dx \parallel_\infty$ s.t $x ...
0
votes
0answers
20 views

Applications of low-rank matrix approximation

There was a similar question here Use of low rank approximation of a matrix that has unfortunately remained unanswered. Although being along the same lines, my question will be formulated in a little ...
0
votes
1answer
40 views

No free lunch theorems

In James Spall's book, when explaining NFL theorems (http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization}) an example is given. Suppose input space has $3$ elements and output space ...
0
votes
1answer
37 views

Coordinate descent with constraints

Coordinate descent is a powerful method for solving optimization problems like $$\min_x \tfrac{1}{2}x^T A x + b^T x + \lambda ||x||_1$$ where $A$ is symmetric and positive definite, $\lambda>0$ ...
0
votes
1answer
218 views

Checking convexity

I know that the function $(\mathbf{a}-\mathbf{b})'(\mathbf{a}-\mathbf{b})$ is convex in $\mathbf{a}$ ($\mathbf{a}$ and $\mathbf{b}$ are vectors, not scalars). Would ...
0
votes
0answers
20 views

Convex Inequality describing Functions inside specific area

Let us assume that we have two functions $f_1$, $f_2:[0,1] \rightarrow \mathbb{R}^{2}$, which describe each a point trajectory on the plane. Let us further assume that we parametrize those functions ...
1
vote
1answer
199 views

Scaling a decimal number to have leading digit 5 or more

Suppose we are given two real numbers: $a, b \in \mathbb{R}$, $b > a$. Find $m \in \{1, 2, 2.5, 5\}$ and $k \in \mathbb{Z}$, satisfying the following condition: $\frac{b-a}{m10^k} \in [5,10)$. How ...