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

learn more… | top users | synonyms

0
votes
0answers
14 views

Find Maximum of Lower Envelope

Okay, I'm not really sure whether the title is good. Consider \begin{align*} \min\{ 5x_1 + \frac{5}{2}x_2 + \frac{5}{3}x_3 + \frac{5}{4}x_4, \\ x_1 + \frac{6}{2}x_2 + \frac{6}{3}x_3 + ...
0
votes
1answer
21 views

Prove that f has at least one global minimizer

$f: \mathbb{R}^n \to \mathbb{R}$ is a continuous function such that $\displaystyle\lim_{\|x\| \to \infty} f(x) = \infty$ On a side note: how can a function have more than one global minimizer? Is a ...
0
votes
0answers
9 views

online algorithm for nested optimization

How to construct a sequence {x_t;\theta_t}, which is online algorithm for following optimization problem: $\arg\min_\theta \sum_t \min_{x_t} \ell_t(x_t;\theta)$ For simply, we can assume ...
1
vote
1answer
35 views

Relation between Riccati Algebraic Equation and optimization problem

Reading this page: http://www.mathworks.com/help/robust/ug/minimizing-linear-objectives-under-lmi-constraints.html I got stuck in the result that says it can be show that minimizing Trace of X (a ...
0
votes
1answer
24 views

Feasible Condition with a single constraint

A linear program with a single constraint minimize $z = c_{1}x_{1} + c_{2}x_{2} +· · ·+c_{n}x_{n}$ subject to $a_{1}x_{1} + a_{2}x_{2} +· · ·+a_{n}x_{n} ≤ b$, $x_{1}, x_{2}, . . . , x_{n} ≥ 0.$ (a) ...
3
votes
0answers
29 views

Easy elementary proof of Farkas Lemma?

Is there any elementary proof of Farkas lemma which does not use convex analysis and hyperplane separation theorem? What about special case below: If the Matrix $A$ is invertible, then there is ...
0
votes
0answers
31 views

Linear Programming - Tableau Condition

The following tableau corresponds to an iteration of the simplex method: ...
1
vote
1answer
41 views

Dual of concave function is convex

If $U(x)$ is strictly increasing and strictly concave and $lim_{x \rightarrow \infty}$ U'(x) = 0, prove that its dual: $$U^{*}(y) = max_x \{U(x) - xy\}$$ is convex. Does anyone know how to prove ...
1
vote
1answer
53 views

Why geometric median cannot be solved analytically

$\DeclareMathOperator*{\argmin}{argmin}$ For a given set of $m$ points $x_1,...,x_m$ with each $x_i\in \mathbb{R}^n$, the geometric median (or the weber point) is defined as $$\argmin\limits_{y \in ...
0
votes
0answers
21 views

Convex sets and minimum points

Let $X$ be the convex set formed by the convex combination of the $n$ points $\{x_1, x_2, ... x_n\}$ in $\mathbb{R}^n$. Let $X^* \subseteq X$ be the convex set of minimal points w.r.t to the convex ...
0
votes
0answers
19 views

A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
0
votes
0answers
14 views

Eliminating variables in convex program

This is a basic convex optimisation question. I have the following problem: $$\max_{\substack{t\le e\\ At\le b}} e^\top t$$ How do I find the optimum $t^*$? I write the KKT conditions, get ...
0
votes
0answers
32 views

weights go to infinity in logistic regression with linearly separable data

I have the loss function of logistic regression $L(W)$ = - $\sum_{i=1}^n {y_i}.log[\sigma(w^Tx)] + {(1-y_i)}.log[1- \sigma(w^Tx)]$ I have derived the Hessian and proven it's positive semi-definite ...
2
votes
1answer
16 views

Showing the multivariate normal is log-concave?

I'm trying to show that $\log p(x) = -\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)$ is concave. How would I go about this in $\mathbb{R}^n$? I've tried taking derivatives but I'm getting stuck once I get ...
-8
votes
0answers
35 views

Want to show that Farkas lemma is equivallent to corolary 2.7. [closed]

I want to show that Farkas lemma (lemma 2.6) is equivalent to corollary 2.7. Any help?
0
votes
0answers
10 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
6 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
1answer
51 views

Show that this function is convex?

So I'm supposed to show that this function is convex, but I have no idea how to go about it...I've been told to use Cauchy Schwarz in order to show that the Hessian is non-negative definite, but I'm ...
0
votes
0answers
10 views

Quasiconcave condition for a power function

Let $f(x, y)= (ax^2+by^2)^n$ where $a, b, n$ are positive, $x, y\in \mathbb{R}$. What is the condition of $n$ so that $f(x, y)$ is a quasiconcave, and concave function? My idea is only calculate ...
0
votes
0answers
27 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
46 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)} ...
-1
votes
0answers
31 views

Relaxed optimization [duplicate]

I am facing an optimization problem $\max f(X)$ Can I solve a relaxed optimization problem $g(X)$ $\max g(X)$ if I can prove that $g(X)> f(X)$.
-2
votes
0answers
22 views

Relaxation of optimization problem [duplicate]

Can I solve the following optimization problem, $$f= \max \{h(Y) - h(Y|U)\}$$ by solving an easier upperbound on $f$ for example $g > f$ where $g= \max\{h(Y)-h(Z)\}$. My aim is to prove that ...
0
votes
1answer
24 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 ...
0
votes
1answer
60 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
2
votes
1answer
38 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 ...
0
votes
0answers
16 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
34 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 ...
0
votes
1answer
26 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 ...
0
votes
1answer
48 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 ...
2
votes
1answer
42 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.
1
vote
0answers
20 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
13 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 ...
0
votes
1answer
27 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.
2
votes
0answers
48 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
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
35 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
28 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
1answer
21 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
0answers
31 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
0answers
28 views

The convexity of the range of concave function

Given a concave function $f: X \rightarrow \mathbb{R}^n $ with a convex domain $X \in \mathbb{R}^n$, is the range of $f$ a convex set also?
1
vote
0answers
40 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
1answer
103 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
2answers
18 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 ...
5
votes
1answer
159 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 ...
0
votes
0answers
33 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
2answers
48 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
13 views

Frobenius norm and Gaussian noise

Why Frobenius norm is considered to a good tool for dealing with Gaussian noise?
0
votes
1answer
32 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 ...
0
votes
0answers
33 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 ...