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

learn more… | top users | synonyms

1
vote
1answer
45 views

Showing that $T+S$ is firmly nonexpansive

Show that $T+S$ is firmly nonexpansive considering that $T$ and $S$ are firmly nonexpansive mappings from $\mathbb R^n$ to $\mathbb R^n$. Definition: We say that $F$ is firmly nonexpansive if: ...
1
vote
0answers
58 views

Parameterized convex optimization

I'm trying to formulate a game so that at Nash equilibrium I achieve supply equales demand. Then I ran into this problem. For all $i,$ $v_{i}\left(x_{i}\right)$ is concave in $x_{i}$. The value ...
1
vote
0answers
59 views

Closed form for Lagrange dual

Can Lagrange dual always be computed in closed form? Can you give me a simple example where the dual is not analytically computable?
3
votes
1answer
59 views

Show that $Z=T(2S−I)+I−S$ is firmly nonexpansive

Suppose $T$ and $S$ are firmly nonexpansive mappings from $\mathbb R^n$ to $\mathbb R^n$. Let $I$ be identity operator. I want to show that $Z=T(2S−I)+I−S$ is firmly nonexpansive. Definition. We say ...
1
vote
0answers
50 views

why is it important to have $\max_x \min_y f(x,y)=\min_y \max_x f(x,y)$?

I am currently trying to understand the minimax theorem of Von Neumann and the improved versions of this theorem. At any case we have the property $$\max_{x\in X} \min_{y\in Y}f(x,y)=\min_{y\in Y} ...
2
votes
1answer
114 views

Continuity of solutions to convex optimization problems

Let $x_A$ solve $$ \min J(x) \quad \text{subject to} \quad Ax=b $$ and $x_B$ solve $$ \min J(x) \quad \text{subject to} \quad Bx=b $$ given that $\|A-B\|_\text{operator} \leq \epsilon$ and that $J$ is ...
0
votes
1answer
39 views

Numerically solving linear equation and optimization

I have to solve for $x$ in the linear equation $Ax=B$. However, $A$ has singular values that are close to zero (very small). So direct inversion is not a good idea. I wanted to solve for $ x$ using ...
2
votes
1answer
91 views

Approximating a function with a convex function

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a continuous, differentiable function. Is there a known algorithm that fits $f$ with $g$, which is an order-$n$ polynomial that is convex, in the least ...
6
votes
0answers
178 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
3
votes
0answers
187 views

How to show that a function is piecewise linear

Let z(t) = min $(c+t d)^T x$ s.t $Ax <= b$ Show that Z(t) is a concave, piecewise linear function of t. I'm really not sure how to even start proving this, I would really ...
1
vote
1answer
28 views

Does linearity decompose down convex sums?

I'm doing some convex optimisation where I'm minimising sum function $f(x) = \sum g_i(x)$, where the $g$'s are convex (and hence so is $f$) and the sum is finite. In doing so it turns out that $f$ is ...
2
votes
1answer
91 views

Initial solution to a Convex Optimization problem

I am aware that in a convex optimization problem, the initial solution does not matter as the algorithm guarantees convergence to the global minimum/maximum. But what if the initial solution does not ...
1
vote
0answers
252 views

Linear programming: writing a problem with artificial variables?

Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
2
votes
0answers
59 views

Convexity of a function

Suppose we have $F: R^n \longrightarrow R$ , $P: R^n \longrightarrow R^n$ and $G: R^n \longrightarrow R$ all nice- let's say given by polynomial and $P$ is invertible - such that $F(x) =G( P(x) )$. ...
1
vote
1answer
95 views

how can I proof the GLOBAL optimality of a problem where the feasible region is disjoint?

I want to minimize the following function. It has two variable, $x$ and $y$ are real. I want proof the global optimality. But the feasible region of the variables are disjoint. My question is, how can ...
1
vote
1answer
187 views

Max function on a closed compact convex set.

Consider a closed convex compact subset $\mathbb{S}$ of $\mathbb{R}^N$ while we denote any of its point by $x=[x_1,x_2,\ldots,x_N]^T$. Define the function \begin{align} f(x)=max(x_1,x_2,\ldots,x_N) ...
0
votes
1answer
155 views

Convex optimization problem to quadratic programming problem

Briefly, have the following problem: \begin{equation} \sum_{i = 0}^n a_i \ (max [ F_i( \bar x ), 0 ] )^2 \rightarrow min, \\\\ s.t.\\\\ A \bar x \leq b \end{equation} where $ F( \bar x ) $ is a ...
0
votes
1answer
189 views

a convex function on a 2 dimensional closed convex set

Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane ...
0
votes
1answer
256 views

Compact Set for Dummies

Can any one tell me in simple words what is a compact set? I read the definition of Compact set, but do not get it. BTW, I do not know topology. In particular, is the probability simplex, $W\ge0, ...
0
votes
1answer
257 views

Gradient of log softmax in matrix form

Suppose $J(\mathbf{A})$ is defined as follows $$J=\text{tr}(\log \mathbf{P})$$ $$\mathbf{P}=\frac{e^\mathbf{A}}{\mathbf{1} \mathbf{1}' e^\mathbf{A}}$$ where division, exp and log are taken pointwise, ...
0
votes
1answer
54 views

matrix completion by rank minimization

In matrix completion, the starting point is often stated as: the optimization problem for matrix completion: min(X): (1/2) ||X-M||^2 s.t. rank(X)<= r Where X is the reconstructed matrix and M ...
1
vote
0answers
47 views

Duality gap in cone programming

Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem $$ (P)\quad \min\{\langle c, x\rangle: Ax\geq_K ...
1
vote
1answer
141 views

How does the two phase method for linear programs work…

I understand that by adding artificial variables the problem can be reformulated as a new problem where the "starting point" is readily found. What I don't get is how when this extended problem is ...
2
votes
1answer
47 views

Why can't the hyperplane H intersected with polyhedral set S contain any line…

S is the polyhedral set $ S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \} $ and $ H : \mathbf{c}^{T}\mathbf{x} = \beta $ with $ \min_S ( ...
0
votes
1answer
277 views

Global Min-Max Optimization

When is \begin{equation} \min_X \max_Y f(X,Y) \end{equation} globally solvable? (i.e. we can find global solution for the optimization problem?) I am not looking for reformulations. Is it only when ...
2
votes
3answers
122 views

Proof of Convexity

Is the function $Trace(AX^TBX)$ a convex function in $X$ or not ? Here, $X$ is a rectangular matrix and $A,B$ are square, symmetric, p.s.d matrices. The entries in $X,A,B$ are real valued.
0
votes
1answer
261 views

Joint Convexity

Is the problem \begin{equation} \min_X \max_Y -\operatorname{tr}(X^TY)-\operatorname{tr}(Y^TYX) \end{equation} Jointly convex in $X$ and $Y$? Can we solve it globally? Why or Why not? $X$ and $Y$ ...
1
vote
1answer
127 views

Convex Sets Versus Convex Functions

Can we specify all convex sets, in terms of convex constraints (convex inequality functions) on a variable?
0
votes
2answers
399 views

What Stopping Criteria to Use in Projected Gradient Descent

Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
1
vote
0answers
47 views

General properties of an optimal solution of a convex program

How do we seek certain properties for a solution of a convex minimization problem. For example we want to make sure if the below objective has a symmetric optimal solution: \begin{equation} \min_X ...
0
votes
1answer
186 views

Strict convex function?

I try to prove that $g(x)= K |x|^2/2 + z(x)$ is strictly convex, given that $z(x) \geq - m(1 + |x|^p)$ with $m \geq 0$, $0 \leq p \leq 2$, forall $x \in \mathbb{R}^n$, provided $K$ is sufficiently ...
0
votes
3answers
78 views

lower bound of a special type of convex functions

Suppose $f$ is a convex, differentiable and $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$. The minimum of $f$ is $0$. ($f$ may not be twice differentiable.) How to show $f(x)\geq\frac{1}{2L}\|\nabla ...
0
votes
1answer
45 views

Concave optimal value?

Let $A \in \mathbb{R}^{n \times m}$ and $B \in \mathbb{R}^{m \times n}$. Consider a compact set $C \subset \mathbb{R}^n$. For all $x \in C$ define $$ f(x) := \min_{y \in \mathbb{R}^m} \{ x^\top A y ...
0
votes
1answer
54 views

Simple question about the solution of non-linear equations

Given, say $4$ non linear equations with $4$ positive parameters, $$f_1(x,y,z,t)=a,\quad f_2(x,y,z,t)=b,\quad f_3(x,y,z,t)=c,\quad f_4(x,y,z,t)=d$$ for given $a,b,c,d$, If I am able to show that ...
0
votes
0answers
72 views

Max Quadratic Expression

Let $A \in \mathbb{R}^{n \times n}$, $A = A^\top$, $B \in \mathbb{R}^{m \times n}$, and $\mathcal{C} \subset \mathbb{R}^n$ be a compact, convex set. For $A$ not negative semidefinite, how to globally ...
0
votes
1answer
73 views

A point which I couldnt understand in a paper.

Currently I am reading a paper and the author has an optimization problem $$\max_w\frac{w^2\alpha}{w^2\beta+v}$$ Then he substitutes $w^2$ with $x$ and defines an objective function using a ...
0
votes
0answers
181 views

Convex Functions on 2 variables over an interval

It is required to show that $f(x) = x_1x_2$ is a convex function on $[a,ma]^T$ where $a\ge 0$ and $m\ge1$.To show convexity we need to show that for $\lambda \in [0,1]$: $f(\lambda x + (1-\lambda ...
2
votes
1answer
63 views

Are all polytopes also convex hulls?

It seems, at least in the 2-D case, that all polytopes are going to be convex. Does this hold if the dimensions are increased?
2
votes
0answers
60 views

Prove that $\text{int}(\text{dom}(f))$ is a convex set.

Let $f$ be a convex function. I have to prove that $\text{int}(\text{dom}(f))$ is a convex set. (Be careful with $-∞$ )
28
votes
4answers
3k views

Please explain the intuition behind the dual problem in optimization.

I've studied convex optimization pretty carefully, but don't feel that I have yet "grokked" the dual problem. Here are some questions I would like to understand more deeply/clearly/simply: 1) How ...
0
votes
1answer
104 views

Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

Wikipedia here explains it like this: I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here: "If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
-1
votes
1answer
105 views

Finding an $O(n \log n)$ time algorithm for an optimization problem

Consider the following optimization problem: Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ ...
1
vote
0answers
37 views

using the ellipsoid algorithm to find a poly time algorithm for the optimization problem

Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in $\mathbb{R}^n.$ Find $\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with $|S| ...
0
votes
1answer
79 views

property of cones and their duals

I am reading Convex Optimization by Boyd and Vandenberghe (free at http://www.stanford.edu/~boyd/cvxbook/) and I am trying to justifying their assertion (p. 53) that if $K$ is a proper cone, $K^*$ is ...
2
votes
0answers
220 views

sufficient condition for KKT problems

For the Karush-Kuhn Tucker optimsation problem, Wikipedia notes that: "The necessary conditions are sufficient for optimality if the objective function f and the inequality constraints g_j are ...
3
votes
3answers
954 views

Prove $ax - x\log(x)$ is convex?

How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function. Any ideas?
1
vote
2answers
163 views

What does the statement “Optimality condition for convex problem” mean? KKT or other condition?

I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with ...
0
votes
1answer
145 views

Matrix computations problem: rank, pseudo inverse,…

Suppose we are given two arbitrary $m \times n$ matrices, $A$, $B$, where we know $B$ has full column rank. Let $m>>n$. Can we always find a square $m \times m $ matrix $X$, such that $A=XB$? I ...
0
votes
0answers
154 views

Is positively weighted sum of eigenvalues of a matrix X, convex function of X?

Is positively weighted sum of eigenvalues of a matrix X, convex function of the matrix X?
3
votes
2answers
1k views

Why does a positive definite matrix defines a convex cone?

I've been working on convex optimization and got stuck. What exactly does a positive definite(p.d) matrix represent geometrically ? what kind of vector space it forms ? If I have a p.d matrix which ...