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

learn more… | top users | synonyms

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 ...
1
vote
1answer
26 views

Generalized Farkas Lemma

Farkas lemma can be stated as follow: If for all $\mu$ such that $\mu^T\cdot a_i \geq 0$ implies that $\mu^T\cdot b \geq 0$ then $b=\sum \lambda_i a_i$ with $\lambda_i \geq 0$ I need a generalized ...
1
vote
1answer
57 views

Armijo rule intuition and implementation

I am minimizing a convex function $f(x,y)$ using the steepest descent method: $$\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma \nabla F(\mathbf{x}_n),\ n \ge 0$$ My function is defined over a specific domain ...
0
votes
1answer
18 views

Complementary slackness with Lagrange Multipliers in Convex Optimization

I was perusing the wiki article on the topic of this post https://en.wikipedia.org/wiki/Convex_optimization In particular the section on the Lagrange multipliers: I would appreciate more insight ...
0
votes
0answers
42 views

Recall that in the context of Fenchel–Rockafellar duality, the primal problem is defined by

Let X and Y be two Hilbert spaces. Let $f : X \rightarrow ]-\infty, +\infty]$ be convex and lower semicontinuous, let $A : X \rightarrow Y$ be linear, and let $g: Y \rightarrow ]-\infty,+\infty]$ be ...
0
votes
2answers
49 views

Steepest descent for a function defined over a specific domain [duplicate]

I am trying to minimize a convex function using the steepest descent method. The function is defined over the domain $D = \{(x, y) \in R^2 : 2x^2+y^2 < 10\}$. The gradient descent iterations: ...
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 ...
0
votes
1answer
34 views

Let $a_1,\ldots,a_m$ be elements of $\mathbb{R}^n.$ Then the convex cone $K_{\Omega}$

I am having a problem with one aspect of the following proof I came across in "An Easy Path to Convex Analysis and Applications" by Mordukhovich and Nam. It is Proposition 3.9 and it is the line ...
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
32 views

Find the distance between two convex sets

Let's say that ||.|| is an Euclidian norm in $R^3$ and we have two sets in $R^3$ defined by inequalities: $Y = \{y| f(y)<a\}, Z = \{ z| g(z)<b \} $ Let's say that $f$ and $g$ are convex and ...
0
votes
0answers
19 views

(Convex) reformulation of a nonlinear program

Consider the following program: \begin{eqnarray*} \min_{\mathrm x}\sum_{i=1}^{n}{\sum_{j=1}^{n}{\big(x_i(Sx)_i-x_j(Sx)_j\big)^2}}\\ \mathrm{subject\; to}\quad \sum_{i=1}^{n}{x_i}=1 \\ x_i\geq 0 ...
0
votes
0answers
61 views

Explain why the function $f(x)=\frac{1}{2}(x-d)^2+\alpha|x|$ is strictly convex.

Let $d\in\mathbb{R}$ and $\alpha>0$ be given. (i) Explain why the function $f(x)=\dfrac{1}{2}(x-d)^2+\alpha|x|$ is strictly convex. (ii) verify that \begin{equation} ...
1
vote
1answer
49 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
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
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 ...
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$ ...
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 ...
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
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
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 ...
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). ...
2
votes
1answer
313 views

Any example of strongly convex functions whose gradients are Lipschitz continuous in $\mathbb{R}^N$

Let $f:\mathbb{R}^N\to\mathbb{R}$ be strongly convex and its gradient is Lipschitz continuous, i.e., for some $l>0$ and $L>0$ we have $$f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{l}{2}||y-x||^2,$$ ...
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 ...
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 ...
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 ...
2
votes
1answer
73 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
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 ...
3
votes
1answer
85 views

Strong duality: When does the optimal primal variable coincide with the primal variable giving the dual function.

I'm considering the inequality-constrained optimization problem of finding $$ x^{\star} = \arg \min_{x} f(x) \;\; \text{s.t.} \;\; h(x) \le 0 $$ which is assumed to have a unique minimizer. The ...
0
votes
1answer
494 views

Show that the dual norm of spectral norm is Nuclear norm.

Could someone help to understand that the dual norm of spectral norm is Nuclear Norm ? We can focus on the real field. Given a matrix $X \in \mathbb{R}^{mn},$ then the spectral norm is defined by: ...
0
votes
1answer
36 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 ...
-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 ...
-1
votes
1answer
45 views

Suppose that f : X → ]−∞, +∞] is convex and proper, that x ̄ ∈ dom f and that λ > 0. Show that

Suppose that $f : X → ]−\infty, +\infty]$ is convex and proper, that $\bar{x} \in dom f$, and that $\lambda > 0$. Show that $$\partial^{\infty}(\lambda f)(\bar{x}) = ...
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 ...
0
votes
0answers
16 views

How to generate feasible $H$-conjugate descent search directions in convex subset

If we want to minimize a quadratic function $f(x)=c^Tx+\frac12x^THx$ (where $H$ is a symmetric positive-semidefinite matrix) in a convex subset $C\subset\mathbb{R}^n$, then is it possible to generate ...
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
42 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
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 ...
1
vote
1answer
18 views

Is every optimization problem with a piece-wise affine objective function the dual of some differentiable problem?

It is well known that a problem can have a $C^1$ objective function and a convex feasible set, while the dual problem can be piece-wise $C^1$ only. So I'm wondering - if you have a piece-wise affine, ...
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} ...