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

learn more… | top users | synonyms

1
vote
1answer
23 views

Smoothness of total variation norm with weight

Let me write total variation norm $$ \|u\|_{TV} = \max_{z\in Q} \langle z, Du\rangle, $$ where $Q$ is the unit ball in $\mathbb R^2$ and $D$ is the corresponding gradient matrix. I can smooth TV by ...
1
vote
1answer
51 views

What is the difference between min and max constraint problems?

For example, let's consider these two min max optimization questions (1) $$\max \ \ g(x,y)=xy$$ $$ \text{s.t. } x^2+y^2=1$$ (2) $$\min \ \ g(x,y)=xy$$ $$ \text{s.t. } x^2+y^2=1$$ Solution: By ...
3
votes
0answers
47 views

Variational characterization of nuclear norm

The nuclear norm $||\cdot||_{*}$ of a matrix is defined as the sum of its singular values. Working from the result at the bottom of this blog post, we have, for a matrix $\mathbf{X}$ and its ...
3
votes
1answer
36 views

Constrained nonlinear optimization

I am wondering what is the easiest/best way to find the values of $x_i$ that maximize the expression $\sum_{i=1}^N a_i \ln (x_i)$ under the constraints $\sum_{i=1}^Nx_i = 1$ and $ 0\leq x_i \leq 1$ ...
0
votes
0answers
48 views

Show that $f + g$ is still strictly convex.

Let $d \in X$ and set $$f: X \to \mathbb{R}: x \mapsto \left(\frac{1}{2}\right) \parallel x-d \parallel^2.$$ Use (*) to show that $f$ is strictly convex. Now let $g$ be any convex function. Show that ...
3
votes
0answers
52 views

How to prove the matrix fractional function is convex by definition

It is well known that the matrix fractional function $f(\mathbf{w},\boldsymbol{\Omega})=\mathbf{w}^T\boldsymbol{\Omega}^{-1}\mathbf{w}$ is jointly convex with respect to $\mathbf{w}$ and ...
0
votes
1answer
38 views

Let $f:\mathbb{R}^n\rightarrow ]-\infty,+\infty]$ be proper and strictly convex. [duplicate]

Let $f:\mathbb{R}^n\rightarrow ]-\infty,+\infty]$ be proper and strictly convex. Show that $f$ has at most one minimizer. I am hoping someone can give me some feedback on the proof for this. I feel ...
0
votes
1answer
41 views

Solution of constrained optimization problem (ADMM)

Consider the following optimization problem which appear in ADMM page 57. Here $\bar{a}$ is avg of $a$. I don't see how eq. 7.13 came? Lagrangian does not seem to bring that. Any help is ...
0
votes
2answers
39 views

Given $\min\limits_x \|x\|_2^2 \quad \text{s.t.} \quad Ax = b$ show $x^* = A^T(AA^T)^{-1}b$

Given $$\min\limits_x \|x\|_2^2$$ $$\text{s.t.} Ax = b$$ show $x^* = A^T(AA^T)^{-1}b$ where $A \in \mathbb{R}^{m \times n}, m < n$ This is projection $x$ onto the hyperplane $Ax - b = 0$ ...
1
vote
1answer
63 views

Examples of $f$ strictly convex, either with one minimizer or with no minimizer.

Let $f\colon X \to [ -\infty, +\infty]$ be proper and strictly convex. Show that $f$ has at most one minimizer. Give examples where $f$ is strictly convex, and either (i) $f$ has one minimizer; or ...
0
votes
1answer
45 views

Prove or disprove convexity

I am dealing with the following function $f:\mathcal{R}^n \rightarrow \mathcal{R}$, how can I prove or disprove the convexity of the following function? $$f(x)=\|x-\frac{Ax}{\langle x,b\rangle}\|_2$$ ...
2
votes
1answer
53 views

Prove that a polytope is closed

Let the polytope defined by $$S:=co \left\{ x_1,x_2,...,x_k \right\}$$ where $x_1,x_2,...,x_k \in \mathbb{R^n}$ and $co \left \{... \right \}$ is the convex Hull. Prove that S i closed. I tried the ...
1
vote
1answer
40 views

Equivalent formulation of linear discrimination problem on Boyd convex optimization slides

In Boyd's CVX slides on pg 189 he has the linear discrimination problem http://stanford.edu/class/ee364a/lectures.html Given data $\{x_1, \ldots, x_n\}$, $\{y_1, \ldots, y_n\}$ The problem of ...
0
votes
1answer
28 views

Prove that a function is convex by only using positive semi-definiteness

let $x \in \mathbb{R}^n$ where $f(x) = (1 + ||x||^2)^{1/2}$. Prove that it is convex. As of right now, we define a convex function to be a function with a positive semi definite second derivative. So ...
0
votes
1answer
27 views

How to extract the positive semidefinite part of a matrix

Motivation: We wish to make an second order approximation of a nonconvex function $f(x), x \in \mathbb{R}^n$ such that it is convex, however we do not have guarantee that $\nabla^2 f(x)$ is convex ...
2
votes
1answer
28 views

Convex Optimization - nuclear norm regularisation of symmetric matrix

I have a problem of the form $\min_{X\in \mathbb{R}^{n \times n}} g(X) - \lambda ||X||_{*}$ where $g$ is convex and differentiable. I would like to use proximal gradient descent to solve this. How ...
1
vote
0answers
34 views

A nonlinear optimization problem with difficult Kuhn-Tucker system of equations

I know about the sufficient optimality theorem Kuhn-Tucker, and this problem can use the Kuhn-Tucker theorem directly, but ridiculously, I got stuck on the system of equations to find one root for ...
0
votes
0answers
30 views

High-dimensional optimization issue

This question is mostly related to programing issues, but I want to understand what is going on inside. Suppose I have a likelihood function with "# of parameters $\propto$ # of observations". That ...
2
votes
1answer
30 views

Regression maximum likelihood

Given this regression model: $y_{i}=\beta_{0}+\beta_{1}x_{i}+E_{i}$. All the assumptions are valid except that now: $E_{i}\sim N(0,x_{i}\sigma^{2})$ Find Maximum likelihood parameters for ...
2
votes
1answer
75 views

Euclidean projection onto convex set

I follow the notation in Chambolle and Pock 2011 24page. In that document, the convex set $P$ is $$ P=\{p\in Y \mid \|p\|_\infty \leq 1\} $$ where $\|p\|_\infty = \max_{i,j}|p_{i,j}|$ and $|p_{i,j}| ...
0
votes
1answer
37 views

Let $f:X\rightarrow ]-\infty,+\infty]$, let $b\in x$ and let $c\in X$. Find Fenchel conjugates of the functions:

Let $f:X\rightarrow ]-\infty,+\infty]$, let $b\in x$ and let $c\in X$. Find Fenchel conjugates of the functions: $(i)\;\;\;\; f(x)+\langle c,x\rangle,$ $(ii)\;\;\;\; f(x-c).$ For (i) I'm thinking ...
0
votes
0answers
15 views

convert semi definite optimization into standard form [duplicate]

Consider the following semi definite optimization problem $\begin{array}{l} \mathop {\min }\limits_{\bf{X}} \,Tr\left( {{\bf{CX}}} \right)\\ subject\,to:\\ Tr\left( {{{\bf{A}}_i}{\bf{X}}} \right) \ge ...
0
votes
0answers
10 views

how does sequential axis search work?

I see that some algorithms that need to search for a global minimum in multiple dimension space, say find x and y to minimize f(x,y), instead of searching in x,y simultaniously, starting from initial ...
0
votes
0answers
15 views

notions of geometry needed for optimization

Could you tell me the notions of geometry (not topology) that are needed before starting courses on convex analysis and optimization ? Thank you.
0
votes
0answers
15 views

Follow up question for: Convexity of the product of two functions in higher dimensions

The question referred to in the title ( Convexity of the product of two functions in higher dimensions) is already answered. However I have a question regarding the answer and I am not able to post it ...
2
votes
1answer
46 views

Weighted $L_1$ norm

I try minimizing the following expression : $ V(x)=\sum_{i=1}^n|x_i - u|w_i $ $w_i > 0 $ I need to find u that minimize this expression. I know how to do it for w=1 (which is is the median). ...
-1
votes
1answer
44 views

Suppose that $X=\mathbb{R}^n$ and that $K=\mathbb{R}_{+}^{n}$.

Suppose that $X=\mathbb{R}^n$ and that $K=\mathbb{R}_{+}^{n}$. using the definition of the Fenchel conjugate verify that $\iota_{K}^{*}=\iota_{-k}$ where $\iota_{K}$ is the indicator function. my ...
0
votes
0answers
27 views

How to write the SDP in cvx for the following optimization problem

How to write the SDP(Semidefinite program) of the following optimization problem \begin{multline} \max_{Z,f ,g} \ trace(KZ) − f^Td \\ subject to \\ trace(W^{−1}Z) = k \\ Z_{ij} ≥ 0 \\ Z = Z^T \\ Ze = ...
1
vote
0answers
36 views

Convexity of the log barrier function

Let's consider the following convex optimization problem of minimizing the log barrier function: $$\min_{\textbf{x}\in \Re^n}f(\textbf{x})=\min_{\textbf{x}\in ...
2
votes
1answer
51 views

How to replace piecewise objective function in convex optimization problem?

Suppose I have a minimization problem \begin{equation} \begin{aligned} & \min\limits_{x} & & g(x)+f(x) \end{aligned} \end{equation} \begin{equation} f(x)= \begin{cases} 1, ...
2
votes
1answer
25 views

Unbounded convex conjugate

This is my first time posting a thread. I apologize if I somehow do not comply with the rules (please remind me if it happens, so next time I can do it correctly:) Today I was having an optimization ...
1
vote
1answer
40 views

Transportation problems

i'm a master student at the deparment of statistics. And i will prepare a presentation on transportation problems in the course of optimization (or linear programming / mathematical programming) I ...
1
vote
1answer
43 views

Intuitive interpretation of proof that projections are non-expansive

Is there an intuitive (e.g. graphical) interpretation of the proof that projections on closed convex sets are non-expansive? Most proofs, e.g. the one given here, are presented as a sequence of ...
0
votes
0answers
28 views

semi infinite programming

We have the following semi infinite convex programming $\begin{array}{l} \mathop {{\rm{Minimize}}\,}\limits_{\left\{ {{r_\alpha }} \right\}_{\alpha = 0}^M,\left\{ {{t_\ell }} \right\}_{\ell = 0}^Q} ...
1
vote
1answer
41 views

Polar set of convex cone

I am stuck with the following question: Let $K = \{x\in \mathbb{R^n}: x_1 \geq x_2 \geq ... \geq x_n \geq 0\}$. Determin $K^{*}$, which is supposed to be the polar set of $K$. I know that $K$ is a ...
0
votes
0answers
34 views

Polar set of convex cones Proof

I have to show the following: Let $K_{1}, K_{2} \subseteq \mathbb{R}^{n}$ be convex cones with $K_{1} \cap K_{2} = \begin{Bmatrix} 0 \end{Bmatrix}$ and $intK_{i} \neq \varnothing , i=1,2$. Show that ...
0
votes
1answer
28 views

Concerning the optimality condition of convex functions

So I am studying convex optimization and I came across this theorem regarding the minimizer of a function in a space $\mathcal{X}$. In particular, the theorem states that if $f:\mathcal{X} \rightarrow ...
1
vote
1answer
61 views

Find the Fenchel conjugate $f^{*}$ of the function $f:\mathbb{R}\rightarrow ]-\infty,+\infty]$ given by

Find the Fenchel conjugate $f^{*}$ of the function $f:\mathbb{R}\rightarrow ]-\infty,+\infty]$ given by \begin{equation*} f(x) = \begin{cases} +\infty & \quad \text{if } x\leq0\\ ...
0
votes
1answer
52 views

Fenchel-Rockafellar duality problem: Show that weak duality holds, i.e., p≥−d .

I am looking for help with motivation for the Fenchel-Rockafellar duality problem. Specifically the following: Let $\;f : X \rightarrow ]-\infty, +\infty]$ be convex and lower semicontinuous, let $A ...
0
votes
0answers
34 views

dual feasibility of Kuhn-Tucker condition?

minimize $f(x)$ subject to \begin{align} f_i(x) & \le 0, \quad i \in \left\{ 1,\ldots,m \right\} \\ h_i(x) & = 0, \quad i \in \left\{ 1,\ldots,p \right\} \end{align} Then the Lagrange ...
0
votes
1answer
43 views

Is mathematical programming an analytical or numerical technique?

Is linear programming, mixed-integer programming, integer programming, nonlinear programming, etc. numerical or analytical techniques? I always thought they were numerical methods because you can't ...
1
vote
2answers
42 views

Gradient and Hessian for linear change of coordinates

I am studying the affine invariance of the Newton step for unconstrained optimization and I came across with the following: Suppose $\textbf{T}\in \Re ^{n\times n}$ is nonsingular and define ...
3
votes
0answers
32 views

Gordans lemma seperation [duplicate]

Let $A$ be an $m × n$ matrix. Recall that Gordan’s lemma states that the system $$\{d : Ad < 0\}$$ is inconsistent if and only if the system $$λ ≥ 0 ∈ R ^m , λ \not= 0, A ^T λ = 0$$ is consistent. ...
1
vote
1answer
60 views

Derive the dual function $g(\lambda, \nu)$ for the least-norm problem

I am trying to find the dual function $g(\lambda, \nu)$ to this problem $$\min\limits_{Ax = b} \|x\|$$ Step 1. Form the Lagrangian $$L(x, \lambda, \nu) = \|x\| + \nu^T(Ax-b) = \|x\| + \nu^TAx - ...
0
votes
0answers
31 views

What does the above simplify into when $f_1$ and $f_2$ are indicator functions of convex subsets $C$ and $D$ of $X$, respectively?

Consider the expression $$\partial (f_1\Box f_2)(\bar{x})=\partial f_1(\bar{x_1})\cap\partial f_2(\bar{x_2}).$$ What does the above simplify into when $f_1$ and $f_2$ are indicator functions of ...
0
votes
1answer
44 views

Gordan’s lemma equivalent statement

Let $A$ be an $m × n$ matrix. Recall that Gordan’s lemma states that the system $$\{d : Ad < 0\}$$ is inconsistent if and only if the system $$λ ≥ 0 ∈ R ^m , λ \not= 0, A ^T λ = 0$$ is consistent. ...
0
votes
3answers
44 views

modeling a set S as a mixed integer linear programming problem

This is actually a homework question and I am very much stumped. I have to model the following set as an MILP S = {x,y∈R| |x| + |y| = 1} There is no need for an objective function but an arbitrary ...
0
votes
2answers
48 views

Compute the support function, $\sigma_{C}$, when C is a subspace.

Recall that in convex analysis the support function is the conjugate of the indicator function and is defined to be $\sigma_{C}(x)=\sup_{v\in C} \langle v,x\rangle$. Compute the support function, ...
1
vote
0answers
37 views

min-max optimization problem

how do you solve the following optimization problem to find the global solution? $~~~~~\underset{y}{min} ~ \underset{x}{max} f(x,y)$ subject to $~~~~~g(x)<0$ with knowing that both g(x) and ...
1
vote
0answers
24 views

Determine $C^{\circ}$ explicity in terms of $A$ and $b$

If $C \subseteq E$ is a closed convex set define $$C^{\circ}=\bigcap_{x\in C}\{u \in E: \langle u,x\rangle\leq 1\}$$ Determine $C^{o}$ if $C= \{x: Ax \leq b\}$ Solution so far: $C^{o}=\bigcap_{x\in ...