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)

8
votes
0answers
80 views
+50

Are any tools or techniques available to solve the “placement of safety points” problem?

Definition 0. Given a metric space $X$ and subsets $H$ and $S$ thereof, define: $$d(H,S) = \sup_{h \in H} \inf_{s \in S}d(h,s)$$ (This as an asymmetric version of the Hausdorff distance.) Here's ...
1
vote
0answers
16 views

Variational Calculus with Discrete Objective

I'm trying to infer a smooth, non-negative function from some given data ($\vec{m},\vec{\alpha},\vec{\beta}$). That is, I want to solve (I think) $$ \mathop{\arg\!\min}_{g \in ...
-1
votes
1answer
22 views

A Basic Question E-views

I ask a question about E-views. Is the P-value in the picture less than 0.05 or greater than 0.05? I'm confused because of the presence of the sign '<' in front of 0.10. Please help mee. Thank you. ...
4
votes
2answers
48 views

L1 regularized unconstrained optimization problem

I am encountering an unconstrained minimization problem. The problem is of the form $$\min_x \frac{\|x-a\|_2^2}{2}+\lambda\|x\|_1$$ where $x,a \in R^n$ and $x$ is the optimization variable. ...
2
votes
2answers
72 views

Showing that mean of vectors minimizes the sum of the squared distances.

Let $S=\{x_1,...,x_n\}$ be a set of vectors in $\mathbb{R}^d$. Now we have to pick a vector $\mu$, such that the following expression is minimized: $$ L(\mu)=\sum_{x\in S} ||x-\mu||_2^2. $$ I think ...
2
votes
0answers
56 views

Maxima and minima of $f(x)=\binom{16-x}{2x-1}+\binom{20-3x}{4x-5}$.

Find the maximum and minimum value of the function $f(x)=\binom{16-x}{2x-1}+\binom{20-3x}{4x-5}.$ ATTEMPT:- By A.M.-G.M. inequality, $\frac{a+b}{2}\ge\sqrt{ab}$, $\quad$ for $a,b\gt 0$ with equality ...
1
vote
0answers
26 views

How to use CVXOPT to solve an semidefinite programming problem

I'm using Sage to solve a problem and would like to use cvxopt to solve a sdp problem. Specifically, I have a list of expressions of the form $$c + \sum_{i,j} a_{i,j} q_{i,j}$$ where each $c$ and all ...
0
votes
0answers
27 views

Smallest distance of a point to a surface

Let $P$ be a hyperplane of dimension $n-1$ in the space $\mathbf{R}^n$, given some integer $n\ge 3$ (let's call the first axes $x,y,z,\ldots$). Then, fix a point $A \in P$ and define the surface ...
2
votes
3answers
48 views

Maximum of $xy+y^2$ subject to right-semicircle $x\ge 0,x^2+y^2\le 1$

Maximum of: $$ xy+y^2 $$ Domain: $$ x \ge 0, x^2+y^2 \le1 $$ I know that the result is: $$ \frac{1}{2}+\frac{1}{\sqrt{2}} $$ for $$ ...
0
votes
1answer
23 views

Maximizing $g(x)$ and monotone transformation $f(g(x)$ is the same?

I have encountered that in some cases maximization of a function had been substituted with a maximization of its monotone transformation. For example, finding the min or max of $f(x,y) = ((x-1)^2 + ...
12
votes
4answers
687 views

Double obstructing wall problem, what is the optimal walk path and length?

Every day, you walk from point A to point B which are exactly $2$ miles apart straight line distance, however, each day, there is a $50$% chance of there being an obstructing wall perpendicular to the ...
0
votes
0answers
15 views

Convert this problem with 2-norm cost to an SOCP?

I am solving a non-convex problem via sequential convex optimization. Here is a minimal example of my problem at iteration $i$: $$ \begin{align*} \min_{\Delta t,F_i}&\left( \Delta ...
0
votes
2answers
26 views

Application of A.M. -G.M. inequality

Let x, y,z be positive numbers. The least value of $ \frac{x(1+y)+y(1+z)+z(1+x)}{(xyz)^{.5}}$ is a) $\frac{9}{2^{.5}}$ b) 6 c) $\frac{1}{6^{.5}}$ d.) None of the above I tried applying the A.M. ...
0
votes
2answers
32 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
0
votes
0answers
18 views

Minimizing convex functions without compatible gradients

I've been working on a minimization problem for a while, involving "simple" conditions, but haven't been able to figure it out. I've tried using Lagrange Multipliers and KKT, but the presence of ...
2
votes
1answer
14 views

Euler- Lagrange, Several functions of 1 variable Question

In this question here, by solving the E-L equations for y and z, you get that $y'' = z$ and $z'' = y$. Thus $y'''' = y$ and $z'''' = z$ However, this solution is $ Ae^x + Be^{-x} + C\sin x + ...
0
votes
0answers
19 views

$\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ iif it exists $j\in\{1,…,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$

Show a vector $\vec c$ exists such that $\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ if and only if it exists $j\in\{1,...,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$ I'm only asking for a ...
-1
votes
0answers
27 views

How to explain polynomial coefficients by minimezed Error function?

We wish to predict ${\bf{t}}$ from an observed $\bf{x}$.We shall fit the data using a polynomial function of the form$$y({\bf{x}},{\bf{w}})=w_0+w_1x+w_2x^2+...+w_Mx^M=\sum_{j=0}^{M}w_jx^j$$ where $M$ ...
2
votes
0answers
16 views

Does it make sense to compare sets (polygons) with different dimensions?

In the context of integer programming, I am considering 3 different linear models for a given problem. The goal is to determine which formulation is the tightest, that is, the one that gives the least ...
0
votes
0answers
18 views

Maximum Likelihood Estimation of a log function with sevaral parameters

I am trying to find out the parameters for which the function will be maximized !$$ \log L(\alpha,\beta,v) = v/\beta(e^{-\beta T} -1) + \alpha/\beta \sum_{i=1}^{n}(e^{-\beta(T-t_i)} -1) + ...
0
votes
0answers
19 views

$\{x\in R^n | Ax \leq b\} \cap \{x \in R^n | Dx \leq d\}= \emptyset$ iff there is a vector $c \in R^n$ such that $c^Tx < c^T y$

Consider two non-empty polyhedra $P := \{x\in R^n | Ax \leq b\}$ and $Q := \{x \in R^n | Dx \leq d\}$. Show that $P \cap Q = \emptyset$ if and only if there is a vector $c \in R^n$ such that $c^Tx ...
0
votes
0answers
34 views

Positivity of the last component of non negative least squares based on active set method

I have followed the instructions given in Lawson and Hanson book for non-negative least squares using active set method. I am having a trouble in justifying one of the statements they have made about ...
0
votes
1answer
47 views

Find the matrix X such as A . X is close to B

Consider : A an m by n matrix B an ...
1
vote
2answers
69 views

Finding the maximum area of a triangle with a perimeter constrain

Using graphical methods, determine the dimensions of a right triangle that has the largest possible area, given that the perimeter cannot be larger than $P$. The final answer should be in terms of ...
1
vote
0answers
12 views

Problem about find the extreme of a function (Multipliers of Lagrange)

Good morning, i have a problem with this: Find the maximum and minimum distances from the origin to the curve $g\left(x,y\right)=5x^{2}+6xy+5y^{2}$ I make this: Function to optimize: ...
1
vote
0answers
22 views

Can a linear program be optimal if its basis is infeasible?

I want to know thanks to the dual theorem wether the following basis is or isn't optimal. That is to say looking for the slack variables. As far as the third line doesn't respect the constraints: ...
0
votes
0answers
12 views

Which coefficient to start with in the dictionary method?

I used to start with the variable with the biggest coefficient in the goal function (in the case of max). yet I read an article that behaving like this may lead to loop. It is rather preferred to do ...
0
votes
1answer
18 views

Is it possible to solve a recurrence with max()?

I have the following problem. Imagine there is a set $P=\{p_1,p_2,p_3\} \subset \mathbb Z $ and I want to describe how it changes in time. Informally, the rule is simple: At every time-step, subtract ...
0
votes
0answers
14 views

How do I define a disjoint bound on a variable for linear programming in code?

Is there a way to define a bound like this: $$x \in 0\, \bigcup \,\left[-1,-0.5\right]\, \bigcup\,\, [0.5,1]$$ It is like a semi continuous variable but with both negative and positive values. ...
17
votes
3answers
616 views

How to prove Lagrange multiplier theorem in a rigorous but intuitive way?

Following some text books, the Lagrange multiplier theorem can be described as follows. Let $U \subset \mathbb{R}^n$ be an open set and let $f:U\rightarrow \mathbb{R}, g:U\rightarrow \mathbb{R}$ be ...
2
votes
0answers
42 views

Solving optimization involving square roots?

I am new to optimization and I have the following problem that I would like to analyze and obtain a good solution (if optimal solution cannot be reached) $$ \max_\mathbf{x} \quad \sum_{n = ...
1
vote
1answer
42 views

Solving constrained Euler-Lagrange equations with Lagrange Multipliers (Geodesics)

I'm trying to solve a calculus of variations geodesics problem using Lagrange Multipliers, showing that the geodesics of a sphere are the so-called great circles. I am using a constrained Lagrangian ...
1
vote
1answer
30 views

$f(z)=\frac{1}{z^2-2z+2}$ - Maximum modulus principle

Let the function $f(z)=\frac{1}{z^2-2z+2}$. I have to find $\max_{z \in D(0,1)} |f(z)|$, but I already know that the maxixum would be on $\bar{D}-interior(D)$ by the maximum modulus principle. Is ...
0
votes
1answer
31 views

On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?

Please refer to Boyd et al.'s convergence analysis of ADMM (Chapter 3 and Appendix A). My question is: Why do we need $f$ and $g$ to be convex? I don't see the need of this assumption. If the ...
1
vote
1answer
35 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
2
votes
1answer
31 views

Partition a triangle into equal areas

A piece of wooden board in the shape of an isosceles right triangle, with sides $1$,$1$, $\sqrt{2}$ is to be sawn into two pieces. Find the length and location of the shortest straight cut which ...
0
votes
0answers
34 views

How to deal with an $xy\le 1$ constraint?

I have to solve the following optimization problem: $$ \begin{align*} \min_{x,y} &\{-x-y\} \\ \text{such that} \\ y &\ge 3 \\ y &\le 30 \\ x &\ge 0 \\ xy &\le 1 \\ \end{align*} $$ ...
0
votes
1answer
17 views

Dealing with non-negativity constraints without using Kuhn-Tucker conditions

Suppose I wish to maximize the function $f(x,y)$ subject to the equality constraint $g(x,y)=c$ as well as the non-negativity constraints $x\geq0$, $y\geq0$. If I first solve it ignoring the ...
0
votes
4answers
57 views

right circular cylinder inscribed in a sphere

Find the dimensions of the right-circular cylinder of greatest vloume that can be inscribed in a sphere with a radius of 6 $in$ I think I need help visualizing, and maybe the solution. I've ...
0
votes
0answers
15 views

Approximating a quadratic term in the constraint set as 2nd order Taylor expansion

I have an optimization problem in the following form: $$\min_{x,y} f(x)+g(y)$$ $$s.t.$$ $$Ax+h(y)=0$$ where $h(y)$ is a quadratic in $y$. Instead of solving this problem directly, $h(y)$ is ...
0
votes
0answers
28 views

Is there a way to calculate RMS value continuously?

Using that the RMS by definition is: $\sqrt {\int_0^T\frac 1T*f(t)^2dt} $ which can be calculated by using Riemann sums in the following way: $\sqrt {\frac 1N\sum_0^Nf[i]^2} $ I've tried that in ...
0
votes
1answer
54 views

Derivative of log-likelihood cost function with respect to a matrix

Recently, I am learning derivative method to a function and thanks to @hans help, I can solve those which can be expressed by Frobenius product. But for the log-likelihood function, I do not how to ...
0
votes
0answers
21 views

Maximization of quadratic form on a sphere [duplicate]

I have to following problem $$\max_{x}x^TAx+b^Tx\quad \mathrm{s.t.}\quad x^Tx\leq c,$$ where $A$ is real, symmetric and positive semi-definite. Firstly I tried to solve the problem with the KKT, but ...
0
votes
0answers
6 views

transformation of one maximization problem

I want to maximize a function $h(x,y)=f(x,y)-g(x,y)$, subject to (1) $0 \leq g(x,y)\leq I$, where $I$ is a fixed positive number; (2) $x\geq 0$ and $y \geq 0$. I come up a method to solve this ...
0
votes
1answer
21 views

What is the class of this Integer programming prob.

I have an optimization problem which seems to be non-linear because of the constraints (right?): $max (\sum U_i\times x_i)\\ \sum x_i\times y_i\times r_i\leq R\\ \sum y_i=1\\ \sum x_i=1\\ x_i, ...
0
votes
0answers
15 views

Analytic solution to semidefinite programming

Problem \begin{align} &\arg\,\min\limits_{0 \le \rho \le 1} \rho \\ s.t.& \begin{bmatrix} A P A - \rho^2P & A^TPB \\ B^TPA & B^TPB \end{bmatrix} + \lambda \begin{bmatrix} C & ...
0
votes
0answers
35 views

Increase max-flow by 1 with minimum changes to edges

Suppose we have a directed graph and we have the maximum flow from $s$ to $t$ as $f$. Now we want the graph to have a flow of $f+1$. This requires us to increase the capacity of a certain subset of ...
0
votes
0answers
21 views

Coordinate descent with equality and inequality constraints

I have an intuitive understanding of why the simple method of coordinate descent does not work with linearly coupled constraints such as; $$\min_x\sum_if_i(x_i)$$ $$s.t.$$ $$Ax=b$$ If we try to ...
0
votes
1answer
24 views

Local extrema of $x^3+y^2+6y$

I have to find local extrema of $x^3+y^2+6y$. I found out that the stationary points are $(0,-3)$. I also found the Hess matrix for this function and computed the determinant, which is $12x$. But now ...
0
votes
0answers
19 views

Minimizing the average

Let's say I have a nice-behaving function $f: \Bbb R^n\to \Bbb R$, and I would like to find its maximum. Then I can apply gradient search algorithms to look for that, and to cope with possible ...