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

learn more… | top users | synonyms

1
vote
2answers
54 views

Why does gradient descent make sense?

Suppose I define two functions of $x$ in terms of a convex function $f$ with a unique minimum $x_0$: $$f_1(x) = 1 \times f(x)$$ $$f_2(x) = 2 \times f(x)$$ Suppose I wanted to minimize each of these ...
1
vote
1answer
30 views

Optimisation over matrix entries

I was looking to write the KKT conditions to solve this optimisation problem. $$\min_{\substack{\sum_j x_{ij}\le k_i \\ i=1,2,\ldots N}} a^\top (I-X)^{-1} b $$ Since there are $N^2$ decision ...
1
vote
1answer
70 views

Minimization over two lines

This is a minimization question where the minimizing points can be chosen freely on two lines: $$\mbox{minimize}\, \prod_{i=1}^K {y_i}\quad \mbox{such that}\quad \prod_{i=1}^K ...
1
vote
1answer
46 views

Dual Optimization Problem

I have the following optimization problem, $$ \text{minimize}_{X,Y} \ \lVert X\rVert_* + \lambda \lVert Y\rVert_1 \\ \text{subject to }X + Y = C$$ $C \in \mathcal{R}^{m \times n}$, $\lVert ...
1
vote
1answer
68 views

Matrix Maximization

I would like to solve the following optimization problem for a matrix $X$ which is symmetric and positive-semidefinite: $$ \mathrm{maximize} \, \, \, f(X) = \log \mathrm{det} X - k_1 \log(k_2 + a^T X ...
1
vote
1answer
158 views

Why is L21 norm not smooth

I have this confusion. I was reading this paper http://www.cis.temple.edu/~yuhong/research/papers/ijcai13b.pdf. I didn't understand why is L21 norm not smooth?
1
vote
1answer
59 views

A particular quadratic minimization problem

Given $n^2$ constants $a_{11},a_{12},\ldots,a_{1n},a_{21},\ldots,a_{nn}$ and $n^2$ non-negative variables $x_{11},x_{12},\ldots,x_{1n},x_{21},\ldots,x_{nn}$. Find the minimum value of $$\sum_{i=1}^n ...
1
vote
1answer
45 views

Linear constraint in convex optimization

Is it true that the solution to a linearly constrained convex minimization problem can only be placed on the boundary of the constraint set, for any nonlinear convex objective, e.g. $$ \min_x f(x)$$ ...
1
vote
1answer
37 views

Problem understanding dual optimization problem?

I am reading this paper: http://dl.acm.org/citation.cfm?id=1390696 Following optimization problem is defined in section 2: \begin{align} \max_{\mathbf{X}>0} \log ...
1
vote
2answers
142 views

Minimization of log-sum-exponential function subject to constraints.

I would like to minimize the following function: $f(x)=log(e^{-x_1}+..+e^{-x_n})$ Subject to: $\sum_{i=1}^{n}{x_i}=1$ $0 \leq x_i \leq 1$ So far I have discovered the following: If all the ...
1
vote
1answer
44 views

Quadratic programs: is the projection onto constraints optimal?

Consider the Quadratic Program $$ x^* := \arg \min_{ x \in X } \ \{ x^\top x + c^\top x \} \ \text{ sub. to: } Ax=b $$ where $X \subset \mathbb{R}^n $ is a non-empty, convex, bounded polyhedron. ...
1
vote
1answer
40 views

Projection onto convex set defined by $\|\mathbf{t} -\mathbf{W}^T\mathbf{y}\|^2 \leq k$

I want to use the method of Projections Onto Convex Sets, and for the problem at hand I need to find a closed form solution for $\mathbf{P}_C$, the projection onto set $C$, defined as: $$C = \{ ...
1
vote
1answer
37 views

Is a constrained optimization problem equalivant to its Lagrangian form?

For the following problem: $\text{min:}\ f(x)\\ s.t. \ g(x)\leq t$ Is the above problem equalivant to the following problem? $\text{min:}\ f(x) + \lambda g(x) \\ s.t. \ \lambda\geq0$ where $t$ and ...
1
vote
1answer
55 views

Convex Sets and extreme supports

Let the set $S$ in $R^n$ consists of the origin $0$ and $n$ lineary independent vectors $T_1, \ldots, T_n$. Show that $C(S)$, the convex hull of of $S$, is the intersection of its extreme supports, ...
1
vote
1answer
39 views

Derivative of a minimum

The expression, $e=\left(x(t,w)-c_x\right){}^2+\left(y(t,w)-c_y\right){}^2$, has a local minimum with respect to $t$ at some $t_0(w)$. Now what does $t_0'(w)$ look like?! $x,y\in C^2$ with respect to ...
1
vote
1answer
40 views

Impact of constraints on convex optimization

Let me start by saying I know almost nothing about optimization so please bear with me. Basically, I am wondering whether it is possible to solve a problem with two constraints by solving the problem ...
1
vote
1answer
46 views

An application of Separation Theorem

Let $X$ be a Hausdorff locally convex topological vector space. Suppose $X_0 \subset X$ is nonempty convex set, $g:\; X\to \mathbb R^m$ is a convex vector function (each component $g_i(x): X\to ...
1
vote
1answer
36 views

Propertise of a Dual Cone

In Convex Optimization by Boyd (P.51) said that " $y\in K^*$ iff $-y$ is the normal of hyperplane that supports $k$ at the origin ($K^*$ is a dual cone of $K$) " what does it mean geometrically? I ...
1
vote
1answer
58 views

Describing a Dual Cone

1)Does dual cone define just for proper cone or all kinds of cone ? 2)Can someone show me a figure that shows a dual cone of a cone ? In Convex Optimization by Boyd (P.51) said that " $y\in k^*$ iff ...
1
vote
1answer
90 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
21 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 ...
1
vote
1answer
46 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 ...
1
vote
1answer
62 views

How to verify correctness of a Fenchel conjugate derivation

Suppose I derived Fenchel conjugate of a function. My goal is to check if my solution is right. Suppose the steps are not available any more and only the final solution is present. Is there any ...
1
vote
1answer
151 views

How to show this algorithm on positive semidefinite matrices converges to a global maximum determinant

I'm dealing with an algorithm which is supposed to converge to the maximum determinant of certain positive semidefinite matrices. The problem is that we have such a matrix, and we vary certain ...
1
vote
2answers
84 views

Trace of quadratic function with 2 PSD matrices - convex?

If A & B are positive semi-definite, is this always convex: $$ trace(XAX^TB) $$ There was a similar question asked here: Trace of a quadratic function, Convexity and here: Confusion related to ...
1
vote
2answers
154 views

Application of Fenchel Young- Inequality

i'm stuck on the weak duality ineqiality. For $X,Y$ euclidean spaces: $f: X\rightarrow (-\infty,\infty]$, $g: Y\rightarrow (-\infty,\infty]$ and $A:X\rightarrow Y$ linear bounded mapping. I want to ...
1
vote
1answer
103 views

Property for the subdifferential and duality mapping in context of the Moreau-Yosida regularization

I have a question arising from the Moreau-Yosida regularization in Banach spaces. The real Banach space $X$ and its dual $X^*$ are both reflexive strictly convex, $f:X \rightarrow \mathbb{R} \cup ...
1
vote
1answer
154 views

Minimizing a linear function on a strictly convex set.

All the theorems that I know considering the uniqueness of a solution to a minimization/maximization problem requires the strict convexity/strict concavity of the objective function. But consider the ...
1
vote
1answer
47 views

Show that every polytope is bounded

The definition of polytope is the convex hull of a finite set. Thus: $$ \parallel\sum_j\lambda _j x_j\parallel\le\sum_j\lambda_j\parallel x_j\parallel\le\sum_j\lambda_j\max_j \parallel ...
1
vote
1answer
59 views

Please explain this theorem with picture

I logically understand this theorem, but I don't intuitively understand with picture. Let $S$ be a nonempty convex open set in $\mathbb R^n$ and let $f\colon S\to\mathbb R$ be differentiable on ...
1
vote
1answer
1k views

Prove convexity of squared Euclidean norm

I need to prove that the square of the Euclidean norm is convex, so: $||\theta x+(1-\theta)y||^2\leq\theta||x||^2+(1-\theta)||y||^2$. Can I use the triangular inequality (if yes, how?) or should I ...
1
vote
1answer
95 views

strict separation theorem?

Im learning and we have a theorem that says: Let $C$ be a non-empty, convex subset of $\mathbb R^d$ and let $p \in \mathbb R^d$ be a point which is not in the closure of $C$. Then there exists a ...
1
vote
1answer
94 views

Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$

$f: R^n \to (-\infty, \infty]$ is a convex function. Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$ I have used definition of convex functions to prove that the right-side is ...
1
vote
1answer
89 views

Dual of this primal optimization problem?

How would one find the dual of the following problem? $min_x 1/2 ||y-x||_2^2 + \lambda||x||_1 $ Can someone please explain to me how to do this since there are no specific constraints?
1
vote
1answer
781 views

Convex conjugate of $\ell_1$ and $\ell_2$ norm

Given a function $f$, we can define a function $f^{*}$, called the convex conjugate (also known as the Fenchel conjugate) of $f$ as follows: $$ f^*(\vec{z})= \sup_{\vec x \in \mathbb ...
1
vote
1answer
92 views

Computation Effort of Algorithms

Consider the strictly convex unconstrained optimization problem $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$ Let $x_\text{opt}$ denote its unique minima and $x_0$ be a given initial approximation ...
1
vote
1answer
53 views

Solution for a optimization of $\max$ function

Let $\mathbb{S}^m$ be an arbitrary closed, compact, convex set in $\mathbb{R}^m$. Let $\mathbf{x}=(x_1,\dots,x_m)$ denote a point in $\mathbb{S}^m$. Then, I define the function \begin{align} ...
1
vote
2answers
684 views

Proof of convexity of linear least squares

It's well known that linear least squares problems are convex optimization problems. Although this fact is stated in many texts explaining linear least squares I could not find any proof of it. That ...
1
vote
1answer
67 views

Containment of one convex hull in another

This question is related my previous question (Comparing two probability distributions) which are both related to my current research. Suppose we have two bounded convex hulls in $\mathbb{R}^n$ ...
1
vote
1answer
59 views

Interpreting a theorem about convex sets

I'm studying about linear programming and I bumped into following theorem (I have added my questions into the image): So in 1st rectangle how did we obtain the resulting equation when $\alpha ...
1
vote
2answers
74 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
125 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
48 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
116 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
48 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
148 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
269 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
57 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
147 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}- ...