Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

1
vote
0answers
149 views

Showing a dual LP solves a primal LP

I originally asked this question: Does solving the LP dual SOLVE the primal LP? It was answered using an example of how the primal and dual solve each other (because of knowledge from strong ...
1
vote
3answers
388 views

A constrained linear least Frobenius norm problem:$\min_{X} \|A-XB\|_F$ subject to $Xv=0$?

Assume we are given two matrices $A, B \in \mathbb R^{n \times m}$ and a vector $v \in \mathbb R^n$. $\|\cdot\|_F$ is the Frobenius norm of a matrix. How can we solve $$\min_{X \in \mathbb R^{n ...
1
vote
1answer
301 views

How would you solve a Tikhonov Regularized Least Squares problem with nonnegative constraints?

For a Tikhonov Regularized Least Squares problem with nonnegative constraints, what are some methods that solve it? Are methods solving a Least Squares problem with nonnegative constraints and the ...
1
vote
1answer
71 views

Is $ \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 $ convex?

Over at How many points to find a polynomial? it was suggested to minimize $$ f(a,b,c,d,e) = \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 .$$ However I don't know if it is possible to find ...
1
vote
4answers
2k views

Max distance between a line and a parabola

I am suppose to use calculus to find the max vertical distance between the line $y = x + 2$ and the parabola $y = x^2$ on the interval $x$ greater then or equal to $-1$ and less then or equal to $2$. ...
1
vote
2answers
328 views

Bilinear Optimization Problem

How could I solve the following optimization problem using MATLAB or an other way? Given ${E}^{1}, {A}^{21}, {A}^{22}, {C}^{1}, {A}^{12}$ $ \underset{{C}^{2}, {E}^{2}}{min} {\left \| {C}^{2}{E}^{1} ...
1
vote
1answer
149 views

Some properties of Yosida-Moreau transform

Let $f(x)$ be a continuous function on $\mathbb{R}^n$, $f(x) \geqslant 0$ for any $x$. Define $$ f_{\alpha}(x) = \inf\limits_{y}\left( f(y) +\frac{|x-y|^2}{2\alpha} \right) $$ where $\alpha > ...
1
vote
0answers
79 views

Minimial Tiling Problem on a sphere

This question is a revision of the math exchange post found here. Consider the following: A sphere, $S$, with radius $r_1$. N regions projected onto $S$, whose projections, $\left\lbrace E_i ...
1
vote
2answers
536 views

Sign restriction on the Lagrange multiplier? Why?

Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints ...
1
vote
0answers
94 views

Set boundary for least-square calculation

When calculating least-squares we use the form $$Xw=y$$ This gives us an approximation, and it can happen that the resulting $w$ will be such that $Xw \lt y$ (entry-wise). Is there a way how to ...
1
vote
1answer
69 views

Upper bound of an expressions with many variables

Assume $0 < p_1 \le p_2 \le \dots \le p_{2k}$. I am looking for a (preferably tight) upper bound for the following expression: $$ \frac ...
1
vote
1answer
267 views

Sudoku mathematically, MILP?

My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
1
vote
1answer
160 views

Voronoi diagram with different metric functions

Given a metric space $(X,d)$ and finite number of points $(x_i)_{i=1}^n$ the Voronoi diagram (or the Dirichlet cell) $C_i$ is given by $$ C_i = \{x\in X:d(x,x_i)<\min\limits_{j\neq i}d(x,x_j)\}. ...
1
vote
1answer
223 views

Questions about weak duality theorem

Following are some corollaries regarding the weak duality theorem. Consider a constrained problem, $\min_{x \in X} f(x),$ subject to $g(x) \leq 0$ and $h(x) =0$. Its dual problem is $\sup_{u \geq ...
1
vote
2answers
118 views

Minimum for this function

I thought of writing this question Minimum for this function in a different way, if it helps. I want to minimize $$\sum_{i=1}^n a_ix_i + \nu \sum_{i=1}^n b_i 2^{x_i} ,$$ where $a_i \in [0,1]$, ...
1
vote
2answers
153 views

Find the range of $x$, given $y_{min} \leq y(x) \leq y_{max}$, where $y(x) $ can be any function ( Updated)

I have a series of inequalities: $$y_{1min} \leq y_{1}(x) \leq y_{1max}$$ $$y_{2min} \leq y_{2}(x) \leq y_{2max}$$ $$..$$ $$y_{nmin} \leq y_{n}(x) \leq y_{nmax}$$ Note that $x\in\mathbb{R}$ The ...
0
votes
1answer
46 views

Maximizing the volume of a box using Lagrange multipliers

We are given a box of surface area $64$. As such, I wish to maximize $f(x,y,z) = xyz$ subject to $g(x,y,z) = 2(xy+xz+yz) - 64$. If I have understood in correctly, I am to find the critical points of ...
0
votes
0answers
37 views

Minimizing a vector constrained to a set

Sorry if this is wordy or over-complicated, I'm not sure how to isolate the problem any more than I have below without losing important context: I'm trying to implement a coordinate block descent ...
0
votes
1answer
23 views

Are there known patterns among minimal expressions?

Let $R = F[z_1, z_2, \dots]$ be the finite-degree polynomials in a countable number of variables. Let $\mathcal{E}(R)$ be the set of all expressions of polynomials. Note that there could be an ...
0
votes
2answers
54 views

Minimize Function over Convex Subset

Suppose that C is a closed convex subset of $\mathbb R^n$ and $x \in \mathbb R^n$. The projection of $\mathbf x$ onto C is the closest point $\mathbf y \in C : \mathbf z = \mathbf y$ minimizes ...
0
votes
1answer
59 views

What trick to calculate this Frechet derivative?

Let $u(t) \in L^{2}(0, 1)$. I need to calculate the first and second Frechet derivatives of $$J(u) = \int_0^1 \left(\int_0^{t^3}u(s)ds\right)^2dt$$ I am completely at a loss here: I know several ...
0
votes
0answers
16 views

Epi-convergence to indicator function

Let the indicator function be defined as $$I(x) \triangleq \begin{cases} 1, & \quad x \geq 0 \\ 0, & \quad x < 0 \end{cases}$$ and $I_{\nu}(x) \in [0,1]$ be a continuous approximation of ...
0
votes
2answers
70 views

Is the geometric-to-arithmetic function convex or concave?

Consider a vector $\mathbf{x} \in \mathbb{R}_{++}^N$. Also consider two functions, $g(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, and $a(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, ...
0
votes
3answers
118 views

Concave function divided by a convex function. What is the result?

Let us say that I have a function $f(x)$ that we know is a concave. And let us also say that we have another function $g(x)$ that is a convex. If I make a new function, $h(x) = \frac{f(x)}{g(x)}$, ...
0
votes
2answers
101 views

Lagrange Multipliers have no solution

$f(x,y)=2x+y$ subject to constraint $x+y=m$. $(2,1)=\lambda(1,1)$ but this does not satisfy $x+y=m$ So there are no solution?
0
votes
3answers
72 views

Why does finding the $x$ that maximizes $\ln(f(x))$ is the same as finding the $x$ that maximizes $f(x)$?

I'm reading about maximum likelihood here. In the last paragraph of the first page, it says: Why does the value of $p$ that maximizes $\log L(p;3)$ is the same $p$ that maximizes $L(p;3)$. The ...
0
votes
1answer
54 views

Homogeneous function has its derivative homogeneous of one less degree

This is from Simon and Blume's Mathematics for Economists: But, for LHS, applying Chain rule goes:$$\dfrac{\partial f}{\partial(tx_1)}(tx_1,\dots,tx_n)\cdot\dfrac{\partial(tx_1)}{\partial ...
0
votes
1answer
45 views

SOCP formulation: wrong inequality direction in constraints

The problem is constrained by a set of inequalities in the form of $$ \| A_i\mathbf{x}\|\geq \mathbf{y_i^Tx} $$ where x is a n-vector of unknowns, $A_i$ are matrices and $y_i$ vectors. Is it possible ...
0
votes
1answer
43 views

The conjugate of conjugate of the function $f=yx^2$

Suppose $f=yx^2$ and the arguments are $x\in\mathbb{R},y>0$. According to the definition of conjugate, $f^*(x,y)=\max\limits_{y',x'}xx'+yy'-y'x'^2$ Because $f$ is not a convex function, I cannot ...
0
votes
1answer
35 views

Proving an inequality involving multiple constraints

Let $R$ be a discrete set and let $f:{\left[ {0,1} \right]^{\left| R \right|}} \times {\left[ {0,1} \right]^{\left| R \right|}} \to \mathbb{R}$ be defined as $f\left( {{\mathbf{x}},{\mathbf{y}}} ...
0
votes
0answers
59 views

travelling salesman problem with pairs of cities and constraints

I am looking for the name of the following two problems, and an approach to solve them. Problem#1: given N nodes, find the shortest path starting at a given start node and ending at a given end node, ...
0
votes
0answers
50 views

KKT minimization problem

Solve $x^2 - 2y \rightarrow \min$ subject to $\max\{3x^2, e^y + 2\} + \sqrt{x^2 + y^2 - 2x + 1} \leq 6x + \sqrt{5}$ and $ \sqrt{x^2 + y^2 - 4x - 4y +8} -2x+2y \leq 0$ I tried computing the ...
0
votes
0answers
65 views

extreme value of increasing or decreasing function

From the three problems: one, two and three, it seems that if $f(x)$ is decreasing function with $a+b+c=abc$ or $a + b + c + a b + b c + c a = 1 + a b c$ then the maximum value of $f(a)+f(b)+f(c)$ ...
0
votes
2answers
52 views

Why this optimization problem is solved like that? any explanations, help? Thanks!

Ok.so I do understand up to step 9. But then it gets all confusing to me...Normally what I would do for these sort of problems is to isolate the lambda symbols in equations 8 and 9 and then equal ...
0
votes
2answers
132 views

A (simple?) question about continuous functions

[EDIT to restrict the function domain to a compact interval, and adapt some of my thoughts.] Suppose I have a continuous and twice differentiable function $f_a(x)$ that maps some compact interval ...
0
votes
0answers
37 views

Confusion related to convexity of a quadratic function

Lets say I have the following function of X $f(X) = (AX^TBX)$ I didn't get why matrices A and B need to be psd to make f(X) convex. Clarifications guys
0
votes
1answer
823 views

Fundamental matrices

Find the fundamental matrix for the two-dimensional system defined by $x_1' = x_1 + tx_2$, and $x_2'=x_2$. And determine the solution for which $x_1(0)=c_1$, and $x_2(0)=c_2$. I am stuck because of ...
0
votes
2answers
524 views

Optimization and window area

A Norman window has the shape of a rectangle with a semi circle on top; diameter of the semicircle exactly matches the width of the rectangle. Find the dimensions of the Norman window whose perimeter ...
0
votes
1answer
44 views

$(a - b \cot \theta) \cos^2 \theta = -\frac{b}{2} \cot \theta$ ,$\theta=$?

This question is a follow up question to this answer. In the equation: $$(a - b \cot \theta) \cos^2 \theta = -\frac{b}{2} \cot \theta.$$ $a$ and $b$ are given. What is the best way to solve for ...
0
votes
0answers
225 views

Gradient Descent with nonlinear constraint on Symmetric positive definite matrix space

I would like to find the stationary point $S_*$ (global minimum) that minimizes the function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ which has been proven to be convex in Convexity of ...
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
99 views

what math topic is this kind of example part of? or what is needed to understand how to solve it? [closed]

we 100000000 sets/locations. each set has, A = % chance of finding a cure (there are many different types of cures) for cancer B = time it takes to extract a cure to caner C = the optimal % chance (IN ...
0
votes
0answers
126 views

MiniMax Theorem

Consider the compact sets $X \in \mathbb{R}^n$, $Y \in \mathbb{R}^m$, $A \in \mathbb{R}^n$, $M \in \mathbb{R}^{n \times m}$. For fixed $(\bar{a},\bar{B}) \in A \times M$, by the MiniMax Theorem we ...
0
votes
1answer
621 views

Maximizing and Minimizing a function

Let $f(x,y)$ be a function such that $f:\mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$. Now we have to maximize $f$ over $x$ and minimize it over $y$ $i.e.\ $ $$\underset{x}{\text{max}}\: ...
0
votes
0answers
92 views

Stationary points of shift-symmetric linear multivariate polynomials

Suppose that I have a function $f(x_1,x_2,\ldots,x_n)$ that is a multivariate polynomial linear in each argument, i.e. each additive term contains $x_i$ raised to the power 1 or zero, but no more than ...
0
votes
1answer
725 views

Local extreme value & saddle point: multi variable calculus

I am asked to find all local extreme values & saddle points of $$f(x,y) = 2x^2 + y^2 - xy - 7y + 8$$ $$f_x(x, y) = 4x-y, \qquad f_y(x,y) = 2y-x-7$$ $$f_x(x,y) = 0, \qquad y = 4x$$ $$f_y(x,y) ...
0
votes
1answer
115 views

Suitable Loss function for Order preserving Factoring of a matrix?

(Old-Question) Given a $n\times n$ symmetric matrix $X$, I would like to factor it using a vector $c$ of size $n \times 1$ such that: $\sum_{i,j} [X_{ij} \cdot c_i\cdot c_j]$ is minimum. How can I ...
0
votes
1answer
245 views

Underlying assumption in a Primal/Dual table

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144. ...
0
votes
3answers
664 views

find the area of the largest rectangle that can fit inside a semi circle of radius 2 cm

find the area of the largest rectangle that can fit inside a semi circle of radius 2 cm I have absolutely no idea where to get started on this...What I did do is $A=(\pi r^2)/2$ (its a semi circle) ...
0
votes
1answer
479 views

Optimization problem with two-step discontinuous function

imagine my function as a staircase with two steps. This function is to be fitted to some empirical data and I'm searching for an algorithm which minimizes the Root Mean Squared Error between this ...